/csci30notes

Lecture notes for CSCI 30/CS 110 (Data Structures and Algorithms)

Primary LanguageTeXCreative Commons Attribution Share Alike 4.0 InternationalCC-BY-SA-4.0

CSCI 30/CS 110 Lecture Notes

This is a repository for my lecture notes on CSCI 30/CS 110 (Data Structures and Algorithms), as currently being taught in First Semester, SY 2019--2020.

How to compile

You will need the following:

  • TeX Live (or any LaTeX distribution)
  • Pygments (pip install Pygments)
  • make (from the build-essential package)
  • The fonts folder (you can get it here)

Then compile the document by running make.

Planned outline

  • Introduction
    • Algorithms, data structures, design and implementation goals, pseudocode
  • The Basics
    • Correctness (done)
      • Mathematical induction, loop invariants
    • Efficiency (80% done)
      • Model of computation, orders of growth, asymptotic notation
    • Recursion (70% done)
      • Thinking recursively, recursive algorithms, divide-and-conquer, solving recurrences
  • Searching and Sorting
    • Searching (to be phased out by next year)
      • Linear search, binary search, jump search
    • Sorting (to be phased out by next year)
      • Quadratic-time sorting, linearithmic-time sorting, lower bound of sorting, linear-time sorting
    • Hashing
      • Hash tables, collision resolution
  • Elementary Data Structures
    • Arrays and Lists
      • Arrays, linked lists, doubly-linked lists
    • Stacks
      • Stack operations, stack implementations, applications with stacks
    • Queues
      • Queue operations, queue implementations, applications with queue, double-ended queues (deques)
  • Non-Linear Data Structures
    • Trees
      • Terminology, implementations, tree traversal
    • Binary Trees
      • Properties, implementations, tree search algorithms
    • Heaps
      • Heap sort, priority queues
    • Self-Balancing Trees
      • AVL trees, red-black trees
    • Dictionaries
      • Binary search trees, hash maps
  • Graphs
    • Introduction to Graphs
      • Definition, terminology, graph representations
    • Shortest Paths
      • Single-source shortest paths, all-pairs shortest paths
    • Minimum Spanning Trees
    • Directed Acyclic Graphs
      • Topological sorting
    • Maximum Flow (?)
  • Advanced Data Structures (?)
    • Disjoint Sets
    • B-Trees
    • Range Queries
    • Fibonacci Heaps
  • Special Topics (?)
    • Amortized Analysis
    • Randomized Algorithms

How to contribute

Right now, I'm not yet accepting pull requests, but feel free to open a new issue here if you want to report any errors.

Bug bounty bonus: If you are currently taking CSCI 30/CS 110, then you may be eligible for bonus points for every non-trivial error you report! Send me an email if you're interested.

License

License: CC BY-SA 4.0 This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.