CS PhD program offers five written qualifying exams in the following core areas of CS to test if a PhD student has an acceptable mastery of basic undergraduate level knowledge in computer science and engineering:
- Programming Languages and Compiler Design
- Database Systems
- Computer Architecture and Digital Design
- Operating Systems and Computer Networks
As part of the requirements for an admission to PhD candidacy, students enrolled in the CS PhD program must pass
- three written qualifying exams in CS, including the Theory qualifying exam,
- one written qualifying exam in Engineering Mathematics, or one of the FENS PhD programs (including CS),
- an oral qualifying exam in CS.
General information about PhD qualifying exams at SU can be found at
Topics covered in each CS core area are listed below:
1. Programming Languages and Compiler Design
Topics Related to Programming Languages :
- Describing Syntax and Semantics
- Names, Bindings, Type Checking, and Scopes
- Data Types
- Expressions and the Assignment Statement
- Statement-Level Control Structures
- Abstract Data Types
- Functional Programming Languages
- Logic Programming Languages
- Object Oriented Design
Topics Related to Compiler Design :
- Lexical processing: tokenization and lexical analysis
- Basics of symbol table organization, type checking and handling of user-defined types
- Data representation issues, memory management
- Runtime environment organization
- Code generation and optimization
- Ravi Sethi, Programming Languages Concepts and Constructs, 2nd ed., Addison-Wesley.
- Alfred Aho, Ravi Sethi, Jeffrey Ullman, and Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1985.
2. Database Systems
- Data Models, E-R Model. Database Architecture.
- Relational Algebra and Calculi.
- Data Manipulation Languages: SQL,QUEL, QBE.
- Functional Dependency Theory. Normalization of Relations.
- Multivalued and Join Dependencies.
- Query processing and optimization techniques
- Indexing techniques
- Transaction processing. Concurrency Control Techniques
- Serializability. Locking, deadlocks, timestamping.
- Security and integrity, authorization, and encryption
- Raghu Ramakrishnan, Johannes Gehrke, Database Management Systems, second edition, McGraw Hill, 2000.
3.Computer Architecture and Digital Design
- Processor: Datapath and Control
- Pipelining (pipelined control, hazards, exceptions, performance)
- Memory Hierarchy (caches, virtual memory)
- Processor-Peripheral Interfacing
- Number systems and conversion, boolean algebra, the assertion level concept
- Minterm and maxterm expansions, Karnaugh maps and Quine McCluskey minimization
- Combinatorial logic circuit design, NAND and NOR gate based design
- State machines and sequential circuits, flip-flops, minimization of state tables, state assignment
- Higher level digital system design using SSI-MSI blocks such as multiplexers/decoders, adders, memory and programmable gate arrays
- Bus oriented systems
- Asynchronous sequential circuits, flow tables, timing hazards
- David A. Patterson, John L. Hennessy, Computer Organization and Design The Hardware/Software Interface, Morgan Kaufmann Publishers, 1994.
- M. Morris Mano, Charles R. Kime, Logic and Computer Design Fundamentals 2nd Edition, Prentice Hall.
4. Operating Systems and Computer Networks
Topics Related to Operating Systems:
- Processes & Interprocess Communication
- Process Scheduling
- Memory Management
- File Systems
- Naming, security, and reliability
- Resource sharing, and remote execution
Topics Related to Computer Networks:
- Network architectures
- Local and wide-area networks
- Network technologies and topologies
- TCP/IP protocols (application, transport and network layers)
- Routing, addressing, naming, multicasting, switching, internetworking
- Congestion/flow/error control
- Medium access control
- Data Link Layer protocols
- Physical layer basics
- Quality of service
- Network security
- A. S. Tanenbaum, Modern Operating Systems, Prentice-Hall, 1992.
- A. S. Tanenbaum, Computer Networks 4th ed., Prentice-Hall, 2003.
- W. Stallings, Computer Networking with Internet Protocols and Technology, Prentice-Hall, 2004.
Topics Related to Data Structures and Algorithms:
- Asymptotic notation, complexity analysis
- Data structures (stacks, queues, priority queues, linked lists, hash tables, binary search trees, AVL trees, red-black trees)
- Advanced data structures (B-trees, binomial trees, Fibonacci heaps, data structures for disjoint sets)
- Sorting and order statistics (heapsort, quicksort, sorting in linear time, medians and order statistics)
- Dynamic programming
- Greedy algorithms
- Amortized analysis
- Elementary graph algorithms (search, topological sort, strongly connected components)
- Minimum spanning trees
- Single-source shortest paths
- All-pairs shortest paths
- Maximum flow
- NP Completeness
- T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press / McGraw-Hill Book Company, 1994.
- Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ 2nd Ed. Addison Wesley
Topics related to Combinatorics and Graph Theory:
- Methods of proof (including the Principle of Mathematical Induction)
- Sets, relations, and functions (Algebra of sets; Countable vs. uncountable sets; Product sets, relations, and functions; Transitive closure and equivalence relations; Number-theoretic functions)
- Logic (Boolean algebras and Boolean functions; Propositions and truth tables (Propositional Calculus); Predicates and quantifiers (Predicate Calculus))
- Sums and recurrences, Finite Calculus
- Integer Functions: Floors, Ceilings, Mod, recurrences and sums involving integer functions
- Binomial Coefficients and properties
- Generating Functions, solving recurrences using generating functions, convolutions
- Graph Theory: Planarity, graph coloring, Hamiltonian Circuit, Euler Paths
- Graham, Knuth and Patashnik, Concrete Mathematics, Addison Wesley, 1992.
Topics Related to Automata Theory and Formal Languages:
- Deterministic Finite State Automata DFA ; definitions , tabular and graphical representations and uses of DFA as language acceptors,.
- Non-deterministic Finite Automata NDFA with and without epsilon (invisible) transitions ; conversion of NFDA to equivalent DFA ; minimal state DFA and algorithms to compute them,
- Algebra of regular expressions RE ; language definitions as RE expressions ; conversions between various finite automata and REs,
- Computational complexity of basic algorithms involving finite automata and REs
- Turing Machines TMs ; decidability, semidecidability and computability ; various versions of TMs (multi-tape, multi-dimensional , random access, nondeterministic etc.) and equivalences between them,
- The halting problem and other derived undecidable problems ; Turing computability
- Basic definitions and problems related to computational complexity ; polynomial , NP and NP-complete problems ; Cook's theorem and some basic NP-completeness proofs
PSPACE-complete problems ; definitions and basic proofs,
Definition of context-free grammars and applications,
General grammars (or re-writing systems),
Recursive functions and basic equivalence result between TMs , general grammars and recursive functions,
Recursion theorem , self-reproduction and consequences,
- P. Linz, An Introduction to Formal Languages and Automata 3rd ed., Jones and Bartlett Pub. , 2000.
- J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation 2nd ed., Addison-Wesley, 2000.