Week | Date | Topic | Reading | Notes |
---|---|---|---|---|
1 | 01/13 | Intro and Review Analysis and Design | KT 1, CLRS 1-4 | Syllabus Jeff Erickson's Intro |
01/15 | Review Analysis of algorithms recurrences and big-Oh | KT 2.1, 2.2, 2.4, Skim 2.3, CLRS 3-4 | Combinarorial cheat sheet Notes on Recurrences KT: Analysis of Algorithms | |
2 | 01/20 | Stable matching | KT 1 | KT: Intro, KT: Stable matching demo |
01/22 | Review: graphs | KT 3 | KT: Graphs | |
01/23 | Last day to complete late registration. Last day to add/drop a course(s) via the Web. | |||
3 | 01/27 | Review graphs | KT 3 | |
01/29 | Review: recurrences | KT 1 | Notes on Recurrences | |
4 | 02/03 | Greedy algorithms | KT 4.1 | KT: Greedy algoritms |
02/05 | Greedy algorithms | KT 4.2, 4.3 | ||
5 | 02/10 | Still greedy | KT 4.3 | |
02/12 | Greedy: shortest path and MST | KT 4.4, 4.5 | KT: Greedy algoritms, continued Jeff Erikson: MST, a different view | |
6 | 02/17 | Minimum Spanning Tree (MST) | KT 4.5 | KT: Greedy algoritms, continued Jeff Erikson: MST, a different view |
02/19 | Divide and conquer | KT 5 | KT:Divide and conquer | |
7 | 02/24 | Divide and conquer | KT 5 | |
02/26 | Divide and conquer | KT 5 | ||
8 | 03/03 | Midterm in class | ||
03/05 | Dynamic programming | KT 6.1, 6.2 | Dynamic programming | |
9 | 03/10 | Dynamic programming | KT 6.3 | |
03/12 | Dynamic programming | KT 6.6 | ||
10 | 03/17 | Dynamic programming | KT 6.4 | |
03/19 | Network flow | KT 7.1, 7.2 | Network flow, Network flow demo | |
03/23-03/27 | Spring break | |||
11 | 03/31 | Dynamic programming: Bellman-Ford | KT 6.8 | Bellman-Ford shortest paths |
04/02 | Network flow applications: Bipartite matching, disjoint paths | KT 7.5, 7.6 | Network flow applications | |
12 | 04/07 | Network flow applications | KT 7.7, 7.8 | |
04/09 | Network flow and applications | |||
13 | 04/14 | NP completeness and intractability | KT 8.1 | Poly time reductions: by equivalence and special case |
04/16 | Poly time reductions | KT 8.2 | Reductions via gadgets: 3-SAT to Independent Set | |
14 | 04/21 | Definition of NP | KT 8.3 | Efficient certifiers and definition of NP |
04/23 | NP-completeness | KT 8.4 | NP-complete | |
15 | 04/28 | NP-hard problems | KT 8.5 | Sequencing problems Longest path song |
04/30 | Beyond NP-complete | |||
8am-10am | 05/08 | Final |
Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF | ![]() | ![]() |