Ph.D. Qualifying Examination

Rules

PhD students who are accepted with MS degree have to take the PhD qualifying exam during their first five semesters. Those PhD students who are accepted without an MS degree have to take the PhD qualifying exam during their first seven semesters. The semesters with leave of absence are included in these limits. Students must have successfully completed all elective courses and the seminar course before taking the exam. Students who have not taken the PhD qualifying exam in the specified period are considered unsuccessful. Students who failed in the exam can take it in the following semester. The examination is offered in fall and spring semesters. The date and place of the examination is announced by the department each semester.

The qualifying examination is composed of a written and an oral part. Students who were successful in the written examination take the oral examination in the same semester. Students who were successful in the written examination but unsuccessful in the oral examination have to take only the oral examination in the following semester. (Please see Lisansüstü Eğitim ve Öğretim Yönetmeliği for details.)

Written Part

The goal of the written exam is to test the breadth knowledge of a student in computer engineering and science topics. The written part consists of three core subjects that are basic components of any undergraduate program in computer engineering and science. Each core subject has two or three subjects that typically correspond to individual courses in the undergraduate curriculum. Finally, each subject has several topics that correspond to chapters and concepts in these courses.

The core subjects, their contents and main textbooks are given in the sequel. The textbooks are simply guides to students and it should be clear that the examination intends to measure the students' knowledge in the basic concepts rather than the details of some specific subject. The student should be able to integrate the material he/she has studied in related courses and be ready to answer questions in these areas.

The written exam is administered as follows:

• In the beginning of the semester, after discussing with the thesis advisor, the student selects one of the three core subjects as his/her main core subject. The student will then be responsible from all subjects and all topics within this selected main core subject.
• The student also selects one subject from each of the other two core subjects. The student will then be responsible from all topics within these two subjects.

For example, a student selects theory as her main core subject. She will be responsible from all subjects, i.e., data structures, algorithms, and automata theory and formal languages, within this core subject. Suppose she also selects programming languages as the subject from the programming systems core subject and operating systems as the subject from the computer systems core subject. Then, she will be responsible from all topics within programming languages and operating systems. She will not be responsible from object-oriented software engineering, database systems, and computer organization in this example scenario.

Oral Part

The oral exam tests the depth knowledge of a student in subjects related to his/her major area of research and thesis topic. The aim of the qualifying examination is to assess how well the student has integrated core subjects and his/her major subject.

Core Subjects

• Programming Systems
• Computer Systems
• Theory

Programming Systems

• Programming Languages

  • Topics:
    • Describing Syntax using Regular Expressions and Context-Free Grammars.
    • Lexical Analysis and Parsing.
    • Names, Bindings and Scopes.
    • Data Types.
    • Expressions and Assignment Statement, Statement-Level Control Structures.
    • Subprograms and Implementation of Subprograms.
    • Concurrency, Exception Handling and Event Handling.
    • Functional Programming.
  • Text:
    • Robert W. Sebesta, Concepts of Programming Languages, 11/E, Pearson, 2017.

• Object-Oriented Software Engineering

  • Topics:
    • Understanding the OO Worldview.
    • OO Analysis.
    • OO System and Object Design.
    • Design Patterns and Architectural Styles.
    • OO Software Testing.
    • Visual Modeling with Unified Modeling Language (UML).
  • Texts:
    • Bernd Bruegge and Allen H. Dutoit, Object-Oriented Software Engineering, Using UML, Patterns, and Java, Third Edition, Prentice-Hall, 2010.
    • Timothy C. Lethbridge and Robert Laganiere, Object-Oriented Software Engineering, McGraw-Hill, 2001.

• Database Systems

  • Topics:
    • Data Models, Entity/Relationship Model, Relational Model.
    • Relational Algebra.
    • Relational Query Languages. SQL.
    • Functional Dependency Theory. Normalization of Relations.
    • Storage and File Organization.
    • Tree-Structured Indexing. ISAM, B+ Trees.
    • Hash-Based Indexing. Static and Dynamic Hashing.
    • Query processing and optimization techniques.
    • Transaction processing. Serializability, Recoverability
    • Concurrency Control Protocols.
  • Texts:
    • A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, Sixth Edition, Mc Graw Hill, 2011.
    • R. Ramakrishnan, J. Gehrke, Database Management Systems, Third Edition, McGraw-Hill, 2003.

Computer Systems

• Computer Organization

  • Topics:
    • Combinational Logic Design.
    • Sequential Logic Design.
    • Digital Building Blocks: Adders, ALU, Counters, Shift Registers.
    • Memory Arrays, Register Files.
    • Processor: Datapath and Control.
    • Pipelining.
    • Memory Hierarchy (caches, virtual memory).
    • I/O systems.
  • Texts:
    • David A. Patterson, John L. Hennessy, Computer Organization and Design The Hardware/Software Interface, Morgan Kaufmann, Fourth Edition, 2008.
    • David Money Harris, Sarah L. Harris, Digital Design and Computer Architecture, Morgan Kaufmann, Second Edition, 2013.

• Operating Systems

  • Topics:
    • Processes and Threads.
    • Interprocess Communication.
    • CPU Scheduling.
    • Synchronization.
    • Deadlocks.
    • Memory Management.
    • Virtual Memory.
    • File Systems (Interface and Implementation).
    • Mass Storage Structure.
    • Input/Output and I/O Systems.
  • Texts:
    • A. Silberschatz, G. Gagne, P. B. Galvin, Operating System Concepts, John Wiley & Sons, Inc, 2013.

Theory

• Data Structures

  • Topics:
    • Fundamental principles of counting including rules of sums and product, permutations and combinations.
    • Set theory including the principle of inclusion and exclusion, axioms of probability, conditional probability, independence, discrete random variables and expectation.
    • Fundamentals of logic and integers including mathematical induction, recursive definitions, Cartesian products and relations, functions, floor, ceiling and modulo, pigenhole principle, partial orders, equivalence relations and partitions.
    • Sums and recurrence relations: first and second order linear recurrence relations, the method of generating functions.
    • Asymptotic notation, complexity analysis.
    • Lists, stacks, queues.
    • Trees (binary trees, binary search trees, AVL trees, 2-3 trees, 2-3-4 trees, red-black trees).
    • Hashing (open addressing, separate chaining).
    • Priority queues (heaps).
  • Texts:
    • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, An Applied Introduction, Addison-Wesley, Fifth Edition, 2003.
    • Frank Carrano, Data Abstraction and Problem Solving with C++, Addison Wesley, Fifth Edition, 2007.
    • M. A. Weiss, Data Structures and Algorithm Analysis in C++, Addison Wesley, Fourth Edition, 2013.

• Algorithms

  • Topics:
    • Augmenting data structures (dynamic order statistics, interval trees).
    • Advanced data structures (B-trees, Fibonacci heaps, van Emde Boas trees, disjoint sets).
    • Sorting and order statistics (heapsort, quicksort, sorting in linear time, medians and order statistics).
    • Dynamic programming.
    • Greedy algorithms.
    • Amortized analysis (aggregate, accounting, and potential methods, dynamic tables).
    • Elementary graph algorithms (search, topological sort, strongly connected components).
    • Minimum spanning trees (the algorithms of Kruskal and Prim).
    • Single-source shortest paths (the algorithms of Bellman-Ford and Dijkstra, difference constraints and shortest paths).
    • All-pairs shortest paths (shortest paths and matrix multiplication, the algorithms of Floyd-Warshall and Johnson).
    • Maximum flow (Ford-Fulkerson method, maximum bipartite matching)
  • Texts:
    • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, third edition, MIT Press and McGraw-Hill, 2009
    • S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, New York: McGraw-Hill, 2006

• Automata Theory and Formal Languages

  • Topics:
    • Finite Automata.
    • Regular expressions, properties of regular sets.
    • Context-free grammars, properties of context-free languages.
    • Pushdown automata.
    • Turing machines.
    • Complexity, NP-Completeness.
    • The Chomsky hierarchy.
  • Texts:
    • M. Sipser, Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, 2013.
    • J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd Edition, Addison-Wesley, 2001.