CSCI 5454: Design and Analysis of Algorithms

Fall 2021

University of Colorado, Boulder



Instructor: Bo Waggoner
TAs: Gabe Andrade, Dhamma Kimpara

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

Course information and syllabus



News:


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:

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