Stanford CS Ph.D. Breadth Requirements Areas
Comprehensive Examinations
Academic Year 1999-00
Each student in the Stanford Computer Science Ph.D. program is required
to pass these comprehensive exams,
(or the corresponding course equivalents)
in their first 3 years of study in the program.
There are 12 areas in total, divided into three areas of systems,
theory/mathematics and applications.
Computer Architecture
| COMPILERS
| Networks
| Prog. Languages
| Software Systems
Computer architecture is a required area.
Choose at least 2 out of the four areas: compilers, networks, programming
languages and software systems.
AA & CM
| Automata
| Logic
| Numerical Analysis
Analysis of algorithms and automata theory are required.
Choose 1 of the 2 logic and numerical analysis.
AI
| Databases
| Graphics
AI is required. Choose one of databases and graphics.
Completing this requirement entails passing 8 out of the 12 areas
or their course equivalents.
(Previously to this year, there were 10 areas, namely those
below minus graphics and networking,
and a student was required to satisfy all 10 areas.)
A student must satisfy 6 out of the 8 areas to be admitted to candidacy.
Also, satisfying 5 out of 8 areas in the first two years is considered
reasonably progress.
(Of course, we all hope you will pass them all in your first year!)
This document describes the expected preparation for each of the
area exams as well as specifying the course alternatives.
Notes:
All examinations are one hour.
All examinations assume a certain mathematical sophistication
and programming abilities. Proofs of correctness for simple programs
may be required. Students are expected to be able to write programs
in C/C++, Pascal and Lisp, and they should be familiar with at least one
assembly language.
Calculators are allowed in all exams.
Computers are only allowed in the open book exams.
Each area can be passed by getting a "pass" grade on its
exam, or by taking the course(s) alternatives listed below,
with an A- grade or higher. For some areas,
two courses are listed and both must be taken for a pass.
Exam: Closed book
Course Alternative:
- CS212 - Computer Architecture and Organization
Readings:
- D. Patterson, J. Hennessy: Computer Architecture: A Quantitative Approach.
- M. Mano: Computer System Architecture, 2nd edition,
Prentice-Hall
- Sieworiek, Bell, and Newell, Computer Structures Readings and Examples
- Hennessy and Patterson, Computer Architecture: The Hardware Software Interface
- Flynn, Computer Architecture: Pipelined and Parallel Processor Design
Exam: Open book
Course Alternative:
- CS143 - Compilers
Readings:
- Alfred Aho, R. Sethi, Jeffrey Ullman: Compilers. All except
sections 5.6-5.10, 7.2-7.9, 9.10-9.12, 10.3-end.
Exam: Closed book
Course Alternative:
Readings:
- CS 244A text, course notes and readings
Exam: Open book
Course Alternative:
- CS242 - Programming Languages
Readings:
- Ravi Sethi, Programming Languages: Concepts and Constructs
Addison-Wesley, 1989. Chapters 1-9.
Exam: Closed book
Course Alternative:
CS140 - Operating Systems OR
CS240A - Operating Systems (previous numbering for the course)
Readings:
- Abraham Silberschatz and Peter B. Galvin: Operating System Concepts.
Fourth Edition
Exam: Closed book
Course Alternative:
- CS161 - Discrete Structures and Algorithms
Readings:
- Alfred Aho, John Hopcroft, Jeffrey Ullman: Data Structures
and Algorithms.
- R. Graham, D. Knuth, O. Patashnik: Concrete Mathematics.
Sections 1.1-1.2, 2.1-2.5, 3.1, 3.4, 4.1-4.7, 5.1-5.2, 6.3,
6.6, 7.1-7.2, 8.1-8.2, 9-page 441.
Exam: Open book
Course Alternative: CS154 or CS254
- CS154 - Introduction to Automata and Complexity Theory, OR
- CS254 - Automata, Languages, and Computability
Readings:
- Hopcroft, J.E. and J.D. Ullman, Introduction to Automata,
Languages and Computation, Addison-Wesley, 1979. Chap.1-7,
8.1-8.5, 9, 12.1-12.4, 13.1-13.13.4.
Exam: Open book
Course Alternative: CS157 or Phil 160a **
** Either CS 257 or CS 258 may be used as an alternative to
CS 157 or Phil 160. It is recommended that one of these
alternatives be used when a student has passed the AI section
and a basic course in logic would be redundant.
- CS157 - Logic and Automated Reasoning
- Phil 160a - First-Order Logic
- CS257 - Automated Deduction and Its Applications
- CS258 - Introduction to Programming Language Theory
Readings:
- Enderton, H., A Mathematical Introduction to Logic,
Academic Press, 1972. Chap. 1 - 3.5.
- Manna, Z. and R. Waldinger, The Deductive Foundations of Computer
Programming, Addison-Wesley Pub. Co, 1993.
Exam: Closed book
Course Alternative:
- CS137 - Fundamentals of Numerical Computation
Readings:
- Kendall E. Atkinson: An Introduction to Numerical Analysis.
Chapters 1, 2, 3, 5, 7, 8 except for sections 2.8, 2.10, 2.11,
2.12, 3.5, 5.4, 5.6, 5.7, 8.7, 8.8.
Exam: Open book
Course Alternative:
- CS221 - Introduction to Artificial Intelligence
Readings:
- Russell & Norvig, "Artificial Intelligence: A Modern Approach"
Prentice Hall, 1995
Chapters 1; 2; 3; 4 (without 4.3); 5; 6; 7; 9; 10.4-10.6;
11; 14; 15; 18; 19 (without 19.6); 22.1-22.4, 22.7, 22.8;
24 (at a nontechnical level, without 24.6);
25 (without pages: 792-795, 800-802; 26.
- Michael R. Genesereth, Nils J. Nilsson: Logical Foundations of
Artificial Intelligence. Chapters 2-5
Exam: Open book
Course Alternative:
- CS145 - Introduction to Databases
Readings:
- Jeffrey D. Ullman and Jennifer Widom, A First Course in Database
Systems, Prentice-Hall, 1997, all chapters except 4.2-4.6
Exam: Closed book
Course Alternative:
Readings:
- CS 148 text, course notes and readings
Comprehensive Exam Chairman: David Cheriton.
Questions: Sara Merryman.
Last Updated 10/10/99.