CAS CS 330 - Spring 2016 - Handouts and Lectures

Homework Assignments and Other Handouts


Assignments and solutions can be found on our Piazza page, under the Resources tab.

Lecture Topics and Slides


Lecture 1 (1/19): Review of syllabus. Stable matching problem. Gale-Shapley algorithm and implementation.
Kevin Wayne's lecture slides and demo, used with permission.

Lecture 2 (1/21): Five representative problems in lecture 1 slides, followed by review material from Chapter 2 (slides).
Problem solving: Max sum subinterval problem solved three ways: O(n^3), O(n^2), O(n log n).

Lecture 3 (1/26): Finish max sum subinterval problem. Then start on intro to graphs, graph data structures, graph algorithms. Chapter 3 (slides).

Lecture 4 (1/28): Graph algorithms: review of inductive proofs with BFS. Connected components, testing for bipartiteness. Strong connectivity in directed graphs.

Lecture 5 (2/2): DAGs, topological sort algorithm. Start in on Chapter 4: greedy algorithms (slides). Solving the interval scheduling and interval partitioning problems (demo).

Lecture 6 (2/4): More greedy algorithms: minimizing max lateness, caching (no proof of Belady's algorithm), Dijkstra's algorithm for shortest paths (+ demo).

Lecture 7 (2/9): Minimum spanning tree properties and efficient algorithms (slides). Application to clustering.

Lecture 8 (2/11): Compression and Huffman codes (slides). Start on Divide-and-Conquer (slides): basics, review of recurrences.

Tuesday 2/16: BU is on a Monday schedule. Regular Monday labs will be held.

Thursday 2/18: John out of town. No lecture today.

Lecture 9 (2/23): Counting inversions (demo), finding the closest pair of points in 2-D (slides)
Fast integer multiplication (slides).

Lecture 10 (2/25): Fast matrix multiplication to wrap up Chapter 5.
Begin Chapter 6: dynamic programming (slides). We covered 6.1: weighted interval scheduling.

Lecture 11 (3/1): Problem solving: Chapter 4, Q21. Discussion of MST programming problem from HW #3. Dynamic programming continued: multiway choice in segmented linear regression (6.3).

Thursday 3/3: In-class midterm. Covers all lecture, lab, homework material up through 2/25.

Spring Break

Lecture 12 (3/15): Review of midterm answers. Continuing dynamic programming: knapsack problem.

Lecture 13 (3/17): Dynamic progamming in 2-D: RNA secondary structure, sequence alignment.

Lecture 14 (3/22): Finish up sequence alignment in linear space. Bellman-Ford shortest path algorithm and applications to Internet routing (slides).

Lecture 15 (3/24): Intro to max flow: capacitated graphs, definition of flows on graph, and problem statements (slides). Weak duality and Ford-Fulkerson algorithm (FF demo slides).

Lecture 16 (3/29): Efficient flow algorithms: choosing augmenting paths. Applications of max-flow: matchings in bipartite graphs, perfect matchings. (Slides).

Lecture 17 (3/31): More advanced applications of max-flow: edge-disjoint paths, project selection with prerequisites (Section 4.11). You are not responsible for material we did not cover in class.

Lecture 18 (4/5): Polynomial-time reductions, demonstrating hardness of problems. Problems and reductions: independent set, vertex cover, set cover, 3-SAT. (Slides).

Lecture 19 (4/7): P vs. NP. Definitions and elaboration. Notion of NP-Completeness. (Slides).

Lecture 20 (4/12): Problem solving: the mystery problem was Q19 from Chapter 7.
Circuit-SAT as "the first" NP-Complete problem. Start on NP-completeness reductions (more slides).

Lecture 21 (4/14): NP-Completeness reductions. Circuit-SAT to 3SAT, 3-SAT to each of Hamiltonian Cycle, TSP, and Subset Sum.

Lecture 22 (4/19): Finish up NP-Completeness reductions from last time.
Local search heuristics (some used in HW #7). We'll cover a handful of Chapter 12 slides, up through the Metropolis-Hastings method.

Lecture 23 (4/21): Local search heuristics, then intro to approximation algorithms. We did up through list-scheduling for load balancing (Slides).

Lecture 24 (4/26): Problem solving: Reducing from 3-SAT and Set Cover. Solved exercise #2 from Chapter 8, pp. 502-4.
Approximation algorithms: finish up load balancing, then center selection.

Lecture 25 (4/28): Center selection. Course recap.

See the syllabus for a tentative gameplan of upcoming material.