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

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.


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.

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

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

HW2 due
Reading

Slides for Kleinberg-Tardos Chapter 7

Resources

CLRS Chapter 26.1, 26.2; Bo's lecture notes

7 Tue Sep 17

Max flow continued; bipartite matching

Reading

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

Resources

CLRS Chapter 26.1, 26.2, 26.3; R. Kleinberg lecture notes (very mathy, but fun advanced reading)

8 Thu Sep 19

Finish matchings and recap Module 1

HW3 due
Reading

Same as Tuesday

Module 2: Approximation, Online, and Randomized Algorithms