CS 1
Introduction to Computer Programming
9 units (3-4-2)
|
first term
A course on computer programming emphasizing the program design process and pragmatic programming skills. It will use the Python programming language and will not assume previous programming experience. Material covered will include data types, variables, assignment, control structures, functions, scoping, compound data, string processing, modules, basic input/output (terminal and file), as well as more advanced topics such as recursion, exception handling and object-oriented programming. Program development and maintenance skills including debugging, testing, and documentation will also be taught. Assignments will include problems drawn from fields such as graphics, numerics, networking, and games. At the end of the course, students will be ready to learn other programming languages in courses such as CS 11, and will also be ready to take more in-depth courses such as CS 2 and CS 4.
Instructor:
Vanier
CS 2
Introduction to Programming Methods
9 units (2-6-1)
|
second term
Prerequisites: CS 1 or equivalent.
CS 2 is a demanding course in programming languages and computer science. Topics covered include data structures, including lists, trees, and graphs; implementation and performance analysis of common algorithms; algorithm design principles, in particular recursion and dynamic programming; concurrency and network programming; basic numerical computation methods. Heavy emphasis is placed on the use of compiled languages and development tools, including source control and debugging. The course includes weekly laboratory exercises and written homework covering the lecture material and program design. The course is intended to establish a foundation for further work in many topics in the computer science option.
Instructors:
Barr, Desbrun, Libeskind-Hadas
CS 3
Introduction to Software Engineering
9 units (2-4-3)
|
third term
Prerequisites: CS 2 or equivalent.
CS 3 is a practical introduction to software engineering with an emphasis on understanding and minimizing risk in large software projects. Students will work in teams on a course-long project. Topics covered include revision control, code reviews, testing and testability, code readability, API design, refactoring, and documentation. The course provides opportunities to present your work to the class, and emphasizes working with other people's code, both that of classmates and pre-existing frameworks. Not offered 2016-17.
CS 4
Fundamentals of Computer Programming
9 units (3-4-2)
|
second term
Prerequisites: CS 1 or instructor's permission.
This course gives students the conceptual background necessary to construct and analyze programs, which includes specifying computations, understanding evaluation models, and using major programming language constructs (functions and procedures, conditionals, recursion and looping, scoping and environments, compound data, side effects, higher-order functions and functional programming, and object-oriented programming). It emphasizes key issues that arise in programming and in computation in general, including time and space complexity, choice of data representation, and abstraction management. This course is intended for students with some programming background who want a deeper understanding of the conceptual issues involved in computer programming.
Instructor:
Vanier
Ma/CS 6 abc
Introduction to Discrete Mathematics
9 units (3-0-6)
|
first, second, third terms
Prerequisites: for Ma/CS 6 c, Ma/CS 6 a or Ma 5 a or instructor's permission.
First term: a survey emphasizing graph theory, algorithms, and applications of algebraic structures. Graphs: paths, trees, circuits, breadth-first and depth-first searches, colorings, matchings. Enumeration techniques; formal power series; combinatorial interpretations. Topics from coding and cryptography, including Hamming codes and RSA. Second term: directed graphs; networks; combinatorial optimization; linear programming. Permutation groups; counting nonisomorphic structures. Topics from extremal graph and set theory, and partially ordered sets. Third term: elements of computability theory and computational complexity. Discussion of the P=NP problem, syntax and semantics of propositional and first-order logic. Introduction to the Gödel completeness and incompleteness theorems.
Instructors:
Scheffer, Lupini
CS 9
Introduction to Computer Science Research
1 unit (1-0-0)
|
first term
This course will introduce the research areas of the computer science faculty, through weekly overview talks by the faculty aimed at first-year undergraduates. Others may wish to take the course to gain an understanding of the scope of the field. Graded pass/fail.
Instructor:
Desbrun
CS 11
Computer Language Lab
3 units (0-3-0)
|
first, second, third terms
Prerequisites: CS 1 or instructor's permission.
A self-paced lab that provides students with extra practice and supervision in transferring their programming skills to a particular programming language. The course can be used for any language of the student's choosing, subject to approval by the instructor. A series of exercises guide the student through the pragmatic use of the chosen language, building his or her familiarity, experience, and style. More advanced students may propose their own programming project as the target demonstration of their new language skills. This course is available for undergraduate students only. Graduate students should register for CS 111. CS 11 may be repeated for credit of up to a total of nine units.
Instructors:
Pinkston, Vanier
CS 21
Decidability and Tractability
9 units (3-0-6)
|
second term
Prerequisites: CS 2 (may be taken concurrently).
This course introduces the formal foundations of computer science, the fundamental limits of computation, and the limits of efficient computation. Topics will include automata and Turing machines, decidability and undecidability, reductions between computational problems, and the theory of NP-completeness.
Instructor:
Umans
CS 24
Introduction to Computing Systems
9 units (3-3-3)
|
third term
Prerequisites: Familiarity with C equivalent to having taken the CS 11 C track.
Basic introduction to computer systems, including hardware-software interface, computer architecture, and operating systems. Course emphasizes computer system abstractions and the hardware and software techniques necessary to support them, including virtualization (e.g., memory, processing, communication), dynamic resource management, and common-case optimization, isolation, and naming.
Instructor:
Pinkston
CS 38
Introduction to Algorithms
9 units (3-0-6)
|
third term
Prerequisites: CS 2; Ma/CS 6 a or Ma 121 a; and CS 21 or CS/EE/Ma 129 a.
This course introduces techniques for the design and analysis of efficient algorithms. Major design techniques (the greedy approach, divide and conquer, dynamic programming, linear programming) will be introduced through a variety of algebraic, graph, and optimization problems. Methods for identifying intractability (via NP-completeness) will be discussed.
Instructor:
Schulman
EE/CS 51
Principles of Microprocessor Systems
12 units (4-5-3)
|
first term
The principles and design of microprocessor-based computer systems. Lectures cover both hardware and software aspects of microprocessor system design such as interfacing to input and output devices, user interface design, real-time systems, and table-driven software. The homework emphasis is on software development, especially interfacing with hardware, in assembly language.
Instructor:
George
EE/CS 52 ab
Microprocessor Systems Laboratory
9 units (3-6-0) second term
|
6 units (1-5-0) third term
Prerequisites: EE/CS 51 or equivalent. The student will design, build, and program a specified microprocessor-based system. This structured laboratory is organized to familiarize the student with electronic circuit construction techniques, modern development facilities, and standard design techniques. The lectures cover topics in microprocessor system design such as display technologies, interfacing with analog systems, and programming microprocessors in high-level languages.
Instructor:
George
EE/CS 53
Microprocessor Project Laboratory
12 units (0-12-0)
|
first, second, third terms
Prerequisites: EE/CS 52 ab or equivalent.
A project laboratory to permit the student to select, design, and build a microprocessor-based system. The student is expected to take a project from proposal through design and implementation (possibly including PCB fabrication) to final review and documentation. May be repeated for credit.
Instructor:
George
CS/EE/ME 75 abc
Introduction to Multidisciplinary Systems Engineering
3 units (2-0-1) , 6 units (2-0-4), or 9 units (2-0-7) first term
|
6 units (2-3-1), 9 units (2-6-1), or 12 units (2-9-1) second term
This course presents the fundamentals of modern multidisciplinary systems engineering in the context of a substantial design project. Students from a variety of disciplines will conceive, design, implement, and operate a system involving electrical, information, and mechanical engineering components. Specific tools will be provided for setting project goals and objectives, managing interfaces between component subsystems, working in design teams, and tracking progress against tasks. Students will be expected to apply knowledge from other courses at Caltech in designing and implementing specific subsystems. During the first two terms of the course, students will attend project meetings and learn some basic tools for project design, while taking courses in CS, EE, and ME that are related to the course project. During the third term, the entire team will build, document, and demonstrate the course design project, which will differ from year to year. Freshmen must receive permission from the lead instructor to enroll. Not offered 2016-17.
CS 80 abc
Undergraduate Thesis
9 units
|
first, second, third terms
Prerequisites: instructor's permission, which should be obtained sufficiently early to allow time for planning the research.
Individual research project, carried out under the supervision of a member of the computer science faculty (or other faculty as approved by the computer science undergraduate option representative). Projects must include significant design effort. Written report required. Open only to upperclass students. Not offered on a pass/fail basis.
Instructor:
Staff
CS 81 abc
Undergraduate Projects in Computer Science
Units are assigned in accordance with work accomplished
Prerequisites: Consent of supervisor is required before registering.
Supervised research or development in computer science by undergraduates. The topic must be approved by the project supervisor, and a formal final report must be presented on completion of research. This course can (with approval) be used to satisfy the project requirement for the CS major. Graded pass/fail.
Instructor:
Staff
CS 90
Undergraduate Reading in Computer Science
Units are assigned in accordance with work accomplished
Prerequisites: Consent of supervisor is required before registering.
Supervised reading in computer science by undergraduates. The topic must be approved by the reading supervisor, and a formal final report must be presented on completion of the term. Graded pass/fail.
Instructor:
Staff
CS 101 abc
Special Topics in Computer Science
Units in accordance with work accomplished
|
offered by announcement
Prerequisites: CS 21 and CS 38, or instructor's permission.
The topics covered vary from year to year, depending on the students and staff. Primarily for undergraduates.
CS 102 abc
Seminar in Computer Science
3, 6, or 9 units as arranged with the instructor.
Prerequisites: Instructor's permission required.
CS 103 abc
Reading in Computer Science
3, 6, or 9 units as arranged with the instructor
Prerequisites: Instructor's permission required.
HPS/Pl/CS 110
Causation and Explanation
9 units (3-0-6)
|
second term
An examination of theories of causation and explanation in philosophy and neighboring disciplines. Topics discussed may include probabilistic and counterfactual treatments of causation, the role of statistical evidence and experimentation in causal inference, and the deductive-nomological model of explanation. The treatment of these topics by important figures from the history of philosophy such as Aristotle, Descartes, and Hume may also be considered. Not offered 2016-17.
CS 111
Programming Practicum
3 units (0-3-0)
|
first, second, third terms
Prerequisites: CS 1 or equivalent.
A self-paced lab that provides students with extra practice and supervision in transferring their programming skills to a particular programming language. The course can be used for any language of the student's choosing, subject to approval by the instructor. A series of exercises guide the student through the pragmatic use of the chosen language, building his or her familiarity, experience, and style. More advanced students may propose their own programming project as the target demonstration of their new language skills. This course is available for graduate students only. Undergraduates should register for CS 11.
Instructors:
Pinkston, Vanier
ACM/CS 114 ab
Parallel Algorithms for Scientific Applications
9 units (3-0-6)
|
second, third term
Prerequisites: ACM 11, 106 or equivalent.
Introduction to parallel program design for numerically intensive scientific applications. Parallel programming methods; distributed-memory model with message passing using the message passing interface; shared-memory model with threads using open MP, CUDA; object-based models using a problem-solving environment with parallel objects. Parallel numerical algorithms: numerical methods for linear algebraic systems, such as LU decomposition, QR method, CG solvers; parallel implementations of numerical methods for PDEs, including finite-difference, finite-element; particle-based simulations. Performance measurement, scaling and parallel efficiency, load balancing strategies. Not offered 2016-17.
CS 115
Functional Programming
9 units (3-4-2)
|
third term
Prerequisites: CS 1 and CS 4.
This course is a both a theoretical and practical introduction to functional programming, a paradigm which allows programmers to work at an extremely high level of abstraction while simultaneously avoiding large classes of bugs that plague more conventional imperative and object-oriented languages. The course will introduce and use the lazy functional language Haskell exclusively. Topics include: recursion, first-class functions, higher-order functions, algebraic data types, polymorphic types, function composition, point-free style, proving functions correct, lazy evaluation, pattern matching, lexical scoping, type classes, and modules. Some advanced topics such as monad transformers, parser combinators, dynamic typing, and existential types are also covered.
Instructor:
Vanier
CS 116
Reasoning about Program Correctness
9 units (3-0-6)
|
first term
Prerequisites: CS 1 or equivalent.
This course presents the use of logic and formal reasoning to prove the correctness of sequential and concurrent programs. Topics in logic include propositional logic, basics of first-order logic, and the use of logic notations for specifying programs. The course presents a programming notation and its formal semantics, Hoare logic and its use in proving program correctness, predicate transformers and weakest preconditions, and fixed-point theory and its application to proofs of programs.
Instructor:
Staff
Ma/CS 117 abc
Computability Theory
9 units (3-0-6)
|
first, second, third terms
Prerequisites: Ma 5 or equivalent, or instructor's permission.
Various approaches to computability theory, e.g., Turing machines, recursive functions, Markov algorithms; proof of their equivalence. Church's thesis. Theory of computable functions and effectively enumerable sets. Decision problems. Undecidable problems: word problems for groups, solvability of Diophantine equations (Hilbert's 10th problem). Relations with mathematical logic and the Gödel incompleteness theorems. Decidable problems, from number theory, algebra, combinatorics, and logic. Complexity of decision procedures. Inherently complex problems of exponential and superexponential difficulty. Feasible (polynomial time) computations. Polynomial deterministic vs. nondeterministic algorithms, NP-complete problems and the P = NP question.
Instructors:
Kechris, Lupini
CS 118
Logic Model Checking for Formal Software Verification
9 units (3-3-3)
|
second term
An introduction to the theory and practice of logic model checking as an aid in the formal proofs of correctness of concurrent programs and system designs. The specific focus is on automata-theoretic verification. The course includes a study of the theory underlying formal verification, the correctness of programs, and the use of software tools in designs.
Instructor:
Holzmann
CS 119
Reliable Software: Testing and Monitoring
9 units (3-3-3)
|
third term
Prerequisites: CS 1 or equivalent; CS 116 and CS 118 are recommended.
The class discusses theoretical and practical aspects of software testing and monitoring. Topics include finite state machine testing algorithms, random testing, constraint-based testing, coverage measures, automated debugging, logics and algorithms for runtime monitoring, and aspect-oriented approaches to monitoring. Emphasis is placed on automation. Students will be expected to develop and use software testing and monitoring tools to develop reliable software systems. Not offered 2016-17.
CS/Ph 120
Quantum Cryptography
9 units (3-0-6)
|
first term
Prerequisites: Ma 1b, Ph 2b or Ph 12b, CS 21, CS 38 or equivalent recommended (or instructor's permission).
This course is an introduction to quantum cryptography: how to use quantum effects, such as quantum entanglement and uncertainty, to implement cryptographic tasks with levels of security that are impossible to achieve classically. The course covers the fundamental ideas of quantum information that form the basis for quantum cryptography, such as entanglement and quantifying quantum knowledge. We will introduce the security definition for quantum key distribution and see protocols and proofs of security for this task. We will also discuss the basics of device-independent quantum cryptography as well as other cryptographic tasks and protocols, such as bit commitment or position-based cryptography.
Instructor:
Vidick
CS 121
Introduction to Relational Databases
9 units (3-0-6)
|
first term
Prerequisites: CS 1 or equivalent.
Introduction to the basic theory and usage of relational database systems. It covers the relational data model, relational algebra, and the Structured Query Language (SQL). The course introduces the basics of database schema design and covers the entity-relationship model, functional dependency analysis, and normal forms. Additional topics include other query languages based on the relational calculi, data-warehousing and dimensional analysis, writing and using stored procedures, working with hierarchies and graphs within relational databases, and an overview of transaction processing and query evaluation. Extensive hands-on work with SQL databases.
Instructor:
Pinkston
CS 122
Database System Implementation
9 units (3-3-3)
|
second term
Prerequisites: CS2, CS38, CS 121 and familiarity with Java, or instructor's permission.
This course explores the theory, algorithms, and approaches behind modern relational database systems. Topics include file storage formats, query planning and optimization, query evaluation, indexes, transaction processing, concurrency control, and recovery. Assignments consist of a series of programming projects extending a working relational database, giving hands-on experience with the topics covered in class. The course also has a strong focus on proper software engineering practices, including version control, testing, and documentation.
Instructor:
Pinkston
CS 123
Projects in Database Systems
9 units (0-0-9)
|
third term
Prerequisites: CS121 and CS122.
Students are expected to execute a substantial project in databases, write up a report describing their work, and make a presentation.
Instructor:
Pinkston
CS 124
Operating Systems
12 units (3-6-3)
|
second term
Prerequisites: CS 24.
This course explores the major themes and components of modern operating systems, such as kernel architectures, the process abstraction and process scheduling, system calls, concurrency within the OS, virtual memory management, and file systems. Students must work in groups to complete a series of challenging programming projects, implementing major components of an instructional operating system. Most programming is in C, although some IA32 assembly language programming is also necessary. Familiarity with the material in CS 24 is strongly advised before attempting this course.
Instructor:
Pinkston
EE/Ma/CS 126 ab
Information Theory
9 units (3-0-6)
|
first, second terms
Prerequisites: Ma 3.
Shannon's mathematical theory of communication, 1948-present. Entropy, relative entropy, and mutual information for discrete and continuous random variables. Shannon's source and channel coding theorems. Mathematical models for information sources and communication channels, including memoryless, Markov, ergodic, and Gaussian. Calculation of capacity and rate-distortion functions. Universal source codes. Side information in source coding and communications. Network information theory, including multiuser data compression, multiple access channels, broadcast channels, and multiterminal networks. Discussion of philosophical and practical implications of the theory. This course, when combined with EE 112, EE/Ma/CS 127, EE 161, EE 167, and/or EE226 should prepare the student for research in information theory, coding theory, wireless communications, and/or data compression.
Instructor:
Effros
EE/Ma/CS 127
Error-Correcting Codes
9 units (3-0-6)
|
second term
Prerequisites: Ma 2.
This course develops from first principles the theory and practical implementation of the most important techniques for combating errors in digital transmission or storage systems. Topics include algebraic block codes, e.g., Hamming, BCH, Reed-Solomon (including a self-contained introduction to the theory of finite fields); and the modern theory of sparse graph codes with iterative decoding, e.g. LDPC codes, turbo codes. The students will become acquainted with encoding and decoding algorithms, design principles and performance evaluation of codes.
Instructor:
Kostina
CS/EE/Ma 129 abc
Information and Complexity
9 units (3-0-6), first and second terms
|
(1-4-4) third term
Prerequisites: basic knowledge of probability and discrete mathematics.
A basic course in information theory and computational complexity with emphasis on fundamental concepts and tools that equip the student for research and provide a foundation for pattern recognition and learning theory. First term: what information is and what computation is; entropy, source coding, Turing machines, uncomputability. Second term: topics in information and complexity; Kolmogorov complexity, channel coding, circuit complexity, NP-completeness. Third term: theoretical and experimental projects on current research topics. Not offered 2016-17.
ME/CS 132 ab
Advanced Robotics: Navigation and Vision
9 units (3-6-0)
|
second, third terms
Prerequisites: ME 115 ab.
The course focuses on current topics in robotics research in the area of autonomous navigation and vision. Topics will include mobile robots, multilegged walking machines, use of vision in navigation systems. The lectures will be divided between a review of the appropriate analytical techniques and a survey of the current research literature. Course work will focus on an independent research project chosen by the student.
Instructors:
Matthies, Burdick
EE/CS/EST 135
Power System Analysis
9 units (3-3-3)
|
second term
Prerequisites: EE 44, Ma 2, or equivalent.
Phasor representation, 3-phase transmission system, per-phase analysis; power system modeling, transmission line, transformer, generator; network matrix, power flow solution, optimal power flow; Swing equation, stability, protection; demand response, power markets.
Instructor:
Low
CS 138
Computer Algorithms
9 units (3-0-6)
|
third term
Prerequisites: CS 21 and CS 38, or instructor's permission.
Design and analysis of algorithms. Techniques for problems concerning graphs, flows, number theory, string matching, data compression, geometry, linear algebra and coding theory. Optimization, including linear programming. Randomization. Basic complexity theory and cryptography.
Instructor:
Schulman
CMS/CS 139
Analysis and Design of Algorithms
12 units (3-0-9)
|
second term
Prerequisites: Ma 2, Ma 3, Ma/CS 6a, CS 21, CS 38/138, CMS/ACM/EE 116, or instructor's permission.
This course covers advanced topics in the design and analysis of algorithms. Topics are drawn from approximation algorithms, randomized algorithms, online algorithms, streaming algorithms, and other areas of current research interest in algorithms.
Instructor:
Vidick
CS 141
Hack Society
9 units (1-6-2)
|
third term
Prerequisites: CS 1 and CS 2.
There is a large gap between the public and private sectors' effective use of technology. This gap presents an opportunity for the development of innovative solutions to problems faced by society. Students will work with start-up, corporate, nonprofit, and government partners to develop and deploy technology based projects that address this gap. Course material will offer an introduction to the design, development, and analysis of digital technology with examples derived from services typically found in the public sector.
Instructor:
Ralph
CS 142
Distributed Computing
9 units (3-0-6)
|
third term
Prerequisites: CS 24, CS 38.
Programming distributed systems. Mechanics for cooperation among concurrent agents. Programming sensor networks and cloud computing applications. Applications of machine learning and statistics by using parallel computers to aggregate and analyze data streams from sensors. Not offered 2016-17.
CS/EE 143
Communication Networks
9 units (3-3-3)
|
first term
Prerequisites: Ma 2, Ma 3, CS 24 and CS 38, or instructor permission.
This course focuses on the link layer (two) through the transport layer (four) of Internet protocols. It has two distinct components, analytical and systems. In the analytical part, after a quick summary of basic mechanisms on the Internet, we will focus on congestion control and explain: (1) How to model congestion control algorithms? (2) Is the model well defined? (3) How to characterize the equilibrium points of the model? (4) How to prove the stability of the equilibrium points? We will study basic results in ordinary differential equations, convex optimization, Lyapunov stability theorems, passivity theorems, gradient descent, contraction mapping, and Nyquist stability theory. We will apply these results to prove equilibrium and stability properties of the congestion control models and explore their practical implications. In the systems part, the students will build a software simulator of Internet routing and congestion control algorithms. The goal is not only to expose students to basic analytical tools that are applicable beyond congestion control, but also to demonstrate in depth the entire process of understanding a physical system, building mathematical models of the system, analyzing the models, exploring the practical implications of the analysis, and using the insights to improve the design.
Instructor:
Low
CMS/CS/EE 144
Networks: Structure Economics
12 units (3-3-6)
|
second term
Prerequisites: Ma 2, Ma 3, Ma/CS 6a, and CS 38, or instructor permission.
Social networks, the web, and the internet are essential parts of our lives and we all depend on them every day, but do you really know what makes them work? This course studies the "big" ideas behind our networked lives. Things like, what do networks actually look like (and why do they all look the same)? How do search engines work? Why do memes spread the way they do? How does web advertising work? For all these questions and more, the course will provide a mixture of both mathematical analysis and hands-on labs. The course assumes students are comfortable with graph theory, probability, and basic programming.
Instructor:
Wierman
CS/EE 145
Projects in Networking
9 units (0-0-9)
|
third term
Prerequisites: Either CMS/CS/EE 144 or CS 142 in the preceding term, or instructor permission.
Students are expected to execute a substantial project in networking, write up a report describing their work, and make a presentation.
Instructor:
Staff
CS/EE 146
Advanced Networking
9 units (3-3-3)
|
third term
Prerequisites: CS/EE 143 or instructor's permission.
This is a research-oriented course meant for undergraduates and beginning graduate students who want to learn about current research topics in networks such as the Internet, power networks, social networks, etc. The topics covered in the course will vary, but will be pulled from current research topics in the design, analysis, control, and optimization of networks, protocols, and Internet applications. Usually offered in alternate years. Not offered 2016-17.
EE/CS 147
Digital Ventures Design
9 units (3-3-3)
|
first term
Prerequisites: none.
This course aims to offer the scientific foundations of analysis, design, development, and launching of innovative digital products and study elements of their success and failure. The course provides students with an opportunity to experience combined team-based design, engineering, and entrepreneurship. The lectures present a disciplined step-by-step approach to develop new ventures based on technological innovation in this space, and with invited speakers, cover topics such as market analysis, user/product interaction and design, core competency and competitive position, customer acquisition, business model design, unit economics and viability, and product planning. Throughout the term students will work within an interdisciplinary team of their peers to conceive an innovative digital product concept and produce a business plan and a working prototype. The course project culminates in a public presentation and a final report. Every year the course and projects focus on a particular emerging technology theme.
Instructor:
Lahouti
EE/CNS/CS 148
Selected Topics in Computational Vision
9 units (3-0-6)
|
third term
Prerequisites: undergraduate calculus, linear algebra, geometry, statistics, computer programming.
The class will focus on an advanced topic in computational vision: recognition, vision-based navigation, 3-D reconstruction. The class will include a tutorial introduction to the topic, an exploration of relevant recent literature, and a project involving the design, implementation, and testing of a vision system.
Instructor:
Perona
CS/SS/Ec 149
Introduction to Algorithmic Economics
9 units (3-0-6)
|
second term
This course will equip students to engage with active research at the intersection of social and information sciences, including: algorithmic game theory and mechanism design; auctions; matching markets; and learning in games.
Instructor:
Echenique and Pomatto
CS 150
Probability and Algorithms
9 units (3-0-6)
|
second term
Prerequisites: CS 38 a and Ma 5 abc.
Elementary randomized algorithms and algebraic bounds in communication, hashing, and identity testing. Game tree evaluation. Topics may include randomized parallel computation; independence, k-wise independence and derandomization; rapidly mixing Markov chains; expander graphs and their applications; clustering algorithms.
Instructor:
Schulman
CS 151
Complexity Theory
12 units (3-0-9)
|
third term
Prerequisites: CS 21 and CS 38, or instructor's permission.
This course describes a diverse array of complexity classes that are used to classify problems according to the computational resources (such as time, space, randomness, or parallelism) required for their solution. The course examines problems whose fundamental nature is exposed by this framework, the known relationships between complexity classes, and the numerous open problems in the area.
Instructor:
Umans
CS/SS 152
Introduction to Data Privacy
9 units (3-0-6)
|
first term
Prerequisites: Ma 3, CS 24 and CS 38, or instructor's permission.
How should we define privacy? What are the tradeoffs between useful computation on large datasets and the privacy of those from whom the data is derived? This course will take a mathematically rigorous approach to addressing these and other questions at the frontier of research in data privacy. We will draw connections with a wide variety of topics, including economics, statistics, information theory, game theory, probability, learning theory, geometry, and approximation algorithms. Not offered 2016-17.
CS 153
Current Topics in Theoretical Computer Science
9 units (3-0-6)
|
second term
Prerequisites: CS 21 and CS 38, or instructor's permission.
May be repeated for credit, with permission of the instructor. Students in this course will study an area of current interest in theoretical computer science. The lectures will cover relevant background material at an advanced level and present results from selected recent papers within that year's chosen theme. Students will be expected to read and present a research paper. Not offered 2016-17.
CMS/CS/CNS/EE 155
Machine Learning Data Mining
12 units (3-3-6)
|
second term
Prerequisites: background in algorithms and statistics (CS/CNS/EE/NB 154 or CS/CNS/EE 156 a or instructor's permission).
This course will cover popular methods in machine learning and data mining, with an emphasis on developing a working understanding of how to apply these methods in practice. This course will also cover core foundational concepts underpinning and motivating modern machine learning and data mining approaches. This course will be research-oriented, and will cover recent research developments.
Instructor:
Yue
CS/CNS/EE 156 ab
Learning Systems
9 units (3-0-6)
|
first, third terms
Prerequisites: Ma 2 and CS 2, or equivalent.
Introduction to the theory, algorithms, and applications of automated learning. How much information is needed to learn a task, how much computation is involved, and how it can be accomplished. Special emphasis will be given to unifying the different approaches to the subject coming from statistics, function approximation, optimization, pattern recognition, and neural networks.
Instructor:
Abu-Mostafa
ACM/CS 157
Introduction to Statistical Inference
9 units (3-2-4)
|
second term
Prerequisites: ACM/EE 116, Ma 3.
Statistical Inference is a branch of mathematical engineering that studies ways of extracting reliable information from limited data for learning, prediction, and decision making in the presence of uncertainty. This is an introductory course on statistical inference. The main goals are: develop statistical thinking and intuitive feel for the subject; introduce the most fundamental ideas, concepts, and methods of statistical inference; and explain how and why they work, and when they don't. Topics covered include summarizing data, fundamentals of survey sampling, statistical functionals, jackknife, bootstrap, methods of moments and maximum likelihood, hypothesis testing, p-values, the Wald, t-, permutation, likelihood ratio tests, multiple testing, scatterplots, simple linear regression, ordinary least squares, interval estimation, prediction, graphical residual analysis.
Instructor:
Zuev
ACM/CS/EE 158
Introduction to Mathematical Statistics
9 units (3-0-6)
|
third term
Prerequisites: CMS/ACM 113, ACM/EE 116 and ACM/CS 157.
Fundamentals of estimation theory and hypothesis testing; minimax analysis, Cramer-Rao bounds, Rao-Blackwell theory, shrinkage in high dimensions; Neyman-Pearson theory, multiple testing, false discovery rate; exponential families; maximum entropy modeling; other advanced topics may include graphical models, statistical model selection, etc. Throughout the course, a computational viewpoint will be emphasized.
Instructor:
Chandrasekaran
CS/CNS/EE 159
Advanced Topics in Machine Learning
9 units (3-0-6)
|
third term
Prerequisites: CS 155; strong background in statistics, probability theory, algorithms, and linear algebra; background in optimization is a plus as well.
This course focuses on current topics in machine learning research. This is a paper reading course, and students are expected to understand material directly from research articles. Students are also expected to present in class, and to do a final project.
Instructor:
Yue
CS/CNS 171
Introduction to Computer Graphics Laboratory
12 units (3-6-3)
|
first term
Prerequisites: Ma 2 and extensive programming experience.
This course introduces the basic ideas behind computer graphics and its fundamental algorithms. Topics include graphics input and output, the graphics pipeline, sampling and image manipulation, three-dimensional transformations and interactive modeling, basics of physically based modeling and animation, simple shading models and their hardware implementation, and fundamental algorithms of scientific visualization. Students will be required to perform significant implementations.
Instructor:
Barr
CS/CNS 174
Computer Graphics Projects
12 units (3-6-3)
|
third term
Prerequisites: Ma 2 and CS/CNS 171 or instructor's permission.
This laboratory class offers students an opportunity for independent work covering recent computer graphics research. In coordination with the instructor, students select a computer graphics modeling, rendering, interaction, or related algorithm and implement it. Students are required to present their work in class and discuss the results of their implementation and any possible improvements to the basic methods. May be repeated for credit with instructor's permission.
Instructor:
Barr
CS 176
Introduction to Computer Graphics Research
9 units (3-3-3)
|
second term
Prerequisites: CS/CNS 171, or 173, or 174.
The course will go over recent research results in computer graphics, covering subjects from mesh processing (acquisition, compression, smoothing, parameterization, adaptive meshing), simulation for purposes of animation, rendering (both photo- and nonphotorealistic), geometric modeling primitives (image based, point based), and motion capture and editing. Other subjects may be treated as they appear in the recent literature. The goal of the course is to bring students up to the frontiers of computer graphics research and prepare them for their own research.
Instructor:
Desbrun
CS 177 ab
Discrete Differential Geometry: Theory and Applications
9 units (3-3-3)
|
first, second terms
Working knowledge of multivariate calculus and linear algebra as well as fluency in some implementation language is expected. Subject matter covered: differential geometry of curves and surfaces, classical exterior calculus, discrete exterior calculus, sampling and reconstruction of differential forms, low dimensional algebraic and computational topology, Morse theory, Noether's theorem, Helmholtz-Hodge decomposition, structure preserving time integration, connections and their curvatures on complex line bundles. Applications include elastica and rods, surface parameterization, conformal surface deformations, computation of geodesics, tangent vector field design, connections, discrete thin shells, fluids, electromagnetism, and elasticity.
Instructor:
Schroeder
CS 179
GPU Programming
9 units (3-3-3)
|
third term
Prerequisites: Working knowledge of C. Some experience with computer graphics algorithms preferred, but not required.
The use of Graphics Processing Units for computer graphics rendering is well known, but their power for general parallel computation is only recently being explored. Parallel algorithms running on GPUs can often achieve up to 100x speedup over similar CPU algorithms. This course covers programming techniques for the Graphics processing unit, focusing on visualization and simulation of various systems. Labs will cover specific applications in graphics, mechanics, and signal processing. The course will introduce the OpenGL Shader Language (GLSL) and nVidia's parallel computing architecture, CUDA. Labwork will require extensive programming.
Instructor:
Barr
CS/EE 181 abc
VLSI Design Laboratory
12 units (3-6-3)
|
first, second terms
Digital integrated system design, with projects involving the design, verification, and testing of high-complexity CMOS microcircuits. First-term lecture and homework topics emphasize disciplined design, and include CMOS logic, layout, and timing; computer-aided design and analysis tools; and electrical and performance considerations. Each student is required in the first term to complete individually the design, layout, and verification of a moderately complex integrated circuit. Advanced topics second and third terms include self-timed design, computer architecture, and other topics that vary year by year. Projects are large-scale designs done by teams. Not offered 2016-17.
Bi/BE/CS 183
Introduction to Computational Biology and Bioinformatics
9 units (3-0-6)
|
second term
Prerequisites: Bi 8, CS 2, Ma 3; or BE/Bi 103; or instructor's permission.
Biology is becoming an increasingly data-intensive science. Many of the data challenges in the biological sciences are distinct from other scientific disciplines because of the complexity involved. This course will introduce key computational, probabilistic, and statistical methods that are common in computational biology and bioinformatics. We will integrate these theoretical aspects to discuss solutions to common challenges that reoccur throughout bioinformatics including algorithms and heuristics for tackling DNA sequence alignments, phylogenetic reconstructions, evolutionary analysis, and population and human genetics. We will discuss these topics in conjunction with common applications including the analysis of high throughput DNA sequencing data sets and analysis of gene expression from RNA-Seq data sets.
Instructor:
Grosse
CNS/Bi/EE/CS 186
Vision: From Computational Theory to Neuronal Mechanisms
12 units (4-4-4)
|
second term
Lecture, laboratory, and project course aimed at understanding visual information processing, in both machines and the mammalian visual system. The course will emphasize an interdisciplinary approach aimed at understanding vision at several levels: computational theory, algorithms, psychophysics, and hardware (i.e., neuroanatomy and neurophysiology of the mammalian visual system). The course will focus on early vision processes, in particular motion analysis, binocular stereo, brightness, color and texture analysis, visual attention and boundary detection. Students will be required to hand in approximately three homework assignments as well as complete one project integrating aspects of mathematical analysis, modeling, physiology, psychophysics, and engineering. Given in alternate years; not offered 2016-17.
CNS/Bi/Ph/CS/NB 187
Neural Computation
9 units (3-0-6)
|
first term
Prerequisites: familiarity with digital circuits, probability theory, linear algebra, and differential equations. Programming will be required.
This course investigates computation by neurons. Of primary concern are models of neural computation and their neurological substrate, as well as the physics of collective computation. Thus, neurobiology is used as a motivating factor to introduce the relevant algorithms. Topics include rate-code neural networks, their differential equations, and equivalent circuits; stochastic models and their energy functions; associative memory; supervised and unsupervised learning; development; spike-based computing; single-cell computation; error and noise tolerance.
Instructor:
Perona
BE/CS/CNS/Bi 191 ab
Biomolecular Computation
9 units (3-0-6) second term
|
(2-4-3) third term
Prerequisites: none. Recommended: ChE/BE 163, CS 21, CS 129 ab, or equivalent.
This course investigates computation by molecular systems, emphasizing models of computation based on the underlying physics, chemistry, and organization of biological cells. We will explore programmability, complexity, simulation of, and reasoning about abstract models of chemical reaction networks, molecular folding, molecular self-assembly, and molecular motors, with an emphasis on universal architectures for computation, control, and construction within molecular systems. If time permits, we will also discuss biological example systems such as signal transduction, genetic regulatory networks, and the cytoskeleton; physical limits of computation, reversibility, reliability, and the role of noise, DNA-based computers and DNA nanotechnology. Part a develops fundamental results; part b is a reading and research course: classic and current papers will be discussed, and students will do projects on current research topics.
Instructor:
Winfree
BE/CS 196 ab
Design and Construction of Programmable Molecular Systems
12 units
|
a (3-6-3) second term
Prerequisites: none.
This course will introduce students to the conceptual frameworks and tools of computer science as applied to molecular engineering, as well as to the practical realities of synthesizing and testing their designs in the laboratory. In part a, students will design and construct DNA logic circuits, biomolecular neural networks, and self-assembled DNA nanostructures, as well as quantitatively analyze the designs and the experimental data. Students will learn laboratory techniques including fluorescence spectroscopy and atomic force microscopy, and will use software tools and program in MATLAB or Mathematica. Part b is an open-ended design and build project. Enrollment in both parts a and b is limited to 12 students.
Instructor:
Qian
Ph/CS 219 abc
Quantum Computation
9 units (3-0-6)
|
first, second, third terms
Prerequisites: Ph 129 abc or equivalent.
The theory of quantum information and quantum computation. Overview of classical information theory, compression of quantum information, transmission of quantum information through noisy channels, quantum error-correcting codes, quantum cryptography and teleportation. Overview of classical complexity theory, quantum complexity, efficient quantum algorithms, fault-tolerant quantum computation, physical implementations of quantum computation.
Instructors:
Kitaev, Preskill
SS/CS 241
Topics in Algorithmic Economics
9 units (3-0-6)
Prerequisites: SS/CS 149.
This is a graduate-level seminar covering recent topics at the intersection of computer science and economics. Topics will vary, but may include, e.g., dynamics in games, algorithmic mechanism design, and prediction markets. Not offered 2016-17.
Instructor:
EAS and HSS faculty
Bi/BE/CS 271 a
Special Topics in Computational Biology - Introduction to Sequence Analysis and Motif Discovery
9 units (3-0-6)
|
first term
Prerequisites: Bi 8, CS 2, or instructor's permission.
Sequence analysis and motif discovery have been two cornerstones of computational biology and bioinformatics since the early days of these sciences, and their importance has been increasing with the development of next-generation sequencing techniques, the ensuing flood of large-scale genomics and epigenomics data, and the need of analyzing these valuable sequence data efficiently. This course will introduce key computational, information-theoretic, and probabilistic methods for sequence analysis and motif discovery including popular models such as Markov models, Hidden Markov models, Bayesian networks, or maximum entropy models as well as popular algorithms such as the expectation-maximization algorithm and its stochastic relatives or the Gibbs sampling algorithm and other Markov chain Monte Carlo methods. Students of this course will develop a solid understanding of these algorithms, profound skills of deriving and implementing them, and the virtuosity of applying them to diverse problems of sequence analysis and motif discovery. Undergraduates can enroll with instructor's permission.
Instructor:
Grosse
CS 274 abc
Topics in Computer Graphics
9 units (3-3-3)
|
first, second, third terms
Prerequisites: instructor's permission.
Each term will focus on some topic in computer graphics, such as geometric modeling, rendering, animation, human-computer interaction, or mathematical foundations. The topics will vary from year to year. May be repeated for credit with instructor's permission. Not offered 2016-17.
CS 280
Research in Computer Science
Units in accordance with work accomplished
Prerequisites: Approval of student's research adviser and option adviser must be obtained before registering.
CS 282 abc
Reading in Computer Science
6 units or more by arrangement
|
first, second, third terms
Prerequisites: Instructor's permission required.
CS 286 abc
Seminar in Computer Science
3, 6, or 9 units, at the instructor's discretion
Prerequisites: Instructor's permission required.
Published Date:
July 28, 2022