CSCI 5454: Design and Analysis of Algorithms

Fall 2019

University of Colorado, Boulder



Instructor: Bo Waggoner
TA: Charlie Carlson

Time: Tues/Thurs 11:00am - 12:15pm
Room: ECCR 150 (and recorded/streamed)

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.


Resources and Links

The course does not have a required textbook. Readings will be posted or linked. We will start out with some readings from Algorithms by Dasgupta, Papadimitriou, and Vazirani (DPV), which can be found online for free.

Bespoke lecture notes (does not cover all topics, see schedule!):

Prof. Bo's office hours: Friday 11-noon, ECES 136

TA Charlie's office hours: Tuesday, Wednesday 12:30 - 1:30pm, ECAE 124


Schedule

1 Tue, Aug 27

Intro: word RAM model, big-O, stable matching problem

HW1 posted
Resources Bo's lecture notes: course intro, word-RAM, big-O; notes on stable matching (only up through proof of Theorem 4 / middle of page 2); Kleinberg-Tardos slides
Module 1: Combinatorial and Graph Algorithms
2 Thu, Aug 29

Depth-first search, directed acyclic graphs, topological sort

Reading

Course syllabus; Dasgupta, Papadimitriou, Vazirani (DPV) Chapter 3

Resources

Bo's lecture notes: depth-first search and topological sort formalizing proofs from lecture; Slides from Kleinberg-Tardos Chapter 3; Erickson Chapter 5 Section 5.2, 5.4, 5.5, 5.6; and Chapter 6 up through 6.4

3 Tue, Sep 3

Breadth-first search, Dijkstra's, Bellman-Ford

HW2 posted
Reading

DPV Chapter 4

Resources

Erickson Chapter 8 (skip Section 8.5)

; CLRS Chapter 24
4 Thu Sep 05

Dynamic programming (1)

HW 1 due
Reading

DPV Chapter 6.1, 6.2, 6.3

Resources

Erickson Chapter 3.7

5 Tue Sep 10

Dynamic programming (2)

Reading

DPV Chapter 6.4, 6.6

6 Thu Sep 12

Flows and cuts

HW 2 due
Reading

Slides for Kleinberg-Tardos Chapter 7

Resources

CLRS Chapter 26.1, 26.2; Bo's lecture notes: flows and cuts

7 Tue Sep 17

Max flow continued; bipartite matching

Reading

Kleinberg-Tardos Network Flow 2 slides (only first four pages); Bo's lecture notes: flows and cuts

Resources

Erickson Chapter 10.1 - 10.4; optionally R. Kleinberg lecture notes (advanced bonus reading)

8 Thu Sep 19

Finish matchings and recap Module 1

HW 3 due
Reading

Same as Tuesday

Module 2: Approximation, Online, and Randomized Algorithms
9 Tue Sep 24

Intro to Approximation Algorithms

Reading

Kleinberg-Tardos slides on approx algs up through slide 16 (fourth page)

Resources

Bo's lecture notes: approximation algs; Jeff Erickson's approximation algs notes

10 Thu Sep 26

Intro to Online Algorithms

HW 4 due
Reading

Avrim Blum lecture notes (Section 22.4 optional)

Resources

Bo's lecture notes: online algs

11 Tue Oct 01

Bin Packing; Intro to Randomized Algorithms

Notify of midterm conflicts
Reading

Peter Cameron Probability book Chapter 1.1, 1.2, 1.3, and 1.10 (optionally, 1.4); review Bo's lecture notes: online algs

Resources

Bo's lecture notes: rough probability review, randomized algs

12 Thu Oct 03

Randomized Algorithms, continued (Max-3SAT, Min-Wt Vertex Cover)

HW5 due
Reading

Kleinberg-Tados slides through slide 30 (page 8); skip contention resolution, guessing cards, and coupon collector sections

Resources

Bo's lecture notes: rough probability review, randomized algs

13 Tue Oct 08

Randomized Algorithms, continued (Min-Wt Vertex Cover, Min cut)

Reading

Bo's lecture notes: randomized algs; rescan last Thurs' reading

14 Thu Oct 10

Randomized and Online Algorithms

HW6 due
Reading

(none)

Resources

"Online Bipartite Matching Made Simple" by Birnbaum and Mathieu

15 Tue Oct 15

Midterm practice day

16 Thu Oct 17

Midterm Exam

17 Tue Oct 22

Data Structures and Streaming: Hash Tables

Reading

Aaron Clauset's lecture notes

18 Thu Oct 24

Data Structures and Streaming: Bloom Filters

Reading

Jeff Erickson's lecture notes (read through 6.3)

Module 3: Continuous, Linear, and Convex Methods
19 Tue Oct 29

Adjacency Matrices and Random Walks

Reading

The Anatomy of a Large-Scale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page

Resources

Linear Algebra Review (notes: sections 1,2,3)

20 Thu Oct 31

Random Walks cont'd, Markov Chain Monte Carlo

HW7 due
Reading

Blum, Hopcroft, Kannan book Ch. 4 up through 4.2

Resources

Bo's lecture notes: random walks

21 Tue Nov 05

Dimensionality reduction: Singular Value Decomposition

Reading

Blum, Hopcroft, Kannan book Chapter 3.1 - 3.5

22 Thu Nov 07

Dimensionality reduction continued: Johnson-Lindenstrauss transform

Resources

Bo's lecture notes on JL

23 Tue Nov 12

Convex Optimization: Gradient Descent

Reading

Tibshirani slides #3-20

Resources

Boyd and Vandenberghe book Ch 3.1.1; Figure 3.2; Ch 3.1.3, 3.1.4; Ch 9.1-9.3

24 Thu Nov 14

Online Convex Optimization: Polynomial Weights

HW8 due
Reading

Penn lecture notes (skip the first page!)

25 Tue Nov 19

Zero-Sum Games and the Minimax Theorem

Resources

Penn lecture notes

26 Thu Nov 21

(Online) Convex Optimization and Minmax

HW9 due Friday

Reading

Shalev-Shwartz monograph Chapter 2.0, 2.3, and 2.4

27 Tue Dec 03

Online Convex Optimization

Reading

(previous reading)

28 Thu Dec 05

Intro to Linear Programming

HW10 due Sun.
Reading

Jeff Erickson's notes (read through Section H.3)

29 Tue Dec 10

Linear Programming Applications

30 Thu Dec 12

Review day

HW11 due Sat.