Ph.D. Qualifying Written Exam

Ph.D. Qualifying Written Exam

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
  • Theory

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),
and then
  • an oral qualifying exam in CS.

General information about PhD qualifying exams at SU can be found at
http://fens.sabanciuniv.edu/en/phdqualifying

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
  • Procedures
  • Abstract Data Types
  • Functional Programming Languages
  • Logic Programming Languages
  • Object Oriented Design

Topics Related to Compiler Design :

  • Lexical processing: tokenization and lexical analysis
  • Parsing
  • 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

References:

  • 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

Topics:

  • 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

References:

  • Raghu Ramakrishnan, Johannes Gehrke, Database Management Systems, second edition, McGraw Hill, 2000.

3.Computer Architecture and Digital Design

Topics:

  • 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

References:

  • 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
  • Input/Output
  • Deadlocks
  • 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

References:

  • 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.

5. Theory

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

References:

  • 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

References:

  • 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,

References:

  • 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.