Green sheet for CS 255: Design and Analysis of Algorithms
San José State University, Spring 2008, Section 1, 1730-1845 TTh, MH 225
instructor: Jeff Smith
Office hours & contact information:
Office hours will be TTh 1600-1730 and MW 1415-1515. 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
Randomized algorithms. Parallel algorithms. Distributed algorithms. NP-completeness of particular problems. Approximation algorithms. Prerequisite: CS 155 or instructor consent.
Text and Topics:
The text is Introduction to Algorithms, 2nd edition, by Cormen et al (ISBN 0-262-03293-7 (hardcover), 0-262-53196-8 (paper)). Note that this is the second edition, with four authors. It's a good idea to bring the text to class every day. This text, its first edition (which some people prefer), and other references will be available in the library's course reserves. Also check the course web site for online references.
We will start with a review of algorithm design techniques, proceed with the topics of the catalog description, and then cover as time permits some additional material from Chapters 15-30 of the text. The relevant sections of the text are
- review of design techniques
Sections 9.1, 9.3, 15.1, 16.1 (and some supplemental material), 16.5
- topics of the catalog description
Sections 5.1-5.3, 7.3-7.4, 9.2, 11.3.3
Chapters 34, 35, 27, 31
and some supplemental material
- additional material as time permits
primarily Chapters 17, 26, 29, and 32
Grading system:
35% on assignments; 45% on 3 in-class tests; 20% on the final exam. All tests will be open book and open notes. Electrical & electronic devices are not permitted (except for preapproved hardship cases).
For each exam or assignment, numeric grades are given and intervals for each letter grade are assigned. For exams these are usually 90% for A-, 80% for B-, etc.; for problem sets the grade intervals are usually more liberal. 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 rather small. 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.
The assignments will primarily be problem sets. There may be occasional programming components. More likely, there will be some problems which you can do either by hand or by writing a program. The language to be used and stylistic issues will be discussed if and when the need arises.
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/255
Learning outcomes
Upon completion of this class, students should be able to
- construct simple NP-completeness proofs
- understand and evaluate different ways of coping with NP-complete problems
- design and analyze randomized, parallel and distributed algorithms, and approximation algorithms.
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 stairwell ahead and to your right as you exit the room. 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).