This is the topics and reading list for the Ph.D. Preliminary Examination. This reading list is the official description of the exam topics.
- Design and Analysis of Algorithms
- Basic analysis tools: growth functions and asymptotic analysis
- Algorithm design strategies: greedy, divide and conquer, dynamic programming
- Analysis & design: hashing, basic searching & sorting, elementary graph algorithms
- Suggested reading: Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 2nd edition.
Chapters: 2-4, 6-8, 11-16, 22-25 (excluding sections 4.4, 11.5, 12.4, 16.4, 16.5, 24.4, 24.5, 25.3).
- Data Structures & Fundamentals of Programming
- C++ and object oriented programming, inheritance, polymorphism, and dynamic variable binding
- Abstract data types and fundamental data structures including: stacks, queues, lists, binary trees, graphs, vectors, maps, sets, containers/iterators, hashing
- Dynamic data structures: dynamic arrays, linked lists, pointers, memory allocation/de-allocation, destructors, copy constructors, assignment/copy semantics
- Expression notations: prefix, postfix, infix
- Recursion
- Suggested reading: Main & Savitch, Data Structures and other objects using C++, 4th edition.
Chapters: 1-10, 14, 15
- Computer Operating Systems
- Process management: processes, threads, CPU scheduling, Process synchronization
- Memory management: main memory, virtual memory
- Storage management: file system interface and implementation, deadlocks, disk structure, OS I/O systems
- Suggested reading: Silberschatz, Galvin, & Gagne, Operating Systems Concepts, 8th edition.
Chapters: 1-13.