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.

Systems Exams

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.

Theory/Mathematics Exams

AA & CM | Automata | Logic | Numerical Analysis

Analysis of algorithms and automata theory are required. Choose 1 of the 2 logic and numerical analysis.

Applications Exams

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.



Systems



Computer Architecture

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

Compilers

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.


Networking

Exam: Closed book

Course Alternative:

CS 244a: Computer Networks: Architecture and Protocols

Readings:

CS 244A text, course notes and readings

Programming Language

Exam: Open book

Course Alternative:

CS242 - Programming Languages

Readings:

Ravi Sethi, Programming Languages: Concepts and Constructs Addison-Wesley, 1989. Chapters 1-9.

Software Systems

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

Theory/Mathematics


Analysis of Algorithms and Concrete Mathematics

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.

Automata and Formal Languages

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.

Logic

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.

Numerical Analysis

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.

Applications



Artificial Intelligence

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

Databases

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

Graphics

Exam: Closed book

Course Alternative:

CS 148

Readings:

CS 148 text, course notes and readings

Comprehensive Exam Chairman: David Cheriton.

Questions: Sara Merryman.

Last Updated 10/10/99.