TWiki>
CS401 Web>Syllabus>LectureNotes>CS401TanyaSpringTemplate (2015-08-25, Main.tanyabw)EditAttach
CS401 Web>Syllabus>LectureNotes>CS401TanyaSpringTemplate (2015-08-25, Main.tanyabw)EditAttachLecture Notes
| 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 | ||
Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r1 - 2015-08-25 - 01:20:04 - Main.tanyabw
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
| Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |  |  |