Green sheet for CS 288: Comprehensive Review
San José State University, Spring 2007, Section 1, 1900-2015 MW, MH 222
instructor: Jeff Smith
Office hours & contact information:
My office hours for Spring 2007 will be MW 1600-1730 and TTh 1430-1530, or by appointment. My office is MH 218. 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
Comprehensive review of foundational material in computer science. Programming language principles. Formal languages and theory of computation. Analysis of algorithms. Comprehensive examination. Course credit is based solely on the comprehensive examination. Prerequisite: CS 240.
About the course:
This course is designed as an alternate culminating experience for those students who have a strong interest in and aptitude for theoretical computer science. Students with an interest in practical applications of computer science are encouraged to take CS 297/298.
Much of the format of this course and the assocated three-part comprehensive examination is mandated by the Department of Computer Science, and described at
http://www.cs.sjsu.edu/mscs/CS288.html. You are strongly encouraged to consult this page. There is also a separate web page for this semester's class, at http://www.cs.sjsu.edu/faculty/smithj/classes/288.
Texts:
The reference texts for this course are
- Cormen et al, Introduction to Algorithms, 2nd edition (ISBN 0-262-03293-7 (hardcover), 0-262-53196-8 (paper))
- Hopcroft, Motwani, and Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edition (ISBN-10: 0321462254, ISBN-13: 9780321462251)
- Scott, Programming Language Pragamatics, 2nd edition (ISBN 978-0-12-633951-2 (hardcover), 0-12-633951-1 (paper))
Ideally you will already own or be able to purchase these texts. They are standard references in their areas, so they should be among the texts that you seriously consider keeping after you leave SJSU. However their popularity will make them relatively easy to sell after this course, should you decide to do that. These texts and perhaps other references will be available in the library's course reserves. It might be worth also checking the course reserves for CS 255.
Grading system and course topics:
The grading system for this class is mandated by the CS department to be based entirely on a three-part comprehensive examination. The exam is mandated to cover Chapters 15-30 from Cormen et al, and all of Hopcroft et al (cf.
the department's CS 288 web site). For 2007, we are allowed to use the second edition of the Scott text, rather than the Mitchell text listed on the web site. You are responsible for Chapters 1-11 and 14 of Scott (this material is as consistent as possible with earlier sections of this course, given the appearance of a second edition of the text). The material in the 3rd edition of the HMU text is not significantly different from that of the 2nd edition. Note that Chapter 34 of Cormen et al covers much of the same material as Chapter 10 of HMU, and much of Chapter 2 of Scott is covered in Hopcroft et al. A tentative class calendar and guidelines for this semester's exam are available on the class web site.
Learning outcomes
Upon completion of this course, students should be able to
- design, analyze, and trace algorithms from a variety of domains
- understand the most useful classes of formal languages, the relations among them, the various representations for instances of each class, and how to convert among these representations
- understand and explain how problems can be shown to be undecidable
- understand and provide evidence for the intractability of problems
- understand the fundamental issues involved in designing, implementing, and translating among programming languages
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 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 side of MH from the parking garage).