CS 535-001 Algorithm Design and Analysis

Spring 2008
MW 2:00 - 3:15 pm, EMS E225
Instructor: Christine Cheng
EMS 1045, 414.229.5170

Syllabus of the course.

Schedule

• 1/23/08: Brief math review.
  
  
• 1/28/08: Framework for analyzing algorithms (Sec. 1.1), Intro to asymptotic notation (Sec. 1.2).
  
  
• 1/30/08: Analyzing runtimes of simple algorithms. Designing algorithms. (Sec. 1.4).
  HW 1. Due on 2/13 (W).
  
  
• 2/4/08: Designing algorithms cont'd.
  
  
• 2/11/08: Review of basic ADT's. (Sec. 2.1, 2.2, 2.3)
  
  
• 2/13/08: The Tree ADT.
  HW 2. Due on 2/25 (M). Note: you only have 1.5 weeks for this homework!
  
  
• 2/18/08: Tree traversals. Priority Queues (Sec. 2.4).
  
  
• 2/20/08: Priority Queues cont'd. Intro to Dictionary ADT (Sec. 2.5).
  
  
• 2/25/08: Hash tables cont'd. HW 1 discussed.
  HW 3. Due on 3/10 (M).
  
  
• 2/27/08: Ordered Dictionaries and binary search trees (Sec. 3.1).
  
  
• 3/3/08: AVL trees (Sec. 3.2).
  
  
• 3/5/08: Splay trees (Sec. 3.4). HW 2 discussed.
  
  
• 3/10/08: HW 2 cont'd. HW 3 discussed.
  
  
• MIDTERMS is scheduled for 3/12 (W). Coverage. Sample Exam.
  
  
• 3/24/08: Intro to greedy algorithms (Sec. 5.1).
  
  
• 3/26/08: Greedy algorithms cont'd. Intro to divide-and-conquer (Sec. 5.2).
  HW 4. Due on 4/9 (W).
  
  
• 3/31/08: Divide-and-conquer cont'd. Intro to dynamic programming (Sec. 5.3).
  
  
• 4/2/08: Dynamic programming cont'd.
  
  
• 4/7/08: Intro to sorting.
  
  
• 4/9/08: A lower bound on comparison-based sorting. Bucket and radix sorts. Selection.
  HW 5. Due on 4/23 (W).
  
  
• 4/14/08: Dynamic programming cont'd. Intro to graphs. (Sec. 6.1, 6.2)
  
  
• 4/16/08: Graph traversals (Sec. 6.3).
  
  
• 4/21/08: HW 4 discussed. Graph traversals cont'd.
  Sol'n to HW 4.
  
  
• 4/23/08: Algorithms on directed graphs.
  HW 6. Due on 5/7 (W).
  
  
• 4/28/08: HW 5 discussed. Intro to shortest path algorithms.
  
  
• 4/30/08: Dijkstra's algorithm. Intro to Bellman-Ford algorithm.
  
  
• 5/5/08: Shortest path algorithms cont'd. Some applications.
  
  
• 5/7/08: Applications cont'd. HW 6 discussed.
  
  
• FINALS is scheduled for 5/13 (Tue) from 12:30-2:30 pm, same room. Coverage. Sample Final.
  Note: Last semester, I wasn't able to cover the section on shortest paths. This time around, do expect questions from this topic.