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