CS675

CMPUT 498/501: Advanced Algorithms

Instructor	Mohammad R. Salavatipour
Lectures	MW 11:00-12:20
Office hours	Mondays 1:00-2:00, U-Comm 6-237

Topics and outcome:

This is a new course that will cover topics in Advanced Algorithms in Theoretical Computer Science (TCS), targeted for senior undergraduate and graduate students interested in TCS. The tentative list of topics to be covered in this course are listed below. We cover some classic topics and more recent advances with applications in other areas: streaming and sketching algorithms for big data, online and randomized algorithms, and approximation algorithms.

Tentative topics (could change later):

Module 1: Classics (Greedy and Dynamic Programming)

Stable matching, Interval scheduling,

Weighted Interval Scheduling, Segmented least Squares,

Advanced DP

Minimum Spanning Trees and Arborescences

Module 2: Randomized Algorithms

Simple deviation bounds, Randomized Min-Cut
Chernoff bound, Hypercube routing,
Randomized load balancing, Hashing
Balls and bins, power of two choices,
Random Walks in Graphs

Module 3: Linear Programming and Combinatorial Optimization

Integer/Linear Programming, Duality, Integrality gap
Matchings, matching polytope

Module 4: Approximation Algorithms

Vertex/Set cover, LP rounding
Knapsack, Bin Packing
Max-Sat
Max-Cut

Module 5: Streaming and Sketching

Probabilistic Counting
Frequency moments, Distinct elements estimation
Sketching

Module 6: Online Algorithms, Learning from experts

Online algorithms, Ski rental, paging
Secretary problem,
Learning from experts, Multiplicative Weight Update

Outcome:

By the end of this course you should have a basic knowledge of some of the basic techniques used in TCS in design and analysis of algorithms.
You should also learn some tools and tricks to tackle problems that might arise in different settings (such as online setting, streaming setting, or interactable/hard to solve optimization problems).

Prerequisites:

CMPUT204 and MATH125 or MATH225. Also CMPUT 304 is strongly recommended. In general strong undergraduate background in theoretical computer science and mathematics would be required. You must also have basic knowledge of graph theory, basic probability, and complexity theory.

Grading Scheme and course policies.

This is a theory course (no programming involved).

Homework assignments (5 assignments, for undergraduates 12% each, for graduate students 10% each)
Final exam (to be scheduled): 40%
For graduate students: Preparing scribed notes in Latex for 2 lectures (can work in groups of 2): 10%

Note: In order to pass the course you need to obtain at least 50% overall AND at least 40% on your final exam.

Read the detailed policies here carefully!

Lectures:
See the list of resources further down for extra references listed for each lecture below.

Greedy, Dynamic Programming:

Lecture 1: Introduction, Stable Matching, Interval Scheduling, Minimizing lateness, Weighted Interval Scheduling
Here are the handwritte notes, and here is the scribed note.
Also see sections 1.1, 4.1, 4.2, 6.1 (KT), and slides for Chapter 1, 4 and 6 by (KW)
Lecture 2: Segmented Least Square, Sequence Alignments, BST
Here are the notes,
Also see sections 6.3, 6.6, 6.6 in (KT), and slides for Chapter 6 by (KW),
extra notes for Advanced algorithms by (JE), and this survey paper.
Lecture 3: Advanced DP: Saving time using monotonicity, SMWAK
Here are the notes,
extra notes for Advanced algorithms by (JE), and this survey paper.

Minimum Spanning Tree, Minimum Arborescence:

Lecture 4: Minimum Spanning Tree (MST), Fredman-Tarjan Algorithm
Here are the notes,
Also see 1.1-1.3 from (AG) combined notes and Lec 6 by (SA).

Lecture 5: MST in linear time, Minimum Arborescence
Here are the notes,
Also 1.4-1.5 from (AG) and Lec 7 by (SA); and 4.9 from (KT).

Randomized Algrithms:

Lecture 6: Introduction, simple deviation bounds.
Here are the notes,
Also, lecture 1-3 from (RA).
Lecture 7: Chernoff bound, Hypercube routing
Here are the notes,
Also Lecture 5 from (RA), and Chapter 10 by (AG).

Lecture 8: Balls and Bins, power of two choices
Here are the notes,
Also Lecture 7 from (RA), Lec 5 from (SA), GuptaS21 Lec6

Lecture 9: Randomized load balancing, Hashing
Here are the notes,
Also lecture 16 from (RA), Lec 3 from (SA) and, notes 5 from (JE).

Lecture 10: Random Walks, resistence graph
Here are the notes,
Also, Lecturse 12 and 13 from (RA), Chapter 6 from (MR), Lec 23 from (SA)

Lecture 11: Finger printing, Polynomial identity testing
Here are the notes,
Also Lecture 13 from (RA), Lecture 16 from (SA) and Chapter 7 from (MR)

Integer/Linear Programming and Combinatorial Optimization:

Lecture 12: Integer/Linear Programming, Duality
Here are the notes,
Also see Lec 6 and 7 from (CO) and Lec 8 by (SA)
Lecture 13: Bipartite Matching, Matching polytope
Here are the notes,
Also see ....
Lecture 14: Weighted Biparite Matching
Here are the notes,
Also see .....
Lecture 15: More on Matching
Here are the notes,
Also see ...

Approximation Algorithms

Streaming and Sketching

Online Algorithms, Learning From Experts

Assignments:

Assignments will be posted on Canvas and submitted there as well.

	posted	Due date
Assignment 1	Sept 17	Oct 1
Assignment 2	Oct 6	Oct 20
Assignment 3	Oct 20	Nov 3
Assignment 4	Nov 5	Nov 19
Assignment 5	Nov 26	Dec 10

Templates

Here is a Latex Template file for preparing assignments and/or lecture notes (here is how it looks when compiled).
Here is the style file you may need to compile it.

You can use Overleaf, an excellent online Latex editor/compiler to write your Latex documents and compile it.
It also has many templates with the source to learn various tricks in using Latex.

Resources:

There is no textbook for this course. However, we will use parts of several books and/or lecture notes from other courses offered by the instructor or
similar course offerings in other universities. We will provide lecture (whiteboard) notes as well as links to relevant readings.
The following is a list of most commonly referred to references:

(KT) J. Kleinberg and E. Tardos, Algorithm Design, 2006 and (KW) Lecture slides by Kevin Wayne for this book.
(JE) J. Erickson, Algorithms Textbook, available (free) here.
(MR) R. Motwani and P. Raghavan,Randomized Algorithms (free access), Cambridge University Press, 2013
(V) V. Vazirani, Approximation Algorithms, available free (also from authors here), Springer-Verlag, Berlin, 2001.
(WS) D. Willamson and D. Shmoys, The Design of Approximation Algorithms, (free download), Cambridge University Press, 2011
A. Blum, J. Hopcroft, and R. Kannan, Foundations of Data Science, available here.

Here are links to offerings of similar courses by other colleagues:

(AG) Advanced Algorithms, by Anupam Gupta at CMU (Fall 2020); Here is a combined lecture notes.
(SA) Algorithm Design and Analysis, by Sepehr Assadi at Waterloo (Fall 2023).
Graduate Algorithms, by Anupam Gupta and Rashmi Vinayak at CMU (Spring 2021).
(RA) Randomized Algorithms, Fall 2005.
(AP) Approximation Algorithms, Winter 2018.
(AS) Algorithms for Streaming and Big Data, Fall 2019.
Advanced Algorithms, by Jonathan Ullman at NEU (Fall 2022).
Algorithms for Big Data, by Chandra Chekuri at UIUC (Fall 2022).
Topics in Algorithms and Combinatorial Optimization, Fall 2009.
Advanced Algorithm Design, by Pravesh Kothari and Christopher Musco at Princeton (Fall 2018).