Computer Science Department Systems

PH.D. QUALIFYING EXAMINATION SYLLABUS

1998/99

Introduction

The exam is offered once a year, normally in late April or May. A student must apply at least 4 weeks in advance of the scheduled date for the exam in order to be considered (contact cheriton@cs.stanford.edu). The candidate must specify the three areas in which they wish to be examined at the time they apply to take the exam.

There is normally a faculty representative from each of the systems qual. areas on the committee who is responsible for the preparation and grading of exams in that area. Each area exam is normally a one hour written exam. However, the faculty examiner for the area may elect to administer an oral exam instead.

Basic knowledge in Computer Science and computer systems is assumed of all candidates. This basic knowledge is reflected by the Systems area of the CSD Comprehensive exam as well as the material covered in: CS 108, CS 111, CS 112, CS 140, CS 260, CS 261 and CS 262.

The following sections provide an outline and reference list for each area to indicate the material covered by the exam. Students are also expected to be familiar with major current literature as well as solve problems in their areas of specialization. Candidates can contact the faculty in their area of specializations in advance of the exam for clarification on the nature and emphasis of the exam.

Programming Languages

• language features: arrays, dynamic allocation, recursion, naming and binding, block structure, procedures, macros, etc. [8]
• basic implementation techniques: heaps, activation records, garbage collection methods
• applicative languages: LISP, Scheme [1], ML
• logic programming
• data structuring and abstraction: Smalltalk [3], Pascal [6], Simula [2], CLU [7], Ada [5], C++ [3']
• basic design tradeoffs in programming languages [4]
• interpreters [1] References include CS 242 Readings plus:

  1. Abelson and Sussman. Structure and Interpretation of Computer Programs. McGraw-Hill, 1984.

  2. O.J. Dahl and C.A.R. Hoare. Hierarchical program structures. In Structured Programming, O.J. Dahl, E.W. Dijkstra, and C.A.R. Hoare, Ed., Academic Press, 1972, pp. 175-220.

  3'. M. Ellis and B. Stroustrup, The Annotated C++ Reference Manual, Addison-Wesley, 1990.

  3. A. Goldberg and D. Robson. SmallTalk-80: the language and its implementation. Addison-Wesley, 1983.

  4. C.A.R. Hoare. Hints on Programming Language Design. Memo AIM 224, Stanford Artificial Intelligence Laboratory, 1975.

  5. J.D. Ichbiah, et al. "Preliminary Ada reference manual". SIGPLAN Notices 14, 6 (June 1979), Part A.

  6. K. Jensen and N. Wirth. Pascal User Manual and Report. Springer-Verlag, 1974.

  7. B.H. Liskov, A. Synder, R. Atkinson, and C. Schaffert. "Abstraction mechanisms in CLU". Comm. ACM 20, 8 (August 1977), 564-576.

  8. R. Sethi. Programming Languages. Addison-Wesley, 1989.

  Compilers

  Knowledge of the principles and organization of compilers as covered in CS 143 and CS 243 [1]. CS 343 is strongly recommended (and will be required background in future years).

  References

  1. Aho, A. V., Sethi, R. and Ullman, J. D. Compilers, Principles, Techniques and Tools. Addison-Wesley, Reading, Mass, 1986.

  Architecture

  References

  EE182: Computer Organization & Design The HW/SW interface by H & P

  EE282: Computer Architecture A quantitative Approach 2nd Ed. by H & P

  CS 315A: Parallel Computer Architecture: A Hardware/Software Approach David E. Culler, Jaswinder Pal Singh with Anoop Gupta

  Graphics

  Knowledge of basic representations of surfaces and solids, scan-conversion algorithms, geometric transformations, viewing projections, visible-surface determination, and shading models, as covered in CS 248. Understanding of basic issues in input and display hardware, graphics software, and user interface design. Some knowledge in depth of either curve, surface, and solid modeling and geometric algorithms at the level of CS 348A, or of sampling, filtering, and local and global illumination methods at the level of CS 348B.

  Typical references for the material in 248, 348A, and 348B, are the online course notes, where available, and the following three books:

  • For 248: Foley, van Dam, Feiner, and Hughes, Computer Graphics: Principles and Practice, second edition, Addison-Wesley, through chapter 17 except chapters 2, 7, and 9.
  • For 348A: Farin, Curves and Surfaces for Computer Aided Geometric Design Academic Press, second edition.
  • For 348B: Cohen and Wallace, Radiosity and Realistic Image Synthesis, Academic Press.

  Networks and Distributed Systems

  Principles of computer communication and networks as covered by CS 244A (See CS244 course material and [4]), including:
  • Transport level issues, techniques and protocols such as session management, naming, error control, flow control, transport-level implementation.
  • Local networks, wide-area networks and internetworking including bus networks, rings, packet radio, satellite, routing, congestion control, etc.
  • Basic knowledge of physical, data link and application levels.

  Concepts, principles and examples of distributed systems as covered by CS244B [1, 2] including: (Cheriton's CS 244B course reader is a good source.)

  • Network interprocess communication, RPC.
  • Naming and authentication techniques.
  • Agreement, negotiation and synchronization protocols.
  • Presentations issues, file access, I/O interfaces.
  • Distributed execution, scheduling, process migration, fault-tolerance and some knowledge of distributed systems security.

  Reading List for Networks and Distributed Systems

  Databases

  Reading List for Databases

  Old Exams

  Database portion of 1995 Systems qual

  Database portion of 1996 Systems qual Jeff Ullman's materials

  Human-Computer Interaction

  Reading List for HCI

  Operating Systems

  Reading List for Operating Systems

  ---

  Last modified: Mon Mar 1 6:19:23 PST 1999

  ---