UCLA Computer Science Department

Exam Description

Syllabus for the Written Qualifying Examination


The Written Qualifying Exam (WQE) will cover fundamental material in 5 "fields":

Artificial Intelligence
Software Systems (Operating Systems, Database Systems)
This document lists topics that these fields are understood to cover for purposes of the examination.

Several texts that cover these topics are also provided. Links have been included to the home page of these texts, and/or to additional resources. Check these links for lecture slides, program source code, solutions to problems in the text, etc.

It may also help to look at sample previous exams (this link works only inside the ucla.edu domain).


See references [HP], [TAN], and on-line UCLA class notes.

I. Instruction Set Architecture (ISA) design

II. Processor organization

III. Memory technology

IV. Input/Output

V. Principles of pipelined processor design

VI. References

[HP] D. Patterson and J. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 2nd Ed., Morgan Kaufmann, 1998.

[TAN] A. Tanenbaum, Structured Computer Organization, 4th Ed. Prentice-Hall, 1997.

For more background on digital design:

[ELM] M. D. Ercegovac, T. Lang, and J.H. Moreno, Introduction to Digital Systems, Wiley & Sons, Inc., 1999.

[KAT] R. Katz, Contemporary Logic Design, Benjamin Cummings, 1994.

[KOR] I. Koren, Computer Arithmetic Algorithms, Prentice Hall, 1993.


This material defines the Fundamentals of Artificial Intelligence. Most of the references are from [RN]. However, equivalent material from a number of other sources could be easily substituted.

I. AI Search Algorithms

II. Knowledge Representation and Reasoning

III. Natural Language Understanding
([RN] Ch. 22)

IV. Perception -- Speech Recognition and Computer Vision
([RN] Ch. 24)

V. Neural Networks
([RN] Ch. 19)

VI. Robotics
([RN] Ch. 25)

VII. References

[RN] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 1995.

[K] Korf, R.E., "Search techniques", Encyclopedia of Information Systems, Hossein Bidgoli (Ed.), Academic Press, San Diego, CA, 2003, pp. 31-43.

[GN] M. Genesereth and N. Nilsson, Logical Foundations of Artificial Intelligence", Morgan Kaufmann, San Francisco, 1987.


I. Physical and MAC layer functionality
([PD] Chs. 2, 3; [KR] Ch. 5)

II. Protocol architecture
([PD] Chs. 4, 5; [KR] Chs. 3, 4)

III. Applications
([PD] Ch. 9; [KR] Ch. 2)

IV. References

[PD] B. Davie, L. Peterson, and D. Clark, Computer Networks: A Systems Approach, 2nd Ed., Morgan Kaufmann, 2000.

[KR] J. Kurose and K. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Addison Wesley Longman, 1999.


Operating Systems and Database Systems represent core material in software systems.

The Operating Systems syllabus covers design and performance evaluation of modern operating systems; mapping and binding of addresses; organization of multiprogramming and multiprocessing systems, including interrupts, process model, and interlocks; resource allocation models and deadlock problems; scheduling and synchronization; memory management and virtual memory; and I/O control and file systems.

The Database Systems syllabus covers information systems and database systems in enterprises; file organization and secondary storage structures; relational model and relational database systems; other models and data management approaches; database design principles; transactions, concurrency, and recovery; and integrity and authorization.

For the Fundamental Exam, the following topics should be mastered:


I. Purpose of operating systems
([N] Chs. 1, 2, 3, 4)

II. Scheduling and process management
([N] Ch. 6)

III. Basics of synchronization
([N] Chs. 7, 8, 9, 10)

IV. Virtual memory
([N] Chs. 11, 12)

V. Caching and buffering
([N] Chs. 5, 13)

VI. Basics of OS architecture
([N] Chs. 3, 18)

VII. Basics of interprocess communications
([N] Chs. 15, 17)

VIII. Basics of file systems
([N] Chs. 13, 16)

IX. Basics of security
([N] Ch. 14)

X. Reference

[N] G. Nutt, Operating Systems: A Modern Perspective, 2nd Edition, Addison-Wesley, 2000.


I. Basic information models
([R] Part I)

II. Schema and query languages
([R] Part II)

III. Design and implementation of database systems
([R] Parts III + IV)

IV. Reference

[R] R. Ramakrishnan, J. Gehrke, Database Management Systems, 2nd Edition, McGraw-Hill, 2000.


I. Grammars and Automata
([HU] Chs. 2, 3, 4, 5, 6, 9; [LP] Chs. 2, 3, 4)

II. Computability and Complexity
([HU] Chs. 7, 8, 9; Sections 12.1, 13.1, 13.2)

III. Design and Analysis of Algorithms
([CLR] Chs. 1-5, 7-13, 16, 17, 19, 23-26, excluding starred sections; [M] Chs. 1, 2, 3, 4, 5, 6, 7)

V. References

[CLR] Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

[M] Manber, Introduction to Algorithms, Addison-Wesley, 1989.

[HU] Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

[LP] Lewis and Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1982.

$Id: WQEsyllabus.html,v 1.7 2001/04/06 22:57:04 stott Exp stott $