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.