|
UCLA Computer Science Department
|
|
|
|
Exam Description
Syllabus for the Written Qualifying Examination
1. BASIS OF THE EXAM
The
Written Qualifying Exam (WQE)
will cover fundamental material in 5 "fields":
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).
ARCHITECTURE
See references
[HP],
[TAN],
and on-line UCLA class notes.
I. Instruction Set Architecture (ISA) design
- state, data formats, instruction formats, instruction types
and functions, addressing modes, provisions for conditional
branching, interrupts and exceptions, subroutines and
stack management
II. Processor organization
- Data path
- logic design of components (register file, ALU, etc.),
the clocking regime used, functions that can be carried out
in one clock step, the critical path for performance,
the control signals and interface to a controller
- Controller
- state diagram to map machine instructions into a
series of actions in the data path
- controller design (state machine and microprogram
controllers); handling of interrupts and exceptions
III. Memory technology
- Design principles and organization of static RAM, dynamic RAM,
disk drives, memory hierarchies, principle of locality, hit ratio
- Cache memory implementation and performance
- parameters (cache size, block size, write through,
write back, etc.), mappings (direct, set associative,
associative), replacement policy
- Virtual memory
- paging and segmentation, virtual memory management
(segment and page tables, TLB, etc.), replacement
policies
- use of virtual memory for protection, physical cache
vs. virtual cache
IV. Input/Output
- Buses
- master/slave vs. arbitrated, synchronous vs. asynchronous
- bus hierarchies (processor/memory, backplane, I/O buses)
- industry-standard buses
- Generic I/O Controllers
- accessing control, data and status registers
- ways of doing I/O: directly programmed, interrupt,
direct memory access
- Interrupts
- identifying the source, priority, selection, masking,
service routines
- Direct memory access
- a typical DMA controller chip
- channels (special purpose I/O processors)
V. Principles of pipelined processor design
- Potential and actual speedup, control hazards, structural
hazards, data hazards; basic techniques to deal with
hazards (forwarding, stalls)
- Performance tradeoffs
- impact of workload, ISA, and implementation on performance
(MIPS, CPI, IPC)
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.
ARTIFICIAL INTELLIGENCE
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
-
Algorithms
([K] pp. 36-1 to 36-21 to get an overview;
[RN] Chs. 3, 4, 5)
- breadth-first search
- depth-first search
- depth-first iterative deepening
- best-first search
- Dijkstra's single-source shortest path algorithm
- the A* algorithm
- iterative-deepening-A*
- depth-first branch-and-bound
- minimax search with alpha-beta pruning
- backtracking for constraint satisfaction problems
- local search
II. Knowledge Representation and Reasoning
-
Knowledge representation
([GN] Chs. 1, 2.1-2.8, 3.1-3.4, 4.1-4.5).
- Predicate calculus. The student should be able to precisely
state knowledge in predicate calculus and draw inferences
from that knowledge using resolution theorem proving.
-
Reasoning
([RN] Chs. 14, 15)
- Reasoning with uncertainty using probabilities.
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.
NETWORKS
I. Physical and MAC layer functionality
([PD] Chs. 2, 3;
[KR] Ch. 5)
- Local area networks (e.g., E-net, Giga-enet, FDDI, Token Ring)
- Wireless cellular networks (e.g., GSM, CDMA)
- Wireless LANs (e.g., packet radio, WaveLAN)
II. Protocol architecture
([PD] Chs. 4, 5; [KR] Chs. 3, 4)
- Protocol design and implementation issues for network layer
protocols and above
- Knowledge of key examples of protocols at network and transport layers
- Knowledge of Internet protocol suite (eg, RIP, BGP, TCP/IP, RTP, etc)
- Basic network programming skills
III. Applications
([PD] Ch. 9; [KR] Ch. 2)
- Web, HTTP
- DNS
- FTP
- Network traffic characteristics
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.
SOFTWARE SYSTEMS
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:
OPERATING SYSTEMS
I. Purpose of operating systems
([N] Chs. 1, 2, 3, 4)
- Virtualization of resources
- Handling of resource sharing
- Providing common services
II. Scheduling and process management
([N] Ch. 6)
- Interrupts
- Basics of scheduling (time slices, pre-emptive queueing,
common scheduling algorithms)
- Basics of process management (context switching, process
swapping, threads)
III. Basics of synchronization
([N] Chs. 7, 8, 9, 10)
- Deadlock (meaning and causes, common prevention mechanisms,
common detection and recovery mechanisms)
- Critical sections
- Semaphores, monitors, etc.
- Spin locks
IV. Virtual memory
([N] Chs. 11, 12)
- Basic concept of address spaces
- Segmentation
- Paging (working set concept, common paging algorithms)
- Interactions with hardware
V. Caching and buffering
([N] Chs. 5, 13)
- Basics of cache design (hit ratio, LRU and other common
cache replacement strategies)
- Purpose of I/O buffers and their use
VI. Basics of OS architecture
([N] Chs. 3, 18)
- Kernels, microkernels, and layering
- Out-of-kernel services
VII. Basics of interprocess communications
([N] Chs. 15, 17)
- Shared memory mechanisms
- Messages
- Remote procedure calls
VIII. Basics of file systems
([N] Chs. 13, 16)
- Directories
- Basic issues of file system layout on disk
- Basic file system protection mechanisms
IX. Basics of security
([N] Ch. 14)
- Access control mechanisms (access control lists, capabilities)
- Basic ideas of encryption and authentication (fundamentals of
encryption, keys, digital signatures)
X. Reference
[N]
G. Nutt, Operating Systems: A Modern Perspective,
2nd Edition, Addison-Wesley, 2000.
DATABASE SYSTEMS
I. Basic information models
([R] Part I)
- Network and graph models
- Relational model, dependencies
- Entity-relationship model
- Object-Oriented models
II. Schema and query languages
([R] Part II)
- Data independence
- Schemas and DDL (Data Definition Language)
- DML (Data Manipulation Language)
- Relational algebra
- Relational calculus and first-order logic
- Completeness, and other characterizations of expressiveness
- Aggregates
- Null values
- SQL
- Object-Oriented and Object-Relational database systems
III. Design and implementation of database systems
([R] Parts III + IV)
- Logical vs. physical design
- Disk architecture and physical representation of relations
- Indexing (B-trees, B+-trees, hash indices)
- Clustering
- Integrity constraints
- Schema evolution
- Concurrency control (persistence, logging, locking,
transactions, 2-phase commit, recovery)
- Basic query performance
- Query optimization
- Database tuning
- Database design
IV. Reference
[R]
R. Ramakrishnan, J. Gehrke,
Database Management Systems, 2nd Edition, McGraw-Hill, 2000.
THEORY
I. Grammars and Automata
([HU] Chs. 2, 3, 4, 5, 6, 9;
[LP] Chs. 2, 3, 4)
- Finite state systems (automata, grammars, languages, regular expressions)
- Context-free languages and pushdown automata
- Phrase structure grammars and Turing machines
II. Computability and Complexity
([HU] Chs. 7, 8, 9; Sections 12.1, 13.1, 13.2)
- Turing machines
- Recursive and recursive enumerable languages and functions
- Determinism and nondeterminism
- Time and space complexity classes (P, NP, LOGSPACE, PSPACE).
- Undecidability (diagonalization, halting problem)
- P and NP: reductions, NP-completeness
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)
- Big-O notation
- Data Structures (stacks, queues, lists, trees, heaps, priority
queues, hashing, balanced trees)
- Sorting and searching
- Depth-first search, breadth-first search
- Connectivity in graphs and strong connectivity in digraphs
- Shortest paths (Bellman-Ford, Dijkstra and Floyd-Warshall algorithms)
- Minimum spanning tree (Prim, Kruskal algorithms)
- Lower-bound theory (decision tree model, sorting and searching)
- Design techniques for algorithms and classic examples:
- divide and conquer
- greed
- dynamic programming
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 $