Lecture meeting time: Tues/Thurs 11 - 12:30,
Lab meeting times:   Mon 11-12 (GCB 201), Mon 12-1 (CAS 233) and Mon 3-4 PM (CAS 323B).
Prof. John W. Byers
Email (preferred): byers @ cs . bu . edu
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).
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.