PhD Preliminary Exam Reading List

Graduate Studies Committee 

PhD Preliminary Examination 
Spring 2018
Topics & Reading List

1. Data Structures

  • C++ and object oriented programming

  • Abstract data types

  • Fundamental data structures including:

                stacks, queues, lists, binary trees, trees, graphs

                vectors, maps, sets, containers and iterators

  • Dynamic data structures: dynamic arrays, linked lists

  • Expression notations: prefix, postfix, infix

  • Binary tree traversals: preorder, postorder, inorder

  • Hashing, 2-3-4 trees, red-black trees

  • Recursion

Suggested reading: Main & Savitch, "Data Structures and other Objects Using C++", Addison Wesley.
Chapters: 1-11, 15

2. Operating Systems

  • Process management: processes, threads, CPU scheduling, Process synchronization

  • Memory management: main memory, virtual memory.

  • Storage management: file system interface and implementation, disk structure, OS I/O systems

Suggested reading: Silberschatz, Galvin, & Gagne, Operating Systems Concepts, 8th edition.
Chapters: 1-6, 8-13.

3. 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, Chapters: 2-4, 6-8, 11-16, 22-25 (excluding sections 4.4, 11.5, 12.4, 16.4, 16.5, 24 .24n, d2 4e.d5i,t i2o5n..3 ).