Lecture meeting time: Tues/Thurs 11 - 12:30,
CAS 222.
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 3-4:30PM, held in MCS 270 (John's office).
Teaching Fellow: Sanaz Bahargam
Email: bahargam @ cs . bu . edu
Office Hours: Tues 4-5:30 and Wed 11-12:30, 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:
January 15:
Assignment 1 (pdf),
(latex source).
Due at the beginning of class on January 31.
January 31:
Assignment 2 (pdf),
(latex source).
Due at the beginning of class on February 14.
February 15:
Assignment 3 (pdf),
(latex source).
Due at the beginning of class on February 28.
February 27:
Sample midterm questions (pdf),
(latex source).
March 5:
Assignment 4 (pdf),
(latex source).
Due at the beginning of class on March 21.
March 21:
Assignment 5 (pdf),
(latex source).
Due at the beginning of class on April 4.
April 5:
Assignment 6 (pdf),
(latex source).
Due by 5PM on April 18.
April 18:
Assignment 7 (pdf),
(latex source).
Due at the beginning of (the last day of) class, May 2.
May 1:
Sample final questions (pdf),
(latex source).
Lectures:
Lecture 1 (1/17): Review of syllabus. Stable matching problem. Gale-Shapley algorithm and implementation.
Kevin Wayne's
lecture slides
and demo,
used with permission.
Lecture 2 (1/22):
Five representative problems, followed by review material from
Chapter 2 (slides).
Begin Max sum subinterval problem solved three ways: O(n^3), O(n^2), O(n log n).
Lecture 3 (1/24):
Finish max sum subinterval problem. Then start on intro to graphs, graph data structures, graph algorithms.
Chapter 3 (slides).
Lecture 4 (1/29):
Finish Chapter 3. BFS and connectivity. Testing for bipartiteness (algorithm developed in class by
the students -- that was fun!). Directed graphs, DAGs, and topological sort.
Lecture 5 (1/31):
Problem solving: Q7 in Chapter 3.
Start in on Chapter 4: greedy algorithms (slides).
Solving the interval scheduling and interval partitioning problems
(demo).
Lecture 6 (2/5): Continuing greedy algorithms from Chapter 4: minimizing max lateness,
Farthest-in-future algorithm for offline caching, Dijkstra's algorithm
(+ demo,
not covered in class).
Lecture 7 (2/7): Minimum spanning tree: properties and efficient algorithms
(slides).
Application to clustering.
Lecture 8 (2/12):
Huffman codes (slides). Wrap-up greedy algorithms.
Lecture 9 (2/14):
Start in on Chapter 5: divide-and-conquer. Review of basics, analyzing recurrences.
Counting inversions
(demo),
finding the closest pair of points in 2-D
(slides).
Lecture 10 (2/19): Problem solving: Q19 from Chapter 4. Fast integer multiplication. Start in on fast matrix multiplication.
(slides).
Lecture 11 (2/21): Fast matrix multiplication, and start on fast polynomial multiplication via FFTs.
Lecture 12 (2/26): Finish up FFTs and begin Chapter 6: dynamic programming.
(slides).
Lecture 13 (2/28): Problem solving: Q3 from Chapter 5. Then back to DP: weighted interval scheduling,
start on segmented least squares problem.
Lecture 14 (3/5): Discussion of HW #3 problems. Problem solving: Q3 from Chapter 6.
Finish segmented least squares problem and move on to Knapsack.
Lecture 15 (3/7): In-class midterm.
Week of 3/11: Spring Break -- no class.
Lecture 16 (3/19): Prof. Byers out of town for a PI meeting. Class cancelled.
Lecture 17 (3/21): Discussion of midterm answers. Problem solving: Q20 from Chapter 6.
Segue back into Knapsack problem and solution in pseudo-polynomial time.
Lecture 18 (3/26): More advanced dynamic programs involving internal sequences:
RNA Secondary Structure, and start of Sequence Alignment.
Lecture 19 (3/28): Sequence Alignment problem. Bellman-Ford shortest path algorithm, and
its application to intradomain routing.
(Slides).
Lecture 20 (4/2): Introduction to max-flow and min-cut problems, basic definitions, and Ford-Fulkerson
algorithm.
(Slides,
(Demo).
Lecture 21 (4/4): Proof of the max-flow, min-cut theorem. Applications of max-flow: matchings in
bipartite graphs, perfect matchings.
(Slides).
Lecture 22 (4/9): 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 23 (4/11): Polynomial-time reductions, demonstrating hardness of problems.
Problems and reductions: independent set, vertex cover, set cover, 3-SAT.
(Slides).
Lecture 24 (4/16): P vs. NP. Definitions and elaboration. Notion of NP-Completeness.
(Slides).
(4/18): No class, but Monday schedule, so regular lab.
Lecture 25 (4/23): Short digression on local search heuristics, since you'll need them to
work on HW #7. We covered a handful of
Chapter 12 slides, up through the Metropolis-Hastings method.
Then, back to NP: Circuit-SAT as "the first" NP-Complete problem. Reduction from Circuit-SAT to 3-SAT.
(Slides).
(4/25): Class cancelled.
Lecture 26 (4/30): Last group of NP-Completeness reductions: 3-SAT to Hamiltonian Cycle, TSP, and Subset Sum.
Then, intro to approximation algorithms.
(Slides).
Lecture 27 (5/2): Approximation algorithms: scheduling and center selection.
Course wrap-up.
See the syllabus
for a tentative gameplan of upcoming material.
Final Exam (Wednesday, 5/8, 12:30 - 2:30 PM), in the normal final exam slot for classes in our time block.