ICS Theory Group

ICS 280, Fall 2000: Exponential Algorithms
Lecture Schedule and Homework Assignments

Week 1 Sep. 26 Why exponential algorithms?
Sep. 28 Constraint satisfaction problems
Week 2 Oct. 3 Problem transformation and NP-completeness
Oct. 5 Other standard NP-complete problems: maximum independent set and traveling salesman problem
Week 3 Oct. 9 Homework 1 due
Oct. 10 Generate and test
Oct. 12 Randomized and derandomized generate and test
Week 4 Oct. 17 Backtracking: simple 2n 3-coloring algorithm; listing all maximal independent sets
Oct. 19 Solving recurrences; enumeration of cases (proof by exhaustion)
Week 5 Oct. 23 Homework 2 due
Oct. 24 Simple randomized (3,2)-CSP algorithm and its derandomization
Oct. 26 Feder and Motwani's randomized (k,2)-CSP algorithm
Week 6 Oct. 31 TSP: dynamic programming, comparison to branch and bound / polyhedral combinatorics approach
Nov. 2 Dynamic programming for graph coloring
Week 7 Nov. 7 Mixing dynamic programming with backtracking
Nov. 9 Pathwidth and faster dynamic programming for special graph classes
Week 8 Nov. 13 Homework 3 due
Nov. 14 No class (away at FOCS 2000)
Nov. 16 Pathwidth and treewidth of planar graphs
Week 9 Nov. 21 Schöning's random-restart hill-climbing k-SAT algorithm
Nov. 23 No class (thanksgiving)
Week 10 Nov. 28 Quantum computation and quantum circuits
Nov. 30 Grover's algorithm for quantum generate-and-test
Dec. 8 Homework 4 due