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": Architecture Artificial Intelligence Networks Software Systems (Operating Systems, Database Systems) Theory 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. ________________________________________________________________ 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. * Home page: http://www.mkp.com/books_catalog/catalog.asp?ISBN=1-55860-428-6 * Additional resources: http://www.mkp.com/books_catalog/cod2/ph2_res.asp [TAN] A. Tanenbaum, Structured Computer Organization, 4th Ed. Prentice-Hall, 1997. * Additional resources: http://www.cs.vu.nl/~ast/books/book_software.html For more background on digital design: [ELM] M. D. Ercegovac, T. Lang, and J.H. Moreno, Introduction to Digital Systems, Wiley & Sons, Inc., 1999. * Home page: http://www.cs.ucla.edu/Logic_Design/ [KAT] R. Katz, Contemporary Logic Design, Benjamin Cummings, 1994. * Home page: http://www.cs.berkeley.edu/~randy/CLD/CLD.html [KOR] I. Koren, Computer Arithmetic Algorithms, Prentice Hall, 1993. * Home page: http://www.ecs.umass.edu/ece/koren/arith/ ________________________________________________________________ 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. * Home page: http://www.cs.berkeley.edu/~russell/aima.html [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. * Home page: http://www.mkp.com/books_catalog/catalog.asp?ISBN=0-934613-31-1 ________________________________________________________________ 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. * Home page: http://www.mkp.com/books_catalog/catalog.asp?ISBN=1-55860-514-2 [KR] J. Kurose and K. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Addison Wesley Longman, 1999. * Home page: http://occ.awlonline.com/bookbind/pubbooks/kurose-ross1/ ________________________________________________________________ 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. * Home page: http://www.cs.colorado.edu/~nutt/osamp.html * Additional resources: file://ftp.aw.com/cseng/authors/nutt/osmp/TMs/ 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. * Home page: http://www.cs.wisc.edu/~dbbook * Additional resources: http://www.cs.wisc.edu/~dbbook/dbbook.support.html ________________________________________________________________ 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. * Home page: http://theory.lcs.mit.edu/~clr/ * Errata: file://theory.lcs.mit.edu/pub/algorithms/ [M] Manber, Introduction to Algorithms, Addison-Wesley, 1989. [HU] Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. * Home page: http://www-db.stanford.edu/~ullman/ialc.html * Additional resources (problem solutions): http://www-db.stanford.edu/~ullman/ialcsols/sols.html [LP] Lewis and Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1982. * Typos: http://www.cs.berkeley.edu/~christos/typos.html ________________________________________________________________ $Id: WQEsyllabus.txt,v 1.13 2001/04/06 22:57:47 stott Exp stott $