|
Ph.D. Qualifying Exams
Requests for an exam are due two months before the exam date. To register for an exam, send email to
Therese Michael (tmichae1 /at/ cs.gmu.edu), indicating which exams you wish to take.
Upcoming Exam Dates
August 11-15, 2008
January 5-9, 2009
August 10-14, 2009
Artificial Intelligence Ph.D. Qualifying Exam
-
Primary course
-
CS 580 (Artificial Intelligence)
-
Primary textbook
-
S. J. Russell and P. Norvig. Artifical Intelligence: A Modern Approach. Prentice Hall, 2nd edition, 2003.
|
Topic
|
Description
|
Readings (Russell and Norvig)
|
|
Search Methods
|
1. Uninformed search methods (breadth-first, depth-first, uniform-cost search)
2. Heuristic search methods (hill-climbing, best-first, A*)
3. Constraint Satisfaction
4. Game playing (mini-max, alpha-beta prunning, heuristic search)
|
Ch II Problem Solving (sections 3-6)
|
|
Knowledge Representation and Reasoning
|
1. First-order logic and natural deduction
2. Clausal form of logic and resolution theorem proving
3. Production systems (forward and backward chaining)
4. Ontologies, frame systems and semantic networks
5. Planning
6. Uncertainty and Probabilistic Reasoning
|
Ch III (sections 7-11)
Ch V (sections 13-14)
|
|
Learning
|
1. Learning from observations (decision tree learning, version space learning)
2. Explanation-based learning
3. Statistical Learning (complete data, instance-based, and neural networks)
|
Ch VI (sections 18-20)
|
|
Communication and Perception
|
1. Natural language processing (lexicographics, syntax, semantics)
2. Perception
|
Ch. VII (sections 22-24)
|
Databases Ph.D. Qualifying Exam
-
Primary course
-
INFS 614 (Database Management)
-
Primary textbook
-
Database Management Systems (3rd Ed.), Ramakrishnan and Gehrke, McGraw-Hill, 2003.
-
Alternative textbook
-
Database System Concepts (5th Ed.), Silberschatz, Korth, and Sudarshan, McGraw-Hill, 2005.
|
Topic
|
Description
|
Readings (R&G)
|
Readings (SK&S)
|
|
Basic concepts
|
1. Managing data
2. Objectives of database systems
3. Historical perspective
4. Database system architecture
5. Transaction management
|
Chapter 1
|
Chapter 1
|
|
Database design and the ER model
|
1. Database design overview
2. Basic concepts of the ER model
3. Integrity constraints in the ER model
4. ER diagrams
5. Advanced ER features
|
Chapter 2 (Sections 2.1-2.6)
|
Chapter 6 (Sections 6.1-6.8)
|
|
The relational model
|
1. Basic structures
2. Integrity constraints (domain, key, foreign key)
3. Converting ER diagrams to relation schemes
4. The relational algebra
5. The relational calculus
|
Chapter 3 (Sections 3.1-3.6)
Chapter 4 (Sections 4.1-4.4)
|
Chapter 2 (Sections 2.1-2.3, 2.5)
Chapter 5 (Sections 5.1-5.2)
Chapter 6 (Section 6.9)
|
|
SQL
|
1. Data definition and modification
2. Basic retrieval, ordering, null values
3. Aggregation, nesting, derived relations
4. Views, assertions, triggers
5. Embedded SQL
|
Chapter 5 (Sections 5.1-5.8)
|
Chapter 3 (Sections 3.1-3.10)
Chapter 4 (Sections 4.1-4.2, 4.4)
|
|
The theory of database design
|
1. Design issues
2. Functional dependencies (closure, attribute closure, Armstrong's axioms)
3. Normal forms (BCNF and 3NF)
4. Decompositions (lossless and dependency preserving)
5. Normalization algorithms
|
Chapter 19 (Sections 19.1-19.6)
|
Chapter 7 (Sections 7.1-7.5)
|
Language Processing Ph.D. Qualifying Exam
-
Primary course
-
CS 540 (Language Processing)
-
Primary textbook
-
A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques and Tools, 2nd ed., Addison-Wesley, 2006.
-
Alternative textbook
-
A. V. Aho, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley, 1986.
-
Alternative textbook
-
K. D. Cooper and L. Torczon, Engineering a Compiler, Morgan Kaufmann, 2004.
-
Alternative textbook
-
A. Appel, Modern Compiler Implementation in C, Cambridge University Press, 1998. Benjamin/Cummings, 1991.
|
Topic
|
Description
|
Readings (Aho, Lam, Sethi, and Ullman)
|
|
Lexical Analysis
|
Function of lexical analysis, token specification,token recognition
|
Ch. 3 (omit 3.9)
|
|
Syntax Analysis
|
Context free language specification, FIRST and FOLLOW set generation, Top-down parsing (recursive, table driven) algorithms and table generation, Bottom-up parsing algorithms and SLR table generation
|
Ch. 2.4, Ch. 4
|
|
Syntax Directed Translation and Attribute Grammars
|
Synthesized and inherited attributes, Writing attribute grammars, Synthesized attribute eval. for LR parsing
|
Ch. 2.3, Ch. 5.1-5.3
|
|
Types
|
Type systems, Type evaluation, Polymorphism, Type inference
|
Ch. 6.3, 6.5
|
|
RT Environments
|
Static and Stack Storage allocation, Runtime addressing, Parameter passing, Garbage collection
|
Ch. 7
|
|
Intermediate Code
|
Types of intermediate languages expression, Control flow, Array addressing
|
Ch. 6
|
|
Code Generation and Optimization
|
Control flow graphs, DAG representations, Register allocation, Basic optimizations, Iterative data-flow analysis, Loops
|
Ch. 8.1, 8.4-8.8, Ch. 9.1, 9.2, 9.6
|
Foundations of Computer Science Ph.D. Qualifying Exam
-
Primary courses
-
50% Algorithms: CS 583 (Design and Analysis of Algorithms)
50% Theory: CS 600 (Theory of Computation)
-
Primary textbooks
-
Intro to Algorithms (2 ed). Cormen, Leiserson, Rivest, Stein
Intro to the Theory of Computation (2 ed). Sipser
Logic in Computer Science. Huth, Ryan
|
Topics
|
Description
|
Readings
|
|
Foundations
|
function growth: O, theta, omega notation
|
Cormen 3
|
|
recurrence relations
|
Cormen 4
|
|
probabilistic analysis; randomized algorithms
|
Cormen 5
|
|
amortized analysis
|
Cormen 17
|
|
dynamic programming
|
Cormen 15
|
|
greedy algorithms
|
Cormen 16.1-3
|
|
Sorting
|
heapsort, quicksort, mergesort
|
Cormen 6, 7, 2
|
|
non-comparison-based
|
Cormen 8
|
|
selection / order statistics
|
Cormen 9
|
|
Data Structures
|
balanced binary search trees
|
Cormen 12, 13
|
|
hash tables
|
Cormen 11
|
|
heaps / priority queues
|
Cormen 6.5, 20
|
|
Graph Algorithms
|
breadth/depth-first search
|
Cormen 22
|
|
minimum spanning trees
|
Cormen 23
|
|
shortest paths
|
Cormen 24, 25
|
|
maximum flow
|
Cormen 26.1-3
|
|
Logic
|
propositional logic
|
Huth 1.1-5
|
|
predicate logic (first-order logic)
|
Huth 2.1-5
|
|
mathematical induction
|
Huth 1.4.2
|
|
well-formed formulas
|
Huth 1.3, 2.1
|
|
natural deduction proofs
|
Huth 1.2, 2.3
|
|
entailment
|
Huth 1.4, 2.4
|
|
soundness and completeness
|
Huth 1.4, 2.5
|
|
Formal Languages and Automata
|
finite automata; regular expressions
|
Sipser 1
|
|
push-down automata; context-free languages
|
Sipser 2
|
|
Turing machines
|
Sipser 3.1
|
|
Computability
|
Church-Turing thesis
|
Sipser 3
|
|
decidable/recursive languages
|
Sipser 4
|
|
recusively-enumerable languages
|
Sipser 4
|
|
reducibilty
|
Sipser 5
|
|
Complexity
|
time complexity: NP-complete
|
Sipser 7, Cormen 34
|
|
space complexity: PSPACE, LOGSPACE (L)
|
Sipser 8
|
Operating Systems Ph.D. Qualifying Exam
-
Primary courses
-
CS 571 (Operating Systems)
-
Primary textbook
-
Operating System Concepts, 7th Edition, Silberschatz, Galvin, and Gagne, John Wiley, 2005.
-
Alternative textbook
-
Distributed Systems: concepts and design, 4th edition, Coulouris, Dollimore, and Kindberg, Addison Wesley, 2005.
-
|
Topics
|
Description
|
Readings (Silberschatz, Galvin, and Gagne)
|
|
Architecture Basics and OS Structures
|
Basic Computer Organization, Computer System Operation,
Storage Structure, I/O Structure, Operating System Operation,
Operating System Services, System Calls, OS Design
Paradigms (Simple Structure, Layered Approach, Microkernels, Modules,
Virtual Machines)
|
Chap. 1 and 2
|
|
Process Management
|
Processes, Threads, CPU Scheduling, Process
Synchronization, Deadlocks
|
Chaps. 3 through 7
|
|
Memory Management
|
Contiguous Allocation, Paging, Segmentation, Virtual
Memory, Page Replacement Algorithms
|
Chaps. 8 and 9
|
|
Storage Management
|
File-System Interface, File System Implementation,
Allocation Methods, Efficiency and Performance Issues, Mass-Storage
Structure
|
Chaps. 10 through 12
|
|
Protection and Security
|
Access Control, Program Threats,
System and Network Threats, Basic Cryptography, User Authentication
|
Chaps. 14 and 15
|
|
Distributed Systems
|
Distributed System Structures,
Distributed File Systems, Distributed Coordination
|
Chaps. 16 through 18
|
Computer Networks Ph.D. Qualifying Exam
-
Primary courses
-
CS 555 (Computer Communications and Networking)
-
Primary textbook
-
Data and Computer Communications, 8th ed., W. Stallings, Prentice Hall, 2007
|
Topic
|
Description
|
Readings (Stallings)
|
|
Protocol and communication model
|
Functions of each layer
|
Chapter 1 and 2
|
|
Communications media characteristics
|
Characteristics of wire, fiber, and radio as channels
|
Chapters 3 and 4
|
|
Analog and digital transmission
|
Analog transmission of digital data; digital transmission of analog data
|
Chapters 5, 6, and 8
|
|
Error detection and correction
|
Cyclic redundancy check
|
Chapter 6
|
|
DLC ARQ protocols
|
Sliding window, selective repeat, go-back-N
|
Chapter 7
|
|
LANs
|
CSMA/CD, binary exponential backoff
|
Chapters 15 and 16
|
|
Wireless
|
CDMA, CSMA/CA
|
Chapters 9 and 17
|
|
Connectionless vs connection-oriented protocols
|
Virtual circuit model; datagram model
|
Chapter 10
|
|
Routing
|
Routing algorithms, distance vector, link-state, border gateways
|
Chapters 12 and 19
|
|
Congestion control
|
Congestion control in data networks and TCP congestion control
|
Chapters 13 and 20
|
|
Internet
|
Internet Protocols, multicasting
|
Chapters 18 and 19
|
|
Transport
|
Connection phase; sliding window; TCP
|
Chapter 20
|
|
Multimedia and real-time networking
|
Quality of service; MIME types
|
Chapters 24 and 19
|
|
Network security
|
Authentication; encryption; message digests
|
Chapter 21
|
Software Modeling Ph.D. Qualifying Exam
-
Primary courses
-
SWE 621 (Software Modeling and Architectural Design)
-
Primary textbook
-
Gomaa, "Designing Concurrent, Distributed, and Real-Time Applications with UML", Addison-Wesley, August 2000.
-
Alternative textbook
-
Sommerville, "Software Engineering", 7th Edition, Addison-Wesley, 2004.
-
Alternative textbook
-
Fowler and Kendall, "UML Distilled", Third Edition, Addison-Wesley, 2004.
|
Topic
|
Description
|
Readings (Sommerville)
|
Readings (Fowler and Kendall)
|
Readings (Gomaa)
|
|
Software Processes
|
Software Process models
|
Chapter 3
|
|
Chapter 5
|
|
Software Prototyping
|
Prototyping in the software process, throw-away prototyping, evolutionary prototyping
|
Chapter 8
|
|
Chapter 5
|
|
Object-Oriented Software Engineering with UML
|
Unified Modeling Language (UML) notation, Object-Oriented Software Life Cycle
|
|
Chapters 1 and 2
|
Chapters 2 and 6
|
|
Use case modeling
|
Use cases, actors, include and extend relationships, use case packages
|
|
Chapter 3
|
Chapter 7
|
|
Static modeling
|
Classes, attributes, and relationships. Multiplicity of associations, association classes, aggregation and composition, generalization/specialization
|
|
Chapters 4 and 6
|
Chapter 8
|
|
Finite state machines and statecharts
|
States, events, conditions, actions and activities, entry and exit actions; hierarchical statecharts.
|
|
Chapter 8
|
Chapter 10
|
|
Dynamic Modeling
|
Object Interaction Modeling; developing interaction models from use cases, ensuring consistency between statecharts and interaction models.
|
|
Chapter 6
|
Chapter 11
|
|
Software Architecture Design
|
Subsystem Structuring Criteria. Distributed application design. Client / server applications.
|
|
|
Chapters 12 and 13
|
|
Concurrent Task Design
|
Concurrent Task Structuring; Task Interfaces - message communication, event synchronization.
|
|
|
Chapter 14
|
|
Class Design
|
Information hiding class design; designing class operations, inheritance in software design, class interface specs.
|
|
|
Chapter 15
|
Software Construction Ph.D. Qualifying Exam
-
Primary course
-
SWE 619 (Software Construction)
-
Primary textbook
-
Liskov. Program Development in Java: Abstraction, Specification, and Object-oriented Design. Addison-Wesley, 2000.
| Topic | Description | Readings (Liskov)
|
|---|
| Abstraction | Decomposition and Abstraction | 1.1
|
|---|
| Parameterization | 1.2
| | Specification | 1.2
| | Java Objects | Program structures and packages | 2.1, 2.2
|
|---|
| Objects and Type Checking | 2.3, 2.4
| | Dispatching and Types | 2.5, 2.6
| | Procedural Abstraction | Specifications | 3.1, 3.2, 3.3
|
|---|
| Implementing | 3.4
| | Designing | 3.5
| | Exceptions | Exceptions in Java | 4.1, 4.2
|
|---|
| Programming with Exceptions | 4.3
| | Design and Defensive Programming | 4.4, 4.5
| | Data Abstraction | Specifications and implementation | 5.1-5.5
|
|---|
| Reasoning | 5.6, 5.7
| | Designing | 5.8, 5.9
| | Iteration Abstraction | Iterators in Java | 6.1
|
|---|
| Specifications and implementation | 6.2-6.4
| | Design | 6.5-6.7
| | Type Hierarchies | Assignment and dispatching | 7.1
|
|---|
| Defining hierarchies | 7.2-7.5
| | Specifications and implementation | 7.6-7.8
| | Theoretical properties | 7.9, 7.10
| | Polymorphic Abstraction | Defining and using | 8.1, 8.2
|
|---|
| Equality and robustness | 8.3-8.6
|
Software Testing Ph.D. Qualifying Exam
(only for IT Ph.D., SWE Concentration)
-
Primary course
-
SWE 637 (Software Testing)
-
Primary textbook
-
Ammann and Offutt, "Introduction to Software Testing", Cambridge University Press, January 2008, ISBN-13: 9780521880381. See the book website for more information. Contact the authors for updated information.
| Topic | Description | Readings
|
|---|
| Introduction and Overview
| Overview of Software Testing
| Chapter 1
| | Graph Coverage
| Graph coverage criteria; creating graphs from source code, design elements, specifications, and use cases; representing graphs algebraically
| Chapter 2
| | Logic Testing
| Logic expression coverage criteria; Structural logic coverage of programs; Specification-based logic coverage; Logic coverage of finite state machines; Disjunctive normal form criteria
| Chapter 3
| | Input Space Partitioning
| Input domain modeling; Combination strategies criteria; Constraints among partitions
| Chapter 4
| | Syntax-Based Testing
| Syntax-based coverage criteria; Program-based grammars; Integration and object-oriented testing; Specification-based grammars; Input space grammars
| Chapter 5
| | Engineering Test Criteria for Technologies
| Testing object-oriented software; Testing web applications and web services; Testing graphical user interfaces; Real-time software and embedded software;
| Chapter 7
|
Information Security and Assurance Ph.D. Qualifying Exam
-
Primary course
-
ISA 562 (Information Security Theory and Practice)
-
Primary textbooks
-
- Computer Security: Art and Science by Matt Bishop, 1st edition. Addison-Wesley.
- Official (ISC)2® Guide to the CISSP® CBK
|
Topic
|
Description
|
Reading (Bishop)
|
Reading (ISC)
| | Introductory concepts | Introductory concepts | Chapter 1 | Chapter 1
|
|---|
| Access control and models | Access control policies and models | Chapters 2, 3, 4, 5, 6, 7, 8, 15 | Chapter 2
|
|---|
| Cryptography | Basic cryptography | Chapter 9 | Chapter 4
|
|---|
| Key management | Distributed access control and identity management | Chapter 10 |
|
|---|
| Authentication and identity | Basic techniques | Chapters 12,14 |
|
|---|
| Cryptographic protocols, telecommunication, and network security | SSL and IpSec, TLS, etc. | Chapter 11 | Chapter 10
|
|---|
| Other topics | Business continuity, risk management, operational security, and physical security | | Chapters 3, 5, 6, 7, 8, 9
|
|---|
|