PhD Minor Comprehensive Examination
The Fall Minor Comprehensive Examination is held in October. The
Spring Minor Comprehensive Examination is held in March.
To register for the exam, submit the Comprehensive Exam Registration form
(PDF) to the
Graduate Program Coordinator, in Gould-Simpson Room 901.
The Minor Comprehensive Exam format is a two hour exam with questions
requiring 15-20 minutes to answer.
The purpose of the Master's Examination is to ensure that students possess a working knowledge of the fundamental areas of computer science. Unlike examinations in individual courses, this exam is designed to test the student's ability to integrate and apply knowledge from the core areas. As a result, the Master's Examination does not simply test a student's recall of course material.
Curriculum
The examination is based on the core computer science courses and their principal prerequisites. The courses are grouped into three core areas:
- theory and algorithms --- 473, 545, and 573
- systems and architecture --- 452, 552, and 576
- languages and compiling --- 453, 520, and 553
The MS exam will have one question related to each of these 9 courses. In each core area, students are to answer any two of the three questions.
Topics
The main exam topics are:
- Operating systems topics include relation of the OS to architecture, process synchronization, OS structure, memory management (including virtual memory), storage allocation, file systems, and protection mechanisms.
- Architecture topics include instruction set design, processor implementation (including pipelining), memory systems design (including caching and support for virtual memory), and advanced architectures (including vector and parallel architectures).
- Compiler topics include binding times, instruction sets, symbol tables, lexical analysis, procedure call mechanisms, recursive descent and bottom-up parsing, type systems, code generation, register allocation, dataflow analysis and code optimization.
- Programming languages topics include data types and polymorphism, procedure mechanisms and recursive procedure implementation, static and dynamic referencing environments, parameter passing, functional and imperative languages, data encapsulation, and methods for semantic specification.
- Theory topics include regular and context free languages, finite automata, pushdown automata, closure properties of formal languages, pumping lemmas, undecidability, complexity, and NP-completeness.
- Algorithms topics include basic data structures, algorithm design paradigms such as divide-and-conquer and dynamic programming, balanced search trees, hashing, sorting and searching, basic graph algorithms, algorithm analysis, recurrence relations and asymptotics.
The examination also assumes mastery of other prerequisite material such as data structures and software design.
Grading
The following is a guideline for the determination of pass/fail grades on the MS Examination. MS Exam questions will be assigned letter grades, which will be converted into points in the following way: A = 4.0, AB = 3.5, B = 3.0, BC = 2.5, etc. Grades in MS core courses will be converted to points in the usual way: A = 4, B = 3, etc. (Only grades that count officially towards the MS degree at the University of Arizona will be considered for this.) The points for the two exam questions in each MS core area will be added to the points for one core course in that area (if a student has taken both core courses in an area, their maximum will be used). Students will be required either (a) to get at least 8 points in each core area; or (b) to get a total of at least 27 points.
Preparation
To prepare for the exam, students should review their recent CSc courses and the following references. Copies of most of these books are on reserve under Computer Science 699 (or the corresponding course) at the Main Library.
- Aho, A. V., Sethi, R., and Ullman, J. D., Compilers: Principles, Techniques and Tools, Addison Wesley, 1986.
- Corman, T.H., Leiserson, C.E., and Rivest, R.L., Introduction to Algorithms, McGraw Hill, 1990.
- Fischer, A. E. and Grodzinsky, F. S., The Anatomy of Programming Languages, Prentice-Hall, 1993.
- Friedman, D. P., Wand, M., and Haynes, C. T., Essentials of Programming Languages, McGraw-Hill, 1992.
- Hennessy, J. L. and Patterson, D. A., Computer Architecture: A Quantitative Approach, Morgan Kaufmann, 2nd Edition, 1996.
- Hopcroft, J. E., and Ullman, J. D., Introduction to Automata Theory, Languages and Computation, Addison Wesley, 1979 (chapters 1-9).
- Manber, U., Introduction to Algorithms, A Creative Approach, Addison Wesley, 1989.
- Papadimitriou, C. H., Computational Complexity, Addison-Wesley, 1994.
- Patterson, D. A. and Hennessy, J. L., Computer Organization and Design: The Hardware/Software Interface, Morgan Kaufmann, 1994.
- Peterson, J., Silberschatz, A., and Galvin, P., Operating System Concepts, Addison Wesley, 4rd Edition, 1994. (The second and third edition authored by Peterson and Silberschatz will also be a sufficient reference).
- Sethi, R., Programming Languages - Concepts and Constructs, Addison-Wesley, 1989.
- Sipser, Introduction to Theory of Computation, ITP-WAD 1997.
- Tanenbaum, A., Modern Operating Systems, Prentice-Hall, 1992.
- Watt, D. A., Programming Language Syntax and Semantics, Prentice-Hall, 1991.
|
