CSE 202: Design and Analysis of Algorithms; Fall 2007

Professor: Ramamohan Paturi (4246 EBU3B)

Teaching Assistant: Peng Du

Announcements:

Course information

Syllabus, Course Organization, Teaching Assistants and Office Hours

Problem sets

• Problem set 1: Mathematical preliminaries and divide and conquer:
• Problem set 2: Divide and conquer and sorting: PostScript, PDF
• Problem set 3: Dynamic programming and greedy method: PostScript, PDF
• Problem set 4: Fast Fourier Transform: PostScript, PDF
• Problem set 5: String Matching: PostScript, PDF
• Problem set 6: Graph Algorithms: PostScript, PDF
• Problem set 7: NP-completeness and Approximation Algorithms: PostScript, PDF

Sample solutions

• Solution set 1: Mathematical preliminaries and divide and conquer: PostScript, PDF
• Solution set 2: Sorting PostScript, PDF
• Solution set 3: Dynamic programming and greedy method PostScript, PDF
• Solutions for sample problems in flows and approximation algorithms: Set 1; Set 2;

Homeworks

• Homework I: Problems 4, 5 and 7 from Kleinberg and Tardos (pages 247-249).
  Due October 18th, 10 AM, outside my office EBU3B 4246
• Homework II: Problems 16 and 19 from Kleinberg and Tardo (pages 196-198) as well as problems 14, 19, and 25 (pages 312-335).
  Due November 2nd, 10 AM, outside my office EBU3B 4246
• Homework III: Problems 8, 39, 41, and 45 (pages 415-448)
  Due November 26th, 2007, 3:30 PM in class
  Additional Problems on Flow: 16, 20, 26, 34, and 46
• Homework IV: Problems 4, 7, and 11 (pages 651-659)
  Due December 12th, 2007, 3PM.

Sample mid-term

Sample final. Final exam from 2006.

Take-Home Final

Final version
Deadline: 3:00 PM, December 14th, 2007.