CS 155
Intro to Design & Analysis of Algorithms
MW 1900-2015, MH 224
Jeff Smith, MH 415, 924-5153
smithj@mathcs.sjsu.edu
Office hours (tentative):
1600-1730 MW, 1500-1600 TTh,
or by appointment.
Text:
Brassard & Bratley, Fundamentals of Algorithmics.
Other texts are available in the reserve book room.
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
general areas. One of these areas is "particular algorithms"
that don't fit well into the other 6 areas; the algorithms
treated will depend on time considerations and on the
background of class members. The Fast Fourier transform will
certainly be covered. The other 6 areas are listed below and
will be covered in the order given.
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 on
academic dishonesty. In the 1995-97 catalog, it's on on pp. 446-47.