Textbook:
Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein (CLRS)
Older editions should be fine as well, but readings below are
listed from the 3rd Edition.
Alternate Text:
Algorithm Design
by Kleinberg and Tardos
Tue | Thu | Fri |
---|---|---|
(3/29) Introduction, Why are you here? Read: Ch. 1 |
(3/31) MergeSort, Recurrences, Asymptotics Read: Ch. 2.3, 3.1 |
(4/1) Homework 0 Released |
(4/5) Integer Multiplication, Solving Recurrences Read: Ch. 4.3-4.5 |
(4/7) Median and Selection Read: Ch. 9 |
(4/8) Homework 0 Due Homework 1 Released |
(4/12) Quicksort, Probability and Randomized Algorithms Read: Ch. 7, 5 |
(4/14) Sorting Lower Bounds, Counting Sort Read: Ch. 8.1-2 |
(4/15) Homework 1 Due Homework 2 Released |
(4/19) Binary Search Trees Read: Ch. 12 |
(4/21) Hashing Read: Ch. 11 |
(4/22) Homework 2 Due Homework 3 Released |
(4/26) Open Addressing, Graphs, DFS Read: Ch. 22 |
(4/28) DFS, Topological Sort Read: Ch. 24, 6 |
(4/29) Homework 3 Due Study for Midterm |
(5/3) Midterm in class | (5/5)
BFS, Shortest Paths, Dijkstra's Algorithm Read: Ch. 24.3 |
(5/6) Homework 4 Released |
(5/10) Dijkstra's Runtime, Amortized Analysis for Binary Counter, Dynamic Programming: Bellman-Ford Read: 24.1, 24.3 |
(5/12) Dynamic Programming: Floyd-Warshall, Longest Common Subsequence, Read: Ch. 25.2, 15.4 |
(5/13) Homework 4 Due Homework 5 Released |
(5/17) Greedy Algorithms: Activity Selection Min Spanning Tree (MST): Prim's and Kruskal's Algorithms Read: Ch. 16, 23 |
(5/19) Finish MSTs, Minimum Cut: Karger's algorithm Read: Kleinberg-Tardos Ch. 13.2: [pdf] |
(5/20) Homework 5 Due Homework 6 Released |
(5/24) Maximum Flow Read: Ch. 26.1-3 |
(5/26) More Maximum Flow, Graph Matchings Read: Ch. 26.2-3 |
(5/27) Homework 6 Due |
(5/31) The Wider World of Algorithms | (6/1) Optional Review Session (tentative, and it will be on June 1st, not June 2nd.) |
(6/4) Final Exam *SATURDAY* at 7pm |