CS 155

Intro to Design & Analysis of Algorithms
1730-1845 MW, MH 224
Jeff Smith, MH 415, 924-5153
smithj@mathcs.sjsu.edu

Office hours:

1600-1730 M, 1500-1530 & 1600-1730 Tu, 1500-1600 & 1700-1730 Th, 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.