CSCI 5454: Design and Analysis of Algorithms

Fall 2021

University of Colorado, Boulder

Go to 2022 version

Go to Lecture notes and videos page

Instructor: Bo Waggoner
TAs: Gabe Andrade, Dhamma Kimpara

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

Course information and syllabus

News:

Midterm exam Tuesday, Oct 12. The modality is TBD, but we will have accommodations for remote or time conflicts.
Final exam Saturday, Dec 11, by 10pm. The modality is also TBD.

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

There will be no required textbook (readings will be posted or linked).

Course links:

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 24	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 26	Depth-first-search, 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 31	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 02	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 07	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 9	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 14	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 16	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 21	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 23	Intro to Online Algorithms	HW4 peer feedback
	Tasks	watch Lecture 7 videos read Lecture 7 notes
	Resources	Avrim Blum's lecture notes

11	Tue Sep 28	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 30	Randomized Algorithms - Part 2	HW5 peer feedback
	Tasks	watch Lecture 8 videos - Sections 4-5 read Lecture 8 notes - Sections 4-5

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

14	Thu Oct 07	Recap day	HW6 peer feedback

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

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

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

18	Thu Oct 21	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 26	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 28	Random Walks on Graphs - Part 3	HW7 peer feedback
	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 02	Johnson-Lindenstrauss Transform	HW8 due; HW9 assigned
	Tasks	watch Lecture 12 videos read Lecture 12 notes

22	Thu Nov 4	Singular Value Decomposition
	Tasks	watch Lecture 13 videos read Blum, Hopcroft, Kannan Ch. 3.1 - 3.5

23	Tue Nov 9	Singular Value Decomposition (continued)

24	Thu Nov 11	Polynomial Weights	HW9 due; HW10 assigned
	Tasks	read Penn notes on polynomial weights (skip first page) (no video assignment)

25	Tue Nov 16	Zero-Sum Games and the Minimax Theorem
	Tasks	Penn notes on zero-sum games (no video assignment)
	Resources	Arora, Hazan, Kale survey on multiplicative weights

26	Thu Nov 18	Zero-Sum Games (continued)	HW10 due

27	Tue Nov 29	Linear Programming Part 1	HW11 assigned
	Resources	Prof. Erickson's LP notes (section H.3 onward)

28	Thu Dec 02	Linear Programming Part 2

29	Tue Dec 07	Review day	HW11 due

	Thu Dec 09	No class - final exam!

	Sat Dec 11, 10pm	Final exam closes, 10:00pm