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