Green sheet for CS 155: Introduction to the Design and Analysis of Algorithms

San José State University, Fall 2007
Section 1, 1900-2015 TR, MH 225
instructor: Jeff Smith
final version

Office hours & contact information:

My office hours for Fall 2007 will be 1400-1500 MW and 1730-1845 TR, or by appointment. My office is MH 218. Email (to ) is usually better for reaching me than the phone (408-924-5153), since I check messages more frequently, and I'm often too busy with a student to answer the phone.

Catalog Description

Algorithm design techniques: dynamic programming, greedy algorithms, Euclidean and extended Euclidean algorithms, Discrete and Fast Fourier transforms. Analysis of algorithms, intractable problems and NP-completeness. Additional topics selected from: selection algorithms and adversary arguments, approximation algorithms, parallel algorithms, and randomized algorithms. Prerequisite: CS 146 (with a grade of "C-" or better) or instructor consent.

Text and Topics:

The text is Algorithm design: foundations, analysis, and Internet examples, by Goodrich and Tamassia (ISBN 978-0-471-38365-9). It's a good idea to bring the text to class every day. Additional references will be available in the library's course reserves, and through the course web site.

The bulk of the course will consist of the following topics (the given section numbers are those of our textbook)

Additional topics will be selected from Approximation Algorithms (13.4), Randomized Algorithms (3.5, 4.3.1, 4.7.2-4.7.3, 14.3.2), the use of adversary arguments (e.g., 14.3.2), and Parallel Algorithms (14.2) as time permits. For some sections of the course, additional examples may be provided that are not in the textbook.

Note that much of Chapters 1-4, 6, and 7 should be familiar from your earlier coursework. This material, including some of the graph algorithms in the sections of the text indicated above, will be reviewed very briefly if at all.

Grading system:

Excluding extra credit, the course will be graded on a 1000-point basis: 500 points on Java programming assignments, 300 on 3 in-class tests, and 200 on the final exam. For each exam or assignment, numeric grades are given and intervals for each letter grade are assigned. The bottoms of these intervals are usually 90% for A-, 80% for B-, etc. Your course grade will be determined by comparing the sum of your numeric grades to the sum of the intervals, except that I often give a grade slightly higher than this to students who have just one poor grade, or who have been improving throughout the course. The intervals for + and - grades are 1.5 percentage points, so that, for example, the borderline between A- and A is normally 91.5%. My standards for the I grade, for makeup exams, and for extending assignment due dates are quite strict. At a minimum, I expect documentation of why you cannot complete the work in the expected time.

Extra credit will not be considered in the determination of grade brackets. So for example, if the range for an A- is 900-915 points, then a student who gets 20 points of extra credit and 900 regular credit points will get a grade of A (based on 920 of 1000 total points) rather than an A- (based on 920 of 1020 total points). There will be from 0 to 30 extra credit points in the course.

All tests will be open book and open notes. Electrical & electronic devices are not permitted (except for preapproved hardship cases).

The separate web pages entitled Assignments, Documentation and Style in Java, Collaboration, and Course Calendar are part of the official greensheet for this course, and you are responsible for knowing their contents. The first two of these give specifications for turning in programming assignments in this course. All four of them, along with other useful documents, are available from the class home page at

http://www.cs.sjsu.edu/faculty/smithj/classes/155

Learning outcomes

Academic integrity

Mandated SJSU academic integrity statement: Your own commitment to learning, as evidenced by your enrollment at San José State University, and the University's Academic Integrity Policy requires you to be honest in all your academic course work. Faculty members are required to report all infractions to the Office of Judicial Affairs. The policy on academic integrity can be found at http://sa.sjsu.edu/judicial_affairs/index.html. This site has other useful information besides the policy.

The most important consequences of the policy are that, unless unless I explicitly specify otherwise, work you turn in for this class should be entirely your own, and you should not share your work with anyone else. Some elaboration of the policy is available on the class web site.

Campus policy in compliance with the Americans with Disabilities Act

If you need course adaptations or accommodations because of a disability, or if you need special arrangements in case the building must be evacuated, please see me soon as possible. Presidential Directive 97-03 requires that students with disabilities register with DRC to establish a record of their disability.

Evacuation

If MH 225 must be evacuated, please use the front stairs (so make a right turn and then a quick left turn and a quick right turn as you leave the classroom). Do not attempt to use the elevators. Do bring your belongings, as you may not be able to reenter the building promptly. When you exit the stairwell, proceed to the Paseo de San Carlos (the grassy strip on the opposite side of MH from the parking garage).