CSCI 5454: Design and Analysis of Algorithms

Fall 2020

University of Colorado, Boulder

---

Go to 2021 version

Go to Lecture notes and videos page

---

Instructor: Bo Waggoner
TA: Gabe Andrade

Time: Tues/Thurs 11:10am - 12:25pm

Course information and syllabus

News:

• (Sep 1) Office hours from now on: Mondays 4pm - 5:30pm; Wednesdays 10am - 11am; Fridays 11am - 12:30pm.
• COVID-19 announcement: We plan to make the class accessible for students in as many situations and time zones as possible. Expect asynchronous, recorded lectures and reading assignments, along with synchronous problem-solving sessions at the scheduled class time.

---

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:

• Canvas: download homeworks and solutions
• Piazza: questions and discussion
• Homework LaTeX template and LaTeX algorithm examples (optional)
• Final project overview

The course does not have a required textbook. Resources:

• (Required) Lecture videos and notes, as assigned below (Collected videos and notes page)
• (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 25	Intro: word-RAM model, big-O notation	HW1 posted
	Tasks	read syllabus watch Lecture 1 videos read Lecture 1 notes sign up for Piazza
Module 1: Combinatorial and Graph Algorithms
2	Thu Aug 27	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 Sep 01	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 03	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 08	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 10	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 15	Max Flow - Part 2	HW3 due
	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 17	Max Flow - Part 3	Quiz 1
	Tasks	watch Lecture 5 videos - Sections 4-5 read Lecture 5 notes - Sections 4-5
	Resources	in-class exercises
Module 2: Approximation, Online, and Randomized Algorithms
9	Tue Sep 22	Intro to Approximation Algorithms	HW4 assigned
	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 24	Intro to Online Algorithms
	Tasks	watch Lecture 7 videos read Lecture 7 notes
	Resources	Avrim Blum's lecture notes
11	Tue Sep 29	Randomized Algorithms - Part 1	HW4 due; HW5 assigned
	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 01	Randomized Algorithms - Part 2
	Tasks	watch Lecture 8 videos - Sections 4-5 read Lecture 8 notes - Sections 4-5
13	Tue Oct 06	Randomized Algorithms - Part 3	HW5 due
	Tasks	watch Lecture 8 videos - Section 6 read Lecture 8 notes - Section 6
14	Thu Oct 08	Recap day	Quiz 2
15	Tue Oct 13	Project discussion
	Resources	Final project overview
16	Thu Oct 15	Hash Tables	HW6 assigned
	Tasks	watch Lecture 9 videos read Prof. Clauset's hash table notes
17	Tue Oct 20	Streaming Algorithms
	Tasks	watch Lecture 10 videos read Prof. Jeff Erickson's lecture notes (through Section 6.4)
Module 3: Continuous, Linear, and Convex Methods
18	Thu Oct 22	Random Walks on Graphs - Part 1	Project proposals due
	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 27	Random Walks on Graphs - Part 2	HW6 due HW7 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 29	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 03	No class - voting day in U.S.	HW7 due tomorrow
22	Thu Nov 05	Johnson-Lindenstrauss Transform	HW8 assigned
	Tasks	watch Lecture 12 videos read Lecture 12 notes
23	Tue Nov 10	Singular Value Decomposition
	Tasks	watch Lecture 13 videos read Blum, Hopcroft, Kannan Ch. 3.1 - 3.5
24	Thu Nov 12	Polynomial Weights	Quiz 3
	Tasks	read Penn notes on polynomial weights (skip first page) (no video assignment)
25	Tue Nov 17	Zero-Sum Games and the Minimax Theorem	HW8 due HW9 assigned
	Tasks	Penn notes on zero-sum games (no video assignment)
	Resources	Arora, Hazan, Kale survey on multiplicative weights
26	Thu Nov 19	Linear Programming Part 1
	Tasks	Prof. Erickson's LP notes (through section H.3)
27	Tue Nov 24	Linear Programming Part 2	HW9 due project update due HW10 assigned
	Resources	Prof. Erickson's LP notes (section H.4 onward)
28	Tue Dec 01	Project Presentations
29	Thu Dec 03	Project Presentations	Quiz 4
	Mon Dec 7	HW10 due
	Fri Dec 11	Final project writeup due, 7:00pm

---