Class meeting time: Tues/Thurs 2:00-3:30 in MCS B33.
Lab meeting times: Fri 11-12 and Fri 2-3 PM in SED 206. Lab webpage.
Instructor:
Prof. John W. Byers
Email (preferred): byers @ cs . bu . edu
Phone: 617-353-8925
Office: MCS 270
Office Hours: Mon 9:30 - 11 and Thurs 3:30-5, held in MCS 270
Teaching Fellow: Karim Mattar
Email: kmattar @ cs . bu . edu
Office Hours: Mon 7-8PM (EMA 302), Tues 3:30 - 4:30 (EMA 302), Fri 12 -2 (between lab meetings; SED 1st floor lounge)
General CS Tutoring Hour: Mon 8-9PM (EMA 302).
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 3:
Homework 1 (pdf),
(latex source).
Due September 15.
September 16:
Homework 2 (pdf),
(latex source).
Due September 29.
October 1:
Homework 3 (pdf),
(latex source).
Due October 15.
October 15:
Midterm study questions (pdf).
October 22:
Homework 4 (pdf),
(latex source).
Due October 29.
October 30:
Homework 5 (pdf),
(latex source).
Due November 12.
November 12:
Homework 6 (pdf),
(latex source).
Due November 24.
November 25:
Homework 7 (pdf),
(latex source).
Due December 10.
Lectures:
Lecture 1 (9/3): 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): Stable matching wrapup. Representative problems + max sum subinterval. Start of review
material from
Chapter 2 (slides).
Lecture 3 (9/10): Running time and Big-O notation review. Survey of common running times and how they
arise. Intro to graphs and their applications.
Lecture 4 (9/15): Graphs and basic graph algorithms. Graph connectivity and traversal problems.
Breadth-first search (BFS) and applications of BFS.
Chapter 3 slides.
Lecture 5 (9/17): Problem solving: Q7 and variant of Q2 from Chapter 3. DAGs and computing a
topological ordering of a DAG.
Lecture 6 (9/22): Greedy algorithms and their analysis. Interval scheduling and minimizing lateness.
Exchange arguments. Chapter 4 slides.
Lecture 7 (9/24): Problem solving: Q16 from Chapter 4. Belady's algorithm for optimal caching
and proof sketch. Start of Dijkstra's algorithm.
Lecture 8 (9/29) Dijkstra's algorithm and analysis. Minimum spanning trees: definitions, algorithms,
and analysis.
Chapter 4 slides, part 2.
Dijkstra's demo.
Lecture 9 (10/1) Problem solving: Q21 & 24 from Chapter 4.
Clustering via MSTs. Huffman codes.
Chapter 4 slides, part 3.
Lecture 10 (10/6) End of Huffman codes. Begin divide and conquer, recurrences, counting inversions.
Chapter 5 slides, part 1.
Lecture 11 (10/8) Problem solving: Q3 from Chapter 5.
Algorithms for closest pair of points and integer multiplication.
Chapter 5 slides, part 2.
Lecture 12 (10/15) In-depth discussion of evaluating recurrence relations via unraveling and via substitution
method. Brief tour of Strassen's algorithm for fast matrix multiplication.
In-class Midterm (10/20)
Lecture 13 (10/22) Midterm solutions. Dynamic programming for weighted interval scheduling (2-way choice) and
segmented least squares (n-way choice).
Chapter 6 slides, part 1.
Lecture 14 (10/29) Dynamic programming problems: knapsack, RNA secondary structure, sequence alignment.
Lecture 15 (11/2) Problem solving: Q20 from Chapter 6. Bellman-Ford for shortest paths. Intro to max flow.
Bellman-Ford slides.
Lecture 16 (11/4) Max-flow / min-cut theorem and algorithms: Ford-Fulkerson, capacity scaling.
Slides and demo.
Lecture 17 (11/9) Applications of max-flow: bipartite matching and network reliability.
Slides (we only covered the first 20).
Notions and applications of polynomial time reducibility.
Chapter 8 slides, (part 1).
Lecture 18 (11/11) Problem solving: Q7 from Chapter 7. More on polytime reducibility and the definition of the class NP.
Lecture 19 (11/18) Non-determinstic polynomial time (NP). NP-hardness, NP-completeness. Using reductions to prove NP-completeness of a problem.
We covered the first 25 of these slides:
Ch. 8 (part 2),
and a few of these
Ch. 8 (part 3), notably the subset sum reduction.
Lecture 20 (11/20) Problem solving: Q14 from Chapter 8. Approximation algorithms:
load balancing, center selection, set cover (Chapter 11.1 - 11.3).
Slides.
Lecture 21 (11/25) A PTAS for Knapsack (11.8). Overview of local search, gradient descent, simulated annealing.
Slides.
Lecture 22 (12/1) Randomized algorithms. Contention resolution, union bounds, global min cut.
Slides.
Lecture 23 (12/3) Working with expectations, linearity of expectation. Coupon collector's problem.
7/8 approximation for MAX 3-SAT. Randomized selection and median-finding.
Lecture 24 (12/8) Problem solving: Q18 from Chapter 13. Randomized quicksort. Universal hashing.
Lecture 25 (12/10) Comprehensive course review.
See the syllabus
for a tentative gameplan of upcoming material.