CSPP 55005: Advanced Algorithms
Winter 2011


Homework 10 is posted
Textbook: Introduction to Algorithms (Third Edition) by Cormen et al. (ISBN: 0-262-03384-4) = CLRS

January 5: Lecture 1; MST algorithms; Data structures for disjoint sets; Readings: CLRS sections 21.1–24.3, chapter 23
January 12: Lecture 2; All-pairs shortest paths:; Floyd-Warshall algorithm; Johnson's algorithm; transitive closure; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 25
January 19: Lecture 3; Maximum flow:; Ford-Fulkerson method; maximum bipartite matching; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 26, sections 26.1–26.3
January 26: Lecture 4; Linear programming: simplex method; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 29, sections 29.1–29.3
February 9: Lecture 5; Linear programming: duality, zero-sum games; Hashing; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 29, sections 29.4–29.5; chapter 11
February 16: Lecture 6; Parallel algorithms; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 27
February 20: Lecture 7; Polynomials and FFT; 2:00–5:00 pm in Ryerson 276; Readings: CLRS chapter 30
February 23: Lecture 8; Red-black trees and B-trees; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapters 13 and 18
March 2: Lecture 9; NP-complete problems and approximation algorithms; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapters 34 and 35
March 9: Lecture 10; Approximation algorithms; Streaming algorithms; 5:30–8:30 pm in Ryerson 276; Readings: CLRS chapter 35; References for data streaming algorithms
March 13: Problem session; 12:00–2:00 pm in Ryerson 276

Organization

Instructors:
Janos Simon
Office hours: by appointment
Office: Ryerson 165
Email: simon at cs dot uchicago dot edu
Gerry Brady
Office hours: Monday and Tuesday 7:00–9:00 pm
Office: Ryerson 165A
Email: brady at cs dot uchicago dot edu
Teaching Assistant:
Eric Purdy
Email: purdy at cs dot uchicago dot edu
Office hours:
Tuesday 8:15–9:15 pm in Ryerson 162

brady at cs dot uchicago dot edu