Â鶹´«Ã½

Ph.D. Preliminary Examination Reading List

This is the topics and reading list for the Ph.D. Preliminary Examination. This reading list is the official description of the exam topics.

  1. 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).
  2. 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
  3. 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.