CS 704 Analysis of Algorithms

Spring 2008
MW 5:30-6:45pm, PHY 120
Instructor: Christine Cheng
EMS 1045 x5170

Syllabus of the course.

• 1/23/08: The stable matching problem. (Sec. 1.1).
  
  
• 1/28/08: Basics of algorithm analysis. (Sec. 2.1, 2.2).
  
  
• 1/30/08: Implementing the stable matching algorithm (Sec. 2.3). Intro to greedy algorithms. (Sections 4.1, 4.2).
  HW 1. Due on 2/13 (W).
  
  
• 2/4/08: Greedy algorithms cont'd.
  
  
• 2/11/08: Divide-and-conquer algorithms (Sec. 5.1, 5.2).
  
  
• 2/13/08: Divide-and-conquer algorithms cont'd. (Sec. 5.3 - 5.5).
  HW 2. Due on 2/27 (W).
  
  
• 2/18/08: Dynamic Programming (Sec. 6.1, 6.2, 6.4).
  
  
• 2/20/08: Dynamic Programming cont'd (Sec. 6.6), exercises.
  
  
• 2/25/08: HW 1 discussed. Intro to graphs (Sec. 3.1, 3.2).
  
  
• 2/27/08: Intro to graphs cont'd. (Sec. 3.2). Dijkstra's algorithm (Sec. 4.4).
  HW 3. Due on 3/12 (W).
  
  
• 3/3/08: Dynamic Programming and shortest paths (Sec. 6.8 -- 6.10). Intro to network flows.
  
  
• 3/5/08: Network flows cont'd.
  
  
• 3/10/08: The max flow-min cut theorem. HW 2 discussed.
  
  
• 3/12/08: HW 3 discussed.
  
  
• Midterms is scheduled for 3/24 (M). Coverage. Sample Exam. (Note: Network Flows was not part of the midterms.
  
  
• 3/26/08: Exam discussed. Finding good augmenting paths (Sec. 7.3).
  
  
• 3/31/08: Applications of max-flows.
  HW 4. Due on 4/14 (M).
  
  
• 4/2/08: Applications of max-flows cont'd.
  
  
• 4/7/08: Intro to randomized algorithms (Sec. 13.1, 13.3, 13.4).
  
  
• 4/9/08: Randomized algorithms cont'd.
  
  
• 4/14/08: Intro to NP-completeness.
  
  
• 4/16/08: Examples of polynomial reducibility.
  HW 5. Due on 4/30 (W).
  
  
• 4/21/08: More NP-completeness.
  
  
• 4/23/08: NP-completeness and sequencing problems.
  For Monotone Satisfiability with Few True Variables, the question should be: given a monotone instance of satisfiability (note that there is no constraint on the clause size here), together with a number m, is there a satisfying assignment for the instance in which at most m variables are set to 1?. That is, as Brad raised in class, the number of variables to be set to true should not have any relation at all to the number of clauses in the instance.
  
  
• 4/28/08: NP-completeness and partition problems.
  
  
• 4/30/08: NP-completeness and numerical problems.
  
  
• 5/5/08: The independence set problem on trees, an FPT algorithm for vertex cover.
  
  
• 5/7/08: An FPT algorithm for finding a forcing partial assignment. Final comments.
  
  
• FINALS is scheduled for 5/14 (Wed) from 5:30-7:30pm. Coverage. Sample Exam.