Info

BU Fall ’23 academic calendar

Lectures

• When:  Tue, Thu 9.30-10.45am
• Where:  COM-101

Instructor

• Prof: Babis Tsourakakis
  Email: ctsourak@bu.edu 
  Office hours (CDS 912):  Tu and Th 16.30-17.30

Teaching Assistants

• TF: Mr. Tiany Chen
  Email: ctony@bu.edu
  Office hours: M 15.30-17.00 (CDS 701), F 10-11.30am (CDS 801)
  
  
• TA: Mr. Kuangfei Long
  Email: kuangfei@bu.edu
  Office hours: Tu and Th 14.15-15.15 (CDS 1001)
  

Lab schedule

Github repo

Piazza website

Prerequisites

Students taking this class must have taken:

• CS 330 (undergraduate algorithms)

Syllabus

Examines advanced algorithmic topics and methods for MSc students, including matrix decomposition techniques and applications, fundamental discrete and continuous optimization methods, approximation and randomized algorithms, NP-completeness. A detailed syllabus is available here. Advanced BA students are also welcome. This class is designed in particular for MSc students (see also CS530).

Textbooks

We will be following closely the following textbooks as our guide:

1. Algorithm Design by Kleinberg and Tardos (KT book)
2. Introduction to Algorithms, fourth edition (CLRS)

We’ll also be using these other textbooks and notes:

• The Design and Analysis of Algorithms by Dexter Kozen
• Algorithms by Jeff Erickson (publicly available)
• Sariel Har-Peled’s notes (publicly available)

Programming

The class assumes familiarity with programming. Recommended language for this class is Python3. Other languages are also welcome (C, C++, Java, Julia etc).

Lectures

We will be using several slides from the official lecture slides that accompany the Kleinberg-Tardos from here.

1st week: Lectures 1 and 2 (9/5, 7) The Stable matching problem and the Gale-Shapley algorithm
Slides and Jupyter notebook (python) code
Readings

• KT book, Sections 1.1 and 2.3 and Kevin Wayne’s slides
• The original Gale-Shapley paper
• Wikipedia article “The Stable Marriage Problem”
• How two matchmakers won the Nobel Prize
• NYT article: The Stable marriage problem
• National Resident Matching Program, the matching algorithm (youtube video)
  

2nd week: Lectures 3 and 4 (9/12, 14) Priority Queues and Entropic Lower Bound
Slides and some Jupyter notebooks here and here
Readings

• KT book, Section 2.5
• Entropy and Counting (read pages 2-4) by Jaikumar Radhakrishnan

3rd Week: Lectures 5 and 6 (9/19, 21): Review loop invariants, bucket sort average case analysis, randomized quicksort
Slides and Jupyter notebook (python) here and here

Readings

• CLRS book, 5.3 Randomized algorithms, Chapter 7 Quicksort, 8.4 Bucket sort
  

4th Week: Lectures 7 and 8 (9/26, 28): randomized QS analysis via the recursion, median and order statistics
Slides

Readings

• CLRS book, Chapter 9 (Median and Order Statistics)
• Randomized Median Finding and Quicksort, notes by Goemans
• Manuel Blum on median finding in linear time (short youtube video)

Slides

Readings

• Chapter “Probabilistic Analysis and Randomized Algorithms” from CLRS
• Probability overview CLRS Appendix and Chapters 1-5 from “Introduction to Probability for Data Science” by Stanley
• Markov and Chebyshev’s inequalities
• Wikipedia article on the coupon collector problem
• Wikipedia article on Ramsey numbers
• Youtube video on visualizing the Monte Carlo algorithm for estimating π

6th and 7th Week: Lectures 11, 12, 13, 14 (10/10, 12, 17, 19): online hiring, introduction to probabilistic method, content resolution, Karger’s minimum cut algorithm
Annotated slides (slides by Kevin Wayne)

Readings

• Chapter “Probabilistic Analysis and Randomized Algorithms” from CLRS
• Chapters 13.1, 13.2, 13.3 from KT

 8th Week: Lectures 15 and 16 (10/24, 26): Chernoff bounds, Load Balancing, hashing, Bloom filters
– Chernoff bound slides
– Annotated slides (cont.)
– Nuts and Bolts of a Spell Checker

Readings

• Chapters 13.6, 13.9, 13.10 from KT
• Notes on Bloom filters
• Load balancing algorithms
• Optional reading : Consistent hashing

 10/31 Midterm

9th Week: Lectures 17 (11/2), 18 (7/11) and 19 (9/11): Greedy algorithms, loop invariant of narrowing the search space, job scheduling, minimum spanning tree
Slides available here and here
MST and Dijkstra here

Readings

• KT: 4.1, 4.2 (Lab), 4.4, 4.5, 4.6
• CLRS: Chapter 16.1, 16.2, 23

10th week: Lecture 20 (11/14): BFS and Dijkstra’s algorithm for single source shortest paths
Lecture 21 (11/16): Dynamic programming ( job scheduling, rod cutting)

Handwritten notes here (11/14)
Slides available here (11/16)

Readings

• CLRS 15.1, 16.1, 24.3 (Dijkstra’s algorithm)

11th week (Thanksgiving week): Lecture 22 (11/21): Dynamic programming cont.
Handwritten notes
Readings

• CLRS Chapter 15 (Dynamic programming)

12th week: Lecture 23 and 24 (11/28, 11/30): Dynamic programming practicing, Integer Programming, Linear Programming, Approximation algorithms, Knapsack problem (IP formulation, pseudopolynomial algorithm)
Handwritten notes

13th week: Lecture 25 and 26 (12/5, 12/7): Approximation algorithms (cont.)

Jupyter notebooks Max Cut, Vertex cover, Set Cover
Kevin Wayne’s Slides

Readings

• CLRS Chapter 35 (Approximation algorithms)
• KT Chapter 11

14th week: Lecture 12/12 Densest subgraph problem, max flow-min cut, approximation algorithm, LP relaxation.
Slides available here

Assignments

All the assignments and their solutions are available on Piazza.