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),
 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
 StatementLevel 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 userdefined types
 Data representation issues, memory management
 Runtime environment organization
 Code generation and optimization
References:
 Ravi Sethi, Programming Languages Concepts and Constructs, 2nd ed., AddisonWesley.
 Alfred Aho, Ravi Sethi, Jeffrey Ullman, and Compilers: Principles, Techniques, and Tools, AddisonWesley, 1985.
2. Database Systems
Topics:
 Data Models, ER 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)
 ProcessorPeripheral 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, flipflops, minimization of state tables, state assignment
 Higher level digital system design using SSIMSI 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 widearea 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, PrenticeHall, 1992.
 A. S. Tanenbaum, Computer Networks 4th ed., PrenticeHall, 2003.
 W. Stallings, Computer Networking with Internet Protocols and Technology, PrenticeHall, 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, redblack trees)
 Advanced data structures (Btrees, 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
 Singlesource shortest paths
 Allpairs shortest paths
 Maximum flow
 NP Completeness
References:
 T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press / McGrawHill 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; Numbertheoretic 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,.
 Nondeterministic 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 (multitape, multidimensional , 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 NPcomplete problems ; Cook's theorem and some basic NPcompleteness proofs

PSPACEcomplete problems ; definitions and basic proofs, 
Definition of contextfree grammars and applications, 
General grammars (or rewriting systems), 
Recursive functions and basic equivalence result between TMs , general grammars and recursive functions, 
Recursion theorem , selfreproduction 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., AddisonWesley, 2000.