CS535 Algorithm Design and Analysis

Spring 2012
TR 4:00-5:15 pm
Instructor: Christine Cheng
EMS 1011 x5170

Syllabus of the course.

Schedule

• 1/24/12: Review of logarithms and exponentials (Sec. 1.3.2). Intro to asymptotic notation (Sec. 1.2).
  
  
• 1/26/12: Asymptotic notation cont'd. Intro to algorithm design (Sec. 1.4).
  On Doing Homework . Homework 1, due 2/2.
  
  
• 1/31/12: Designing algorithms cont'd: prefix averages, binary search, maximum subsequences sum problem.
  
  
• 2/2/12: Designing algorithms cont'd: max subsequences sum cont'd. Intro to basic data structures (2.1): stacks and queues.
  Homework 2, due 2/9.
  
  
• 2/7/12: Resizing arrays. Vectors.
  
  
• 2/9/12: Lists and Trees. Tree traversals.
  Homework 3, due 2/16.
  
  
• 2/14/12: Implementing trees. Priority queues. Heapsort.
  
  
• 2/16/12: Heapsort con'td. Bottom-up heap construction. Intro to Binary Search Trees.
  Homework 4, due 2/23.
  
  
• 2/21/12: HW 3 discussed. BST's continued. A clarification.
  
  
• 2/23/12: AVL Trees.
  Homework 5, due 3/1.
  
  
• 2/28/12: AVL Trees continued. HW 4 discussed.
  
  
• 3/1/12: Splay trees. Here's a link to the paper I briefly mentioned in class.
  Homework 6, due 3/8.
  
  
• 3/6/12: HW 5, problem 3 discussed. Skip lists.
  
  
• 3/8/12: Sorting -- mergesort and quicksort.
  
  
• 3/13/12: HW6 and sample exam discussed.
  
  
• Midterms is scheduled for March 15 (Th). Coverage. A sample exam.
  
  
• 3/27/12: Midterms returned and discussed. Lower bound on comparison-based sorting algorithms. Bucket Sort.
  
  
• 3/29/12: Radix Sort. QuickSelect.
  Homework 7, due 4/5.
  
  
• 4/3/12: Intro to the greedy method.
  
  
• 4/5/12: The Marden Lecture.
  Homework 8, due 4/12. Solution.
  
  
• 4/10/12: The greedy method cont'd. Intro to divide and conquer.
  
  
• 4/12/12: Divide and conquer cont'd.
  Homework 9, due 4/19.
  
  
• 4/17/12: Dynamic programming.
  
  
• 4/19/12: Dynamic programming cont'd.
  Homework 10, due 4/26.
  
  
• 4/24/12: Graphs and graph traversals.
  
  
• 4/26/12: Graph traversals cont'd. Intro to algorithms for directed graphs.
  Homework 11, due 5/3.
  
  
• 5/1/12: Algorithms for directed graphs cont'd. HW 9, HW 10 discussed.
  
  
• 5/3/12: Dijkstra's algorithm.
  Homework 12, due 5/10.
  
  
• Final exam is scheduled for May 17 (Th), from 3 to 5 PM. A sample exam. Here's another one. Coverage.