Lecture Notes

101/13Intro and Review
Analysis and Design
KT 1, CLRS 1-4Syllabus
Jeff Erickson's Intro
01/15Review Analysis of algorithms
recurrences and big-Oh
KT 2.1, 2.2, 2.4, Skim 2.3, CLRS 3-4Combinarorial cheat sheet
Notes on Recurrences
KT: Analysis of Algorithms
201/20Stable matchingKT 1KT: Intro, KT: Stable matching demo
01/22Review: graphsKT 3KT: Graphs
01/23Last day to complete late registration.
Last day to add/drop a course(s) via the Web.
301/27Review graphsKT 3
01/29Review: recurrencesKT 1Notes on Recurrences
402/03Greedy algorithmsKT 4.1KT: Greedy algoritms
02/05Greedy algorithmsKT 4.2, 4.3
502/10Still greedyKT 4.3
02/12Greedy: shortest path and MSTKT 4.4, 4.5KT: Greedy algoritms, continued
Jeff Erikson: MST, a different view
602/17Minimum Spanning Tree (MST)KT 4.5KT: Greedy algoritms, continued
Jeff Erikson: MST, a different view
02/19Divide and conquerKT 5KT:Divide and conquer
702/24Divide and conquerKT 5
02/26Divide and conquerKT 5
803/03Midterm in class
03/05Dynamic programmingKT 6.1, 6.2Dynamic programming
903/10Dynamic programmingKT 6.3
03/12Dynamic programmingKT 6.6
1003/17Dynamic programmingKT 6.4
03/19Network flowKT 7.1, 7.2Network flow, Network flow demo
03/23-03/27Spring break
1103/31Dynamic programming: Bellman-FordKT 6.8Bellman-Ford shortest paths
04/02Network flow applications: Bipartite matching, disjoint pathsKT 7.5, 7.6Network flow applications
1204/07Network flow applicationsKT 7.7, 7.8
04/09Network flow and applications
1304/14NP completeness and intractabilityKT 8.1Poly time reductions: by equivalence and special case
04/16Poly time reductionsKT 8.2Reductions via gadgets: 3-SAT to Independent Set
1404/21Definition of NPKT 8.3Efficient certifiers and definition of NP
04/23NP-completenessKT 8.4NP-complete
1504/28NP-hard problems KT 8.5

Sequencing problems

Longest path song

04/30Beyond NP-complete
Topic revision: r1 - 2015-08-25 - 01:20:04 - Main.tanyabw
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF