CS 255: Design and Analysis of Computer Algorithms

1900-2015 MW, MH 235
Jeff Smith, MH 415, 924-5153
smithj@mathcs.sjsu.edu

Office hours:

Tuesday & Thursday 1-1:30 and 3-4, Wednesday 5:00-7:00, or by appointment.

Text:

Cormen, Leiserson, and Rivest, Introduction to Algorithms. Additional resources will likely be used to supplement the course. Some will be available in the library's course reserves.

Grading system:

35% on problem sets
45% on 3 1-hour exams
20% on final exam

All exams will be open book and open notes.

The final grade will be computed by adding your scores and comparing to the sum of the grade brackets for all the assignments and tests. In borderline cases, consideration will be given to those who did the homework regularly or improved during the course.

There will be a class web page at

http://www.mathcs.sjsu.edu/faculty/smithj/classes/255
Note that this is accessible from my home page.

Topics:

Most of the course will be devoted to the identification, treatment, and analysis and identification of hard problems, including the specific topics of NP-completeness, approximation algorithms, parallel algorithms, and probabilistic algorithms. These correspond roughly to Chapters 30, 33.7-33.9, 36, and 37 of the text. Additional topics will be covered as time permits.

Class Attendance:

Class attendance is not required, but is strongly recommended. Beginning one week after the first exam, only documentable compelling reasons will be considered for withdrawal requests.

Collaboration:

The work you turn in should be your own. Do not share your work with anyone else. Please become familiar with the official university policy on academic dishonesty, as stated in the 2000-2002 catalog, pp. 430-431, or at http://info.sjsu.edu/web-dbgen/catnarr/policies/n30.html.