CS 155

Intro to the Design & Analysis of Algorithms
1900-2015 MW, MH 225
Jeff Smith, MH 415, 924-5153, `smithj@mathcs.sjsu.edu`

Office hours (tentative):

1500-1600 MTWTh, 1830-1900 MW, or by appointment.

Text:

Brassard & Bratley, Fundamentals of Algorithmics. Other texts are available in the reserve book room, which is now in Clark Library.

Grading system:

35% on problem sets; 45% on three 1-hour exams; 20% on final exam.
All exams will be open book and open notes. The final grade will be computed by comparing the sum of your scores to the sum of the grade brackets for all assignments and tests. In borderline cases, consideration goes to those who did the homework regularly or improved during the course.

Topics:

We will spend roughly 2 weeks in each of 7 areas, one of which consists of those algorithms that don't fit well into the other 6 areas. The algorithms treated here will depend on time considerations and the background of class members, but will certainly include the Fast Fourier Transform. The other 6 areas will be covered in the order given below.

divide & conquer (Section 4.7 and Chapter 7)
dynamic programming (Chapter 8)
greedy methods (Chapter 6)
search techniques (Chapter 9)
lower bounds (Sections 12.2-12.3)
intractable problems (Section 12.5)

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 onacademic dishonesty, as stated in the 1998-2000 catalog, pp. 446-47.