Computer Science

Baskin School of Engineering
335 Baskin Engineering Building
(831) 459-2158
http://www.soe.ucsc.edu

Lower-Division Courses

2. Computer Literacy. F,W,S
Introduction to how computers work and how to use them. Topics covered include network information systems, text editors, formatting, file and directory system, spreadsheets and databases. Computers as symbol manipulation devices. Introduction to programming concepts and computer languages. Impact of computers on society. Designed for students with little or no experience using computers. Preference is given to students who have not taken other computer engineering or computer science courses. Students cannot receive credit for this course and Computer Engineering 3. (General Education Code(s): IN.) P. Franca

10. Introduction to Computer Science. F,W
An overview of the theory, foundations, and practice of computer science with emphasis on what computers can and cannot do, now and in the future. Topics include algorithms and data, correctness and efficiency of algorithms, hardware, programming languages, limitations of computation, applications, and social issues. No programming skills are required as a prerequisite. Major concepts and open problems in computer science are presented without reliance on sophisticated mathematical tools. (General Education Code(s): IN.) P. Tantalo, M. Abadi

12A. Introduction to Programming. F,W,S
An introductory programming course for computer science and engineering majors where students learn programming and documentation skills, as well as algorithmic problem solving and programming methodologies. Introduces students to computers, compilers, and editors, and they are expected to write medium-sized programs. Topics include, but are not limited to, procedures and functions, conditionals and loop control structures, static and dynamic memory manipulations, and text processing. Prior experience with Unix helpful, and some prior programming experience strongly recommended (e.g., course 10). This course is required for computer engineering, computer science, electrical engineering, and information systems management majors. Prerequisite(s): eligibility to enroll in Mathematics 19A (Mathematics 2B or 3 or 40 or higher on mathematics placement exam) or Mathematics 19A or 11A or Economics 11A or Applied Math and Statistics 11A. Concurrent enrollment in course 12L required. (General Education Code(s): IN.) The Staff

12B. Introduction to Data Structures. W,S
Teaches students to implement common data structures and the algorithms associated with each data structure, through progressively difficult exercises. Topics include big "O" notation; pointers, recursion (induction), and dynamic allocation; linked lists and list processing; stacks, queues, binary trees and binary search trees; simple sorting techniques and simple search techniques. Students will gain a working knowledge of the elements of the Java and C programming languages. Prior experience with Unix is assumed. Prerequisite(s): course 12A. Concurrent enrollment in course 12M required. Enrollment limited to 150. (General Education Code(s): IN.) W. Mackey

12L. Computer Programming Laboratory (2 credits). F,W,S
Laboratory sequence complementing topics taught in course 12A by providing training and exposure to several software development tools and practices not covered in course 12A. In addition, the lab provides an initial exposure to a second programming language to reinforce concepts from course 12A. Prerequisite(s): eligibility to enroll in Mathematics 19A (Mathematics 2B or 3 or 40 or higher on mathematics placement exam) or completion of Mathematics 11A or 19A or Economics 11A or AMS 11A. Previous or concurrent enrollment in 12A required. I. Pohl, S. Brandt, A. Pang, C. McDowell

12M. Data Structures Laboratory (2 credits). W,S
Complements course 12B, gaining additional competence with a number of important software development tools, languages, and techniques. Included are advanced Unix features and utilities such as grep, find, diff, the shell, and pipes; C programs utilizing I/O, arrays, pointers, and structures; a scripting language to perform simple text and file manipulation; and the make utility. Prerequisite(s): courses 12A and 12L. Concurrent enrollment in course 12B required. W. Mackey

13H. Introduction to Programming and Data Structures (Honors). *
Provides an accelerated introduction to programming and data structures. Includes a review of basic programming, including loop and conditional control structures, procedures and parameter passing, and arrays. Course goes on to cover same material as course 12B. Students cannot receive credit for this course and course 12A or 12B. Prerequisite(s): interview only; students must have completed a high school or college level programming course in Java, C, or C++. A short oral examination given to ascertain programming level. Concurrent enrollment in course 13L required. Enrollment limited to 25. (General Education Code(s): IN.) S. Brandt, D. Long

13L. Introduction to Programming and Data Structures Laboratory (2 credits). *
Provides accelerated introduction to practical aspects of programming and data structures. Covers three areas: 1) common programming tools, including Unix commands, compilers and linkers, editors, debuggers, and Makefiles; 2) basic programming techniques, including design, testing, and debugging; and 3) C programming, focusing on the major differences between C and Java. Previous or concurrent enrollment in course 13H required. Prerequisite(s): interview only; students must have completed a high school or college level programming course in Java, C, or C++. A short oral examination given to ascertain programming level. S. Brandt, C. McDowell

60G. Beginning Programming: Social Sciences and Humanities. F,W
An introduction to the basic techniques of computer programming. Detailed study of one programming language. Extensive practice using a computer, particularly personal computers, to solve problems. Course 60G is intended for social sciences and humanities students. Students can only receive credit for either 60G or 60N. Students cannot receive credit for course 60G if taken concurrently with or subsequently to course 12A. (General Education Code(s): IN.) P. Franca

60M. Scientific Computation with Matlab and Maple. *
Basic concepts from calculus visualized using Matlab and Maple; plotting data and functions, integration, differentiation, limits; solving systems of equation; linear regression; and example applications from science and engineering. Prerequisite(s): Mathematics 19B, or 20B, or by consent of instructor. Enrollment limited to 60. M. Warmuth

60N. Beginning Programming: Natural Sciences. S
An introduction to the basic techniques of computer programming. Detailed study of one programming language. Extensive practice using a computer to solve problems. Course 60N is intended for science students. Students can only receive credit for either 60G or 60N. Students cannot receive credit for course 60N if taken concurrently with or subsequently to course 12A. (General Education Code(s): IN.) The Staff

80B. Systems and Simulation. F
An introduction to systems analysis as an approach to understanding and solving complex problems. The use of simulation as an aid in this problem solving. Examples are taken from ecology, economics, physics, computer science, and other fields. Intended as a generally accessible undergraduate course in which students can develop and explore computer simulation models matched to their individual interests. (General Education Code(s): T2-Natural Sciences, Q.) R. Levinson

80C. Computer Arts and Graphics. *
Covers the design and use of various computer graphics programs for painting, drawing, computer-aided design, modeling, and animation. Students create graphical images using available software and design programs. Exposure to peripherals such as mice, laser printers, and possibly video and experimental peripherals. Use of SGI graphics workstations. Includes discussion of computer art and its development over time, and includes slides and videos of computer graphics. Not intended for computer science or computer engineering majors, who are advised to take course 160. (General Education Code(s): T2-Natural Sciences.) S. Lodha

80G. Introduction to Unix. *
Introduction to computing, the Internet, and the World Wide Web through the language of the Unix operating system. Oriented to the beginner, the course presupposes no previous acquaintance with any particular sort of computer. It covers the basic concepts of text editing and formatting, writing Web pages in basic HTML, and promotes a rigorous understanding of Unix commands and shell scripts. Views communication with a computer as a matter of learning a few simple though powerful languages. (Also offered as Linguistics 80G. Students cannot receive credit for both courses.) (General Education Code(s): T2-Natural Sciences.) The Staff

80J. Technology Targeted at Social Issues. F,S
Introduces the idea that engineering can be a means for addressing social issues. Case studies and guest speakers. Issues might include: economic development, privacy, activism, safe drinking water, inexpensive shelters, sustainable energy, education, and waste disposal. (General Education Code(s): T7-Natural Sciences or Social Sciences.) S. Lodha, J. Davis

80K. Foundations of Interactive Game Design. W
Surveys history, technology, narrative, ethics, and design of interactive computer games. Work in teams to develop novel game design storyboards. Intended as a generally accessible undergraduate course in which students can explore the interplay of narrative, graphics, rule systems, and artificial intelligence in the creation of interactive games. Programming experience not required. Enrollment limited to 150. (General Education Code(s): T2-Natural Sciences.) E. Whitehead

80V. VRML 3D Worlds on the Web. *
This hands-on course covers authoring and publishing 3D virtual worlds on the web. Focus is on tools and techniques for adding new dimensions to online publications including 3D worlds, sound, animation, and interactions. Topics are updated as technology changes. Representative topics have included VRML, HTML, XML, X3D, U3D, Acrobat, etc. Introduces students to concepts in 3D graphics, transformations, and animation through lectures, individual/group laboratory exercises, and a final project. Students must know how to use e-mail, a text editor, and a web browser. Enrollment limited to 80. (General Education Code(s): T2-Natural Sciences.) A. Pang

94. Group Tutorial. F,W,S
Provides a means for a small group of students to study a particular topic in consultation with a faculty sponsor. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

94F. Group Tutorial (2 credits). F,W,S
Provides a means for a small group of students to study a particular topic in consultation with a faculty sponsor. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

99. Tutorial. F,W,S
Students submit petition to sponsoring agency. May be repeated for credit. The Staff

99F. Tutorial (2 credits). F,W,S
Students submit petition to sponsoring agency. May be repeated for credit. The Staff

Upper-Division Courses

101. Algorithms and Abstract Data Types. F,W
Studies basic algorithms and their relationships to common abstract data types. Covers the notions of abstract data types and the distinction between an abstract data type and an implementation of that data type. The complexity analysis of common algorithms using asymptotic (big "O") notation is emphasized. Topics include sorting and searching techniques, basic graph algorithms, and algorithm design techniques. Abstract data types covered include priority queues, dictionaries, disjoint sets, heaps, balanced trees, and hashing. Familiarity with C, Java, and Unix is assumed. Prerequisite(s): course 12B or 13H, Computer Engineering 16 or 16H, Mathematics 19B, and one course from the following: Mathematics 21, 22, 23A, 24, or Applied Mathematics and Statistics 27. Enrollment restricted to School of Engineering majors.
P. Tantalo, A. Van Gelder

102. Introduction to Analysis of Algorithms. F
Methods for the systematic construction and mathematical analysis of algorithms. Order notation, the RAM model of computation, lower bounds, and recurrence relations are covered. The algorithm design techniques include divide-and-conquer, branch and bound, and dynamic programming. Applications to combinatorial, graph, string, and geometric algorithms. Prerequisite(s): course 101. M. Warmuth, A. Van Gelder, S. Lodha, D. Helmbold, D. Achlioptas

104A. Fundamentals of Compiler Design I. F
An introduction to the basic techniques used in compiler design. Topics include compiler structure, symbol tables, regular expressions and languages, finite automata, lexical analysis, context-free languages, LL(1), recursive descent, LALR(1), and LR(1) parsing; and attribute grammars as a model of syntax-directed translation. Students use compiler building tools to construct a working compiler. Prerequisite(s): course 101 and Computer Engineering 12 and 12L. W. Mackey

104B. Fundamentals of Compiler Design II. S
A detailed study of the structure and design of a compiler. Continues study begun in course 104A. Topics include compiler structure emphasizing the back end, type systems, run-time environments; static, stack and heap storage management, garbage collection; addressing, register allocation, code generation; basic blocks and data-flow analysis; local and global code optimization; interpretation versus compilation. Students generate machine code runnable on a real machine. Prerequisite(s): course 104A. W. Mackey

105. Systems Programming. W
Covers fundamentals of systems programming including standard tools, shell programming, file I/O, files and directories, system data files and information, Unix processes, process control, synchronization, signals, event-driven programming, terminal I/O, daemons, interprocess communication, basic network programming, and basic user-interface programming. Prerequisite(s): course 101 and Computer Engineering 12 and 12L. Enrollment restricted to School of Engineering majors. E. Miller, W. Mackey, S. Brandt, D. Long

109. Advanced Programming. W,S
An introduction to object-oriented techniques of software development including data abstraction, inheritance, polymorphism, and object-oriented design. Extensive practice using a computer to solve problems, including construction of graphical user interfaces and a multithreaded client/server applications. Prerequisite(s): course 101. The Staff, D. Bailey, I. Pohl, C. McDowell

111. Introduction to Operating Systems. F,S
Fundamental principles of operating systems: process synchronization, deadlocks, memory management, resource allocation, scheduling, storage systems, and study of several operating systems. A major programming project will be required. Prerequisite(s): course 101 and Computer Engineering 110. E. Miller, W. Mackey,
S. Brandt, D. Long

112. Comparative Programming Languages. W
Covers several programming languages and compares styles, philosophy, and design principles. Principles underlying declarative, functional, and object-oriented programming styles are studied. Students write programs emphasizing each of these techniques. Prerequisite(s): course 104A. W. Mackey, M. Abadi, D. Long, C. Flanagan, A. Van Gelder, C. McDowell

115. Software Methodology. W,S
Emphasizes the characteristics of well-engineered software systems. Topics include requirements analysis and specification, design, programming, verification and validation, maintenance, and project management. Practical and research methods are studied. Imparts an understanding of the steps used to effectively develop computer software. Prerequisite(s): course 101. Enrollment restricted to computer science, computer engineering, and information systems management majors. Enrollment limited to 25. D. Bailey, E. Whitehead, C. Flanagan, L. Werner

116. Software Design Project. S
Students in teams specify, design, construct, test, and document a complete software system in a specialized application domain. Class time is spent in technical discussions and ongoing design reviews. A formal presentation and demonstration of each project is required. An organizational meeting will be held during the preceding quarter. Projects may be drawn from industry and campus research groups. Prerequisite(s): course 115. E. Whitehead, L. Werner

122. Computer Security. S
Introduction to computer security (including selected topics in network security). Access control. Security in programming languages. Basic cryptography. Security protocols. Prerequisite(s): course 111 or permission of instructor. Enrollment restricted to School of Engineering majors. Enrollment limited to 100. E. Miller, M. Abadi

128. Distributed Systems: File Sharing, Online Gaming, and More. *
Covers topics in distributed computing including communication, naming, synchronization, consistency and replication, fault tolerance, and security. Examples drawn from peer-to-peer systems, online gaming, the World Wide Web; other systems also used to illustrate approaches to these topics. Students implement simple distributed systems over the course of the quarter. Prerequisite(s): course 101 or Computer Engineering 150. Course 111 or 105 recommended. E. Miller, S. Brandt, D. Long

129. Data Storage Systems. *
Covers all aspects of storage systems technology from magnetic media up through system software, including principles of magnetic recording, hard drive technology and evolution, performance measurement, file systems, storage networking, disk arrays, network-attached storage, and alternative storage technologies. Prerequisite(s): course 101, 111, and Physics 5A or 6A. E. Miller, S. Brandt, D. Long

130. Computational Models. F,S
Various representations for regular languages, context-free grammars, normal forms, parsing, pushdown automata, pumping lemmas, Turing machines, the Church-Turing thesis. Prerequisite(s): course 101. D. Bailey, M. Warmuth, R. Levinson

132. Computability and Computational Complexity. W
Turing machines, general phase-structure grammars, the Chomsky hierarchy, recursive functions, diagonalization, the Halting problem, computability and unsolvability, computational complexity, time and space bounds, NP-completeness with emphasis on reductions between problems from various areas. Prerequisite(s): course 130. M. Warmuth, P. Kolaitis, D. Helmbold

140. Artificial Intelligence. W
Introduction to the contemporary concepts and techniques of artificial intelligence, including any or all of: machine perception and inference, machine learning, optimization problems, computational methods and models of search, game playing and theorem proving. Emphasis may be on any formal method of perceiving, learning, reasoning, and problem solving which proves to be effective. This includes both symbolic and neural network approaches to artificial intelligence. Issues discussed include symbolic versus nonsymbolic methods, local versus global methods, hierarchical organization and control, and brain modeling versus engineering approaches. Lisp or Prolog may be introduced. Involves one major project or regular programming assignments. Prerequisite(s): course 101 and one of the following: course 130, Computer Engineering 177, or Mathematics 115. I. Pohl, R. Levinson

142. Machine Learning and Data Mining. W
Introduction to machine learning algorithms and their applications. Topics include classification learning, density estimation and Bayesian learning regression, and online learning. Provides introduction to standard learning methods such as neural networks, decision trees, boosting, and nearest neighbor techniques. Prerequisite(s): course 101 and one of Applied Mathematics and Statistics 5, 7, 113, 131, or Computer Engineering 107. Enrollment limited to 50.
M. Warmuth, D. Helmbold

146. Game AI. S
Course provides a comprehensive introduction to the use of artificial intelligence (AI) in computer games. Building on fundamental principles of AI, course explains how to create non-player characters (NPCs) with progressively more sophisticated capabilities. Prerequisite(s): course 140; familiarity with C++. Enrollment restricted to juniors, seniors, and graduate students. Enrollment limited to 20. The Staff

160. Introduction to Computer Graphics. F,S
Introduces different techniques of modeling, transformation, and rendering to obtain computer generated imagery. Topics include 2D and 3D graphical primitives, line drawings, curves and surface modeling, projections, matrix composition, hidden surface removal, and shading algorithms. Several intensive programming assignments on bit-mapped raster scan displays and a major programming project are required. Prerequisite(s): course 101 and Mathematics 21 or Applied Mathematics and Statistics 27. Concurrent enrollment in course 160L required. Enrollment limited to 35. A. Pang, S. Lodha, J. Davis

160L. Introduction to Computer Graphics Laboratory (2 credits). F,S
Complements course 160, gaining additional competence with a number of important software development tools, graphics libraries, and graphical user interfaces. Included are OpenGL program, utilizing rubberbanding, picking, trackballing, display lists, double buffering, lighting, shading, materials and textures; and FLTK program, utilizing sliders, buttons, and dialog boxes. Prerequisite(s): course 101 and Mathematics 21 or Applied Math 27. Concurrent enrollment in course 160 required. Enrollment restricted to all engineering majors. Enrollment limited to 35. A. Pang, S. Lodha, J. Davis

161. Visualization and Computer Animation. W
Introduction to standard techniques of computer animation and data visualization. Topics include mathematical foundations; creature and behavioral animation; scalar, vector and tensor visualization methods. Involves programming exercises, instruction in available software, and a project. Prerequisite(s): course 160 and 160L or equivalent. Enrollment restricted to students majoring in computer sciences, computer engineering, or electrical engineering. Concurrent enrollment in course 161L required. Enrollment limited to 35. A. Pang, S. Lodha

161L. Visualization and Computer Animation Laboratory (2 credits). W
Complements course 161, gaining additional competence with a number of important software development tools and techniques. Included are Visualization Toolkit (VTK) and Insight Toolkit (ITK); C, OpenGL, and FLTK programs utilizing visualization techniques of isosurfacing, transfer function, volumetric rendering, streamlines visualization; video capture for facial animation and pose estimation, group and behavioral animations. Prerequisite(s): courses 160 and 160L; concurrent enrollment in course 161 required. Enrollment restricted to all engineering majors. Enrollment limited to 35. A. Pang, S. Lodha

164. Game Engines. S
Covers the graphic elements in computer games. Topics include modifying, optimizing, adding components, and building a game engine. Course evaluation based on exams and several programming projects, including a game built using the student's game engine. Prerequisite(s): courses 160 and 160L. Concurrent enrollment in course 164L required. A. Pang

164L. Game Engines Lab. S
Provides hands-on experience in using, designing, and building game engines. Students also explore different special effects, such as particle systems, spring systems, and game physics. Prerequisite(s): courses 160 and 160L. Concurrent enrollment in course 164 required. A. Pang

180. Database Systems I. W
Introduction to the concepts, approaches, tools, and methodology of database design. Covers the entity-relationship model, the relational model, relational algebra, relational calculus, commercial languages (such as SQL and QBE), functional dependencies, normal forms, and design theory. Other topics may include knowledge-bases, constraint databases, and alternative database models. (Formerly offered as Database Systems.) Prerequisite(s): course 101. W. Tan, N. Polyzotis, P. Kolaitis

181. Database Systems II. S
Introduction to the architecture and implementation of database systems. Topics covered include data storage, tree and hash indexes, storage management, query evaluation and optimization, transaction management, concurrency control, recovery, and XML data management. Prerequisite(s): course 180. Enrollment limited to 50. W. Tan, N. Polyzotis

183. Hypermedia and the Web. *
An introduction to the construction of hypermedia systems and large-scale web applications. Topics covered include pre-web hypertext systems, hypermedia data models, namespaces, system architecture of the web, design of large linked information spaces, design and development of database-backed web applications, web site load testing, and web collaboration technologies. Students work in teams over the term to develop a significant web application. Prerequisite(s): course 180. Enrollment limited to 40. E. Whitehead

190X. Methods of Cryptography. F
Theory and practice of encryption and decryption. Classic ciphers. Shannon's information-theoretic approach. Block and stream ciphers. The DES standard. Public key systems: Diffie-Hellman key exchange, RSA, digital signatures. Elliptic curve cryptography. Authentication protocols. Prerequisite(s): Mathematics 19B, 21, and Computer Engineering 16, or equivalent courses. Applied Mathematics and Statistics 27 or equivalent may be substituted for Mathematics 19B and 21. Consult with instructor regarding a course equivalent. J. Yellin

193. Field Study. F,W,S
Provides for individual programs of study with specific academic objectives carried out under the direction of a member of the Computer Science Department and using resources not normally available on campus. Credit is based on the presentation of evidence of achieving the objectives, usually a term paper or project. Cannot normally be repeated for credit. Students submit petition to sponsoring agency. The Staff

193F. Field Study (2 credits). F,W,S
Provides for individual programs of study with specific academic objectives carried out under the direction of a faculty member of the Computer Science Department and a willing sponsor at the field site. Uses resources not normally available on campus. Credit is based on the presentation of evidence of achieving the objectives by submitting a written and oral presentation. Cannot normally be repeated for credit. Intended for students majoring in computer science. Students submit petition to sponsoring agency. The Staff

194. Group Tutorial. F,W,S
A program of independent study arranged between a group of students and a faculty member. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

194F. Group Tutorial (2 credits). F,W,S
A program of independent study arranged between a group of students and a faculty member. Intended for students majoring in computer science. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

195. Senior Thesis Research. F,W,S
Students submit petition to sponsoring agency. The Staff

195F. Senior Thesis Research (2 credits). F,W,S
Intended for majors. Students submit petition to sponsoring agency. The Staff

198. Individual Study or Research. F,W,S
Students submit petition to sponsoring agency. May be repeated for credit. The Staff

198F. Individual Study or Research (2 credits). F,W,S
Intended for majors. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

199. Tutorial. F,W,S
For fourth-year students majoring in computer science. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

199F. Tutorial (2 credits). F,W,S
For fourth-year students majoring in computer science. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

Graduate Courses

200. Research and Teaching in Computer Science and Engineering (3 credits). F
Basic teaching techniques for teaching assistants, including responsibilities and rights of teaching assistants, resource materials, computer security, leading discussion or lab sessions, presentation techniques, maintaining class records, electronic handling of homework, and grading. The course examines research and professional training, including use of the library and online databases, technical typesetting, writing journal and conference papers, publishing in computer science and computer engineering, giving talks in seminars and conferences, and ethical issues in science and engineering. Required for all teaching assistants. Enrollment restricted to graduate students. S. Brandt

201. Analysis of Algorithms. F,S
Rigorous analysis of the time and space requirements of important algorithms, including worst case, average case, and amortized analysis. Techniques include order-notation, recurrence relations, information-theoretic lower bounds, adversary arguments. Analysis of the key data structures: trees, hash tables, balanced tree schemes, priority queues, Fibonacci and binomial heaps. Algorithmic paradigms such as divide and conquer, dynamic programming, union-find with path compression, augmenting paths. Selected advanced algorithms. Introduction to NP-completeness. Enrollment restricted to graduate students; undergraduate students may enroll in this course if they have completed either course 102 or Computer Engineering 177 and have the consent of the instructor. P. Tantalo, A. Van Gelder, D. Helmbold

203. Programming Languages. F
Covers current issues in programming languages. Language topics include object oriented, concurrent, functional, and logic programming, and other programmable applications such as symbolic manipulators and simulation. Enrollment restricted to graduate students; undergraduate students may enroll for this course if they have completed course 112 and have the consent of the instructor. C. Flanagan, A. Van Gelder, C. McDowell

204. Compiler Design. S
A detailed study of the structure and design of a compiler. Topics include compiler structure, pushdown automata, symbol tables, regular expressions and languages, finite state automata, tokens and lexical analyzers, context-free languages, LL(1), recursive descent, LR(1) parsing, attribute grammars as a model of syntax-directed translation, addressing, register allocation, code optimization, and code generation for real machines. Enrollment restricted to graduate students. Offered in alternate academic years. The Staff, W. Mackey

210. Computational Models and Complexity. *
Finite automata and regular expressions, universal models of computation, computability and unsolvability, relations between complexity classes, hierarchy theorems, reductions, complete problems for the major complexity classes (L, NL, P, NP, PSPACE). Other topics may include complexity of counting and enumeration problems, complexity of approximation, randomized complexity classes. Prerequisite(s): course 201. M. Warmuth, P. Kolaitis, D. Helmbold

211. Combinatorial Algorithms. W
Fundamental combinatorial algorithms, graph algorithms, flow problems, matching problems, linear programming, integer programming, NP-completeness, approximation algorithms for optimization problems. Prerequisite(s): course 201. Offered in alternate academic years.
P. Kolaitis, D. Achlioptas

217. Logic in Computer Science. *
The applications and uses of formal systems to computer science. Covers the syntax and semantics of propositional logic and first-order logic, normal forms, soundness and completeness theorems, Herbrand's theorem, unification and resolution, foundations of logic programming, automated theorem proving. Other topics may include deductive databases, database query languages, nonmonotonic reasoning. Enrollment restricted to graduate students. Offered in alternate academic years. A. Van Gelder, P. Kolaitis

221. Advanced Operating Systems. F
A detailed study of the issues involved in operating systems design and implementation. Readings cover current research topics and systems of historical significance. Topics include (but are not restricted to) process and memory management, protection, security, synchronization, performance evaluation, file systems, distributed systems. Enrollment restricted to graduate students; undergraduates by interview only. E. Miller, S. Brandt, D. Long

223. Advanced Computer Security. *
Overview of research topics in computer and network security. Topics may include cryptographic operations, security properties and policies, authentication and access control, attacks on computer systems and defenses against them, security in programming languages, and network protocols for security. Enrollment restricted to graduate students or consent of instructor. E. Miller, M. Abadi

229. Storage Systems. W
Topics include storage devices, storage architectures, local file systems, high-performance file systems, and next-generation storage devices and architectures; covers issues of performance, reliability, scalability, robustness, and security. Prerequisite(s): course 221 or permission of instructor. E. Miller, S. Brandt, D. Long

232. Distributed Systems. S
Overview of research topics in distributed computer systems. Topics may include communication paradigms, process management, naming, synchronization and coordination, consistency and replication, fault tolerance, and security. Examples include distributed operating systems, distributed file and object systems, distributed document systems, and peer-to-peer systems. Prerequisite(s): course 221 or permission of instructor. E. Miller, D. Long

240. Artificial Intelligence. S
Prepares students for doing research in artificial intelligence. Major topics covered are search and heuristics, knowledge representation, planning, deduction and inference, reinforcement learning, associative pattern retrieval, and adaptive search. Discussion includes current research issues in AI problem-solving methods. Individualized projects. Undergraduates may enroll in this course if they have completed course 140. Enrollment limited to 30.
I. Pohl, R. Levinson

241. Knowledge Engineering. *
Introduction to the acquisition, representation, and application of knowledge in expert systems. Topics include production systems, backward and forward chaining, dependency-directed backtracking, reasoning with uncertainty, certainty factors, fuzzy systems, knowledge representation (rules, frames, and semantic nets), inference engines, and metaknowledge. Discussion includes current research issues in adaptive expert systems. Involves one major project. Undergraduates may enroll in this course if they have completed course 140. Offered in alternate academic years. R. Levinson

242. Machine Learning. F
Introduction to machine learning algorithms. Covers learning models from fields of statistical decision theory and pattern recognition, artificial intelligence, and theoretical computer science. Topics include classification learning and the Probably Approximately Correct (PAC) learning framework, density estimation and Bayesian learning, EM, regression, and online learning. Provides an introduction to standard learning methods such as neural networks, decision trees, boosting, nearest neighbor, and support vector machines. Requirements include one major experimental learning project or theoretical paper. Enrollment restricted to graduate students. Enrollment limited to 30. M. Warmuth, D. Helmbold

244. Artificial Intelligence in Games. W
Artificial intelligence has long used game-playing as a metric for progress. Key algorithms such as alpha-beta and HPA search studied. Computer algorithms for backgammon, poker, and chess examined. There will be individulalized projects. Prerequisite(s): course 201; and course 211 or 240 or 242. Enrollment limited to 20. I. Pohl

250. Information Theory and Communication. W
Physical, technological, and mathematical bases for measures of information in digital signaling and their applications. Physical and information entropies. Optimal codes. Entropy of natural languages. Channel capacity. Optimal communication. Shannon's theorems. Network information theory. Introduction to quantum information theory and computation. Prerequisite(s): Computer Engineering 107 or equivalent, or permission of instructor. Enrollment restricted to graduate students. J. Yellin

253. Advanced Programming Languages. S
Covers issues in the design, implementation, analysis, and specification of programming languages. Topics include formal semantics (including operational, axiomatic, and denotational semantics), advanced type systems, program analysis (including abstract interpretation and model checking), specification, and verification. Prerequisite(s): course 203 or equivalent. C. Flanagan

260. Computer Graphics. *
Advanced course in computer graphics. Topics may vary depending on interests of students and research directions in the field. Main topics include in-depth study of curves and surface modeling, deformations, advanced ray tracing, and radiosity methods. Enrollment restricted to graduate students; undergraduates by interview only. Enrollment limited to 20. A. Pang, S. Lodha

262. Computer Animation. W
An in-depth treatment of computer animation, including its origins in conventional animation, 2-D animation, inbetweening, motion control, morphing, graphical motion editors, animation languages, motion blur, simulation of articulated body motion, realtime animation, and special-purpose animation hardware. Enrollment restricted to graduate students. Enrollment limited to 15. J. Davis

272. Evolutionary Game Theory. W
Reviews static equilibrium concepts, games of incomplete information, and the traditional theory of dynamic games in discrete time. Develops recent evolutionary game models, including replicator and best reply dynamics, and applications to economics, computer science, and biology. Prerequisite(s): upper-division math courses in probability theory are strongly recommended. (Also offered as Biology 274 and Economics 272. Students cannot receive credit for more than one of these courses.) M. Warmuth, D. Friedman, B. Sinervo

277. Database Systems I. *
Advanced course on principles of database systems. Main topics include overview of the relational data model and relational query languages; recursive queries, datalog, and fixed-points; query processing and optimization; database design, dependencies, normal forms, and the chase procedure. Additional topics may include information integration, complex objects, semistructured data, and XML. (Formerly Database Systems.) Prerequisite(s): course 180 (or equivalent) or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. Offered in alternate academic years. W. Tan, N. Polyzotis

278. Database Systems II. S
Advanced course in implementation techniques for database systems. Topics include transaction management, locking protocols for tables, and locking for index structures; query optimization, database statistics, and query processing; access methods for multidimensional data; and database recovery in centralized and distributed systems. Additional topics may include objects in databases, parallel database systems, advanced query optimization techniques, and data mining. Prerequisite(s): course 277 or 181 (or equivalent) or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. W. Tan, N. Polyzotis

279. Software Reuse and Component-Based Software Engineering. *
Detailed study of interlocking business, organizational, and technical issues in large-scale software reuse and component-based software engineering. Topics include architecture, design for reuse, domain engineering, model-driven development, domain-specific kits, components, frameworks, software agents, generators, problem-oriented languages, library design, reuse tools, patterns, and aspects. Assumes prior exposure to software engineering topics. Prerequisite(s): computer engineering 276 or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. C. McDowell

280A. Seminar in Computer Science Research (2 credits). *
Weekly seminar covering topics of current research in computer science. Enrollment limited to 30. May be repeated for credit. The Staff

280G. Seminar on Software Engineering (2 credits). *
Weekly seminar covering topics of current research in software engineering. Prerequisite(s): permission of instructor. Enrollment restricted to graduate students. Enrollment limited to 30. May be repeated for credit. N. Whitehead, C. Flanagan, L. De Alfaro, C. McDowell

280J. Seminar on Computer Graphics (2 credits). F,W,S
Weekly seminar covering topics of curren research in computer graphics. Enrollment restricted to graduate students and by permission of instructor. Enrollment limited to 30. May be repeated for credit. J. Davis

280S. Seminar on Computer Systems (2 credits). F,W,S
Weekly seminar series covering topics of current research in computer systems. Enrollment by permission of instructor. Enrollment limited to 30. May be repeated for credit. E. Miller, S. Brandt, D. Long

290A. Topics in Algorithms and Complexity Theory: Probabilistic Algorithms and Average Case Analysis. *
Examines the use of probability theory both in the design and analysis of algorithms. Uses probability theory to analyze the average performance of deterministic algorithms on randomly chosen or "typical" inputs, rather than on worst case inputs. Also a look at algorithms that use randomization, such as random walk and simulated annealing techniques. Examples of specific topics include martingales, random graphs, and rapidly mixing Markov Chains. Enrollment restricted to graduate students. Enrollment limited to 15. Offered in alternate academic years. May be repeated for credit. D. Haussler

290B. Advanced Topics in Computer Graphics. F,S
A graduate seminar in computer graphics on topics from recently published research journal articles and conference proceedings. Topics vary from year to year depending on interests of students. Primary areas of interest are likely to be scientific visualization, modeling, rendering, scattered data techniques, wavelets, and color and vision models. Students read technical papers and present class lectures. Guest lectures supplement the student presentations. A research project is required. Enrollment limited to 15. A. Pang, S. Lodha, J. Davis

290C. Advanced Topics in Machine Learning. S
In-depth study of current research topics in machine learning. Topics vary from year to year but include multi-class learning with boosting and SUM algorithms, belief nets, independent component analysis, MCMC sampling, and advanced clustering methods. Students read and present research papers; theoretical homework in addition to a research project. Prerequisite(s): course 242. M. Warmuth, D. Helmbold

290D. Neural Computation. *
An introduction to the design and analysis of neural network algorithms. Concentrates on large artificial neural networks and their applications in pattern recognition, signal processing, and forecasting and control. Topics include Hopfield and Boltzmann machines, perceptions, multilayer feed forward nets, and multilayer recurrent networks. Enrollment restricted to graduate students. Offered in alternate academic years. D. Haussler, M. Warmuth

290E. Object-Oriented Programming Methodology. S
Object-oriented programming methodology is the application of abstract-data types and polymorphism to coding solution. Topics geared to beginning thesis research in this field. Prerequisite(s): courses 201 and 203. Enrollment restricted to graduate students. Enrollment limited to 20. I. Pohl, C. McDowell

290F. Applications of Combinatorics. S
Combinatorial mathematics, including summation methods, working with binomial coefficients, combinatorial sequences (Fibonacci, Stirling, Eulerian, Harmonic, Bernoulli numbers), generating functions and their uses, Bernoulli processes, and other topics in discrete probability. Oriented toward problem solving, applications mainly to computer science, but also physics. (Formerly Topics in Combinatorial Mathematics.) Prerequisite(s): Computer Engineering 16 and Applied Mathematics and Statistics 27. Enrollment restricted to graduate students and upper-division undergraduates. Offered in alternate academic years. May be repeated for credit. J. Yellin

290G. Topics in Software Engineering. W
Research seminar on current topics in software engineering. Topics vary from year to year depending on the current research of the instructor(s) and interests of students. Students read technical papers from relevant journals and conference proceedings. Synthesis and understanding of materials is demonstrated by a required research project. Prerequisite(s): Computer Engineering 276 recommended. Enrollment restricted to graduate students; undergraduates may enroll with permission of instructor. Enrollment limited to 35. May be repeated for credit. E. Whitehead, L. De Alfaro, C. McDowell, L. Werner

290H. Topics in Database Systems. *
Focuses on current research topics in database systems. Different offerings cover different topics depending on current research of instructor(s) and the interests of students. Students read technical papers from journals and conference proceedings and present class lectures. A research project is required. Prerequisite(s): course 180 (or equivalent) or 277 or consent of instructor. Enrollment restricted to graduate students. Enrollment limited to 20. W. Tan, N. Polyzotis, P. Kolaitis

290I. Internet Technology and Policy. *
Graduate seminar that explores the transforming effects of the Internet on the physical access to information, the content of communications, the security of private information, and the availability of investments. Computer engineering and computer science undergraduate students may enroll in this course if they have completed Computer Engineering 152; other graduate and advanced undergraduate students may enroll with consent of the instructor. J. Yellin

290S. Advanced Topics in Computer Systems. *
Focuses on current research topics in computer systems. Topics vary from year to year depending on the current research of the instructor(s) and the interests of the students. Students read technical papers from current journals and conference proceedings, and present class lectures. A research project is required. Prerequisite(s): course 221. Enrollment restricted to graduate students; qualified undergraduates may enroll with instructor's consent. E. Miller, W. Tan, S. Brandt, D. Long

290X. Cryptography and Computer Security. *
Research seminar on encryption and related technologies. Topics include theory of codes, random sequences and generators, public key cryptosystems, private key cyphers, key exchange protocols, quantum computing and cryptography. Major project required. Prerequisite: interview with instructor. Enrollment limited to 12. J. Yellin

290Y. Quantum Computing. *
Quantum information theory and theory of quantum computation. Quantum algorithms for database search, integer factorization, and order finding. Quantum coding and error correction. Shannon and von Neumann entropies. Quantum communication and cryptography. Prerequisite(s): course 201. Recommended: courses 210, 250, Computer Engineering 251, Physics 215. Knowledge of quantum mechanics helpful but not required. Some knowledge of Shannon information theory strongly recommended. See instructor to discuss course requirements before enrolling. Enrollment restricted to graduate students or seniors by consent of instructor. J. Yellin

296. Masters Project (2 credits). F,W,S
Independent completion of a masters project under faculty supervision. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

297. Independent Study or Research. F,W,S
Independent study or research under faculty supervision. Although this course may be repeated for credit, not every degree program will accept a repeated course towards degree requirements. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

297F. Directed Readings in Machine Learning (2 credits). F,W,S
Directed readings in machine learning. Students read, present, and discuss current papers in machine learning. Specific topics include online learning the PAC (Probably Almost Correct) learning model, pattern recognition, and practical learning algorithms. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

299. Thesis Research. F,W,S
Thesis research conducted under faculty supervision. Although the course may be repeated for credit, not every degree program will accept a repeated course towards degree requirements. Students submit petition to sponsoring agency. May be repeated for credit. The Staff

*Not offered in 2006-07