Home Page for CS515 (Spring 2007)

Schedule

• Monday, Wednesday, Friday, 4:10pm--5:00pm in EPS 350

Textbook

• Introduction to Algorithms (2nd edition), by Cormen, Leiserson, Rivest and Stein, MIT Press.

Instructor: Dr. Binhai Zhu

• Office: EPS 355
• Office hours: Tue, Wed, Thu: 2:30pm-3:30pm; Wed: 10-11am (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by lecture

• This is roughly the CS515 schedule from 2006. Changes will be made starting Jan 18, 2007.
• Jan 19 --- Algorithmic complexity: concepts and properties (read chapter 1,2,3).
• Jan 22 --- Algorithmic complexity: concepts and properties (read chapter 3). Solving recurrence relations (read chapter 4).
• Jan 24 --- Solving recurrence relations (read chapter 4).
• Jan 26 --- Solving recurrence relations (read chapter 4). \Theta-notation and strongly asympotic relation.
• Jan 29 --- The hiring problem (read p. 91-100).
• Jan 31 --- Randomly permuting an input array (read p. 100-104).
• Feb 2 --- The birthday paradox (read p. 106-108).
• Feb 5 --- Max-SAT. Quicksort (read p. 145-158).
• Feb 7 --- Linear time selection (read p. 189-192).
• Feb 9 --- Randomized selection (read p. 181-189).
• Feb 12 --- Lower bound for sorting. Linear sorting algorithms: Bucket Sort (read p. 174-176).
• Feb 14 --- Linear sorting algorithms: Counting Sort (read p. 164-170). Balls and bins (read p.109-110).
• Feb 16 --- Convex Hull algorithms (read p. 947-955).
• Feb 19 --- No class (President's Day).
• Feb 21 --- Convex Hull algorithms (read p. 947-955).
• Feb 23 --- Test 1 (contents: everything covered up to Feb 21).
• Feb 26 --- No class (make-up lectures were done on Feb 14, 16 and 21).
• Feb 28 --- Convex Hull algorithms (read p. 947-955).
• Mar 2 --- Divide & Conquer CH algorithm. CCW, CW primitives (read p. 934-936). Line segment intersections (read p. 934-942).
• Mar 5 --- Plane sweep (read p. 943-945). Closest pair (read p. 957-961).
• Mar 7 --- Closest pair. Triangulating a simple polygon in O(n log n) time.
• Mar 9 --- Triangulating a monotone polygon in O(n) time. Greedy Algorithms (read p. 370-378).
• Mar l2 & 14 & 16 --- No classes, Spring break.
• Mar 19 --- Greedy methods (read p. 370-392).
• Mar 21 --- Dynamic programming and the LCS problem (read p. 350-355).
• Mar 23 --- Dynamic programming review (Matrix chain multiplication,optimal triangulation of convex polygons) (read p. 331-338).
• Mar 26 --- Assembly line scheduling (read p. 324-330). Dynamic programing on TSP.
• Mar 28 --- Introduction to approximation algorithm. Map labeling using circles and circle pairs (read handouts).
• Mar 30 --- Introduction to approximation algorithm (read handouts on 2-approximations for Diameter, TSP and min-diameter spanning tree problems).
• Apr 2 --- Test 2.
• Apr 4 --- A better approximation for TSP and optimal bridge problem (read handouts).
• Apr 6 --- No class (Good Friday).
• Apr 9 --- P, NP (read p. 966-982). NP-completeness, HC < TSP, IS < VC.
• Apr 11 --- NP, co-NP (read p. 966-982). Subset-Sum < Rectangle Packing, 3SAT < Clique (read p. 983-1005).
• Apr 13 --- NP-completeness, 3SAT < VC (read p. 1005-1017), VC < Clique (read p. 983-1017). Greedy method for VC. Approximation for Minimum Vertex Cover (read p. 1024-1026).
• Apr 16 --- NP-completeness, 3SAT < Subset-Sum.
• Apr 18 --- NP-completeness, IS < Set Packing, VC < Hitting Set (read handouts).
• Apr 20 --- No class (make-up lectures were done on April 9, 13).
• Apr 23 --- Test 3.
• Apr 25 --- Review for Test 3 and for final.
• Apr 27,30 --- Project presentations.
• May 2,4 --- Project presentations.

Tests (30%)

• CS515 - test 1 (Test 1 is scheduled on Feb 23, during regular class time.)
• CS515 - test 2 (Test 2 is scheduled on Apr 2, during regular class time.)
• CS515 - test 3 (Test 3 is scheduled on Apr 23, during regular class time.)

Assignments (30%)

• CS515 - assignment 1 (pdf) (Due: Feb 16, 2007.)
• CS515 - assignment 2 (pdf) (Due: Mar 28, 2007.)
• CS515 - assignment 3 (pdf) (Due: April 18, 2007.)

Project (10%)

Final Exam (30%): May 10, 2007, 4:00pm-5:50pm

Final Grade