Computer Science - Graduate Courses

CMPS 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

CMPS 201: Analysis of Algorithms. F,W

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, M. Schlag, D. Helmbold

CMPS 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

CMPS 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. W. Mackey

CMPS 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

CMPS 211: Combinatorial Algorithms. F

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

CMPS 217: Logic in Computer Science. F

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

CMPS 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

CMPS 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

CMPS 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

CMPS 232: Distributed Systems. *

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

CMPS 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

CMPS 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

CMPS 242: Machine Learning. W

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

CMPS 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, M. Mateas

CMPS 248: Interactive Narrative. S

Covers wide range of practices including hypertext, interactive fiction, embedded narratives in games, interactive drama, and artificial intelligence-based story generation. Through a mixture of readings, assignments, and project work, explores the theoretical positions, debates, and technical and design issues arising from these different approaches. Students may not receive credit for this course and course 148. Enrollment restricted to graduate students. Enrollment limited to 20. M. Mateas

CMPS 250: Introduction to Information Theory. W

An introduction to information theory including topics such as entropy, relative entropy, mutual information, asymptotic equipartition property, channel capacity, differential entropy, rate distortion theory, and universal source coding. (Also offered as Electrical Engineering 253. Students cannot receive credit for both courses.) Prerequisite(s): Computer Engineering 107, or Applied Mathematics and Statistics 131 or equivalent course, or permission of instructor. Enrollment restricted to graduate students. H. Sadjadpour

CMPS 253: Advanced Programming Languages. *

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

CMPS 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

CMPS 262: Computer Animation. F

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

CMPS 272: Evolutionary Game Theory. *

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. Students cannot receive credit for both courses.) M. Warmuth, D. Friedman, B. Sinervo

CMPS 277: Principles of Database Systems. F

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. (FormerlyDatabase Systems I.) 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

CMPS 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

CMPS 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

CMPS 280A: Seminar in Computer Science Research (2 credits).F,S

Weekly seminar covering topics of current research in computer science. Enrollment by permission of instructor. Enrollment limited to 30. May be repeated for credit. The Staff

CMPS 280D: Seminar in Database Systems (2 credits).S

Covers advanced research topics from the recent literature in database systems and related fields. Involves presentations from UCSC students and faculty, and guest talks from researchers in industry and other academic institutions. Enrollment by permission of instructor. Enrollment by permission of instructor. Enrollment limited to 30. May be repeated for credit. W. Tan, N. Polyzotis, P. Kolaitis

CMPS 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

CMPS 280J: Seminar on Computer Graphics (2 credits).F,W,S

Weekly seminar covering topics of current 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

CMPS 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

CMPS 290A: Topics in Algorithms and Complexity Theory: Probabilistic Algorithms and Average Case Analysis. W

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, D. Achlioptas

CMPS 290B: Advanced Topics in Computer Graphics. 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

CMPS 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

CMPS 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

CMPS 290E: Object-Oriented Programming Methodology. *

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

CMPS 290F: Applications of Combinatorics. W

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. 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

CMPS 290G: Topics in Software Engineering. *

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

CMPS 290H: Topics in Database Systems. W

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

CMPS 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

CMPS 290S: Advanced Topics in Computer Systems. S

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

CMPS 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

CMPS 290Y: Quantum Computing. S

Quantum information theory and theory of quantum computation. Quantum circuits. Algorithms for database search, integer factorization, and order finding. Quantum coding and error correction. Quantum teleportation. Shannon and von Neumann entropies. Quantum communication and cryptography. See instructor to discuss course requirements before enrolling. Enrollment restricted to graduate students. Undergraduates may enroll with the consent of the instructor. J. Yellin

CMPS 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

CMPS 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

CMPS 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

* - Not currently offered.