LEC # | TOPICS | KEY DATES |
---|---|---|
Unit 1: Introduction | ||
1 | Algorithmic thinking, peak finding | Problem set 1 out |
2 | Models of computation, Python cost model, document distance | |
Unit 2: Sorting and Trees | ||
3 | Insertion sort, merge sort | Problem set 1 due Problem set 2 out |
4 | Heaps and heap sort | |
5 | Binary search trees, BST sort | |
6 | AVL trees, AVL sort | Problem set 2 due |
7 | Counting sort, radix sort, lower bounds for sorting and searching | Problem set 3 out |
Unit 3: Hashing | ||
8 | Hashing with chaining | |
9 | Table doubling, Karp-Rabin | Problem set 3 due Problem set 4 out |
10 | Open addressing, cryptographic hashing | Problem set 4 due |
Quiz 1 | ||
Unit 4: Numerics | ||
11 | Integer arithmetic, Karatsuba multiplication | Problem set 5 out |
12 | Square roots, Newton's method | |
Unit 5: Graphs | ||
13 | Breadth-first search (BFS) | |
14 | Depth-first search (DFS), topological sorting | Problem set 5 due Problem set 6 out |
Unit 6: Shortest Paths | ||
15 | Single-source shortest paths problem | |
16 | Dijkstra | |
17 | Bellman-Ford | |
18 | Speeding up Dijkstra | Problem set 6 due |
Quiz 2 | ||
Unit 7: Dynamic Programming | ||
19 | Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths | Problem set 7 out |
20 | Parent pointers; text justification, perfect-information blackjack | |
21 | String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack | |
22 | Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros. | Problem set 7 due |
Unit 8: Advanced Topics | ||
23 | Computational complexity | |
24 | Algorithms research topics |