Ph.D. Qualifying Exam

Each Ph.D. student has to take (and pass) Ph.D. qualifying exam after finishing his/her required course work with 2,75 GPA. Ph.D. students who have the conditions must take CMP702 Qualifying Exam course in same semester. Ph.D. qualifying exam consists of a written part and an oral part.

  • Ph.D. Qualifying exam is offered each semester in final exam week. The examination committees are organized in April and November.
  • The written part contains 10 subject areas. The questions in the written part are at the undergraduate level and can cover the topics that are given under each subject area. The undergraduate courses related to each subject area are listed below wıth the topics that are covered these courses.
  • There are two questions from each subject area, and the student is asked to attempt only one of the questions from each subject area. Each question is graded out of 30 points.
  • The written part is given as two sessions on two different days. (150+150=300 minutes).
  • The oral part can contain the questions from the subject areas of the written part, the subject areas related to the candidate’s Ph.D. thesis area, and the candidate’s Ph.D. thesis.
  • The students are expected to be successful at both written and oral parts of the exam.

Written Part

  • The written part is given as two sessions and contains a total of 10 subject areas.
  • There are two questions from each subject area, and the student is asked to attempt only one question from each subject area.

Session 1: Theory

Data Structures and Algorithms

Related Courses:
  • BBM201 Data Structures
  • BBM202 Algorithms
  • Analysis of Algorithms
  • Sorting algorithms (elementary algorithms, mergesort, quicksort, heapsort)
  • Search algorithms (elementary algorithms, balanced trees, hashing)
  • Graph representations (directed, undirected)
  • Graph algorithms (graph search, centrality, minimum spanning tree, shortest path)
  • String algorithms (substring search, regular expressions, compression)
  • Data Structures
  • Performance Analysis, Space and Time Complexity
  • Multidimesional Arrays
  • Band, Sparse, Triangular Matrices
  • Stacks and Queues
  • Evaluation of Expressions
  • Array-based Linked Lists
  • Linked Lists
  • LL Applications (Stacks, Queues, Hashtables)
  • Doubly Linked Lists
  • Binary Trees
  • Tries
  • Graph Representation
  • Digraph
Main Reading Sources:
  • Algorithms, 4 th Edition, R. Sedgewick and K. Wayne, Addison-Wesley Professional, 2011.
  • Graph Theory with Algorithms and its Applications in Applied Science and Technology, S. Saha Ray, Springer, 2013.
Additional Reading Sources:
  • Introduction to Algorithms, 3 rd Edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, MIT Press and McGraw-Hill, 2009.
  • Social Network Analysis, 3 rd Edition, John Scott, SAGE Publications, 2013.

Discrete Mathematical Structures

Related Courses:
  • BBM205 Discrete Mathematical Structures
  • Logic: propositional logic, logical equivalence, predicates, quantifiers and logical reasoning
  • Sets, functions, sequences and sums, introductory discrete probability
  • Counting: Pigeonhole principle, permutations and combinations, binomial theorem
  • Mathematical reasoning: proof strategies, mathematical induction
  • Introduction to number theory: greatest common divisor, primes, Euclidean algorithm
  • Analysis of time complexity of algorithms and asymptotic notation
  • Advanced Counting: recurrence relations, solving recurrence equations, inclusion-exclusion principle
  • Graph theory and trees: graph families, graph parameters, matchings in graphs
  • Trees: tree parameters, tree traversals, minimum spanning trees
  • Graph isomorphism, Euler path, Euler circuit, Hamilton path, Hamilton cycle
  • Finding shortest paths, graph coloring, connectivity and planar graphs
Main Reading Sources:
  • R. Johnsonbaugh, "Discrete Mathematics", Seventh edition, Prentice Hall, 2009
  • K. Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill, 2012.

Automata and Formal Languages

Related Courses:
  • BBM401 Automata Theory and Formal Languages
  • Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA)
  • Regular Expressions and Regular Languages
  • Conversions among DFA’s, NFA’s and Regular Expressions.
  • The Pumping Lemma for Regular Languages and Properties of Regular Languages
  • Context-Free Grammars (CFG’s) and Context-Free Languages
  • Derivations, Parse Trees and Ambiguity
  • Pushdown Automata (PDA) and Equivalence of CFG’s and PDA’s
  • The Pumping Lemma for Context-Free Languages, and Properties of Context-Free Languages
Main Reading Sources:
  • J.E. Hopcroft, R. Motwani, and J.D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, 3rd Edition, Addison Wesley, 2007.
Additional Reading Sources:
    li>M. Sipser, "Introduction to The Theory of Computation", 2nd Edition, Course Technology, 2006.
  • Ü. Yarımağan, "Özdevinirler Kuramı ve Biçimsel Diller", Bıçaklar Kitabevi, 2003.

Algorithm Analysis

Related Courses:
  • BBM408 Algorithm Analysis
  • Algorithm Analysis
  • Growth Functions, Asymptotic Notations
  • Divide and Conquer Algorithms
  • Recurrence Equations and Solving Recurrence Equations
  • Sorting, Searching
  • Dynamic Programming
  • Greedy Algorithms
  • Amortized Analysis
  • Graph Algorithms
Main Reading Sources:
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein Introduction to Algorithms, MIT Press and McGraw-Hill, 2009.

Programming Languages

Related Courses:
  • BBM301 Programming Languages
  • Grammars, regular expressions.
  • Lexical analysis and parsing.
  • Lex and Yacc
  • Control flow.
  • Procedures, argument passing.
  • Evaluation and substitution.
  • Scope, binding, environments.
  • Procedure abstraction.
  • Side effects.
  • Abstract data types, encapsulation.
  • Message passing.
  • Type checking/inference.
  • Functional programming.
Main Reading Sources:
  • R. W. Sebesta, Concepts of Programming Languages, Pearson (Tenth Edition), 2012
Additional Reading Sources:
  • M. L. Scott, Programming Language Pragmatics (3rd Edition), 2009
  • B. C. Pierce, Types and Programming Languages, The MIT Press, 2002

Session 2: System

Data Management and Database Systems

Related Courses:
  • BBM371 Data Management
  • BBM471 Database Management Systems
  • Entity – Relationship Model
  • Relational data model
  • Integrity constraints and relational design
  • Relational Algebra - Relational Calculus
  • SQL : Standard Query Language
  • Storing and indexing (storing media, tree based indexes, key based indexes)
  • Storage Devices
  • File Structures
  • External sort
  • Query processing, optimization
  • Transactional management
  • Concurrency management
  • Recovery
Main Reading Sources:
  • Database Management Systems, Raghu Ramakrishnan, Johannes Gehrke, ISBN-10: 0072465638 | ISBN-13: 978-0072465631 | Edition: 3
  • Veri Tabanı Sistemleri, Ünal Yarımağan, Akademi Kitapevi, 2000

Operating Systems

Related Courses:
  • BBM341 Systems Programming
  • BBM342 Operating Systems
  • Process management
  • Process scheduling
  • Process syncronization
  • Deadlocks
  • Memory Management Strategies
  • Virtual memory management
  • File System
  • Implementing file Systems
Main Reading Sources:
  • Operating System Concepts, A. SilberSchatz, P. Galvin, and G. Gagne, 8nd ed., John Wiley & Sons.
Additional Reading Sources:
  • Modern Operating Systems, Andrew Tanenbaum, 3rd ed., Prentice Hall.
  • Bilgisayar İşletim Sistemleri, Ali Saatçi, 2. Baskı, Bıçaklar Kitabevi.

Logic Design and Computer Architectures

Related Courses:
  • BBM231 Logical Design
  • BBM234 Computer Organization
  • Boolean algebra and boolean functions
  • Minimization of boolean functions
  • Combinational logic
  • Memories, MUX, DEMUX, encoder, decoder and uses in design
  • Analysis and design of synchronous sequential circuits
  • Computer system performance analysis
  • Arithmetic for computers
  • Instruction set architecture
  • Single-cycle and pipelined processor design
  • Memory: caches and virtual memory
  • Multiprocessors
Main Reading Sources:
  • M. Morris Mano, Michael Ciletti, Digital Design, Prentice Hall, 5h Ed., 2012.
  • Patterson, David A., and John L. Hennessy, Computer organization and design: the hardware/software interface, Morgan Kaufmann, 5th Edition, 2013.

Computer Networks

Related Courses:
  • BBM451 Computer Networks
  • Packet Switching and Circuit Switching
  • Delay, Loss, and Throughput in Packet-Switched Networks
  • Principles of Network Applications
  • The Web and HTTP
  • FTP
  • SMTP
  • DNS
  • Peer-to-Peer Applications
  • Video Streaming and Content Distribution Networks
  • Transport-Layer Services
  • Multiplexing and Demultiplexing
  • Connectionless Transport: UDP
  • Principles of Reliable Data Transfer
  • Connection-Oriented Transport: TCP
  • Principles of Congestion Control
  • TCP Congestion Control
  • Virtual Circuit and Datagram Networks
  • What's Inside a Router?
  • The Internet Protocol (IP)
  • IPv4, IPv6
  • Generalized Forwarding & SDN
  • Routing Algorithms
  • Routing in the Internet: Inter-AS & Intra-AS Routing, BGP
  • Broadcast and Multicast Routing
  • SDN Control Plane
  • ICMP, ICMPv6, Network Management & SNMP
  • Error-Detection and -Correction Techniques
  • Multiple Access Links and Protocols
  • Switched Local Area Networks
  • Link Virtualization: A Network as a Link Layer
  • Data Center Networking
  • Wireless Links and Network Characteristics
  • WiFi: 802.11 Wireless LANs
  • Cellular Internet Access
  • Mobility Management: Principles
Main Reading Sources:
  • Jim F. Kurose, Keith W. Ross, Computer Networking: A Top-Down Approach, 7th Edition, 2017 (First 7 chapters)

Software Engineering

Related Courses:
  • BBM382 Software Engineering
  • BBM487 Software Engineering Lab.
  • Basic concepts of software engineering.
  • Types of computer systems and the software as a part of them.
  • The relation of software engineering to the systems engineering.
  • The scope of software engineering: Software development (analysis, design, coding, and test), software engineering management, software configuration management, software engineering processes, software engineering tools and methods, and software quality assurance.
  • Software metrics and software cost estimation.
  • Cost of software quality.
  • Software development process models and process reference models.
  • Basic phases of software development.
  • Object-oriented analysis and design concepts, and the Unified Modeling Language (UML).
  • UML views and diagrams.
  • Use-case, activity, class, package, interaction, state, component, and deployment diagrams.
  • The object-oriented development process and recommended usage of UML diagrams.
Main Reading Sources:
  • Sommerville I., Software Engineering, 9th ed., Addison-Wesley Professional, 2011.
  • Pilone D. & Pitman N., UML 2.0 in a Nutshell, 2nd ed., O'Reilly Media, 2005.
Hacettepe University Department of Computer Engineering
06800 Beytepe Ankara