Study Guides for the Written Ph.D. Qualifying Exams in CS

Theory Exam

The Theory exam will last 2-1/2 hours and cover topics in algorithms and complexity of computation, including data structures and necessary mathematical background. Topics come from CS 430: Introduction to Algorithms and CS 535: Design and Analysis of Algorithms. Notes (including all definitions and statements of the theorems) from the relevant chapters from the reference book will be provided together with writing paper. No other books, notes, or other help (calculators, cell phones, etc.) are allowed, except for writing implements. The difficulty level of the exam will be comparable to final exams from CS 535 (or see the sample exams). Topics from CS 430 are required at a level of rigor consistent with the study guide. Taking CS 530 can help students attain a sufficient level of rigor regarding the complexity of computation.

Previous Exams: F04, S05, F05, S06, F06, S07, F07, S08, S09, F09, S10, F10, S11, F11, S12

Reference: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 3nd edition. MIT Press, 2009.

Topics: The entire book excluding the following: Chapters 27 - 29, 31, and the starred subchapters.

Note: Starting Fall 2012 the formal languages and computability topics have been dropped from the Theory exam. Topics from CS 535 have replaced the topics from CS 530. The previous exams through Fall 2011 include questions from CS 430 and CS 530 instead of CS 430 and CS 535. In Spring 2012, students taking the exam were allowed to choose between CS 535 or CS 530. This choice is no longer available.

Note: there has been a change of topics starting fall 2011, and formal languages and computability are no longer required. Topics from CS 530 have been removed and topics from CS 535 have been added. The sample exams (through fall 2010) include questions from CS 430 and 530 instead of CS 430 and 535.

Study Guide for the old Theory Exam (through Spring 2011)

(» Click to open)

Systems Exam

The Systems exam will last 2 hours and include topics from CS 450 and CS 550. The exam will be closed-book, closed-notes.

Previous Exams: S05, F05, S11, S12

References

• Silberschatz, Galvin, and Gagne. Operating System Concepts, 7th edition, Wiley
• A. S. Tanenbaum, M. van Steen. Distributed Systems: Principles and Paradigms, 2nd edition, Prentice Hall.

Topics: Issues in communication (including remote procedure call; remote method invocation; and message- and stream-oriented communication); Processes and threads; Naming; Synchronization; Consistency and replication; Fault tolerance; Shared/Parallel/Distributed File Systems; Security in distributed systems; Client-Server Architecture; Code Migration and Scheduling.

Programming Languages Exam

The Programming Languages exam will last 2 hours and include topics from CS 536 (and from CS 440 as prerequisite material). The exam will be closed-book, closed-notes.

Previous Exams: F04, S05, F05, S06, F06, S07, F07, S08, F08, S09, S10, F10, S11, F11, S12, F12

CS 440 References

• A. V. Aho , R. Sethi, J.D. Ullman. Compilers: Principles, Techniques and Tools. Addison Wesley.
• K. C. Louden. Programming Languages, Principles and Practice. Thomson Publications.
• M. L. Scott. Programming Language Pragmatics. Morgan Kaufmann Publishers.

CS 440 Topics: Language design; Compilation and interpretation; Programming language syntax; Names, scopes and bindings; Parameter passing scheme; Semantic analysis; Control flow; Recursion; Data types and data abstractions.

CS 536 References

• David Gries. The Science of Programming. Springer-Verlag (ISBN 0-387-96480-0).
• Willem-Paul de Rover, et al. Concurrency and Verification - Introduction to Compositional and Non-compositional Methods. Cambridge University Press.
• K. M. Chandy, J. Misra. Parallel Program Design - A Foundation. Addison Wesley.
• Gregory R. Andrews. Foundation of Multithreaded, Parallel, and Distributed Programming. Pearson Addison Wesley.

CS 536 Topics

• Basic Program Semantics and Correctness: Deductive proofs; Predicates; Using assertions to document programs; Predicate transformer WP; Deterministic/non-deterministic semantics and proof rules (skip, abort, and composition commands; assignment, alternative, and iterative commands).
• Topics in Formal Methods: Hoare logics for shared-variable concurrency and for synchronous message passing; Transformational design and Hoare logic; Parallel program design (Parallelism and programming; Programming notation; Programming logic; Architectures and mappings) Proof techniques for shared variable programming and for distributed programming.