|
|
|
|
|
| 9/2/19 |
Sorting Weds: Syllabus Fri: Heap review |
Mini 1 (due Fri. 9/13 in class) HW 1: Sorting and Asymptotic Analysis (due Fri. 9/20 in class) (tex file in case you want a template) |
CLRS 6 KT 2.5 |
| 9/9/19 |
Asymptotic analysis and recurrences Tues: Suggestions for time management for long HW assignments (not handed out in class) Weds/Thurs: Practice with Asympotic Analysis Fri: Practice problems with induction (not handed out in class) |
Mini 2 (due Fri. 9/20 in class) |
CLRS 2.3, 3.1 KT 2.1-2.2 |
| 9/16/19 |
More sorting and divide-and-conquer |
Mini 3 (due Fri. 9/27 in class) |
CLRS 4.3-4.4, 7 KT 5.1-5.2, 13. |
| 9/23/18 | Master theorem, divide-and-conquer |
Mini 4 (due Fri. 10/4 in class) HW 2: Divide-and-Conquer (due Fri. 10/11 in class) (tex file in case you want a template) |
CLRS 4.5, 8.1, 8.3 |
| 9/30/19 |
Greedy algorithms: making change, interval scheduling, Dijkstra |
Mini 5 (due Fri. 10/11 in class) |
CLRS 16.1-16.2, 24.3 KT 4.1, 4.4 |
| 10/7/19 | Minimum spanning trees: Prim's algorithm and Kruskal's algorithm |
Mini 6 (due Mon./Tues. 10/21-22 in class) |
CLRS 23 (see 23.2 for Prim and Kruskal pseudocode and examples) KT 4.5 |
| 10/14/19 |
Review, MIDTERM (Fri. 10/18) Sun: Midterm 1 study guide Some sample problems Weds: Pictures from review activity: asymptotic 1, asymptotic 2, sorting algorithms, sorting properties, greedy paradigm, divide-and-conquer paradigm, graphs and Dijkstra |
||
| 10/21/19 |
Dynamic programming: making change, weighted interval scheduling |
Mini 7 (due Fri. 11/1 in class) HW 3: Greedy and Dynamic Programming (due Fri. 11/8 in class) |
CLRS 15.3 (components of DP algorithm) (see also 15.2, 15.4 for more examples of DP algorithms) KT 6.1 (weighted interval scheduling, with an example of reconstructing solutions), 6.2 (structure of DP algorithms) (see also 6.3-6.7 for more examples of DP algorithms) |
| 10/28/19 |
More DP: Bellman-Ford Fri: Bellman-Ford example |
Mini 8 (due Fri. 11/8 in class) | KT 6.8 (Bellman-Ford discussion) |
| 11/4/19 |
Network Flow Mon: Ford-Fulkerson pseudocode |
Mini 9 (due Fri. 11/15 in class) HW 4: Algorithmic Paradigms and Network Flow (due Weds. 11/20 in class) |
KT 7.1 (max flow problem and Ford-Fulkerson), 7.2 (max flow = min cut), 7.5 (bipartite matching), 7.12 (baseball elimination) (see also 7.6-7.11 for more examples of problems that can be solved using NF) |
|
11/11/19 |
Problem reductions Thurs: Midterm 2 study guide Some sample problems |
KT 8.1-8.2 (reductions between IS and VC and from 3-SAT to IS, implications of polynomial time reductions) | |
| 11/18/19 | NP-hardness and NP-completeness, MIDTERM (Fri. 11/22) | ||
| 11/25/19 |
|
||
| 12/2/19 |
More on NP-completeness |
Mini 10 (due Weds. 12/11 in class) | |
| 12/9/19 |
Approximation algorithms Mon: Final exam study guide (not handed out in class) Sample final (not handed out in class) |
||
