CS PhD program offers written qualifying exams in the following **basics, core** and **specialization** areas of CS to test if a PhD student has an acceptable mastery of basic undergraduate level knowledge in computer science and engineering:

**CS Basics**

- Data Structures and Algorithms (CS300, CS301)

**Core Areas**

- Programming Languages and Compiler Design (CS305, CS402)
- Database Systems and Software Engineering (CS306, CS308)
- Computer Architecture and Digital Design (CS303, CS401)
- Operating Systems and Computer Networks (CS307, CS408)
- Automata Theory and Theory of Computation (CS302, CS407)

**Specialization areas:**

- Computer Graphics (CS405)
- Machine Learning (CS412)
- Artificial Intelligence (CS404)
- Cryptography and Network Security (CS432)

As part of the requirements for an admission to PhD candidacy, students enrolled in the CS PhD program must pass:

- the Data Structures and Algorithms exam;
- two qualifying exams from the
*core area exams;* - another written qualifying exam in CS (
*can be a core or specialization area exam*) -OR- Engineering Mathematics -OR- one of the other FENS PhD programs; - an oral qualifying exam in CS after successfully passing the 4 written exams.

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

### 1. Data Structures and Algorithms

#### Topics

- 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)
- Recurrences
- 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

### 2. 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 Programming Languages

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

### 3. Database Systems and Software Engineering

#### Topics Related to 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

#### References

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

#### Topics Related to Software Engineering

- Software development processes
- Agile software development
- Software modelling (UML)
- Requirements engineering
- Software architecture
- Object oriented design
- Software design patterns
- Software verification and validation

#### References

- Object Oriented Software Engineering: Practical Software Development using UML and Java (2nd edition), Timothy C. Lethbridge and Robert Laganiere, McGraw-Hill, 2005, ISBN 0-07-710908-2
- Software Engineering (10th edition), Ian Sommerville, Pearson, 2016, ISBN
978-0133943030

### 4. 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.

### 5. 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
- Network architectures

#### Topics Related to Computer Networks

- 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 (reference).
- W. Stallings, Computer Networking with Internet Protocols and Technology, Prentice-Hall, 2004 (main text).

### 6. Automata Theory and Theory of Computation

#### Topics

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

### 7. Computer Graphics

#### Topics

- Overview of graphics systems, applications
- Graphics and raster graphics algorithms for drawing in 2D
- Geometrical transformations in 2D and 3D
- Viewing in 3D
- Computer animation principles
- Color and shading; Shaders
- Texture mapping
- Illumination and Radiosity
- Modeling shapes with polygonal meshes
- Modeling curves: implicit, explicit and parametric; emphasis on cubic polynomials
- Surface modeling: Bicubic Bezier polynomials, splines, nurbs
- Visible surface determination
- Virtual Environments

#### References

### 8. Machine Learning

#### Topics

- Basics of probability and statistics
- Parameter estimation, MLE, MAP
- Model evaluation
- Model complexity, overfitting, bias/variance, regularization
- Supervised classification models

- K-NN
- Decision trees
- Bayes classifier
- Naive bayes classifier
- Logistic regression
- Support vector machines
- Neural networks
- Deep learning fundamentals
- Ensemble methods

- Regression

- Linear regression
- Polynomial and Ridge regression
- Regression trees

- Dimensionality reduction

- Feature selection, extraction
- PCA

- Clustering

- K-means
- Gaussian Mixture Models
- Spectral clustering

#### References

- Introduction to Machine Learning by Ethem Alpaydin,
- Pattern Recognition and Machine Learning by Christopher M. Bishop
- Machine Learning by Tom Mitchell,
- Pattern classification by Richard O. Duda, Peter E. Hart [and] David G. Stork.
- Machine Learning: A Probabilistic Perspective by Kevin R Murphy

### 9. Artificial Intelligence

#### Topics

- Search Algorithms

- Solving problems by searching [RN, Ch3]
- Blind search: breadth-first search, uniform cost search, depth-first search, depth-first iterative deepening [RN, Ch3]
- Heuristic search: best-first search, A* search, iterative-deepening A*, weighted A* [RN, Ch3]
- Local search: hill-climbing search, simulated annealing, local beam search, genetic algorithms [RN, Ch4]
- Adversarial search: minimax algorithm, alpha-beta pruning, depth-limited search with evaluation functions, expectimax search [RN, Ch5]
- Backtracking search: constraint satisfaction problems (CSPs), constraint propagation, forward checking, arc/path consistency, backtracking search for CSPs, local search for CSPs [RN, Ch6]

- Knowledge Representation and Reasoning

- Propositional logic: satisfiability, entailment, deduction by resolution, SAT, DPLL, representing combinatorial search problems in propositional logic [RN, Ch7]
- First-order logic (FOL): satisfiability, entailment, deduction by resolution, representing knowledge in FOL [RN, Ch8 & Ch9]
- Planning: Situation Calculus, planning by FOL resolution, STRIPS, ADL, planning by searching [RN, Ch10]
- Reasoning under uncertainty: quantifying uncertainty, Bayesian networks (BNs), semantics of BNs, exact inference in BNs, variable elimination algorithm, approximate inference in BNs, sampling methods [RN, Ch13 & Ch14]
- Decision making under uncertainty: preferences, utilities, policies, decision trees/networks, value of information, Markov decision processes, value iteration, policy iteration [RN, Ch16 & Ch17]

- Learning [RN, Ch18 ]

- Supervised learning: decision trees; Bayes classifier; linear regression; neural networks
- Gradient descent
- Model Evaluation: overfitting, loss
- Ensembles

#### References

- [RN] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (3rd Edition).

### 10. Cryptography and Network Security

#### Topics

- Cryptography and Computer and Network Security Concepts
- Classical (Historical) Encryption Techniques
- Symmetric Cryptography, Block Ciphers and Related Cryptosystems (AES, DES, 3DES, etc.)
- Block Cipher Modes of Operation
- Random Bit Generation and Stream Ciphers
- Public-Key Cryptography, RSA and DH
- Digital Signatures
- Cryptographic Hash Functions
- Message Authentication Codes
- Key Management and Distribution
- User and Message Authentication Protocols
- Transport-Level Security (SSL, TLS, SSH)
- Electronic Mail Security and Related Protocols
- IP Security
- Firewalls
- Intrusion Detection Systems

#### Reference

- W. Stallings, Cryptography And Network Security: Principles And Practice, 6th or 7th ed., Pearson, 2016. Missing topics can be found in earlier versions of that book or as online chapters (if you cannot find, please write to Albert Levi)