Home Page for CS515 (Spring 2006)

Schedule

• Monday, Wednesday, Friday, 3:10pm--4:00pm in Roberts 301

Textbook

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

Instructor: Dr. Binhai Zhu

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

Syllabus by lecture

• Jan 11 --- Algorithmic complexity: concepts and properties (read chapter 1,2,3).
• Jan 13 --- Algorithmic complexity: concepts and properties (read chapter 3). Solving recurrence relations (read chapter 4).
• Jan 16 --- No class, Martin Luther King Day.
• Jan 18 --- Solving recurrence relations (read chapter 4).
• Jan 20 --- Solving recurrence relations (read chapter 4).
• Jan 23 --- The hiring problem (read p. 91-100).
• Jan 25 --- Randomly permuting an input array (read p. 100-104).
• Jan 27 --- The birthday paradox (read p. 106-108).
• Jan 30 --- Max-SAT. Quicksort (read p. 145-153).
• Feb 1 --- Quicksort (read p. 153-158).
• Feb 3 --- Randomized selection (read p. 181-189). Lower bound for sorting.
• Feb 6 --- Linear sorting algorithms (read p. 165-176).
• Feb 8 --- Balls and bins (read p.109-110).
• Feb 10 --- Convex Hull algorithms (read p. 947-955).
• Feb 13 --- Convex Hull algorithms (read p. 947-955).
• Feb 15 --- Convex Hull algorithms (read p. 947-955).
• Feb 17 --- Test 1.
• Feb 20 --- No class, President's Day.
• Feb 22 --- Divide & Conquer CH algorithm. CCW, CW primitives (read p. 934-936).
• Feb 24 --- Line segment intersections (read p. 934-942).
• Feb 27 --- Plane sweep (read p. 943-945). Closest pair (read p. 957-961).
• Mar 1 --- Triangulating a simple polygon in O(n log n) time.
• Mar 3 --- Greedy Algorithms (read p. 370-378).
• Mar 6 --- Greedy Algorithms (read p. 379-392).
• Mar 8 --- Dynamic programming (read p. 331-338).
• Mar 10 --- The LCS problem (read p. 350-355). Optimal triangulation of convex polygons (read p. 331-338).
• Mar l3 & 15 & 17 --- No classes, Spring break.
• Mar 20 --- Assembly line scheduling (read p. 324-330).
• Mar 22 --- Dynamic programing on TSP.
• Mar 24 --- Floyd's shortest path algorithm (read p. 629-633). Introduction to approximation algorithm (read handouts on 2-approximations for TSP and Diameter problems).
• Mar 27 --- Better approximations for TSP and Diameter problems (read handouts).
• Mar 29 --- Test 2.
• Mar 31 --- Map labeling using circles and circle pairs (read handouts).
• Apr 3 --- NP, co-NP (read p. 966-982).
• Apr 5 --- NP-completeness, SAT < 3SAT, 3SAT < Clique (read p. 983-1005).
• Apr 7 --- NP-completeness, 3SAT < Subset-Sum, 3SAT < VC (read p. 1005-1017).
• Apr 10 --- NP-completeness, VC < Clique (read p. 983-1017). Approximation for Minimum Vertex Cover (read p. 1024-1026).
• Apr 12 --- Optimal bridge problem, Min-diameter spanning tree (read handouts).
• Apr 14 --- Easter Friday, no class.
• Apr 17 --- NP-completeness, IS < Set Packing, VC < Hitting Set (read handouts).
• Apr 19 --- Review for final.
• Apr 21 --- Test 3.
• Apr 24,26,28 --- Project presentations.

Tests (30%)

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

Assignments (30%)

• CS515 - assignment 1 (pdf) or CS515 - assignment 1 (ps) (Due: Feb 13, 2006.)
• CS515 - assignment 2 (pdf) or CS515 - assignment 2 (ps) (Due: Mar 22, 2006.)
• CS515 - assignment 3 (pdf) or CS515 - assignment 3 (ps) (Due: Apr 17, 2006.)

Project (10%)

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

Final Grade