CS 155
Intro to Design & Analysis of Algorithms........1900-2015 MW, MH 422
Jeff Smith........MH 415............924-5153............smithj@mathcs.sjsu.edu
Office hours:
1530-1600 & 1800-1900 MW, 1600-1700 Tu, 1700-1730
TTh, or by appointment.
Text:
Smith, Design and Analysis of Algorithms. 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 the
following areas, basically in the order given. However, some
particular algorithms may be covered in the first half of the
course, along with the appropriate design technique. The "?"
below means that the amount of coverage depends on the background
of students in the class.
divide & conquer (Sections 2.14, 2.16, 2.17?, 4.7?, 4.9?)
dynamic programming (Sections 2.18, 2.19)
greedy methods (Section 2.20)
particular algorithms (Sections 4.15, 4.16?, 4.17, 4.19)
search techniques (Sections 4.10, 4.11, 4.12, 4.13?)
lower bounds (Sections 4.2, 4.3, 4.18)
intractable problems (Section 4.20?, Chapter 5)
Collaboration:
The work you turn in should be your own.
Please become familiar with the official university policy on
academic dishonesty on pp. 446-47 of the 1995-97 catalog.