Home Page for CS223 (Spring 2007)

Schedule

• Tuesday, Thursday, 11:00am--12:15pm in EPS 103

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

TA for session 1 (Wed, 11am-12:50pm): David Lopez (email: davidl@cs)

• Office hours: Wed: 1pm-2pm; Thu: 10-11am (in EPS 109)

TA for session 2 (Fri, 2:10pm-4:00pm): Natrajan Thamizhmani (email: natrajant@cs)

• Office hours: Wed: 8am-12pm (in EPS 109)

Syllabus by lecture

• I will update this web page as classes go on. For some topics related to math, I will simply use whiteboard. Otherwise, the lectures might be conducted in .ppt or .pdf slides, which will be posted on this course web page. In either cases, skipping classes systematically is not encouraged --- you will simply find that after continuously skipping 3-4 lectures you cannot follow me anymore.
• Jan 18 --- Course overview (by Brendan Mumey).
• Jan 23 --- Algorithmic complexity: big-O notations, concepts and properties (read CLRS chapter 1,2,3).
• Jan 25 --- Solving recurrence relations. Ex 1. T(n)=T(n/2)+1===1+log n. Ex 2. T(n)=2T(n/2)+n===n log n + n. Ex 3. T(n)=T(n/2)+n===2n-1.
• Jan 30 --- Solving recurrence relations. Ex 4. T(n)=2T(n/2)+n^2=== 2n^2-n. Ex 5. T(n)=8T(n/2)+n===2n^3 - n^2. Ex 6. T(n)=2T(n/4)+n===2n-\sqrt{n} (read CLRS chapter 4).
• Feb 1, Feb 6 --- Heaps, heapsort and priority queue (read CLRS chapter 6).
• Feb 8 --- Linear time selection (read CLRS p. 189-192).
• Feb 13, Feb 15 --- Hashing and hash tables (read CLRS chapter 11). Solution for the crystal ball problem.
• Feb 20,22 --- Binary search trees (read CLRS p. 253-264).
• Feb 22, Mar 1, Mar 6 --- Red-black trees (read CLRS p. 273-293).
• Feb 27 --- Test 1.
• Mar 6, Mar 8 --- Greedy methods (read CLRS p. 370-391).
• Mar 13, 15 --- No class (Spring Break).
• Mar 20, Mar 22, Mar 27 --- Dynamic programming (read CLRS p. 331-338 and 350-355).
• Mar 27 --- Graph Algorithms, 1 (read Sedgewick p. 3-40).
• Mar 29 --- Graph Searching---BFS (read Sedgwick 121-129 or CLRS 531-538; also read Sedgwick 62-68).
• Apr 3 --- Test 2.
• Apr 5 --- Review of Proofs, Graph Searching---DFS (read CLRS 540-545 or Sedgwick 81-96).
• Apr 10 --- Review of Proofs, Properties and applications of DFS (read Sedgwick 97-110). Minimum Spanning Trees (read Sedgwick 227-257).
• Apr 12 --- Minimum Spanning Trees (read Sedgwick 227-264). Union-Find Operations (read handouts).
• Apr 17 --- Dijkstra's Shortest Path Algorithm (read Sedgwick 277-302).
• Apr 19 --- Floyd's All-Pairs Shortest Path Algorithm (read Sedgwick 304-312).
• Apr 24 --- Randomized algorithm and RSA Public Key Cryptography (read CLRS 91-98 and 881-885).
• Apr 26 --- Test 3.
• May 1 --- Review of course contents and Test 3.
• May 3 --- Question answering session.

Tests (30%)

• CS223 - test 1 (Test 1 is scheduled on Feb 27, during regular class time. Contents: Everything covered until the end of Feb 15th. You can bring one A4 cheat sheet --- you have to decide what to put on your own cheat sheet. But no lecture notes and no books!)
• CS223 - test 2 (Test 2 is scheduled on April 3, during regular class time. Contents: Everything covered from Feb 20 until the end of the dynamic programming topic. Cheat sheet policy as in Test 1.)
• CS223 - test 3 (Test 3 is scheduled on Apr 26, during regular class time. Contents: all the graph-related stuff covered from March 27 to April 19. Cheat sheet policy as in Test 1.)

Lab Assignments (40%)

• CS223 - assignment 1 (pdf) (Due: at the end of the lab in Week 4---Feb 9, 2007.)
• CS223 - assignment 2 (pdf) (Due: at the end of the lab in Week 7---Mar 2, 2007.)
• CS223 - assignment 3 (pdf) (Due: at the end of the lab in Week 11---Mar 30, 2007.)
• CS223 - assignment 4 (pdf) (Due: at the end of the lab in Week 13---Apr 13, 2007.)
• CS223 - assignment 5 (pdf) (Due: at the end of the lab in Week 16---May 4, 2007.)

Final Exam (30%): May 10, 2007, 12:00pm-1:50pm

Final Grade