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