Graduate courses in Computer Science

Intellectual property law as it relates to computer science including copyright registration, patents, and trade secrets; contract issues such as non-disclosure/non-compete agreements, license agreements, and works-made-for-hire; dispute resolution; and principles of business formation and ownership. Emphasis is on topics of current interest such as open source and the free software movement, peer-to-peer sharing, encryption, data mining, and spam.

1 unit, Aut (Hansen, D)

CS 204. Computational Law

Legal informatics based on representation of regulations in computable form. Encoding regulations facilitate creation of legal information systems with significant practical value. Convergence of technological trends, growth of the Internet, advent of semantic web technology, and progress in computational logic make computational law prospects better. Topics: current state of computational law, prospects and problems, philosophical and legal implications. Prerequisite: basic concepts of programming.

3 units, Spr (Genesereth, M)

CS 205A. Mathematical Methods for Robotics, Vision, and Graphics

Continuous mathematics background necessary for research in robotics, vision, and graphics. Possible topics: linear algebra; the conjugate gradient method; ordinary and partial differential equations; vector and tensor calculus. Prerequisites: 106B or X; MATH 51 and 113; or equivalents.

3 units, Aut (Fedkiw, R)

CS 205B. Mathematical Methods for Fluids, Solids, and Interfaces

Numerical methods for simulation of problems involving solid mechanics and fluid dynamics. Focus is on practical tools needed for simulation, and continuous mathematics involving nonlinear hyperbolic partial differential equations. Possible topics: finite element method, highly deformable elastic bodies, plasticity, fracture, level set method, Burgers' equation, compressible and incompressible Navier-Stokes equations, smoke, water, fire, and solid-fluid coupling. Prerequisite: 205A or equivalent.

3 units, Spr (Fedkiw, R)

CS 221. Artificial Intelligence: Principles and Techniques

(Only one of 121 or 221 counts towards any CS degree program.) Topics: search, constraint satisfaction, knowledge representation, probabilistic models, machine learning, neural networks, vision, robotics, and natural language understanding. Prerequisites: 103 or 103B; 106B or 106X; and exposure to probability. Recommended: 107 and facility with basic differential calculus.

3-4 units, Win (Ng, A)

CS 222. Rational Agency and Intelligent Interaction

(Same as PHIL 358.) For advanced undergraduates, and M.S. and beginning Ph.D. students. Logic-based methods for knowledge representation, information change, and games in artificial intelligence and philosophy. Topics: knowledge, certainty, and belief; time and action; belief dynamics; preference and social choice; games; and desire and intention. Prerequisite: propositional and first-order logic. Recommended: modal logic; game theory.

3 units, Spr (Shoham, Y)

CS 223A. Introduction to Robotics

Topics: robotics foundations in kinematics, dynamics, control, motion planning, trajectory generation, programming and design. Recommended: matrix algebra.

3 units, Win (Kolarov, K)

CS 223B. Introduction to Computer Vision

Fundamental issues and techniques of computer vision. Image formation, edge detection and image segmentation, stereo, motion, shape representation, recognition.

3 units, Win (Thrun, S)

CS 224M. Multi-Agent Systems

For advanced undergraduates, and M.S. and beginning Ph.D. students. Topics: logics of knowledge and belief, other logics of mental state, theories of belief change, multi-agent probabilities, essentials of game theory, social choice and mechanism design, multi-agent learning, communication. Applications discussed as appropriate, but emphasis is on conceptual matters and theoretical foundations. Prerequisites: basic probability theory and first-order logic.

3 units, Aut (Shoham, Y)

CS 224N. Natural Language Processing

(Same as LINGUIST 280.) Methods for processing human language information and the underlying computational properties of natural languages. Syntactic and semantic processing from linguistic and algorithmic perspectives. Focus is on modern quantitative techniques in NLP: using large corpora, statistical models for acquisition, translation, and interpretation; and representative systems. Prerequisites: CS 121/221 or CS124/LINGUIST 180, CS103, CS109.

3-4 units, Spr (Manning, C)

CS 224S. Speech Recognition and Synthesis

(Same as LINGUIST 281.) Automatic speech recognition, speech synthesis, and dialogue systems. Focus is on key algorithms including noisy channel model, hidden Markov models (HMMs), Viterbi decoding, N-gram language modeling, unit selection synthesis, and roles of linguistic knowledge. Prerequisite: programming experience. Recommended: CS 221 or 229.

2-4 units, Win (Jurafsky, D)

CS 224U. Natural Language Understanding

(Same as LINGUIST 188, LINGUIST 288.) Machine understanding of human language. Computational semantics (determination of sense, event structure, thematic role, time, aspect, synonymy/meronymy, causation, compositional semantics, treatment of scopal operators), and computational pragmatics and discourse (coherence relations, anaphora resolution, information packaging, generation). Theoretical issues, online resources, and relevance to applications including question answering, summarization, and textual inference. Prerequisites: one of LINGUIST 180, CS 224N,S; and logic such as LINGUIST 130A or B, CS 157, or PHIL150).

2-4 units, alternate years, not given this year

CS 225A. Experimental Robotics

Hands-on. Topics: kinematic and dynamic control of motion, compliant motion and force control, sensor-based collision avoidance, motion planning, dynamic skills, and robot-human interfaces. Limited enrollment. Prerequisite: 223A.

3 units, not given this year

CS 225B. Robot Programming Laboratory

For robotics and non-robotics students. Students program mobile robots to exhibit increasingly complex behavior (simple dead reckoning and reactivity, goal-directed motion, localization, complex tasks). Topics: motor control and sensor characteristics; sensor fusion, model construction, and robust estimation; control regimes (subsumption, potential fields); probabalistic methods, including Markov localization and particle filters. Student programmed robot contest. Programming is in C++ on Unix machines, done in teams. Prerequisite: programming at the level of 106B, 106X, 205, or equivalent.

3-4 units, Aut (Konolige, K)

CS 226. Statistical Techniques in Robotics

For students seeking to develop robust robot software and those interested in real-world applications of statistical theory. Probabilistic state estimation, Bayes filters, Kalman filters, information filters, and particle filters. Simultaneous localization and mapping techniques, and multi-robot sensor fusion. Markov techniques for making decisions under uncertainty, and probabilistic control algorithms and exploration.

3 units, Spr (Staff)

CS 227. Reasoning Methods in Artificial Intelligence

Technical presentation of logical algorithmic techniques for problem solving in AI. Combines formal algorithmic analysis with a description of recent applications. Topics: representation and modelling, propositional satisfiability, constraint satisfaction, planning and scheduling, advanced topics. Focus is on recent results. Prerequisites: familiarity with basic notions in data structures and with techniques in algorithm design and analysis. Recommended: previous or concurrent course in AI.

3 units, Spr (Yorke-Smith, N)

CS 227B. General Game Playing

A general game playing system accepts a formal description of a game to play it without human intervention or algorithms designed for specific games. Hands-on introduction to these systems and artificial intelligence techniques such as knowledge representation, reasoning, learning, and rational behavior. Students create GGP systems to compete with each other and in external competitions. Prerequisite: programming experience. Recommended: 103 or equivalent. (Genesereth)

3 units, Spr (Genesereth, M)

CS 228. Structured Probabilistic Models: Principles and Techniques

Probabilistic modeling languages for representing complex domains, algorithms for reasoning and decision making using these representations, and learning these representations from data. Focus is on probabilistic graphic models, including Bayesian and Markov networks, extensions to temporal modeling such as hidden Markov models and dynamic Bayesian networks, and extensions to decision making such as influence diagrams. Basic techniques and their applications to domains including speech recognition, biological modeling and discovery, medical diagnosis, message encoding, vision, and robot motion planning. Prerequisites: basic probability theory and algorithm design and analysis.

3 units, Win (Koller, D)

CS 228T. Structured Probabalistic Models: Theoretical Foundations

For students interested in advanced methods in machine learning and probabilistic AI. Theoretical foundations and extension for the ideas and algorithms covered in CS 228. Topics include theory and advanced algorithms for approximate inference in graphical models, representation and inference in continuous processes, and theory and algorithms for learning with missing data and hidden variables. Pre- or corequisites: CS 228; strong mathematical foundation.

2-3 units, Win (Koller, D)

CS 229. Machine Learning

Topics: statistical pattern recognition, linear and non-linear regression, non-parametric methods, exponential family, GLIMs, support vector machines, kernel methods, model/feature selection, learning theory, VC dimension, clustering, density estimation, EM, dimensionality reduction, ICA, PCA, reinforcement learning and adaptive control, Markov decision processes, approximate dynamic programming, and policy search. Prerequisites: linear algebra, and basic probability and statistics.

3 units, Aut (Ng, A)

CS 240. Advanced Topics in Operating Systems

Recent research. Classic and new papers. Topics: virtual memory management, synchronization and communication, file systems, protection and security, operating system extension techniques, fault tolerance, and the history and experience of systems programming. Prerequisite: 140 or equivalent.

3 units, Aut (Engler, D), Spr (Engler, D)

CS 240C. Advanced Operating Systems Implementation

Operating system techniques for meeting the performance, security, flexibility, and robustness needs of demanding applications. Review of hardware/software interface and traditional operating system concepts. Recent operating systems research. Lab to apply concepts. Students work with a minimal operating system capable of running on standard PC hardware. Operating system written in C with some assembly. Prerequisite: 140 or consent of instructor. (Mazieres)

3 units, not given this year

CS 240D. Distributed Storage Systems

File system implementation, low-level database storage techniques, and distributed programming. File system structures, journaling and logging, I/O system performance, RAID (redundant arrays of inexpensive disks), remote procedure call abstraction, and systems illustrating these concepts. File systems, distributed computing, replication and consistency, fault tolerance, and crash recovery. Programming assignments. Final project to build a functioning Unix file system. Prerequisites: C++ and familiarity with Unix; 140 or consent of instructor. (Mazieres)

3 units, not given this year

CS 240E. Low Power Wireless System Software

The structure and implementation of software systems for low power embedded sensors; how to build software that can run unattended for years on small batteries. Topics: hardware trends, energy profiles, execution models, aggregation, storage, application requirements, allocation, power management, resource management, scheduling, time synchronization, programming models, software design, and fault tolerance. Students build working systems on TinyOS, a low-power embedded operation system.

3 units, not given this year

CS 240X. Advanced Operating Systems II

Same content as 240, with expanded topics focusing on more difficult and specialized papers. Recent topics in systems research.

3 units, not given this year

CS 242. Programming Languages

Central concepts in modern programming languages, impact on software development, language design trade-offs, and implementation considerations. Functional, imperative, and object-oriented paradigms. Formal semantic methods and program analysis. Modern type systems, higher order functions and closures, exceptions and continuations. Modularity, object-oriented languages, and concurrency. Runtime support for language features, interoperability, and security issues. Prerequisite: 107, or experience with Lisp, C, and an object-oriented language.

3 units, Aut (Mitchell, J)

CS 243. Program Analysis and Optimizations

Program analysis techniques used in compilers and software development tools to improve productivity, reliability, and security. The methodology of applying mathematical abstractions such as graphs, fixpoint computations, binary decision diagrams in writing complex software, using compilers as an example. Topics include data flow analysis, instruction scheduling, register allocation, parallelism, data locality, interprocedural analysis, and garbage collection. Prerequisites: 103 or 103B, and 107.

3-4 units, Win (Lam, M)

CS 244. Advanced Topics in Networking

Classic papers, new ideas, and research papers in networking. Architectural principles: naming, addressing, routing; congestion control, traffic management, QoS; wireless and mobility; overlay networks and virtualization; network security; switching and routing; content distribution; and proposals for future Internet structures. Prerequisite: 144 or equivalent.

3-4 units, Win (McKeown, N)

CS 244B. Distributed Systems

Distributed operating systems and applications issues, emphasizing high-level protocols and distributed state sharing as the key technologies. Topics: distributed shared memory, object-oriented distributed system design, distributed directory services, atomic transactions and time synchronization, application-sufficient consistency, file access, process scheduling, process migration, and storage/communication abstractions on distribution, scale, robustness in the face of failure, and security. Prerequisite: 249A. Corequisite: 244A.

3 units, Spr (Cheriton, D)

CS 244C. Readings and Projects in Distributed Systems

Companion project option for 244B. Corequisite: 244B.

3-6 units, Spr (Guibas, L)

CS 244E. Low Power Wireless Networking

Challenges of low power wireless networking protocols and applications. Topics: the OSI model, 802.11, Bluetooth, 802.15.4, Zigbee, 6lowpan, hardware considerations, traffic patterns, media access (CSMA, TDMA, RTS/CTS, idle listening), DSSS, UWB, radio propagation models, cross-layer interactions, flooding, dissemination, gossip, epidemics, probabilistic approaches, global versus local communication, and in-network processing. Students read papers and build working protocols on TinyOS, a low-power embedded operating system.

3 units, not given this year

CS 245. Database Systems Principles

File organization and access, buffer management, performance analysis, and storage management. Database system architecture, query optimization, transaction management, recovery, concurrency control. Reliability, protection, and integrity. Design and management issues. Prerequisites: 145, 161.

3 units, Win (Garcia-Molina, H), Sum (Staff)

CS 247. Human-Computer Interaction Design Studio

Project-based. Methods used in interaction design including needs analysis, user observation, idea sketching, concept generation, scenario building, storyboards, user character stereotypes, usability analysis, and market strategies. Prerequisites: 147 and 106A or equivalent background in programming.

3-4 units, Win (Winograd, T)

CS 247L. Human Computer Interaction Technology Laboratory

Hands-on introduction to contemporary HCI technologies. Interaction design with Adobe Flash, mobile development, physical computing, and web applications. Corequisite: 247.

1 unit, Win (Winograd, T)

CS 248. Introduction to Computer Graphics

Input and display devices, scan conversion of geometric primitives, 2D and 3D geometric transformations, clipping and windowing, scene modeling and animation, algorithms for visible surface determination, local and global shading models, color, and real-time rendering methods. Written assignments and programming projects. Prerequisites: 108, MATH 103 or equivalent.

3-5 units, Aut (Levoy, M)

CS 249A. Object-Oriented Programming from a Modeling and Simulation Perspective

Topics: large-scale software development approaches, encapsulation, use of inheritance and dynamic dispatch, design of interfaces and interface/implementation separation, exception handling, design patterns, minimalizing dependencies and value-oriented programming. The role of programming conventions/style/restrictions in surviving object-oriented programming for class libraries, frameworks, and programming-in-the-large; general techniques for object-oriented programming. Prerequisites: C, C++, and programming methodology as developed in 106B or X, and 107 (107 may be taken concurrently). Recommended: 193D.

3 units, Aut (Cheriton, D)

CS 249B. Advanced Object-Oriented Programming

How to produce reasonable-cost, high quality software such as next-stage, large-scale systems that handle life-critical systems. Software process, people, practice, and audit: integrating invariant checks with production software; collection implementation; generic programming and templates; design of value types; named descriptions for large value types; memory management; controlling placement; locality and consumption; concurrency with modular object-oriented programming. Inheritance: when and why multiple inheritance naming, directories, manager, and other design patterns.

3 units, Win (Cheriton, D)

CS 255. Introduction to Cryptography

For advanced undergraduates and graduate students. Theory and practice of cryptographic techniques used in computer security. Topics: encryption (single and double key), digital signatures, pseudo-random bit generation, authentication, electronic commerce (anonymous cash, micropayments), key management, PKI, zero-knowledge protocols. Prerequisite: basic probability theory.

3 units, Win (Boneh, D)

CS 256. Formal Methods for Reactive Systems

Formal methods for specification, verification, and development of concurrent and reactive programs. Reactive systems: syntax and semantics, fairness requirements. Specification language: temporal formulas (state, future, and past) and omega-automata. Hierarchy of program properties: safety, guarantee, obligation, response, persistence, and reactivity. Invariant generation. Deductive verification of programs: verification diagrams and rules, completeness. Modularity. Parameterized programs. Algorithmic verification of finite-state programs (model checking). Prerequisite: 154, 156, 157, or equivalent.

3 units, Win (Manna, Z)

CS 256L. Formal Methods for Reactive Systems Laboratory

Practical application of the specification and verification methods in 256. Individual projects include implementation of verification methods, verification case studies, or tool evaluation, depending on student preference.

2 units, Win (Manna, Z)

CS 258. Introduction to Programming Language Theory

Syntactic, operational, and semantic issues in the mathematical analysis of programming languages. Type systems and non-context-free syntax. Universal algebra and algebraic data types. Operational semantics given by rewrite rules; confluence and termination. Denotational semantics and elementary domain theory for languages with higher-type functions and recursion. Treatment of side effects. Prerequisites: 154, 157 or PHIL 160A.

3 units, Win (Mitchell, J)

CS 259. Security Analysis of Network Protocols

Hands-on experience in formal methods to verify and evaluate the security of network protocols and other systems. Common security protocols and their properties including secrecy, authentication, key establishment, and fairness. Topics: standard formal models and tools used in security protocol analysis; their advantages and limitations. Fully automated, finite-state, model-checking techniques. Constraint solving, process algebras, protocol logics, probabilistic model checking, and game theory. Students select a protocol or secure system to analyze, specify it in the chosen model, use a formal analysis tool to verify its properties, and present findings.

3 units, not given this year

CS 261. Optimization and Algorithmic Paradigms

Algorithms for network optimization: max-flow, min-cost flow, matching, assignment, and min-cut problems. Introduction to linear programming. Use of LP duality for design and analysis of algorithms. Approximation algorithms for NP-complete problems such as Steiner Trees, Traveling Salesman, and scheduling problems. Randomized algorithms. Introduction to online algorithms. Prerequisite: 161 or equivalent.

3 units, Win (Plotkin, S)

CS 262. Computational Genomics

(Same as BIOMEDIN 262.) Applications of computer science to genomics, and concepts in genomics from a computer science point of view. Topics: dynamic programming, sequence alignments, hidden Markov models, Gibbs sampling, and probabilistic context-free grammars. Applications of these tools to sequence analysis: comparative genomics, DNA sequencing and assembly, genomic annotation of repeats, genes, and regulatory sequences, microarrays and gene expression, phylogeny and molecular evolution, and RNA structure. Prerequisites: 161 or familiarity with basic algorithmic concepts. Recommended: basic knowledge of genetics.

3 units, Win (Batzoglou, S)

CS 268. Geometric Algorithms

Techniques for design and analysis of efficient geometric algorithms for objects in 2-, 3-, and higher dimensions. Topics: convexity, triangulations and simplicial complexes, sweeping, partitioning, and point location. Voronoi/Delaunay diagrams and their properties. Arrangements of curves and surfaces. Intersection and visibility problems. Geometric searching and optimization. Random sampling methods. Impact of numerical issues in geometric computation. Example applications to robotic motion planning, visibility preprocessing and rendering in graphics, model-based recognition in computer vision, and structural molecular biology. Prerequisite: discrete algorithms at the level of 161. Recommended: 164.

3 units, Spr (Staff)

CS 270. Introduction to Biomedical Informatics: Fundamental Methods

(Same as BIOMEDIN 210.) Methods for modeling biomedical systems and for making those models explicit in the context of building software systems. Emphasis is on intelligent systems for decision support and Semantic Web applications. Topics: knowledge representation, controlled terminologies, ontologies, reusable problem solvers, and knowledge acquisition. Recommended: exposure to object-oriented systems, basic biology.

3 units, Aut (Musen, M)

CS 271. Introduction to Biomedical Informatics: Principles of Systems Design

(Same as BIOMEDIN 211.) Focus is on undertaking design and implementation of computational and information systems for life scientists and healthcare providers. Case studies illustrate what design factors lead to success or failure in building systems in complex biomedical environments. Topics: requirements analysis, workflow and organizational factors, functional specification, knowledge modeling, data heterogeneity, component-based architectures, human-computer interaction, and system evaluation. Prerequisite: 210, or consent of instructor.

3 units, Win (Das, A)

CS 272. Introduction to Biomedical Informatics Research Methodology

(Same as BIOE 212, BIOMEDIN 212, GENE 212.) Hands-on software building. Student teams conceive, design, specify, implement, evaluate, and report on a software project in the domain of biomedicine. Creating written proposals, peer review, providing status reports, and preparing final reports. Guest lectures from professional biomedical informatics systems builders on issues related to the process of project management. Software engineering basics. Prerequisites: 210, 211 or 214, or consent of instructor.

3 units, Aut (Altman, R; Cheng, B; Klein, T)

CS 273A. A Computational Tour of the Human Genome

(Same as BIOMEDIN 273A, DBIO 273A.) Computational biology through an exploration of human genome. Key genetic concepts from a bioinformatics perspective. Biomedical advances resulting from sequencing of human and related organisms. Genome sequencing: technologies, assembly, personalized sequencing. Functional landscape: genes, regulatory modules, repeats, RNA genes. Genome evolution: processes, comparative genomics, ultraconservation, co-option. Additional topics: population genetics and personalized genomics, ancient DNA, and metagenomics.

3 units, Aut (Batzoglou, S; Bejerano, G)

CS 274. Representations and Algorithms for Computational Molecular Biology

(Same as BIOE 214, BIOMEDIN 214, GENE 214.) Topics: algorithms for alignment of biological sequences and structures, computing with strings, phylogenetic tree construction, hidden Markov models, computing with networks of genes, basic structural computations on proteins, protein structure prediction, protein threading techniques, homology modeling, molecular dynamics and energy minimization, statistical analysis of 3D biological data, integration of data sources, knowledge representation and controlled terminologies for molecular biology, graphical display of biological data, machine learning (clustering and classification), and natural language text processing. Prerequisites: programming skills; consent of instructor for 3 units.

3-4 units, Spr (Altman, R)

CS 275. Translational Bioinformatics

(Same as BIOMEDIN 217.) Analytic, storage, and interpretive methods to optimize the transformation of genetic, genomic, and biological data into diagnostics and therapeutics for medicine. Topics: access and utility of publicly available data sources; types of genome-scale measurements in molecular biology and genomic medicine; analysis of microarray data; analysis of polymorphisms, proteomics, and protein interactions; linking genome-scale data to clinical data and phenotypes; and new questions in biomedicine using bioinformatics. Case studies. Prerequisites: programming ability at the level of CS 106A and familiarity with statistics and biology.

4 units, Win (Butte, A)

CS 276. Information Retrieval and Web Search

(Same as LINGUIST 286.) Text information retrieval systems; efficient text indexing; Boolean, vector space, and probabilistic retrieval models; ranking and rank aggregation; evaluating IR systems. Text clustering and classification: classification algorithms, latent semantic indexing, taxonomy induction; Web search engines including crawling and indexing, link-based algorithms, and web metadata. Prerequisites: CS 107, CS 109, CS 161.

3 units, Aut (Manning, C; Raghavan, P)

CS 277. Experimental Haptics

Haptics as it relates to creating touch feedback in simulated or virtualized environments. Goal is to develop virtual reality haptic simulators and applications. Theoretical topics: psychophysical issues, performance and design of haptic interfaces, haptic rendering methods for 3-D virtual environments, and haptic simulation and rendering of rigid and deformable solids. Applied topics: the CHAI haptic library; implementation of haptic rendering algorithms; collision detection in 3-D environments; design of real-time models for deformable objects. Guest speakers. Lab/programming exercises; a more open-ended final project. Enrollment limited to 20. Prerequisite: experience with C++. Recommended: 148 or 248, 223A.

3 units, Spr (Staff)

CS 278. Systems Biology

(Same as BIOC 278, BIOE 310, CSB 278.) Complex biological behaviors through the integration of computational modeling and molecular biology. Topics: reconstructing biological networks from high-throughput data and knowledge bases. Network properties. Computational modeling of network behaviors at the small and large scale. Using model predictions to guide an experimental program. Robustness, noise, and cellular variation. Prerequisites: background in biology and mathematical analysis.

3 units, Aut (Covert, M; Dill, D; Brutlag, D; Ferrell, J)

CS 279. Computational Methods for Analysis and Reconstruction of Biological Networks

Types of interactions, including: regulatory such as transcriptional, signaling, and chromatin modification; protein-protein interactions; and genetic. Biological network structure at scales such as single interaction, small subgraphs, and global organization. Methods for analyzing properties of biological networks. Techniques for reconstructing networks from biological data, including: DNA/protein sequence motifs and sequence conservation; gene expression data; and physical binding data such as protein-DNA, protein-RNA, and protein-protein. Network dynamics and evolution. Prerequisites: biology at the level of BIO 41; computer science and data structures at the level of CS 103 and 106; and probability and statistics at the level of STATS 116.

3 units, not given this year

CS 294. Research Project in Computer Science

Student teams work under faculty supervision on research and implementation of a large project in some major sub-discipline in computer science. Lectures on state-of-the-art methods related to the particular problem domain. Prerequisites: consent of instructor.

3 units, not given this year

CS 294A. Research Project in Artificial Intelligence

Student teams under faculty supervision work on research and implementation of a large project in AI. State-of-the-art methods related to the problem domain. Prerequisites: AI course from 220 series, and consent of instructor.

3 units, Aut (Koller, D), Win (Ng, A)

CS 294H. Social Software

Interface, systems, and algorithms concepts in designing social software including personalized home pages and social networks. Topics include collaborative filtering, user-generated content, search, social networks, actions, blogs, and controlled online experimentation.Team-based project.

3 units, Aut (Klemmer, S; Kamvar, S)

CS 294S. Research Project in Software Systems and Security

Topics vary. Focus is on emerging research themes such as programmable open mobile Internet that spans multiple system topics such as human-computer interaction, programming systems, operating systems, networking, and security. May be repeated for credit. Prerequisites: CS 103 and 107.

3 units, Spr (Lam, M)

CS 294W. Writing Intensive Research Project in Computer Science

Restricted to Computer Science and Computer Systems Engineering undergraduates. Students enroll in the CS 294W section attached to the CS 294 project they have chosen.

3 units, Aut (Koller, D), Win (Ng, A), Spr (Lam, M)

CS 295. Software Engineering

Software specification, testing, and verification. Emphasis is on current best practices and technology for developing reliable software at reasonable cost. Assignments focus on applying these techniques to realistic software systems. Prerequisites: 108. Recommended a project course such as 140, 143, or 145. GER:DB-EngrAppSci

2-3 units, Spr (Aiken, A)

CS 298. Seminar on Teaching Introductory Computer Science

Faculty, undergraduates, and graduate students interested in teaching discuss topics raised by teaching computer science at the introductory level. Prerequisite: consent of instructor.

1-3 units, Aut (Sahami, M)

CS 300. Departmental Lecture Series

For first-year Computer Science Ph.D. students. Presentations by members of the department faculty, each describing informally his or her current research interests and views of computer science as a whole.

1 unit, Aut (Motwani, R)

CS 302. Tech Law with Progressive Minds

How the advent of computing technologies is reflected in the confluence of law, public policy, and technology. Issues relating to civil liberties, consumer protection, e-voting, copyright law, patent law, international patent law, trade secrets, political processes, and litigation.

1 unit, not given this year

CS 309. Industrial Lectureships in Computer Science

Guest computer scientist. By arrangement. May be repeated for credit.

1 unit, not given this year

CS 309A. Software as a Service

For technology and business students. The shift from traditional software model of disconnected development and CD-ROM deployment to engineering and delivery on the Internet as a service. Guest industry experts give first-hand view of changes in the software industry.

1 unit, Aut (Chou, T)

CS 315A. Parallel Computer Architecture and Programming

The principles and tradeoffs in the design of parallel architectures. Emphasis is on naming, latency, bandwidth, and synchronization in parallel machines. Case studies on shared memory, message passing, data flow, and data parallel machines illustrate techniques. Architectural studies and lectures on techniques for programming parallel computers. Programming assignments on one or more commercial multiprocessors. Prerequisites: EE 282, and reasonable programming experience.

3 units, Win (Olukotun, O)

CS 315B. Parallel Computing Research Project

Advanced topics and new paradigms in parallel computing including parallel algorithms, programming languages, runtime environments, library debugging/tuning tools, and scalable architectures. Research project. Prerequisite: consent of instructor.

3 units, not given this year

CS 319. Topics in Digital Systems

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, offered occasionally

CS 326A. Motion Planning

Computing object motions in computer graphics, geometrical computing, robotics, or artificial intelligence for applications such as design, manufacturing, robotics, animated graphics, surgical planning, drug design, assembly planning, graphic animation of human figures, humanoid robots, inspection and surveillance, simulation of crowds, and biology. Path planning methods to generate collision-free paths among static obstacles. Extensions include uncertainty, mobile obstacles, manipulating moveable objects, maneuvering with kinematic constraints, and making and breaking contacts. Configuration space, geometric arrangements, and random sampling. Theoretical methods.

3 units, Win (Latombe, J)

CS 327A. Advanced Robotics

Emerging areas of human-centered robotics and interactive haptic simulation of virtual environments. Topics: redundancy; task-oriented dynamics and control, whole-body control-task and posture decomposition, cooperative robots, haptics and simulation, haptically augmented teleoperation, human-friendly robot design. Prerequisites: 223A or equivalent.

3 units, not given this year

CS 329. Topics in Artificial Intelligence

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, offered occasionally

CS 339. Topics in Numerical Analysis

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, offered occasionally

CS 340. Topics in Computer Systems

Topics vary every quarter, and may include advanced material being taught for the first time. May be repeated for credit.

3-4 units, Aut (Staff)

CS 340V. Networked Systems for Virtual Worlds

Open to graduate students and advanced undergraduates. Systems and networking aspects of building large, distributed virtual 3D environments, with a focus on scalability, consistency, security, fairness, and federation. Topics include existing architectures, naming, routing, caching, migration, interoperability, and attribution. Open-ended research project. Prerequisite: some systems and networking background. May be repeated for credit.

3-4 units, Aut (Levis, P)

CS 342. Programming Language Design

Tools for analysis and optimization of iterative coding systems. LDPC codes, Turbo codes, RA codes, optimized ensembles, message passing algorithms, density evolution, analytic techniques. Prerequisite: 376A.

3 units, not given this year

CS 343. Advanced Topics in Compilers

Topics change every year. May be repeated for credit. Prerequisite: 243.

3 units, Spr (Staff)

CS 344. Build an Internet Router

High-performance embedded system design. Student teams of two software engineers (C experience required) and one hardward engineer (Verilog experience required) build a fully functioning Internet router Work in team of three. How router interoperates with others in class. Open-ended design challenge judged by panel of industry experts. Prerequisites: 144, 244A, or network programming experience.

3 units, Spr (McKeown, N)

CS 344B. Advanced Topics in Distributed Systems

Continuation of 244B. The use of distributed systems research in practical systems. New applications due to the growth in high-bandwidth connections. Distributed systems knowledge and techniques from research and system implementations, and active research topics. Readings include research publications.

2 units, not given this year

CS 345. Advanced Topics in Database Systems

Content varies. May be repeated for credit with instructor consent. Prerequisite: 145. Recommended: 245.

3 units, not given this year

CS 345A. Data Mining

Algorithms for mining large-scale data, including data from the web and data maintained by web-based enterprises. Finding frequent itemsets and correlated items; web crawling; finding important web pages; link-spam detection; collaborative filtering; stream mining; clustering; optimizing ad selection; and virtual databases and extraction of relations from the web.

3 units, Win (Ullman, J; Rajaraman, A)

CS 345C. Data Integration

Techniques for integrating data from multiple heterogeneous data sources. Topics: semantic heterogeneity; languages for mediating between disparate data sources; techniques for automatic schema reconciliation and reference reconciliation; adaptive query processing; basics of XML and its relevance to data integration; peer-to-peer data sharing data exchange; combining structured and unstructured data; and dataspaces. Recommended: 145.

3 units, not given this year

CS 346. Database System Implementation

A major database system implementation project realizes the principles and techniques covered in earlier courses. Students independently build a complete database management system, from file structures through query processing, with a personally designed feature or extension. Lectures on project details and advanced techniques in database system implementation, focusing on query processing and optimization. Guest speakers from industry on commercial DBMS implementation techniques. Prerequisites: 145, 245, programming experience in C++.

3-5 units, Spr (Widom, J)

CS 347. Transaction Processing and Distributed Databases

The principles and system organization of distributed databases. Data fragmentation and distribution, distributed database design, query processing and optimization, distributed concurrency control, reliability and commit protocols, and replicated data management. Distributed algorithms for data management: clocks, deadlock detection, and mutual exclusion. Heterogeneous and federated distributed database systems. Overview of commercial systems and research prototypes. Prerequisites: 145, 245.

3 units, Spr (Garcia-Molina, H)

CS 348A. Computer Graphics: Geometric Modeling

The mathematical tools needed for the geometrical aspects of computer graphics and especially for modeling smooth shapes. Fundamentals: homogeneous coordinates, transformations, and perspective. Theory of parametric and implicit curve and surface models: polar forms, Bezier arcs and de Casteljau subdivision, continuity constraints, B-splines, tensor product, and triangular patch surfaces. Subdivision surfaces and multiresolution representations of geometry. Representations of solids and conversions among them. Surface reconstruction from scattered data points. Geometry processing on meshes, including simplification. Prerequisite: linear algebra. Recommended: 164.

3-4 units, not given this year

CS 348B. Computer Graphics: Image Synthesis Techniques

Intermediate level, emphasizing the sampling, shading, and display aspects of computer graphics. Topics: local and global illumination methods including radiosity and distributed ray tracing, texture generation and rendering, volume rendering, strategies for anti-aliasing and photo-realism, human vision and color science as they relate to computer displays, and high-performance architectures for graphics. Written assignments and programming projects. Prerequisite: 248 or equivalent. Recommended: Fourier analysis or digital signal processing.

3-4 units, Spr (Hanrahan, P)

CS 349. Topics in Programming Systems

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, not given this year

CS 349W. Abstractions for Highly Interactive Web Applications

Web development basics, including HTML, Javascript, DOM, and Javascript. Toolkits for developing Web applications, such as Ruby on Rails and Django. Techniques for increasing the interactivity of web applications beyond simple forms, such as AJAX. Interaction styles in web applications.

3 units, Aut (Staff)

CS 355. Advanced Topics in Cryptography

Topics: pseudo-random generation, zero knowledge protocols, elliptic curve systems, threshold cryptography, security analysis using random oracles, lower and upper bounds on factoring and discrete log. May be repeated for credit. Prerequisite: 255.

3 units, not given this year

CS 357. Advanced Topics in Formal Methods

Topics vary annually. Possible topics include automata on infinite words, static analysis methods, runtime analysis methods, verification of real-time and hybrid systems, and formalization of middleware services. May be repeated for credit. Prerequisite: 256.

3 units, offered occasionally

CS 359. Topics in the Theory of Computation

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, not given this year

CS 359D. Hardness of Approximation

Results on and proof techniques for ruling out good approximation algorithms for NP-hard optimization problems. Topics: the PCP theorem; parallel repetition theorem; the unique games conjecture; applications to set cover, clique, max cut, network design, and problems. Prerequisites: 154 and 261, or equivalents.

3 units, not given this year

CS 361A. Advanced Algorithms

Advanced data structures: union-find, self-adjusting data structures and amortized analysis, dynamic trees, Fibonacci heaps, universal hash function and sparse hash tables, persistent data structures. Advanced combinatorial algorithms: algebraic (matrix and polynomial) algorithms, number theoretic algorithms, group theoretic algorithms and graph isomorphism, online algorithms and competitive analysis, strings and pattern matching, heuristic and probabilistic analysis (TSP, satisfiability, cliques, colorings), local search algorithms. May be repeated for credit. Prerequisite: 161 or 261, or equivalent.

3 units, not given this year

CS 361B. Advanced Algorithms

Topics: fundamental techniques used in the development of exact and approximate algorithms for combinational optimization problems such as generalized flow, multicommodity flow, sparsest cuts, generalized Steiner trees, load balancing, and scheduling. Using linear programming, emphasis is on LP duality for design and analysis of approximation algorithms; interior point methods for LP. Techniques for development of strongly polynomial algorithms.

3 units, not given this year

CS 364A. Algorithmic Game Theory

Topics at the interface of theoretical computer science and game theory such as: algorithmic mechanism design; combinatorial and competitive auctions; congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory and the Internet; network games; price of anarchy; and selfish routing. Prerequisites: 154N and 161, or equivalents.

3 units, Aut (Roughgarden, T)

CS 364B. Topics in Algorithmic Game Theory

Topics on the interface of theoretical computer science and game theory. May be taken prior to 364A; may be repeated for credit. Prerequisites: 154N and 161, or equivalents.

3 units, not given this year

CS 365. Randomized Algorithms

Design and analysis of algorithms that use randomness to guide their computations. Basic tools, from probability theory and probabilistic analysis, that are recurrent in algorithmic applications. Randomized complexity theory and game-theoretic techniques. Algebraic techniques. Probability amplification and derandomization. Applications: sorting and searching, data structures, combinatorial optimization and graph algorithms, geometric algorithms and linear programming, approximation and counting problems, parallel and distributed algorithms, online algorithms, number-theoretic algorithms. Prerequisites: 161 or 261, STATS 116, or equivalents.

3 units, Aut (Motwani, R)

CS 369. Topics in Analysis of Algorithms

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

3 units, not given this year

CS 369A. Advanced Geometric Algorithms

Approximate, randomized, and high-dimensional geometric algorithms. Topics of current interest: clustering; nearest-neighbor search; shortest paths; geometric random walks; shape fitting; geometric embeddings; coresets; geometric TSP; and linear programming. Prerequisites: 368 or equivalent.

3 units, not given this year

CS 369F. Topics in Analysis of Algorithms

Focus is on combinatorial optimization with emphasis on online algorithms.

3 units, Spr (Plotkin, S)

CS 374. Algorithms in Biology

(Same as BIOMEDIN 374.) Algorithms and computational models applied to molecular biology and genetics. Topics vary annually. Possible topics include biological sequence comparison, annotation of genes and other functional elements, molecular evolution, genome rearrangements, microarrays and gene regulation, protein folding and classification, molecular docking, RNA secondary structure, DNA computing, and self-assembly. May be repeated for credit. Prerequisites: 161, 262 or 274, or BIOCHEM 218, or equivalents.

2-3 units, Spr (Batzoglou, S)

CS 376. Research Topics in Human-Computer Interaction

Interactive systems, research areas in interaction techniques, and the design, prototyping, and evaluation of user interfaces. Topics: computer-supported cooperative work; audio, speech, and multimodal interfaces; user interface toolkits; design and evaluation methods; ubiquitous and context-aware computing; tangible interfaces, haptic interaction; and mobile interfaces.

3 units, alternate years, not given this year

CS 377. Topics in Human-Computer Interaction

Contents change each quarter. May be repeated for credit. See http://hci.stanford.edu/academics for offerings.

2-3 units, not given this year

CS 378. Phenomenological Foundations of Cognition, Language, and Computation

Critical analysis of theoretical foundations of the cognitive approach to language, thought, and computation. Contrasts of the rationalistic assumptions of current linguistics and artificial intelligence with alternatives from phenomenology, theoretical biology, critical literary theory, and socially-oriented speech act theory. Emphasis is on the relevance of theoretical orientation to the design, implementation, and impact of computer systems as it affects human-computer interaction.

3-4 units, alternate years, not given this year

CS 377W. Create Engaging Web Applications Using Metrics and Learning on Facebook

Experimental course. Students work in small, interdisciplinary teams to create, launch, and optimize web-based applications for social networks such as Facebook. Tools include Google Analytics. Online experiments and user responses to learn how to iterate and improve applications. Guest experts.

3-4 units, not given this year

CS 379D. Computer Vision and Image Analysis in the Study of Art

Application of algorithms to computer vision, image analysis, and two-dimensional Western art such as paintings, drawings, and etchings. Topics: multispectral image enhancement and color manipulation; geometric perspective and warped (anamorphic) perspective; visual metrology; view synthesis; statistical analysis of form; texture and brushstrokes; and shape-from-shading. These techniques, pattern classification, statistical estimation methods, and stylometry (quantification of artistic style) address art historical problems such as attribution, authentication, and dating to reveal artists' working methods.

3 units, not given this year

CS 379Y. Interdisciplinary Design for Agile Aging

(Same as HUMBIO 131, MED 279Y.) Offered by the d.school. Perspectives from computer science, design, social and behavioral sciences, physiology, geriatrics, and biodesign to develop projects that address the potential of people to maintain vitality and mobility as they age. New ways to integrate computer and device technologies with behavioral and social interventions. Focus is on small-group projects based on real-world need finding. Prerequisite: background in one of design, computing, medicine, behavioral sciences, communications, or business.

3-4 units, Win (Winograd, C; Winograd, T; Friedlander, A; Yock, P)

CS 379Z. Design Project for Agile Aging

(Same as MED 279Z.) Second of two quarter sequence; students may take 379Y without 379Z; offered by the d.school. Small teams develop projects that can have an impact in the world through products, programs, and practices that affect people's health on a broad scale. Technical interventions, social and contextual design, organizational contexts, and business and distribution issues. Limited enrollment. Prerequisites: CS379Y, and master's level skills in one of design, computing, medicine, behavioral sciences, communications, or business.

3-4 units, not given this year

CS 390A. Curricular Practical Training

Educational opportunities in high technology research and development labs in the computing industry. Qualified computer science students engage in internship work and integrate that work into their academic program. Students register during the quarter they are employed and complete a research report outlining their work activity, problems investigated, results, and follow-on projects they expect to perform. 390 A, B, and C may each be taken once. (Motwani)

1 unit, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 390B. Curricular Practical Training

1 unit, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 390C. Curricular Practical Training

1 unit, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 393. Computer Laboratory

For CS graduate students. A substantial computer program is designed and implemented; written report required. Recommended as a preparation for dissertation research. Register using the section number associated with the instructor. Prerequisite: consent of instructor.

1-9 units, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 395. Independent Database Project

For graduate students in Computer Science. Use of database management or file systems for a substantial application or implementation of components of database management system. Written analysis and evaluation required. Register using the section number associated with the instructor. Prerequisite: consent of instructor.

1-6 units, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 399. Independent Project

Letter grade only.

1-9 units, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 399P. Independent Project

Graded satisfactory/no credit.

1-9 units, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 447. Software Design Experiences

Small teams develop technology prototypes combining product and interaction design. Focus is on software and hardware interfaces, interaction, design aesthetics, and underpinnings of successful design including a reflective, interactive design process, group dynamics of interdisciplinary teamwork, and working with users. Prerequisite: CS 247A.

3-4 units, Spr (Winograd, T)

CS 448. Topics in Computer Graphics

Topic changes each quarter. Recent topics: exotic input and display technologies, graphics architectures, advanced rendering techniques, modeling shape and motion, data visualization, and computational photography. See http://graphics.stanford.edu/courses for offerings. May be repeated for credit. Prerequisite: 248 or consent of instructor.

3-4 units, not given this year

CS 448A. Topics in Computer Graphics: Computational Photography

Capabilities unique to digital cameras. Sensors; in-camera processing systems; the ability to refocus photographs after they are taken or to combine views taken with different camera settings, aim, or placement. New technologies for creating efficient, controllable illumination such as pulsed LEDs or video projectors; the ability to selectively illuminate objects, recolor a scene, or extract shape information. How these developments relax notions of what constitutes a photograph, blur the distinction between photography and scene modeling, and lead to new photographic techniques, scientific tools, and art forms. (Levoy)

3-4 units, not given this year

CS 448B. Topics in Computer Graphics: Special Topics in Visualization

Topic changes each quarter. Recent topics: exotic input and display technologies, graphics architecures, advanced rendering techniques, modeling shape and motion, data visualization, and computational photography. See http://graphics.stanford.edu/courses/ for current offerings.

1-3 units, not given this year

CS 450. Introduction to Biotechnology

Academic and industrial experts discuss latest developments in fields such as bioenergy, green process technology, the production of industrial chemicals from renewable resources, protein pharmaceutical production, industrial enzyme production, stem cell applications, medical diagnostics, and medical imaging. Discussions of biotechnology ethics, business and patenting issues, and entrepreneurship in biotechnology.

3 units, not given this year

CS 468. Topics in Geometric Algorithms

Recent offerings include: shape matching, proximity and nearest-neighbor problems, visibility and motion planning, collision detection, geometric sampling methods, shape interpolation, and computational topology. May be repeated for credit. Prerequisite: 268, 368, or consent of instructor.

3 units, Aut (Memoli Techera, R), Win (Staff), Spr (Koltun, V)

CS 499. Advanced Reading and Research

For CS graduate students. Register using the section number associated with the instructor. Prerequisite: consent of instructor.

1-15 units, Aut (Staff), Win (Staff), Spr (Staff), Sum (Staff)

CS 528. Broad Area Colloquium for Artificial Intelligence, Geometry, Graphics, Robotics, and Vision

Weekly series of informal research talks on topics related to perceiving, modeling, manipulating, and displaying the physical world. The computational models and numerical methods underlying these topics. May be repeated for credit.

1 unit, not given this year

CS 531. Numerical Analysis/Scientific Computing Seminar

Weekly research lectures by experts from academia, national laboratories, industry, and doctoral students. May be repeated for credit.

1 unit, not given this year

CS 541. Clean Slate Internet Research Seminar

How would a global communications infrastructure be designed starting from a hypothetical clean slate, given what is known now? How should the Internet look in 15 years? Research questions and ideas and approaches in subfields of with Internet design including network architecture, network security and robustness, mobile wireless networking, distributed services and systems, and theory-inspired network architecture. Guest speakers from Stanford and industry. See http://cleanslate.stanford.edu.

1 unit, alternate years, not given this year

CS 545. Database and Information Management Seminar

Current research and industrial innovation in database and information systems.

1 unit, Win (Widom, J)

CS 547. Human-Computer Interaction Seminar

Weekly speakers. May be repeated for credit.

1 unit, Aut (Winograd, T), Win (Winograd, T), Spr (Winograd, T)

CS 548. Internet and Distributed Systems Seminar

Guest speakers from academia and industry. May be repeated for credit.

1 unit, not given this year

CS 571. Surgical Robotics Seminar

Surgical robots developed and implemented clinically on varying scales. Seminar goal is to expose students from engineering, medicine, and business to guest lecturers from academia and industry.engineering and clinical aspects connected to design and use of surgical robots, varying in degree of complexity and procedural role.

1 unit, Win (Barbagli, F)

Registrar's Office

Stanford Bulletin, Archive 2008-09

Stanford Bulletin, Archive 2008-09

Alphabetical Index

Bulletin Archive

Graduate courses in Computer Science