Qualifying Exams for the Ph.D. Programs

Students are allowed at most two attempts to pass the qualifying exams. Only the failed areas need be retaken. Deadlines for taking the exams are given in the following table.

The result of an exam may be Pass, Fail, or Conditional Pass. For a conditional pass, the Committee will decide what condition the student must meet. For example, the student could be required to take a course or do some other assigned task.

Written and Oral Qualifying Exam Deadlines	For Students Entering the Program With a
	Bachelor's Degree in CS		Master's Degree (not necessarily in CS)
	Full-time	Part-time	Full-time	Part-time
First attempt at exams	5th semester		3rd semester	The semester during which they complete 24 credit hours
Second attempt at exams	6th semester		4th semester	The following semester

Notes:

• Students in the "old program" (pre-Fall 2003) do not take written qualifying exams.
• For these purposes, the semester following Spring is Fall. (Summer is ignored.)

The written qualifying exam tests three areas: Theory, Systems, and Programming Languages.

Theory Exam Information

The Theory exam will last 2 1/2 hours and cover topics in algorithms, complexity, computability, and formal languages. Topics come from CS 532 and CS 535. (CS 530 and an undergraduate course in formal languages is a valid substitute for CS 532.) The exam will consist of three problems related to material from the reference books below. Copies of relevant chapters from the reference books 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 532 or CS 535.

Systems Exam Information

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

Programming Languages Exam Information

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.

Exam Results

The results of the written exams will be available within ten days of the exam. After that, a student who has failed a subject has ten days to submit a written request for re-examination of the exam to the PhD coordinator. The request must include an explanation of why the student believes the score of the exam is incorrect. The graduate committee should answer the request for re-examination within ten days.

Previous Written Exams Available for Study
Theory	Fall 2004, Spring 2005, Fall 2005, Spring 2006, Fall 2006, Spring 2007, Fall 2007, Spring 2008
Systems	Spring 2005, Fall 2005
Programming Languages	Fall 2004, Spring 2005, Fall 2005, Spring 2006, Fall 2006, Spring 2007, Fall 2007

Study Guide for the Theory Exam
CS 530 Reference Michael Sipser. Introduction to the Theory of Computation. Brooks Cole.	CS 530 Topics Sipser, Chapters 1, 2, 3, 4, 5, 7.
CS 535 Reference T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 2nd edition. MIT Press.	CS 535 Topics Cormen, et al., Chapters 2, 3, 4 (without 4.4), 6, 7, 8, 9, 10, 11 (without 11.5), 12 (without 12.4), 13, 14, 15, 16 (without 16.4 and 16.5), 17, 19, 20, 21 (without 21.4), 22, 23, 24, 25, 26 (without 26.4 and 26.5), 34.

Study Guide for the Systems Exam
CS 450 and 550 References Silberschatz, Galvin, and Gagne. Operating System Concepts, 6th edition, Wiley A. S. Tanenbaum, M. van Steen. Distributed Systems: Principles and Paradigms, 2nd edition, Prentice Hall.	CS 550 Topics Issues in communication including Remote procedure call Remote method invocation Message- and stream-oriented communication Processes and threads Naming Synchronization Consistency and replication Fault tolerance Distributed file systems Security in distributed systems

Study Guide for the Programming Languages Exam
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 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 A Hoare logic for shared-variable concurrency A Hoare logic 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 Proof techniques for distributed programming

The purpose of the oral qualifying exam is to judge the research capabilities of a student. It is to be determined whether or not the student is capable of the academic elements that constitute the research process. These elements may be categorized as:

• A scholarly review of a topic.
• A formal description of a problem.
• Familiarity with techniques that may be useful in solving the problem.
• Innovative ideas useful to solving the problem.
• A capability to present this work in written as well as oral form.

It is expected that the student will address the above requirement by presenting one or more research problems. The student should carefully review each problem, exhibit knowledge of techniques required to solve the problems, propose partial or full solutions, and show prospects for further research, if possible. While the student may address more than one problem, the student should guard against simply reviewing a number of problems. It is possible that the student has published results based on the presented research. This would be additional evidence of the student's research capabilities.

The following procedural rules apply from Spring 2004 onward:

• The PhD coordinator will coordinate the exam.
• The student will be examined by a faculty group that excludes the advisor. Each group will decide the format of the exam. This could be:
  • A description of research of the student's choice.
  • A specific paper/topic assignment for the student.
• A written report may be required.
• The examination methodology should be announced to the student well in advance.
• The qualifier is to be held at the beginning of the semester. The date, time, and schedule should be announced at least two weeks in advance.
• The exam will be closed.
• A review of the examination will be given to the student along with the result of the exam within a week of the exam.