One component of the Qualifier Requirment of PhD students in the Computer Science program (who have entered on or after the Fall, 2004 semester) is passing a set of Core Competency Exams. These exams are offered directly after the Spring semester. Students must take the exams at their earliest opportunity, and must pass all of the exams by the end of their second year. In addition, students must obtain a "high competency" score on at least two of the exams. If an exam is retaken, the score of the last exam taken is used.

This web page lists the topics and reading that form the material from which exam questions will be drawn. The material reflects what the faculty feels a student should take out of an undergraduate program in Computer Science. It is expected that students of the caliber we wish to have in our graduate program should be able to pass the exams after a quick review of the material

The reading and topic lists are given below. They are listed by core area:

• Analysis of Algorithms
• Theory of Computation
• Operating Systems
• Computer Architecture
• Compiler Design

Any questions on the reading lists should be directed to the CSE Department Graduate Program Committee Co-Chair.

Analysis of Algorithms

Introduction to Algorithms, 2nd Edition by by T. Cormen, C. Leiserson, R. Rivest, & C. Stein, The MIT Press, Cambridge, Massachusetts, 2001. (Chapters mentioned below are in this book.)

1. Algorithm Basics:

• Definitions, Properties (Ch. 1)
• Algorithm Performance Analysis (Ch. 2)
• Insertion Sort & MergeSort
• Growth of Functions (Ch. 3)
• Recurrences & their Solution (Ch. 4)
• Recursive Algs

2. Sorting & Order Statistics:

• Heapsort, Priority Queues (Ch. 6)
• Quicksort (Ch. 7)
• Lower Bounds, Sorting in Linear Time (Ch. 8)

3. Basic Data Structures:

• Stacks, queues, lists, graphs, trees (Ch. 10)
• Hashing (Ch. 11)
• Disjoint Sets Union/Find (Ch. 21)

4. Graph Algorithms:

• Bread-first & Depth-first Search (Ch. 22)
• Topological Sort
• Shortest Paths: Bellman-Ford, Dijkstra (Ch. 24)

5. Greedy Algorithms:

• Huffman Trees (Ch. 16)
• Minimum Spanning Trees: Kruskal's & Prim's algs (Ch. 23)

6. Dynamic Programming:

• Matrix-chain multiplication (Ch. 12)
• Floyd-Warshall's algorithm (Ch. 25)

7. P, NP, NP-completeness (Ch. 34):

• The Complexity Classes P & NP
• Polynomial-time Reductions among Problems
• NP-complete Problems, P=NP?

8. Miscellaneous:

• String Matching (Ch. 32)
• Convex Hull algs (Section 33.3)
• Polynomials and the Fast Fourier Transform (Ch. 30)

Theory of Computation

Theory of Computing: A Gentle Introduction by Efim Kinber, Carl Smith, Prentice Hall; 1st edition (December 15, 2000) ISBN: 0130279617

1. Introduction.

• Mathematical Preliminaries. (Section 1.4)

2. Finite Automata.

• Deterministic Finite Automata. (Section 2.1)
• Nondeterministic Finite Automata. (Section 2.2)
• Determinism versus Nondeterminism. (Section 2.3)
• Regular Expressions. (Section 2.4)
• Nonregular Languages. (Section 2.5)

3. Context Free Languages.

• Context-Free Grammars. (Section 3.1)
• Parsing. (Section 3.2)
• Pushdown Automata. (Section 3.3)
• Languages and Automata. (Section 3.4)
• Closure Properties. (Section 3.5)
• Languages That Are Not Context-Free. (Section 3.6)

4. Turing Machines.

• Definition of a Turing Machine. (Section 4.1)
• Computations by Turing Machines. (Section 4.2)
• Extensions of Turing Machines. (Section 4.3)
• Nondeterministic Turing Machines. (Section 4.4)
• Turing Enumerable Languages. (Section 4.5)

5. Undecidability.

• The Church-Turing Thesis. (Section 5.1)
• Universal Turing Machines. (Section 5.2)
• The Halting Problem. (Section 5.3)

Operating Systems

Primary reference (the current textbook in CSE 303): Chapters 1-6 in Modern Operating Systems, 2nd Ed., Andrew S. Tanenbaum, Prentice-Hall, 2001, ISBN 0-13-031358-0

Also permitted as an alternate reference for the same material: Chapters 1-14 in Operating System Concepts, 6th Ed., Silberschatz, Galvin and Gagne, John Wiley & Sons, 2003, ISBN 0-471-25060-0

• Types of operating systems
• OS feature migration
• Computer system organization from an OS standpoint
• System calls
• Processes and threads
• Process and thread scheduling: issues and algorithms
• Process synchronization and communication: race conditions, mutual exclusion, semaphores, monitors, message passing
• Deadlocks: detection, recovery, avoidance, prevention
• Memory management: swapping, virtual memory, paging, segmentation
• Page replacement algorithms
• I/O: device controllers, memory-mapped I/O, busy-waiting, interrupt-driven I/O, DMA
• Mass storage: disk hardware and formatting
• File systems: file naming conventions, file system structure, file operations
• File system implemention issues: directories, file system layout, disk space management

Sample Questions (PDF)

Computer Architecture

D. Patterson and J. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 2rd Ed., Morgan Kaufmann, 1998, ISBN 1-55860-428-6.

M. Arnold, Verilog Digital Computer Design: Algorithms into Hardware, PTR Prentice Hall, 1999, ISBN 0-13-639253-9.

Patterson and Hennessy, Chapter 2: Performance:

• Performance, Metrics, Speedup and Benchmarks (Sections 2.1-2.5)

Patterson and Hennessy, Chapter 3: MIPS ISA

• Operations (Section 3.2)
• Operands (Section 3.3)
• Instruction Representation (Section 3.4)
• Decision Instructions (Section 3.5)
• Procedures (Section 3.6)
• MIPS Addressing (Section 3.8)

Arnold, Chapter 2

• Algorithmic State Machines
• Register Transfer Notation
• Behavioral and Structural modeling
• Division Example

Patterson and Hennessy, Chapter 4: Computer Arithmetic

• Signed, unsigned (Section 4.2)
• Binary & hex representations (Section 4.2)
• Addition & Subtraction (Section 4.3)
• Logical Operations (Section 4.4)
• ALU Construction (Section 4.5)
• Multiplication (final implementation only, NO Booth's Algorithm) (Section 4.6)
• Division (final implementation only) (Section 4.7)
• Floating point representation, addition and multiplication (Section 4.8)

Patterson and Hennessy, Chapter 5: Processor Datapath & Control

• Clocking (Section 5.1)
• Single Cycle Datapath (Section 5.2-5.3)
• Multicycle MIPS Implementation (Section 5.4)
• Exceptions (Section 5.6)

Patterson and Hennessy, Chapter 6: Pipelining

• Overview (Section 6.1)
• Datapath, structural Hazards (Section 6.2)
• Control, control hazards (Section 6.3)
• Data Hazards and Forwarding (Section 6.4)
• Data Hazards and Stalls (Section 6.5)
• Branch Hazards (Section 6.6)
• Exceptions (Section 6.7)

Patterson and Hennessy, Chapter 7: Memory Hierarchy

• Caches (Section 7.2)
• Cache Performance (Section 7.4)
• Virtual Memory (Section 7.4 )

Patterson and Hennessy, Chapter 8: I/O

• Disks (Section 8.3)
• Buses (Section 8.4)
• I/O Interaces (Section 8.5)

Compiler Design

Compilers: Principles, Techniques and Tools by Aho, Sethi and Ullman, Addison Wesley, ISBN 0-201-10088-6.

Chapters 1, 2, 3, 4, 5, 6, 8.1-8.5, 9.8-9.10, 10.1-10.3

Topics: Lexical Analysis, Syntax Analysis, Syntax-Directed Translation, Type Checking, Intermediate Code Generation, Code Generation, Code Optimization