|
PhD 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
January 9-13, 2012
August 13-17, 2012
January 7-11, 2013
Artificial Intelligence PhD 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 PhD 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 PhD 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 PhD 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 PhD Qualifying Exam
- Primary courses
- CS 571 (Operating Systems)
- Primary textbook
- Operating System Concepts, 8th Edition, Silberschatz,
Galvin, and Gagne, John Wiley, 2008.
- 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 |
Computer-System Organization, Computer-System
Architecture, Operating-System Structure, Operating-System Operations,
Storage Levels and Caching, Operating System Services, User Operating
System-Interface, System Calls, OS Design Paradigms (Simple Structure,
Layered Approach, Microkernels, Modules, Virtual Machines), OS
Generation, System Boot |
Chap. 1 and 2 |
| Process Management |
Processes, Threads, CPU Scheduling, Process
Synchronization, Deadlocks, Atomic Transactions |
Chaps. 3 through 7 |
| Memory Management |
Contiguous Allocation, Paging, Segmentation, Virtual
Memory, Page Replacement Algorithms, Thrashing |
Chaps. 8 and 9 |
| Storage Management |
File-System Interface, File System Implementation,
Allocation Methods, Efficiency and Performance Issues, Mass-Storage
Structure, Disk Scheduling, RAID 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 PhD 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 PhD Qualifying Exam (January 2012)
- 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 Modeling PhD Qualifying Exam (August 2012)
- Primary courses
- SWE 621 (Software Modeling and Architectural Design)
- Primary textbook
- Gomaa, "Software Modeling and Design: UML, Use Cases,
Patterns, and Software Architectures”, Cambridge University Press,
February 2011, ISBN: 9780521764148
- Alternative textbook
- Gomaa, "Designing Concurrent, Distributed, and Real-Time
Applications with UML", Addison-Wesley, August 2000.
- Alternative textbook
- Fowler and Kendall, "UML Distilled", Third Edition,
Addison-Wesley, 2004.
| Topic |
Description |
Readings (Gomaa 2011) |
Readings (Fowler and Kendall) |
Readings (Gomaa 2000) |
| Software Processes |
Software Process models |
Chapter 3 |
Chapter 2
|
Chapter 5 |
| Software Prototyping |
Prototyping in the software process, throw-away
prototyping, evolutionary prototyping |
Chapter 3 |
|
Chapter 5 |
| Object-Oriented Software Engineering with UML |
Background. Unified Modeling Language (UML) notation,
Object-Oriented Software Life Cycle |
Chapters 2 and 5 |
Chapters 1 and 2 |
Chapters 2 and 6 |
| Use case modeling |
Use cases, actors, include and extend relationships,
use case packages |
Chapter 6 |
Chapter 9 |
Chapter 7 |
| Static modeling |
Classes, attributes, and relationships. Multiplicity
of associations, association classes, aggregation and composition,
generalization/specialization; software context class diagrams, entity modeling; object structuring criteria, stereotypes. |
Chapters 7 and 8 |
Chapters 3 and 5 |
Chapter 8 and 9
|
| Finite state machines and statecharts |
States, events, conditions, actions and activities,
entry and exit actions; hierarchical statecharts. |
Chapter 10
|
Chapter 10 |
Chapter 10 |
| Dynamic Modeling |
Object Interaction Modeling; developing interaction
models from use cases, ensuring consistency between statecharts and
interaction models. |
Chapters 9 and 11 |
Chapters 4 and 12
|
Chapter 11 |
| Software Architectural Design |
Multiple views of software architecture, Subsystem Structuring Criteria. Distributed
application design. Client/server applications. |
Chapters 12, 13, and 15 |
|
Chapters 12 and 13 |
| Concurrent Task Design |
Concurrent Task Structuring; Task Interfaces - message
communication, event synchronization. |
Chapter 18 |
|
Chapter 14 |
| Class Design |
Information hiding class design; designing class
operations, inheritance in software design, class interface specs. |
Chapter 14 |
|
Chapter 15 |
| Design Patterns
|
Design patterns and
architectural patterns; architectural styles; architectural structure
patterns, architectural communication patterns.
|
Chapters/sections 4.5,
12.3, 12.4, 15.2, 15.3, 16.2, and 17.6, Appendix A
|
|
Chapters 3 and 12
|
| Relational Database design
|
Design of database wrapper
classes, identifying primary keys, mapping associations to foreign
keys, mapping whole/part and generalization / specialization
relationships to relational databases.
|
Chapter 15
|
|
|
Software Construction PhD 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 PhD Qualifying Exam
(only for IT PhD)
- 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 PhD 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 |
|
