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

---