CSCI 5454: Design and Analysis of Algorithms

Fall 2020

University of Colorado, Boulder



Instructor: Bo Waggoner
TA: Gabe Andrade

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

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 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