Lecture Topics (tentative)
Wed, Jan 21 — Greedy I: Course Intro and Minimum Spanning Tree (Notes)
Reading: KT §1.2 and §2 (especially 2.1, 2.2, 2.4) and §3.1-3.3 and 4.4
Fri, Jan 23 — Greedy II: Algorithms for Minimum Spanning Tree and Interval scheduling start (Notes)
Reading: KT §4.5 (see also, §3.1-3.3 and 4.4)
Mon, Jan 26 — Greedy III: Universuty closed due to weather. Please watch the following short video on interval scheduling, material that is needed for sections this week. See also the Notes.
Reading: KT §4.1
Mon-Tue, Jan 26-27 — Section: Practice with greedy
Reading: KT §4.1 and §4.5
Wed, Jan 28 — Dynamic Programming I: Weighted interval scheduling. See the notes from class.
Reading: KT §6.1 and §6.2
Fri, Jan 30 — Dynamic Programming II: Segmented Least Squares. See the notes from class.
Reading: KT §6.3
Mon, Feb 2 — Dynamic Programming III: Shortest Path in Graphs. See the notes from class.
Reading: KT §4.4 and §6.8
Mon-Tue, Feb 2-3 —
Section: Quiz on greedy (based on the HW1) and practice with dynamic programming
Wed, Feb 4 —
Dynamic Programming IV: Sequence Alignment. See the notes from class.
Reading: KT §6.6
Fri, Feb 6 — Dynamic Programming V: The Knapsack Problem. See the notes from class.
Reading: KT §6.4
Mon, Feb 9 —
Review for Prelim I (one more greedy and reductions). See the notes from class.
Mon-Tue, Feb 9-10 —
Section: Quiz on dynamic programming (based on the HW2) and practice for the prelim
Wed, Feb 11 —
Stable Matching I. See the notes from class.
Wed, Feb 11 — Stable Matching I. See the notes from class.
Reading: KT §1.1
Thu, Feb 12 —
Prelim I at 7:30-9pm
Fri, Feb 13 —
Stable Matching II. See the notes from class
Reading: KT §1.1
Mon, Feb 16 —
February break
Wed, Feb 18 —
Maximum Bipartite Matching and Network Flows basics. See the notes from class
Reading: KT §7.1 and §7.5
Fri, Feb 20 — Network Flows II: Ford-Fulkerson Algorithm. See the notes from class.
Reading: KT §7.1 and §7.2
Mon, Feb 23 — Network Flows III: Correctness of the Ford-Fulkerson Algorithm and min cuts. See the notes from class
Reading: KT §7.2
Wed, Feb 25 — Network Flows IV: More applicatins of max flows. See the notes from class
Reading: KT §7.7-§7.8
Fri, Feb 27 — Network Flows V: Application of Min Cuts. See the notes from class
Reading: KT §7.11
Mon, Mar 2 — NP completeness I: Proving Harness by Reductions (Independent Set, Vertex Cover). See the notes from class.
Reading: KT §8.1
Wed, Mar 4 — NP completeness II: P, NP, NP-completeness and SAT (and 3-SAT). See the notes from class.
Reading: KT §8.2-§8.4
Fri, Mar 6 — NP completeness III: Proving independent Set NP-complete. See the notes from class.
Reading: KT §8.2-§8.4
Mon, Mar 9 — NP completeness IV: Sequencing Problems: Traveling Salesman, Hamiltonian Cycle, and Hamialtonian Path. See the notes from class.
Reading: KT §8.5
Wed, Mar 11 — NP completeness V: NP completeness VI: Hard Problems with numbers. See the draft notes for class.
Reading: KT §8.8
Fri, Mar 13 — NP completeness VI: Taxonomy of NP-hard problems and asymetry of NP
Reading: KT §8.9 and KT §8.10
Mon, Mar 16 —
Wed, Mar 18 — Divide and Conquer I:
Reading: KT §5.1