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.
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
.
- 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
- Correctness (done)
- 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
- Searching (to be phased out by next year)
- 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)
- Arrays and Lists
- 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
- Trees
- 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 (?)
- Introduction to Graphs
- Advanced Data Structures (?)
- Disjoint Sets
- B-Trees
- Range Queries
- Fibonacci Heaps
- Special Topics (?)
- Amortized Analysis
- Randomized Algorithms
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.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.