TWiki> CS401 Web>Syllabus>LectureNotes (2017-11-06, Main.tanyabw)EditAttach

Lecture Notes

WeekDateTopicReadingNotes
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

Attachments Attachments
Topic attachments
I Attachment Action Size Date Who Comment
PowerPointppt 01demo-propose-and-reject.ppt manage 198.5 K 2015-01-05 - 19:26 UnknownUser  
PDFpdf 01stable-matching.pdf manage 324.6 K 2012-08-27 - 13:12 UnknownUser Lecture 1 slides
PDFpdf 02analysis.pdf manage 449.3 K 2012-08-28 - 13:00 UnknownUser Lecture 2 slides
PDFpdf 02recurrences-divide-conquer.pdf manage 382.0 K 2015-09-10 - 21:26 UnknownUser  
PDFpdf 03graphs.pdf manage 2696.2 K 2017-09-14 - 19:21 UnknownUser  
PDFpdf 04greed.pdf manage 1932.9 K 2017-09-28 - 19:59 UnknownUser  
PDFpdf 04mst.pdf manage 713.4 K 2015-02-11 - 06:59 UnknownUser  
PDFpdf 05divide-and-conquer.pdf manage 928.9 K 2017-10-13 - 03:08 UnknownUser  
PDFpdf 06bellman-ford.pdf manage 289.0 K 2015-03-31 - 21:34 UnknownUser  
PDFpdf 06dynamic-programming.Tanya.pdf manage 613.0 K 2017-11-06 - 21:46 UnknownUser  
PDFpdf 07assignment.pdf manage 121.8 K 2015-03-31 - 21:36 UnknownUser  
PDFpdf 07demo-maxflow.pdf manage 82.1 K 2015-03-31 - 21:34 UnknownUser  
PDFpdf 07maxflow-applications.pdf manage 4588.3 K 2015-03-31 - 21:35 UnknownUser  
PDFpdf 07maxflow.pdf manage 731.1 K 2015-03-31 - 21:35 UnknownUser  
PDFpdf 08intractability.pdf manage 653.2 K 2015-04-21 - 05:36 UnknownUser  
PDFpdf 08np-complete.pdf manage 6135.9 K 2015-04-21 - 05:36 UnknownUser  
PDFpdf 08reductions-poly.pdf manage 957.5 K 2015-04-21 - 05:36 UnknownUser  
PDFpdf 13-mst.pdf manage 287.2 K 2015-02-11 - 07:00 UnknownUser  
PDFpdf ScalingMaxFlowAlgorithm.pdf manage 90.8 K 2012-11-08 - 17:55 UnknownUser  
PDFpdf cmbntrcs_mitch.pdf manage 253.4 K 2015-01-05 - 19:25 UnknownUser  
Waveform sound filemp3 longest-path.mp3 manage 1642.5 K 2017-10-22 - 06:02 UnknownUser  
PDFpdf recurrences.pdf manage 579.0 K 2015-01-05 - 19:25 UnknownUser  
Edit | Attach | Print version | History: r30 < r29 < r28 < r27 < r26 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r30 - 2017-11-06 - 21:46:52 - Main.tanyabw
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu		 WISEST
Helping Women Faculty Advance
Funded by NSF