CAS CS 330 - Spring 2017 - Lectures and Readings
Homework Assignments and Other Handouts
Assignments and any other handouts can be found on our
Piazza page,
under the Resources tab.
Homework 1 was due on January 26th, returned on February 8th. Average was 33.1 / 40, standard deviation was 5.6.
Homework 2 was due at 5PM on February 10th. 1 free late day due to BU snow closure on Feb 9th. Average was 38.4 / 50, standard deviation was 8.6.
Homework 3 was due on Thursday February 23rd. Average was 39.1 / 50, standard deviation was 8.3.
The midterm was held in class on Thursday March 2. Average was 75.5 / 100, standard deviation was 16.
Homework 4 was due on Thursday March 16th. Average was 34.6 / 40, standard deviation of 5.3.
Homework 5 was due on Thursday March 30th. Programming portion only (Question 5) was due on Tuesday April 4th.
Average was 49 / 60, standard deviation of 13.5.
Homework 6 was due on *Tuesday April 18th* (updated from original 4/13 due date because of snow days).
Average was 47 / 60, standard deviation of 9.1.
Homework 7 was due on *Tuesday May 2* (updated from original 4/27 due date because of snow days).
Average was 39.5 / 50, standard deviation of 9.6.
Lecture Topics and Slides
Lecture 1 (1/19) [John]: Review of syllabus. Stable matching problem. Gale-Shapley algorithm and implementation.
Chapter 1 lecture slides,
and Gale-Shapley demo.
Reading: Chapter 1.
Lecture 2 (1/24) [Dora]:
Five representative problems in lecture 1 slides, followed by review material from Chapter 2 (slides on Piazza).
Problem solving: Max sum subinterval problem solved two ways (so far): O(n^3) and O(n^2). More later in the class.
Reading: Chapter 2 (review).
Lecture 3 (1/26) [Dora]:
Finish max sum subinterval problem. Then start on intro to graphs, graph data structures, graph algorithms. BFS and proof of level-order property.
Chapter 3 slides.
Reading: Chapter 3.1 - 3.3 (hopefully mostly review).
Lecture 4 (1/31) [John]: Adjacency list vs. adjacency matrix review.
Graph algorithms: BFS implementation, connected components,
testing for bipartiteness. Strong connectivity in directed graphs.
Chapter 3 slides.
Reading: Chapter 3.4 - 3.5.
Lecture 5 (2/2) [John]:
DAGs, topological sort algorithm
(demo).
Start in on Chapter 4: greedy algorithms (slides).
Solving the interval scheduling problem
(demo).
Reading: Chapter 3.6, 4.1.
Lecture 6 (2/7) [Dora]:
More greedy algorithms to illustrate proof techniques: classroom scheduling,
minimizing maximum lateness.
Reading: Chapter 4.1 - 4.2. Continuing with slides above.
Next topic: Weighted graphs. Dijkstra's algorithm for shortest paths.
(demo).
Chapter 4.4.
Lecture scheduled for Thurs 2/9 was snowed out.
Lecture 7 (2/14) [Dora]:
Dijkstra's algorithm, proof, and efficient implementation.
Minimum spanning tree (MST) problem definition. Cut and cycle properties in minimum spanning trees.
(MST slides).
Reading: Chapter 4.4, 4.5.
Lecture 8 (2/16) [John]:
Efficient algorithms for minimum spanning trees, especially Kruskal's and Prim's algorithms.
Compression and Huffman codes.
Huffman slides (you are only responsible through slide 18).
Reading: Chapter 4.6 - 4.8.
Tuesday 2/21 was on a Monday schedule at BU. No lecture.
Lecture 9 (2/23) [Dora]: Huffman code algorithm, but without proof of correctness.
Divide and conquer: quick review of mergesort algorithm and recurrences.
Counting inversions.
Chapter 5 slides.
Reading: Chapter 5.1 - 5.3
Lecture 10 (2/28) [John]: Divide and conquer continued. Closest pair of points.
Karatsuba's algorithm for multiplying integers. Strassen's fast matrix multiply.
Reading: Chapter 5.4 - 5.5.
The midterm was held in class on Thurs, March 2.
Spring Break was March 4-12.
Lecture scheduled for Tues 3/14 was snowed out.
Lecture 11 (3/16) [Dora]: Introduction to dynamic programming. Weighted interval scheduling.
Recursion vs. memoization approaches.
Chapter 6 slides.
Reading: Chapter 6.1 - 6.2.
Lecture 12 (3/21) [Dora]: Quick review of homework #3, Q4 solution.
Then back to dynamic
programming: n-way choice in segmented least squares problem, adding an extra variable in
classic knapsack problem.
Reading: Chapter 6.3 - 6.4.
Lecture 13 (3/23) [John]: More dynamic programming. Wrap up of knapsack problem.
Dynamic programming over subintervals: sequence alignment. Combining DP with divide and
conquer to do sequence alignment in linear space.
Reading: Chapter 6.6 - 6.8. (We skipped RNA sequence alignment in 6.5 due to snow days).
Lecture 14 (3/28) [John]: Distributed shortest paths algorithm that also handles negative edge weights: Bellman-Ford.
Intro to max flow: capacitated graphs, definition of flows on graph, and min-cut and max-flow problem statements.
Chapter 7 slides.
Reading: Chapter 7.1 - 7.2.
Lecture 15 (3/30) [John]: Max-flow, min-cut. Weak duality. Ford-Fulkerson algorithm via augmenting paths on the residual graph. Proof of max-flow, min-cut theorem. Capacity scaling approach to efficient max-flow implementation.
Reading: Chapter 7.3-7.4.
Lecture 16 (4/4) [Dora]: Applications of max-flow, min-cut. Bipartite matching and the marriage theorem. Disjoint paths. Circulations.
Chapter 7 application slides.
Reading: Chapter 7.5-7.7.
Lecture 17 (4/6) [Dora]: Polynomial-time reductions, demonstrating hardness of problems. Problems and reductions: independent set, vertex cover, set cover, 3-SAT.
Slides.
Reading: Chapter 8.1-8.2.
Lecture 19 (4/11) [John]: P vs. NP. Definitions and elaboration. Notion of NP-Completeness. Circuit-SAT as "the first" NP-Complete problem.
Slides.
Reading: Chapter 8.3-8.4.
Lecture 20 (4/13) [John]: Problem solving: Q17 from Chapter 7. Proving other problems are NP-complete. Circuit-SAT reduction to 3-SAT. 3-SAT reduction to
Directed Hamiltonian Cycle.
Slides.
Reading: Chapter 8.5-8.8.
Lecture 21 (4/18) [Dora]: More NP-completeness reductions selected from Chapters
8.5 - 8.8: TSP, Subset-Sum.
Local search heuristics (some used in HW #7). We covered a handful of
Chapter
12 slides, up through the Metropolis-Hastings method.
Reading: Chapter 12.1-12.2.
Lecture 22 (4/20) [Dora]: Intro to approximation algorithms. The load balancing problem.
NP-hardness via reduction from subset sum. List-scheduling algorithm for load balancing
to achieve a 2-approx and a 3/2-approx through tighter analysis.
Chapter 11 slides,
list scheduling demo.
Reading: Chapter 11.1-11.2.
Lecture 23 (4/25) [John]: NP-Complete problem solving: Lecture Planning problem, reductions from 3-SAT and Set Cover.
Derived from solved exercise #2 on Chapter 8, pp. 502-4.
Back to approximation algorithms: center selection.
Lecture 25 (4/27) [John]: Center selection 2-approximation proof. Poly-time approximation scheme for Knapsack (11.8). Quick discussion of randomized algorithm for global Min-Cut (13.2) -- slides on Piazza.
Reading: Chapter 11.8, 13.2.
Lecture 26 (5/2) [Dora]: Comprehensive course review, focusing on the second half of the course.