Home Page for CS515 (Spring 2005)

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: Tue, Thu: 11am-12pm; Wed: 10-11am, 2pm-3pm (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by lecture

• Jan 12 --- Algorithmic complexity: concepts and properties (read chapter 1,2,3).
• Jan 14 --- Algorithmic complexity: concepts and properties (read chapter 3). Solving recurrence relations (read chapter 4).
• Jan 17 --- No class, Martin Luther King Day.
• Jan 19 --- Solving recurrence relations (read chapter 4).
• Jan 21 --- The hiring problem (read p. 91-100).
• Jan 24 --- Randomly permuting an input array (read p. 100-104).
• Jan 26 --- The birthday paradox (read p. 106-108). Quicksort (read p. 145-157).
• Jan 28 --- Quicksort (read p. 156-158). Max-SAT.
• Jan 31 --- Randomized selection (read p. 181-189).
• Feb 2 --- Lower bound for sorting, linear sorting algorithms (read p. 165-176).
• Feb 4 --- Counting sort (read p. 168-170). Convex Hull.
• Feb 7 --- Balls and bins (read p. 109-110). Convex Hull.
• Feb 9 --- Convex Hull Algorithms (read p. 947-955).
• Feb 11 --- Convex Hull Algorithms (read p. 947-955).
• Feb 14 --- Test 1.
• Feb 16 --- Line segment intersections (read p. 934-942).
• Feb 18 --- Plane sweep (read p. 943-945). Closest pair (read p. 957-961).
• Feb 21 --- President's Day. No class.
• Feb 23 --- Cox-deBoor Equations for B-splines (covered by Starkey).
• Feb 25 --- Non-Uniform Rational B-splines (covered by Starkey).
• Feb 28 --- Greedy Algorithms (read p. 370-378).
• Mar 2 --- Greedy Algorithms (read p. 379-392).
• Mar 4 --- Dynamic programming (read p. 331-338).
• Mar 7 --- Optimal triangulation for convex polygons (read p. 331-338).
• Mar 9 --- The LCS problem (read p. 350-355).
• Mar 11 --- Assembly line scheduling (read p. 324-330).
• Mar 14 & 16 & 18 --- No classes, Spring break.
• Mar 21 --- Floyd's shortest path algorithm (read p. 624-633).
• Mar 23 --- Dynamic programming on TSP. Introduction to approximation algorithms (read handouts).
• Mar 25 --- Easter Friday, no class.
• Mar 28 --- Test 2.
• Mar 30 --- Map labeling using circle and circle pairs (read handouts).
• Apr 1 --- Minimum Vertex Cover and TSP (read handouts).
• Apr 4 --- Optimal bridge problem (read handouts).
• Apr 6 --- NP, co-NP (read p. 966-982).
• Apr 8 --- NP-completeness, SAT < 3SAT, 3SAT < Clique, 3SAT < Subset-Sum (read p. 983-1017).
• Apr 11 --- NP-completeness, 3SAT < Subset-Sum, HC < TSP, VC < IS, VC < Hitting Set (read p. 983-1017).
• Apr 13 --- NP-completeness, 3SAT < VC, IS < Set Packing (read p. 983-1017).
• Apr 15 --- Test 3.
• Apr 18 --- Project presentations.

Tests (30%)

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

Assignments (30%)

• CS515 - assignment 1 (pdf) or CS515 - assignment 1 (ps) (Due: Feb 11, 2005.)
• CS515 - assignment 2 (pdf) or CS515 - assignment 2 (ps) (Due: Mar 23, 2005.)
• CS515 - assignment 3 (pdf) or CS515 - assignment 3 (ps) (Due: Apr 13, 2005.)

Project (10%)

Final Exam (30%): May 2, 2:00pm-3:50pm

Final Grade