Calendar

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