CSC 331: Design & Analysis of Computer Algorithms
Fall, 2008

Tue/Thu, 1:00-2:15 pm
Chambers 3146


Course Description


Instructor:
Stephen L. Davis; click here for my weekly schedule.

Text:
S Dasgupta, C Papdimitriou, & U Vazirani, Algorithms, McGraw-Hill, 2008

Overview:

This course is about algorithm design strategies, including greedy, divide-and-conquer, and dynamic programming methods, and the analysis of algorithm complexity. Topics of the course, keyed to our text, are outlined in the Schedule Guesstimate below.

Evaluation:

We will have frequent homework augmented by occasional programming tasks, two reviews, and a final examination, as indicated below. A rough recipe for the proportions in which these events combine to produce your evaluation is Your "homework" grade will include in-class presentations. "Other considerations" include alertness and participation in class.

Class Policies:

The reviews and final examination are pledged events; you are expected to be vigilant in upholding the Honor Code.

The Code of Responsibility prohibits "unauthorized review, transfer, or alteration of information on the computer." Plagiarism is an Honor Code violation.

Homework will be assigned and monitored regularly. Collaboration on homework is encouraged. However, you are responsible for work which bears your name; that is, it is presumed that you understand and can defend any work which you submit.

Collaboration on programming tasks may be more restricted. In any case, though specific attribution of work on the various components of the assignment is expected.

If you have any questions regarding ground rules for individual events, do not hesitate to ask for clarification.

Come to every class meeting and come on time. Missing class deprives both you of a first-hand class experience and your classmates of your particular perspectives. I monitor attendance; missing 20% of class meetings can trigger action to encourage more faithful attendance. In any event, you are responsible for all material discussed in class, whether you are present or absent.

Schedule Guesstimate:

(volatile!)
Class Dates Section Discussed Event  Chapter Topic
Aug 26, 28 0 1.1, 1.2    0: Prolog / 1: Algorithms with numbers
Sep 2, 4 1.3--1.4 1.5    
Sep 9, 11 2.1, 2.2 2.3, 2.4  2: Divide-and-conquer algorithms
Sep 16, 18 2.5, 2.6 catch up    
Sep 23, 25 3.1, 3.2 3.3, 3.4    3: Decompositions of graphs
Sep 30, Oct 2 catch up Review Thursday Review #1  
Oct 7, 9 4.1--4.4 4.6, 4.7  4: Paths in graphs
Oct 14, 16 no class Bernard Lecture Fall Break  
Oct 21, 23 5.1, 5.2 5.3, 5.4  5: Greedy algorithms
Oct 28, 30 6.1--6.3 6.4, 6.5    6: Dynamic programming
Nov 4, 6 6.6, 6.7 catch up    
Nov 11, 13 7.1, 7.2 7.3--7.5    7: Linear algebra & reductions
Nov 18, 20 catch up Review Thursday Review #2  
Nov 25, 27 7.6, 7.7 no class Thanksgiving  
Dec 2, 4 8.1 8.2, 8.3  8: NP-complete problems
Dec 9, 11 debriefReading Day    
Dec 12--18 Final Examination