Green sheet for CS 255: Design and Analysis of Algorithms

San José State University, Spring 2006, Section 2, 1730-1845 MW, MH 222
instructor: Jeff Smith
 

Office hours & contact information:

My office hours for Spring 2006 will be MW 1600-1730 and TTh 1400-1500, or by appointment. My office is MH 415. Email (at smithj@cs.sjsu.edu) 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 that will be useful for CS 288. The relevant sections of the text are

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.

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.

See the separate sheets on Assignments & Documentation for specific requirements for submissions. These, a tentative class calendar, and other useful documents will be available on the class web page at

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

Learning outcomes

Upon completion of this class, students should be able to

Academic integrity

The university policy on academic integrity can be found, along with other useful information, on the web site of the Office of Judicial Affairs.

The most important consequences of this 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 additional information on this topic 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 222 must be evacuated, please use the stairwell to your left 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 site of MH from the parking garage).