Computer Engineering Ph.D. Qualifying Exam Guidelines
The following guidelines are set for the Ph.D. Qualifying Examination in Computer Engineering, in addition to rules and regulations at Middle East Technical University Student Handbook. These are effective as of the first semester of 20062007 academic year.
General Information

Ph.D. Qualifying exam consists of a written part and an oral part. The candidate is considered successful when he/she passes both parts.

Ph.D. Qualifying exam is given twice a year each May and November.

The candidate should get the approval of his/her advisor and petition the department at least one month before the exam.

The candidate failing to pass the Ph.D. Qualifying exam is given a second chance in the subsequent offering of the exam. Failure in the second attempt leads to the dismissal of the student from the Ph.D. program.
Written Exam
The written exam consists of two parts; Core and Breadth.
Core part
The Core part of the exam covers the following 7 main topics:

Data Structures (CENG 213),

Algorithms (CENG 315),

Discrete Math (CENG 223),

Theory of Computation (CENG 280),

Programming Languages (CENG 242),

Operating Systems (CENG 334),

Digital Design and Computer Architecture (CENG 232 & CENG331)
The questions from the Core part will be at the undergraduate level and will cover the content that is listed in the Core subjects table below. In the exam, there will be two questions from each topic, and the student will be asked to attempt only one question from each. Each subject is graded over 20 points and the student is considered successful if her/his total grade is 84 out of 140 (which corresponds to 60% of the maximum grade). In addition, if the student is unsuccessful in the core exam, s/he will be exempt from the subjects on which s/he scored at least 14 out of 20. In the subsequent exam, s/he will be expected to score 60% of the maximum grade from the remaining subjects only. The student reserves the right to “not be exempt” if s/he wishes. The exemption status from a course is valid only for the next exam session.
Breadth part
The Purpose of the Exam To evaluate the student’s ability and potential to conduct research at the doctoral level and to encourage the student to have an earlier involvement in research
Expectations from the Student before the Exam

To choose a topic within the student’s research field.

To conduct a literature survey on this topic.

To make a contribution to this topic as explained below.

To prepare the study in the “IEEE conference proceedings format ” in at least 6 pages.

To submit this work to the examination committee (jury) latest 1 week before the exam.
Expectations from the Student during the Exam

To present the student’s study (30 minutes)

Answer questions about the study (10 minutes)

Answer general questions in the Ph.D. field of the student (20 minutes, if the jury finds it necessary the question answer part can be extended).
Expected Contribution The student can choose to make one or more of the following types of contributions:

Literature evaluation: A literature survey is required in every study, but those students who select this category will be expected to conduct a more detailed literature survey by identifying the advantages and disadvantages of the previous studies, compare them with each other, and provide an analysissynthesis of the literature in the selected topic.

Implementation: The student will implement a paper in the selected topic which should be chosen together with the student’s advisor and produce results by changing various parameter values if applicable.

Novel approach: The student will propose a novel approach to a selected problem and implement this approach to produce results. This category includes improving an existing algorithm using a different approach.

Comparison: The student will compare two or more algorithms that are selected with the student’s advisor, and discuss the results obtained as a result of this comparison.

Theoretical contribution: The student will propose a novel theoretical approach such as a formula, theory, proof, etc. and show the correctness, utility, and reasoning behind this approach.

Case study: The student will apply an existing method or process to a realistic problem and discuss the results that are obtained.
Grading The success of the student will be measured according to the table below. The student whose weighted grade total is 60 or higher will be considered successful.
Ratio  Point [0100]  
%40  Written work  
%20  Presentation and questions related to the presentation  
%40  General questions in the selected field  
Weighted Total:  100 
General Principles about the Administration of the Exam

For every student who will take this exam, a jury comprised of 5 people with Ph.D. degree and experts in the selected field will be formed by the qualifying exam committee. This jury will include the student’s advisor. It is crucial that the jury members read the study before the exam and prepare questions to be asked during the exam.

The written work prepared by the student must be original. It should not be put together by copying and pasting from the previous work.

Jury members could check the document submitted by the student against plagiarism using http://www.ithenticate.com/to which METU has a subscription.

A study prepared for the master’s thesis cannot be directly used for his exam. A contribution is expected to be made during the Ph.D. studies even if the topic remains the same.

An article (published or unpublished) written by the student as the primary author can be used for this exam. However, the same article cannot be used by more than one student, and if it was published it should not be published more than 12 months before the exam.

In case of failure for the first time, a new topic can be chosen or the jury must indicate the expectations from the student for the second exam if the same topic will be used.

In case the student is taking this exam for the second time from the same topic, a supporting document explaining the changes from the previous version must be provided by the student to the jury along with the latest version of the study.
Ph.D. Qualifying Exam – Core Part Syllabus
Course  Topics  Resources 

Data Structures  Algorithm analysis for data structures  * Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ (3rd ed.), Addison Wesley, 2006 
Lists, stacks, queues  
Trees  
Priority queues  
Hashing  
Algorithms  Analysis of Algorithms  * Introduction to Algorithms, T. H. Cormen, C. E. Lieserson, R. L. Rivest, C. Stein, Mc GrawGill 
Sorting, Searching  
String Processing  
Graph Algorithms  
Greedy Approach  
Divide and Conquer Algorithms  
Dynamic Programming  
Exhaustive Search  
Complexity Classes, NPcompleteness  
Discrete Mathematics  Propositional Logic: Logic, Equivalences  * K.H. Rosen, Discrete Mathematics and its Applications, (Sixth Edition) McGrawHill, 2007. * W.K. Grassmann and J.P. Tremblay, Logic and Discrete Mathematics: A Computer Science Perspective, Prentice Hall, 1996 
Predicate Logic: Predicates and Quantifiers, Nested Quantifiers, Methods of Proof  
Sets and Functions: Sets, Set Operations, Functions, Growth of Functions, Complexity of Algorithms  
Integers: Integers and Division, Integers and Algorithms  
Induction and Recursion: Sequences and Summations, Mathematical Induction, Recursive Definitions and Structural Induction, Recursive Algorithms  
Counting: Permutations and Combinations, Recurrence Relations, Solving Recurrence Relations, Generating Functions, Inclusion and Exclusion  
Relations: Relations and Their Properties, Representing Relations, Closure of Relations, Equivalence Relations, Partial Orderings  
Graphs: Int to Graphs, Graph Terminology, Representing Graphs, Connectivity, Euler and Hamiltonian Paths, Shortest Path Problem, Graph Coloring  
Trees: Int to Trees, Applications of Trees, Spanning Trees, Min Spanning Trees  
Theory of Computation  Finite Automata and Regular Expressions: Alphabets and languages, Finite representations of languages,Deterministic finite automata, Nondeterministic finite automata, Equivalence of DFA and NFA, Finite automata versus regular languages, Pumping lemma and its applications, State minimization  * Elements of the Theory of Computation, H.R.Lewis, C.H.Papadimitriou, (2nd ed.), PrenticeHall, 1998. * Introduction to the Theory of Computation, M.Sipser, Course Technology, 2005. 
Pushdown Automata and Context Free Grammars: Parse trees and derivations,Pushdown automata, Pushdown automata versus contextfree grammars, Closure properties,Pumping theorem and its applications, Deterministic PDAs  
Regularity and contextfreeness of languages  
Turing Machines and unrestricted grammars: Turing machines – definition and examples, Computing with TMs, Recursive and recursively enumerable languages, Extensions of TMs, Nondeterministic TMs, Unrestricted grammars  
ChurchTuring thesis, universal Turing machines  
Halting problem  
Programming Languages  Storage structures, control structures, scope and binding  * Programming Language Concepts and Paradigms, D.A. Watt, PrenticeHall, 1990. * Programming Languages: Concepts and Constructs, R. Sethi, Addison Wesley, 1996. 
Data and procedural abstraction  
Type systems  
Lexical and syntactic description of languages  
Objectoriented programming languages  
Functional programming languages  
Logic programming languages  
Operating Systems  Operating Systems Structures  * Modern Operating Systems, A.S. Tanenbaum, PrenticeHall, ISBN 0135957524, 1992. * Operating System Concepts, A. Silberschatz, P.B. Galvin, (4th ed.), AddisonWesley, ISBN 0201504804, 1994. * Design and Implementation of the 4.3BSD Operating System, S.J. Leffler, M.K. McKusick, M.J. Karels, J.S. Quarterman, AddisonWesley, ISBN 0201061961, 1989. 
Processes, Threads and Their Management  
Process and Processor Scheduling  
Process Synchronization  
Interprocess Communication  
Deadlocks  
Memory Management  
Storage Management (I/O Processing, File Systems)  
Protection and Security  
Digital Design and Computer Architecture  Combinational Circuits  * Digital Design, M. Mano, PrenticeHall, ISBN 0132129949, 1991. * Computer Organization, C. Hamacher, Z.G. Vranesic, S. Zaky, (4th ed.) McGrawHill, ISBN 0071143238, 1996. * Computer Organization and Design, D.A. Patterson, J.L. Hennessy, (2nd ed.), MorganKaufmann, ISBN l55860491X, 1998. * Computer Systems: A Programmer’s Perspective by Randal E. Bryant and David R. O’Hallaron Prentice Hall, 2003 
Combinational Circuit Minimization: Algebraic and Karnaughmap minimization  
Synchronous Sequential Circuits  
Registers, Counters  
RAM, ROM, PLA, and PAL  
Arithmetic Logic Unit, Multiplication and Division, Floating Point operations  
Pipelining: Hazards, Forwarding, Branch Prediction  
Memory Hierarchy: Interleaving, Cache Memory, Virtual Memory  
I/O Systems: Buses, I/O Interfaces, Interrupts, DMA 
Ph.D. Qualifying Exam – Breadth Part Syllabus
Course  Topics  Resources 

Artificial Intelligence  Uninformed and Heuristic Search  * Artificial Intelligence: A Modern Approach, S.Russell, P.Norvig, Prentice Hall, 1995. * Logical Foundations of Artificial Intelligence, M.R.Genesereth, N.Nilsson, Morgan Kaufmann, 1988. 
Game Playing  
Constraint Satisfaction and Propagation  
Knowledge and Reasoning  
Theorem Proving  
Planning  
Reasoning with Uncertainty  
Machine Learning: Learning from examples (supervised learning, decision trees, Regression and classification, ANN, SVM), Learning probabilistic models (Bayesian learning, Naive Bayes classifiers, EM algorithm), Reinforcement Learning (passive RL, active RL)  
Computer Graphics  Rendering Pipeline: Major stages of the rendering pipeline  * Computer Graphics: Principles and Practice, Foley, Van Dam, Feiner, Hughes, (2nd ed.), Addison Wesley, 1995. * Computer Graphics, Hearn, Baker,(2nd ed.), Prentice Hall, 1994. * Fundamentals of Computer Graphics, Shirley and Marschner, (3rd ed.), AK Peters, 2009. * Realistic Ray Tracing, Shirley and Morley, (2nd ed.), AK Peters, 2003. 
Geometric Transformations: Homogeneous coordinates, Vectors, points, normals, Translation, scaling, rotation, sheer transformations (2D and 3D)  
Raster Algorithms: Line rasterization, Triangle rasterization, Antialiasing  
Viewing: Parallel projections, Perspective projections, Clipping, Viewport transformation  
Visible Surface Detection: Backface elimination, Zbuffer algorithm  
Phong Shading Model: Ambient Light, Diffuse Reflection, Specular Reflection  
Polygonal Surface Shading: Flat shading, Goraud shading, Phong shading  
Texturing: Generating of uv coordinates (for both 2D and 3D texture mapping), Mipmapping, Bilinear interpolation, Bump mapping  
Volume Rendering: Marching cubes algorithm, Direct volume rendering  
Three Dimensional Object Representations: Hermite curve, Natural cubic splines, Bezier curves and surfaces, Geometric continuities, Joining curves and surfaces  
Ray tracing: Parametric lines, Parametric and implicit surfaces, Rayobject intersections (triangle, sphere, plane), Basic ray tracing algorithm, Generating simple shadows with ray tracing, Accelleration structres (bounding boxes, octtree, kdtree)  
Radiosity: Basic radiosity algorithm, Radiosity equation, Hemicube method for form factor calculations, Jacobi iteration and Gauss Seidel for solving Ax=b  
Natural Language Processing  Linguistic knowledge representation and propagation  * Speech and Language Processing, Jurafsky and Martin, PrenticeHall, 2000. * Natural Language Understanding, J.Allen,2.ed,BenjaminCummings, 1995. * Prolog and Natural Language Analysis, F.C.N. Pereira, S.M. Shieber, CSLI, 1987. 
Computational aspects of Morphology  
Syntactic representation in NLP (phrase structure, dependency, unification)  
Parsing strategies for natural languages (bottomup,topdown, mixed)  
Parsing decisions and improvements (determinism, nondeterminism, charts)  
Grammar formalisms (dependency grammars, categorical grammars, phrasestructure grammars) and hierarchy for natural languages  
Handling nonlocal dependencies  
Compositional semantics: Lambdacalculus and logical form  
Basics of dataintensive linguistics (ngrams, language models, classifiers)  
Database Systems  Physical data organization  * Database Management Systems, Raghu Ramakrishnan, McGrawHill. * Principles of Database and Knowledgebase Systems, volume 1, Ullman, Computer Science Press. * Database system concepts, Silberschatz & Korth, McGrawHill. 
Data models  
Relational database design theory (normalization)  
Relational query languages  
Integrity and security  
Transaction management  
Concurrency control  
Recovery techniques  
Query optimization  
Numerical Computation  Numerical stability of algorithms and conditioning of problems  * Numerical Methods, G.Dahlquist, A.Björck, PrenticeHall. * Matrix Computations, G. Golub, C.F. Van Loan, THe Johns Hopkins University Press. * Yousef Saad, Iterative Methods for Sparse Linear Systems, SIAM. 
Linear systems: Norms, matrix norms, Gaussian elimination, forward and backward substitution, pivoting, Householder’s reflection, Given’s rotations, GramSchmidt method, QR, Singular Value Decomposition, Linear Least Squares problems and curve fitting, Relaxation methods (Jacobi, GaussSeidel)  
Matrix eigenvalue Problems: Power method, inverse iteration, Rayleigh Quotient, and QR iterations, Jacobi method, Arnoldi and Lanczos processes, Krylov subspace methods for solution of linear systems (GMRES, CG, BiCGStab), preconditioning  
Finding roots of nonlinear equations: Bisection, Secand, Newton’s methods, fixed point iteration  
Interpolation: Lagrange interpolation, Newton’s interpolation and divided differences, Runge’s phenomenon, Splines, Orthogonal polynomials  
Numerical integration: Interpolatory quadrature, Composite quadrature rules  
Software Engineering  Lifecycles and process models  * Software Engineering: a Practitioners Approach, R.S. Pressman, (4th ed.), McGrawHill. * Software Engineering, Sommerville, (4th ed.), AddisonWesley 
Software project management  
Specification and modeling techniques  
Traditional, object oriented and component based approaches  
Software metrics  
Software quality  
Testing and integration methods  
Maintenance  
Pattern Recognition and Image Analysis  Image Transform: Discrete Fourier transform (FFT excluded), Discrete Haar Wavelet transform  * Digital Image Processing, R. C. Gonzales and R. E. Woods, PrenticeHall, 3rd edition, 2008. * Pattern Classification, R.O. Duda, P. E. Hart and D. G. Stork, WileyInterscience, 2nd edition, 2000. * Computer Vision, L. G. Shapiro and G. C. Stockman, Prentice Hall, 2001. 
Image Enhancement Techniques: Point Processing (basic intensity transformations), Histogram processing, Image negation, power law, log transformations, Spatial Filtering, Convolution (smoothing, sharpening)  
Image Compression: Redundancy and measuring image information, Huffman coding  
Morphological Operations: Erosion, dilation, opening, closing  
Image Segmentation: Edge detection (Canny, Hough transform), Thresholding  
Image Representation and Description: Chain codes, Polygons, Regional descriptors  
Texture: Texelbased Texture Descriptions, Quantitative Texture Measures  
Contentbased image retrieval: Image Distance Measures (Color, Texture and Shape Similarity Measures), Precision, Recall and Fscore Performance Analysis  
Motion from 2D images: Image Subtraction  
Stereo Vision: Matching: Cross Correlation, Symbolic Matching, The Epipolar and The Ordering Constraints  
Bayesian Decision Theory: Gaussian Density Estimation, Classifier Discriminant Functions  
Maximum Likelihood Method: Gaussian Density Estimation  
Nonparametric techniques: Parzen Window, KNearest Neighbor  
Unsupervised learning: Mixture Resolving, Unsupervised Bayes Method, Maximum Likelihood Method  
Clustering: Kmeans Clustering, Hierarchical Clustering, Component Analysis  
Neurocomputing  Learning and generalization  * Neural Computing: Theory and Practice, P.D. Wasserman. * Introduction to the Theory of Neural Computation, J. Hertz, A. Krogh, and R.G. Palmer, AddisonWesley, 1991. * Neural Networks: A Comprehensive Foundation, S. Haykin, Macmillan, 1994. 
Multilayer perceptrons and the backpropagation algorithm  
Hopfield model  
Recurrent networks  
Unsupervised learning and self organizing maps  
Adaptive resonance theory  
Radial basis function networks  
Higher order neural networks  
Neurodynamics  
Parallel Computing  Parallelism and classification of parallel computers: Performance bottlenecks, Classification of parallel computers and applications, Programming models for parallel computers  * Introduction to Parallel Computing, by Grama, Gupta, Kumar, and Karypis, Addison Wesley, 2003. * Parallel Programming for Multicore and Cluster Systems, Rauber and Runger, Springer Verlag, 2010. * Sourcebook of parallel computing, Jack Dongarra, et.al. Kaufmann, 2002. 
Pipelining and vector processing: Instruction pipelining, superscalar execution, and instruction scheduling, Pipelining arithmetic operations, Performance analysis of pipelined operations  
Interconnection topologies and implementing various communication operations: Metrics for evaluating performance of interconnection networks, Point to point and collective communication operations and their implementation  
Task decomposition and design of parallel algorithms: Principles of parallel algorithm design, Task interaction and dependency graphs, Graph partitioning/clustering, Load balancing  
Analysis of parallel algorithms: Speed improvement and efficiency, Amdhal’s law, Gustafson’s law, Weak and strong scalability  
Parallelism in various applications (e.g. matrix problems in scientific applications, sorting and searching, etc.)  
Distributed Systems  Time Synchronization  * Distributed Systems: Principles and Paradigms, 2nd edition, A.S. Tanenbaum, M. Van Steen, Pearson Higher Education, 2007. * Distributed Systems: Concepts and Design 4th edition, J. Dollimore, T. Kindberg, G. Coulouris, AddisonWesley, 2006. * Principles of Concurrent and Distributed Programming, 2nd edition, B. BenAri, AddisonWesley, 2006. 
Coordination  
Structuring Distributed Systems  
Process Interaction and Group Communication  
Distributed File Systems  
Concurrency Control  
Distributed Shared Memory  
Basics of FaultTolerance and RealTime Systems  
Programming Languages and Compilers (Advanced)  Typed lambda calculus  * Foundations for Programming Languages, (first six chapters) J.C. Mitchell, MIT Press, 1996. * Compilers: Principles, Techniques, and Tools, A.V. Aho, R. Sethi, J.D. Ullman, AddisonWesley, 1986. 
Semantic specification of languages: Operational, denotational and axiomatic approaches  
Algebraic specification of data types  
Partial correctness proofs with before and after assertions  
Lexical and syntactic analysis of languages  
Syntaxdirected translation, attribute grammars  
Abstract machines, intermediate languages  
Code generation  
Networked Systems  The principles and techniques employed in computer and wireless networks; the sevenlayer protocol suite known as ISO model  * Computer Networking: A top down approach, 6th Ed., J.F. Kurose, K.W. Ross, AddisonWesley, 2012. * Computer Networks, 5th Ed., A.S. Tanenbaum, Prentice Hall, 2011. * Cryptography and Network Security: Principles and Practice, 5th Ed., W. Stallings, Prentice Hall, 2011. 
Data link layer issues (medium access control, reliable data transfer)  
Network layer issues (packet versus circuitswitching, routing algorithms, IP, QoS)  
Transport layer issues (error control, flow control, congestion control, endtoend argument, TCP, UDP)  
Network programming (socket interface)  
Performance evaluation of computer networks  
Security of computer networks (confidentiality, integrity, and authentication)  
Wireless networks (Cellular networks, mobility management, WLAN)  
Bioinformatics  Sequence analysis, next generation sequencing: Genome annotation, Computational evolutionary biology, Comparative genomics, Genetics of disease, Analysis of mutations in cancer  * Understanding Bioinformatics, M. Zvelebil and J.O. Baum, Garland Science, 2008. * Bioinformatics: the machine learning approach, 2nd Ed., Baldi and S. Brunak, MIT press, 2001. * Principles of Computational Cell Biology, V. Helms, WileyBlackwell, 2008. 
Gene and protein expression, gene regulation  
Structural bioinformatics: Protein folding problem, prediction of secondary/tertiary structure, Structural alignment, Multiple structural alignment, Protein docking  
Functional classification of proteins, human genome annotation  
Statistical modeling of biological data  
Biological Text Mining  
Bioimage Informatics: Highthroughput image analysis  
Biological networks and computational systems biology 