Lecture meeting time: Tues/Thurs 3:30 - 5,
CAS 316.
Lab meeting times:
Mon 11-12 (GCB 201), Mon 12-1 (CAS 233) and Mon 3-4 PM (CAS 323B).
Instructor:
Prof. John W. Byers
Email (preferred): byers @ cs . bu . edu
Phone: 617-353-8925
Office: MCS 270
Office Hours: Mon 9:30 - 11AM and Wed 11-12:30AM, held in MCS 270 (John's office).
Teaching Fellow: Sam Epstein
Email: samepst @ cs . bu . edu
Office Hours: Tues 12-1, Wed 2-3, Thu 10-11, held in EMA 302 (next to ugrad lab).
Official Course Description: This course examines the basic principles of algorithm analysis; techniques of efficient programming; analysis of sorting and searching; graph algorithms; string-matching algorithms; matrix algorithms; integer and polynomial arithmetic; the fast Fourier transform; and NP-hard and NP-complete problems.
Textbook: Algorithm Design, by Kleinberg and Tardos. ISBN 0-321-29535-8.
Syllabus: The details of the class are available on the syllabus.
Homework Assignments and Other Handouts:
September 1:
Homework 1 (pdf),
(latex source).
Due September 15. Average: 33/40.
September 16:
Homework 2 (pdf),
(latex source).
Due September 29. Average: 33/50.
September 29:
Homework 3 (pdf),
(latex source).
Due October 13. Average: 35/60 (with many regrades requested).
October 13:
Practice questions for the midterm.
October 13:
Homework 4 (pdf),
(latex source).
Due October 28. Average: 29/40.
October 31:
Homework 5 (pdf),
(latex source).
Due November 11. Average: 36/50.
November 14:
Homework 6 (pdf),
(latex source).
Due November 22.
November 28:
Homework 7 (pdf),
(latex source).
Due December 8.
December 12: Recommended
study questions for the final.
Lectures:
Lecture 1 (9/6): Review of syllabus. Stable matching problem. Gale-Shapley algorithm and implementation.
Kevin Wayne's
lecture slides
and demo
used with permission.
Lecture 2 (9/8): Max sum subinterval problem solved three ways: O(n^3), O(n^2), O(n log n). Start of review
material from
Chapter 2 (slides).
Lecture 3 (9/13): Wrap up review material from
Chapter 2 (slides).
Review of graph terminology, graph data structures. and basic graph algorithms from
Chapter 3 (slides).
We covered through Sec 3.4: BFS analysis, testing bipartiteness.
Lecture 4 (9/15): Strong connectivity (3.5), DAGs and topological ordering (3.6), including a
demo
(not covered in lecture). Beginning of Chapter 4:
(slides):
greedy algorithms, interval scheduling
(demo).
Lecture 5 (9/20) Discussion of Question 4 on HW #1, and problems from HW #2. Problem solving: Q2 and Q7 from Chapter 3.
Interval Partioning.
Lecture 6 (9/22) Greedy algorithms: minimizing maximum lateness, Belady's farthest-in-future algorithm
for caching, review of Dijkstra's shortest path algorithm
(demo).
Lecture 7 (9/27) Minimum spanning trees (MSTs). Cut and cycle property. Proof of correctness and running time
of Kruskal's and Prim's algorithms for finding an MST. Problem solving: Q21 from Chapter 4.
Next
set of slides.
Lecture 8 (9/29) More greedy algorithms from Chapter 4. Clustering, then
Huffman codes.
Lecture 9 (10/4) Wrapup of Huffman codes. Start on divide-and-conquer: counting inversions
[slides,
demo].
Lecture 10 (10/6) Problem solving: Q28 from Chapter 4. Divide-and-conquer: closest pair of points.
Lecture 11 (10/11) Integer and matrix multiplication
[slides].
(We'll try to come back to polynomial multiplication and FFTs as time allows).
Next topic: Dynamic Programming [slides].
Lecture 12 (10/13) Dynamic programming. Basic principles; weighted interval scheduling.
Lecture 13 (10/15) Problem solving: Q3 from Chapter 5. Multi-way choice, k-way segmentation problem.
Lecture 14 (10/20) Advanced dynamic programming. Adding a new variable -- knapsack problem.
Lecture 15 (10/22) Problem solving: Q20 from Chapter 6. Dynamic programming over intervals:
RNA sequencing.
Lecture 16 (10/27) In-class midterm. Closed book, notes, and phones. The midterm average was 71.
Lecture 17 (11/1) Bellman-Ford algorithm and applications.
[slides].
Lecture 18 (11/3) Midterm answers. Max-flow, min-cut. Ford-Fulkerson algorithm.
[slides]
and
[demo].
Lecture 19 (11/8) Running time analysis; max-flow in polynomial time via capacity scaling.
Applications of network flow: computing maximal matchings.
[slides].
Lecture 20 (11/10) Class cancelled.
Lecture 21 (11/15) More applications of network flow:
Perfect matchings in bipartite graphs. Edge-disjoint paths, network connectivity
graph, and Menger's theorem. On to Chapter 8: starting with intractability:
[slides].
Lecture 22 (11/17) Problem solving: Q27 from Chapter 7.
Notions of poly-time reducibility and hardness. Reductions between combinatorial problems.
Definition of the class NP. Certifiers and certificates.
[slides (we
covered only the first 24)].
Lecture 23 (11/22) NP completeness and proving that a problem is NP-hard. Quick tour of circuit-SAT
and connection to 3-SAT. 3-SAT reductions to Hamiltonian cycle, to Traveling Salesman, and to
subset sum from these
slides.
Lecture 24 (11/29) Problem solving: Q14 from Chapter 8.
[slides].
Motivation for approximation algorithms: load balancing, center selection, set cover (Chapter 11.1 - 11.3).
Lecture 25 (12/1)
A PTAS for Knapsack (11.8). Quick overview of local search, gradient descent, simulated annealing
(Slides).
Randomized algorithms. (Slides).
Lecture 26 (12/7) Contention resolution. Union bounds. Global min cut. Working with expectations, linearity of expectation. Coupon collector's problem.
Lecture 27 (12/9) 7/8 approximation for MAX 3-SAT. Randomized quicksort. Universal hashing.
Course wrap-up.
Lab (12/12): Final exam review.
Final Exam (Friday 12/16, 3-5 PM): Final exam (in the normal final exam slot for classes in our time block).
See the syllabus
for a tentative gameplan of upcoming material.