CSCI 5454: Design and Analysis of Algorithms

Fall 2023

University of Colorado, Boulder

Instructor: Bo Waggoner
TAs: Dhamma Kimpara, Maneesha Papireddygari

Time: Tues/Thurs 9:30am - 10:45am, ECCS 1B28 and online

Course information and syllabus

Overview

This graduate-level course will survey a variety of approaches to designing and rigorously analyzing efficient algorithms. Topics include: combinatorial and graph algorithms; randomized, online, and approximation algorithms; and continuous convex or linear-algebra based methods.

Links and Resources

Course links:

Canvas: Zoom link, download homeworks and solutions
Zulip: questions and discussion (signup link on Canvas)
Gradescope: submitting assignments

The course does not have a required textbook. Resources:

(Required) Lecture videos and notes, as assigned below (Collected videos and notes page)
(Useful) Homework LaTeX template and LaTeX algorithm examples
(Supplement) Algorithms ("DPV") by Dasgupta, Papadimitriou, and Vazirani (can be found online for free)
(Supplement) Algorithms and lecture notes by Jeff Erickson
(Supplement) Algorithm Design and lecture slides by Kleinberg and Tardos.

Schedule


1	Tue Aug 29	Intro: word-RAM model, big-O notation	HW01 posted
	Tasks	read syllabus watch Lecture 1 videos read Lecture 1 notes sign up for Zulip
Module 1: Combinatorial and Graph Algorithms

2	Thu Aug 31	DFS and topological sort
	Tasks	watch Lecture 2 videos read Lecture 2 notes
	Resources	Slides from Kleinberg-Tardos Chapter 3; DPV Chapter 3; Erickson Chapter 5 Section 5.2, 5.4, 5.5, 5.6; and Chapter 6 up through 6.4

3	Tue Sep 05	Shortest Paths on Graphs	HW01 due; HW02 posted
	Tasks	watch Lecture 3 videos read Lecture 3 notes
	Resources	DPV Chapter 4; Erickson Chapter 8 (skip Section 8.5)

4	Thu Sep 07	Dynamic Programming - Part 1
	Tasks	watch Lecture 4 videos - Sections 1-3 read Lecture 4 notes - Sections 1-3
	Resources	DPV Chapter 6.1, 6.2, 6.3; Erickson Chapter 3.7

5	Tue Sep 12	Dynamic Programming - Part 2	HW02 due; HW03 posted
	Tasks	watch Lecture 4 videos - Sections 4-6 read Lecture 4 notes - Sections 4-6
	Resources	Bo's knapsack notes; DPV Chapter 6.4, 6.6

6	Thu Sep 14	Max Flow - Part 1
	Tasks	watch Lecture 5 videos - Sections 1 - 2 read Lecture 5 notes - Sections 1 - 2
	Resources	Slides for Kleinberg-Tardos Chapter 7

7	Tue Sep 19	Max Flow - Part 2	HW03 due; HW04 posted
	Tasks	watch Lecture 5 videos - Section 3 read Lecture 5 notes - Section 3
	Resources	Erickson Chapter 10.1 - 10.4; advanced, bonus reading: R. Kleinberg lecture notes

8	Thu Sep 21	Max Flow - Part 3
	Tasks	watch Lecture 5 videos - Sections 4-5 read Lecture 5 notes - Sections 4-5
Module 2: Approximation, Online, and Randomized Algorithms

9	Tue Sep 26	Intro to Approximation Algorithms	HW04 due; HW05 posted
	Tasks	watch Lecture 6 videos read Lecture 6 notes
	Resources	Kleinberg-Tardos approx algs slides (through slide 16), Erickson approx algs notes

10	Thu Sep 28	Intro to Online Algorithms
	Tasks	watch Lecture 7 videos read Lecture 7 notes
	Resources	Avrim Blum's lecture notes

11	Tue Oct 3	Randomized Algorithms - Part 1	HW05 due; HW06 posted
	Tasks	watch Lecture 8 videos - Sections 1-3 read Lecture 8 notes - Sections 1-3
	Resources	Peter Cameron probability book Chapter 1.1, 1.2, 1.3, 1.10, and optionally 1.4.

12	Thu Oct 5	Randomized Algorithms - Part 2
	Tasks	watch Lecture 8 videos - Sections 4-5 read Lecture 8 notes - Sections 4-5

13	Tue Oct 10	Randomized Algorithms - Part 3	HW06 due
	Tasks	watch Lecture 8 videos - Section 6 read Lecture 8 notes - Section 6

14	Thu Oct 12	Review day

15	Tue Oct 17	Hash Tables
	Tasks	watch Lecture 9 videos read Lecture 9 notes

16	Thu Oct 19		No class; exam time (at home)

17	Tue Oct 24	Streaming Algorithms
	Tasks	watch Lecture 10 videos read Lecture 10 notes
Module 3: Continuous, Linear, and Convex Methods

18	Thu Oct 26	Random Walks on Graphs - Part 1
	Tasks	watch Lecture 11 videos - Sections 1 and 2 read Lecture 11 notes - Sections 1 and 2
	Resources	Linear algebra review notes (Sections 1,2,3)

19	Tue Oct 31	Random Walks on Graphs - Part 2	HW07 due HW08 assigned
	Tasks	watch Lecture 11 videos - Sections 3 and 4 read Lecture 11 notes - Sections 3 and 4
	Resources	The Anatomy of a Large-Scale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page

20	Thu Nov 2	Random Walks on Graphs - Part 3
	Tasks	watch Lecture 11 videos - Section 5 read Lecture 11 notes - Section 5
	Resources	Blum, Hopcroft, Kannan book Ch 4 up through 4.2

21	Tue Nov 7	Johnson-Lindenstrauss Transform	HW08 due HW09 assigned
	Tasks	watch Lecture 12 videos read Lecture 12 notes

22	Thu Nov 9	Singular Value Decomposition
	Tasks	watch Lecture 13 videos read Lecture 13 notes
	Resources	Blum, Hopcroft, Kannan book Ch 3.1 - 3.5

23	Tue Nov 14	Online No-Regret Learning	HW09 due, HW10 assigned
	Tasks	read Lecture 14 notes (no video assignment)

24	Thu Nov 16	Zero-Sum Games and the Minimax Theorem
	Tasks	read Lecture 15 notes (no video assignment)
	Resources	Arora, Hazan, Kale survey on multiplicative weights

	Nov 21-23	(Fall break)

25	Tue Nov 28	Zero-Sum Games (continued) and Linear Programming (Part 1)
	Tasks	read Lecture 16 notes, Sections 1-3 (no video assignment)
	Resources	Prof. Erickson's LP notes (section H.3 onward)

26	Thu Nov 30	Linear Programming (Part 1 and/or 2)	HW10 due; HW11 assigned
	Tasks	read Lecture 16 notes, Sections 1-3 (no video assignment)

27	Tue Dec 5	Linear Programming (Part 2)
	Tasks	read Lecture 16 notes, Sections 4-5 (no video assignment)

28	Thu Dec 7	Review or special topics day	HW11 due

29	Tue Dec 12	Special topic day - Quantum computing	Final exam released
	Resources	Prof. Aaronson's Quantum Computing notes

30	Thu Dec 14	No class - final exam!

	Sat Dec 16	Final exam due (online): 4pm