CS 535-001 Algorithm Design and Analysis

Fall 2009
MW 9:30 - 10:45 am, EMS E145
Instructor: Christine Cheng
EMS 1011, 414.229.5170

Syllabus of the course.

Schedule

• 9/02/09: Math review.
  
  
• 9/09/09: Framework for analyzing algorithms (Sec. 1.1). Asymptotic notation (Sec. 1.2).
  Homework 1 , due September 16 (W).
  
  
• 9/14/09: Asymptotic notation cont'd. Designing algorithms (Maximum subsequence sum problem) (Sec. 1.4).
  
  
• 9/16/09: Designing algorithms cont'd (Stable Matching problem).
  Homework 2 , due September 23 (W).
  
  
• 9/21/09: Proof of correctness of the Gale-Shapley algorithm. Review of simple ADT's: stacks, queues, vectors and lists (Sec. 2.1, 2.2).
  
  
• 9/23/09: Trees (Sec. 2.3).
  Homework 3 , due September 30 (W). Question 2 is from your book. Note that Gale-Shapley algorithm is the algorithm we discussed in class that finds a stable matching. I distributed a copy of it; if you were not in, come see me for a copy or you can find one online.
  
  
• 9/28/09: Trees cont'd. Intro to priority queues and heaps (Sec. 2.4).
  
  
• 9/30/09: Heaps.
  Homework 4 , due October 7 (W).
  
  
• 10/05/09: HW 2 reviewed. Intro to the Dictionary ADT (Sec 2.5).
  
  
• 10/07/09: Hash tables cont'd. Ordered Dictionaries and Binary Search Trees (Sec. 3.1).
  Homework 5 , due October 14 (W).
  
  
• 10/12/09: HW 3 reviewed. BST's cont'd. Intro to AVL trees (Sec. 3.2).
  
  
• 10/14/09: AVL trees cont'd. Correction. Splay trees (Sec. 3.4).
  Homework 6 , due October 21 (W).
  
  
• 10/19/09: Splay trees cont'd. HW 4 reviewed. Mergesort and Quicksort (Sec. 4.1, 4.3).
  
  
• 10/21/09: HW 5 and 6 reviewed.
  
  
• Midterms is scheduled for 10/26 (M). Coverage. Sample 1. Sample 2.
  
  
• 10/28/09: Randomized quicksort (Sec. 4.3). Lower bounds for comparison-based sorting (Sec. 4.4). Bucket and Radix sort (Sec. 4.5).
  Homework 7 , due November 4 (W).
  
  
• 11/02/09: Exam I returned and reviewed. The greedy method (Sec. 5.1).
  
  
• 11/04/09: Selection. The greedy method cont'd.
  Homework 8 , due November 11 (W).
  
  
• 11/9/09: Task scheduling cont'd. Divide and conquer (Sec. 5.2).
  
  
• 11/11/09: Divide and conquer cont'd. Intro to dynamic programming. (Sec. 5.3).
  Homework 9 , due November 23 (M). Note: You have 1.5 weeks to work on this.
  
  
• 11/16/09: Dynamic Programming cont'd.
  
  
• 11/18/09: More DP: matrix chain multiplication and the knapsack problem.
  
  
• 11/23/09: HW 8 returned and reviewed. Intro to graphs. (Sec. 6.1, 6.2)).