Ph.D. Qualifying Exams

Exams

Artificial Intelligence Exam

Databases Exam

Language Processing Exam

Foundations of Computer Science Exam

Operating Systems Exam

Computer Networks Exam

Software Modeling Exam

Software Construction Exam

Software Testing Exam
(only for IT PhD)

Information Security and Assurance Exam

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
Complexity	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
Polymorphic Abstraction	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)²® 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