CSCI 5454: Design and Analysis of Algorithms

Fall 2022

University of Colorado, Boulder

Instructor: Bo Waggoner
TAs: Vimal Kakaraparthi, Anish Thilagar

Time: Tues/Thurs 8:00am - 9:15am, ECCS 1B12 and online

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 23	Intro: word-RAM model, big-O notation	HW1 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 25	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 Aug 30	Shortest Paths on Graphs	HW1 due; HW2 posted
	Tasks	watch Lecture 3 videos read Lecture 3 notes
	Resources	DPV Chapter 4; Erickson Chapter 8 (skip Section 8.5)

4	Thu Sep 01	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 06	Dynamic Programming - Part 2	HW2 due; HW3 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 08	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 13	Max Flow - Part 2	HW3 due; HW4 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 15	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 20	Intro to Approximation Algorithms	HW4 due; HW5 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 22	Intro to Online Algorithms
	Tasks	watch Lecture 7 videos read Lecture 7 notes
	Resources	Avrim Blum's lecture notes

11	Tue Sep 27	Randomized Algorithms - Part 1	HW5 due; HW6 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 Sep 29	Randomized Algorithms - Part 2
	Tasks	watch Lecture 8 videos - Sections 4-5 read Lecture 8 notes - Sections 4-5

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

14	Thu Oct 06	Recap day

15	Tue Oct 11	No class; exam time (at home)

16	Thu Oct 13	Hash Tables	HW7 assigned
	Tasks	watch Lecture 9 videos read Lecture 9 notes

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

18	Thu Oct 20	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 25	Random Walks on Graphs - Part 2	HW7 due HW8 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 Oct 27	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 01	Johnson-Lindenstrauss Transform	HW9 assigned
	Tasks	watch Lecture 12 videos read Lecture 12 notes

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

23	Tue Nov 8	Dimensionality Reduction continued

24	Thu Nov 10	Online No-Regret Learning	HW9 due, HW10 assigned
	Tasks	read Lecture 14 notes (no video assignment)

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

26	Thu Nov 18	Zero-Sum Games continued

	Nov 22-24	(Fall break)

27	Tue Nov 29	Linear Programming Part 1	HW10 due; HW11 assigned
	Tasks	read Lecture 16 notes, Sections 1-3 (no video assignment)
	Resources	Prof. Erickson's LP notes (section H.3 onward)

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

29	Tue Dec 06	Review day	HW11 due

30	Thu Dec 08	No class - final exam!

	Sat Dec 10	Final exam due (online): 10pm