# Graduate

## Ph.D. Qualifying Exam (Pre-Fall 2017)

Current Ph.D. Qualifying Exam Guidelines

Students who are admitted to the Ph.D. program are expected to pass the Qualifying Examination within their first three semesters in the program. Poor performance by a student in any one area of the Qualifiers may result in the student failing the entire Qualifiers based on the judgment of the committee. Students are expected to pass on the first attempt. If a student does not pass on the first attempt, he/she may request in writing to repeat the exam. Based upon the student's academic standing and on the results of the qualifiers, the Graduate Examination Committee may grant a second test. Students who fail the Qualifying Examination the second time will be dropped by the program.

Students may withdraw their applications in writing one week before the exam is scheduled. Late withdrawals are not accepted and no shows are counted as one failed attempt.

The required areas are (1) Computer Architecture, (2) Operating Systems, and (3) Theory of Algorithms. Instructions for the core exams follow.

The CSE qualifying examinations are normally held the third Friday and following Monday after the official start of classes in the fall and spring semesters.

Recommended texts along with a selection of topics in each area are as follows.

### OPERATING SYSTEMS

**Texts:**

- Operating Systems Concepts, 8th edition, by Silberschatz & Galvin
- Distributed Operating Systems, latest edition, by A. Tanenbaum

**Topics:**

- Stand-Alone Operating Systems – (Process Scheduling & Coordination, Deadlocks, Main and Virtual Memory Management, File Management, Disk Storage Management)
- Distributed Operating Systems – (General Concepts, Fully Distributed Process Coordination and Communication, Client/Server model, RPC's, Deadlocks, Distributed File Systems)

**The Operating Systems Exam is a closed book, closed notes exam.**

### COMPUTER ARCHITECTURE

**Texts:**

- Computer Organization & Design, The Hardware/Software Interface, 3rd/4th Edition, David Patterson & John Hennessy, Morgan Kaufmann Publishers, 2007.
- Computer Architecture: A Quantitative Approach, 4th Edition, John Hennessy & David Patterson, Morgan Kaufmann Publishers, 2006.
- Advanced Computer Architecture: Parallelism, Scalability, Programmability, K. Hwang, McGraw-Hill Computer Science Series, 1993.

**Topics:**

- Basic computer architecture principles, instruction set design, performance metrics, analysis, Benchmarking, basic pipelining principles, processor design principles (datapath and control unit design), RISC, CISC, fixed and floating point computer arithmetic, impact of VLSI on computer architecture
- Multiprocessors, multicomputers, SIMD/MIMD Computers, Interconnect architectures, performance metrics and laws, scalability, parallel algorithms and architectures
- Advanced processor technology, superscalar, superpipeline, vector processing, TLP, ILP, methods to improve ILP, memory hierarchy, virtual memory, cache memory, shared/distributed memory, cache coherence, instruction pipeline design, pipeline hazards, pipeline scheduling, instruction reordering

**The Computer Architecture Exam is a closed book, closed notes exam.**

### THEORY OF ALGORITHMS

**Texts:**

- Algorithm Design (latest edition) by Jon Kleinberg and Eva Tardos, Addison Wesley, 2005.
- Introduction to Algorithms (Third Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2001.

**Topics:**

- Topics in discrete mathematics: logic, set theory, number theory, combinatorics, discrete probability theory, mathematical induction, recursion
- Basics of algorithm analysis: time/space complexity, growth of functions, solving recurrences (Chapters 1-4 of CLRS and Chapters 1-2 of KT)
- Sorting algorithms (Chapters 6-9 of CLRS)
- Data structures: linked lists, binary search trees, stacks, queues, hash tables, priority queues, heaps, disjoint sets (Chapters 6, 10-12, 21 of CLRS and Sections 2.5, 3.3, 4.6 of KT)
- Graph algorithms: breadth-first search, depth-first search, topological sort, strongly connected components, minimum spanning trees, single-source shortest paths (Chapters 22-25 of CLRS and Chapter 3 of KT)
- Greedy algorithms (Chapter 16 of CLRS and Chapter 4 of KT)
- Divide and conquer (Chapter 5 of KT)
- Dynamic programming (Chapter 15 of CLRS and Chapter 6 of KT)
- Network Flow (Chapter 26 of CLRS and Chapter 7 of KT)
- NP and Computational Intractability (Chapter 34 of CLRS and Chapter 8 of KT)
- Parallel algorithms
- Approximation Algorithms

This exam is a comprehensive exam that can contain questions from different courses. For example, the Algorithms section might require knowledge of basic data structures and mathematics taught during your undergraduate studies.

**The Theory of Algorithms Exam is closed book, closed notes exam.**

Apart from questions that require some problems to be solved, there may be subjective type questions. For example, from the topics covered in the syllabus, you may be asked to define a concept, write a formal statement of a main result, give a supporting proof or explanation, state some applications of an algorithm or concept, etc. It is expected that there will be a mixture of problems to test knowledge as well as problem solving skills.

### Sample Exams

These links to sample questions are only intended to be used as guides. Actual questions in your exams may be formatted differently, cover different subtopics, and may vary in degree of difficulty.