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 2^{n} 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 | |

Finals Week |
Dec. 8 | Homework 4 due |