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

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.