Course Descriptions
Courses offered in our department for
Applied and Computational Mathematics,
Control and Dynamical Systems,
and
Computer Science
are listed below. Be aware that some courses are not offered every year; see the course schedule page to check if the class is offered this year.
ACM | CS | CMS | CDS | IDS
Applied + Computational Mathematics Courses
- ACM 11. Introduction to Matlab and Mathematica. 6 units (2-2-2); third term. Prerequisites: Ma 1 abc. CS 1 or prior programming experience recommended. Matlab: basic syntax and development environment; debugging; help interface; basic linear algebra; visualization and graphical output; control flow; vectorization; scripts, and functions; file i/o; arrays, structures, and strings; numerical analysis (topics may include curve fitting, interpolation, differentiation, integration, optimization, solving nonlinear equations, fast Fourier transform, and ODE solvers); and advanced topics (may include writing fast code, parallelization, object-oriented features). Mathematica: basic syntax and the notebook interface, calculus and linear algebra operations, numerical and symbolic solution of algebraic and differential equations, manipulation of lists and expressions, Mathematica programming (rule-based, functional, and procedural) and debugging, plotting, and visualization. The course will also emphasize good programming habits and choosing the appropriate language/software for a given scientific task.
- ACM 80 abc. Undergraduate Thesis. 9 units; first, second, third terms. Prerequisite: 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 ACM faculty (or other faculty as approved by the ACM undergraduate option representative). Projects must include significant design effort. Written report required. Open only to upper class students. Not offered on a pass/fail basis.
- ACM 81 abc. Undergraduate Projects in Applied and Computational Mathematics. Units are assigned in accordance with work accomplished; first, second, third terms. Prerequisites: Consent of supervisor is required before registering. Supervised research or development in ACM by undergraduates. The topic must be approved by the project supervisor, and a formal final report must be presented on completion of research. Graded pass/fail.
- ACM 95/100 ab. Introductory Methods of Applied Mathematics for the Physical Sciences. 12 units (4-0-8); second, third terms. Prerequisites: Ma 1 abc, Ma 2 or equivalents. Complex analysis: analyticity, Laurent series, contour integration, residue calculus. Ordinary differential equations: linear initial value problems, linear boundary value problems, Sturm-Liouville theory, eigenfunction expansions, transform methods, Green’s functions. Linear partial differential equations: heat equation, separation of variables, Laplace equation, transform methods, wave equation, method of characteristics, Green’s functions.
- ACM/IDS 101 ab. Methods of Applied Mathematics. 12 units (4-4-4); first, second, terms. Prerequisites: Math 2/102 and ACM 95ab or equivalent. First term: Brief review of the elements of complex analysis and complex-variable methods. Asymptotic expansions, asymptotic evaluation of integrals (Laplace method, stationary phase, steepest descents), perturbation methods, WKB theory, boundary-layer theory, matched asymptotic expansions with first-order and high-order matching. Method of multiple scales for oscillatory systems. Second term: Applied spectral theory, special functions, generalized eigenfunction expansions, convergence theory. Gibbs and Runge phenomena and their resolution. Chebyshev expansion and Fourier Continuation methods. Review of numerical stability theory for time evolution. Fast spectrally-accurate PDE solvers for linear and nonlinear Partial Differential Equations in general domains. Integral-equations methods for linear partial differential equation in general domains (Laplace, Helmholtz, Schrödinger, Maxwell, Stokes). Homework problems in both 101 a and 101 b include theoretical questions as well as programming implementations of the mathematical and numerical methods studied in class.
- ACM/IDS 104. Applied Linear Algebra. 9 units (3-1-5); first term. Prerequisites: Ma 1 abc, some familiarity with MATLAB, e.g. ACM 11 is desired. This is an intermediate linear algebra course aimed at a diverse group of students, including junior and senior majors in applied mathematics, sciences and engineering. The focus is on applications. Matrix factorizations play a central role. Topics covered include linear systems, vector spaces and bases, inner products, norms, minimization, the Cholesky factorization, least squares approximation, data fitting, interpolation, orthogonality, the QR factorization, ill-conditioned systems, discrete Fourier series and the fast Fourier transform, eigenvalues and eigenvectors, the spectral theorem, optimization principles for eigenvalues, singular value decomposition, condition number, principal component analysis, the Schur decomposition, methods for computing eigenvalues, non-negative matrices, graphs, networks, random walks, the Perron-Frobenius theorem, PageRank algorithm.
- ACM 105. Applied Real and Functional Analysis. 9 units (3-0-6); second term. Prerequisite: Ma 2, Ma 108a, ACM 104 or equivalent. This course is about the fundamental concepts in real and functional analysis that are vital for many topics and applications in mathematics, physics, computing and engineering. The aim of this course is to provide a working knowledge of functional analysis with an eye especially for aspects that lend themselves to applications. The course gives an overview of the interplay between different functional spaces and focuses on the following three key concepts: Hahn-Banach theorem, open mapping and closed graph theorem, uniform boundedness principle. Other core concepts include: normed linear spaces and behavior of linear maps, completeness, Banach spaces, Hilbert spaces, Lp spaces, duality of normed spaces and dual operators, dense subspaces and approximations, hyperplanes, compactness, weak and weak* convergence. More advanced topics include: spectral theory, compact operators, theory of distributions (generalized functions), Fourier analysis, calculus of variations, Sobolev spaces with applications to PDEs, weak solvability theory of boundary value problems.
- ACM/EE 106 ab. Introductory Methods of Computational Mathematics. 12 units (3-0-9); second, third terms. Prerequisites: Ma 1 abc, Ma 2, Ma 3, ACM 11, ACM 95/100 ab or equivalent. The sequence covers the introductory methods in both theory and implementation of numerical linear algebra, approximation theory, ordinary differential equations, and partial differential equations. The linear algebra parts covers basic methods such as direct and iterative solution of large linear systems, including LU decomposition, splitting method (Jacobi iteration, Gauss-Seidel iteration); eigenvalue and vector computations including the power method, QR iteration and Lanczos iteration; nonlinear algebraic solvers. The approximation theory includes data fitting; interpolation using Fourier transform, orthogonal polynomials and splines; least square method, and numerical quadrature. The ODE parts include initial and boundary value problems. The PDE parts include finite difference and finite element for elliptic/parabolic/hyperbolic equation. Stability analysis will be covered with numerical PDE. Programming is a significant part of the course.
- CMS/ACM/IDS 107. Linear Analysis with Applications. 12 units (3-3-6); first term. Prerequisites: ACM 104 or equivalent, Ma 1b or equivalent. Covers the basic algebraic, geometric, and topological properties of normed linear spaces, inner-product spaces, and linear maps. Emphasis is placed both on rigorous mathematical development and on applications to control theory, data analysis and partial differential equations.
- ACM 109. Mathematical Modelling. 9 units (3-0-9); third term. Prerequisites ACM 95/100 ab or equivalent. This course gives an overview of different mathematical tools to analyze partial differential equations encountered across mathematics, biology, engineering and science. We will look at the main properties of different classes of linear and nonlinear PDEs and the behavior of their solutions using tools from functional analysis and calculus of variations with an emphasis on applications. We will discuss different types of reaction-diffusion systems, kinetic equations, advection and transport equations, the method of characteristics, gradient flows and entropy methods, conservation laws, population dynamics, parabolic equations and their spectral analysis, slow-fast dynamics, relaxation, asymptotic stability, blow-up and extinction of solutions, method of moments, instabilities and pattern formation, hydrodynamic scaling techniques and non-dimensionalisation. We will focus on representative models from different areas which may include: Lotka-Volterra equations, the Fokker-Planck equation, the Boltzmann equation, the Fisher/KPP equation, Burger’s equation, movement of cells and bacterial chemotaxis (Patlack-Keller-Segel model), SI models from epidemiology, predator-prey systems, chemical reactions, enzymatic reactions. The list is flexible and depends on the audience. If you are interested in this course, feel free to contact the instructor with (types of) models you would like to study.
- Ec/ACM/CS 112. Bayesian Statistics. 9 units (3-0-6); third term. Prerequisites: Ma 3, ACM/EE/IDS 116 or equivalent. This course provides an introduction to Bayesian Statistics and its applications to data analysis in various fields. Topics include: discrete models, regression models, hierarchical models, model comparison, and MCMC methods. The course combines an introduction to basic theory with a hands-on emphasis on learning how to use these methods in practice so that students can apply them in their own work. Previous familiarity with frequentist statistics is useful but not required.
- CMS/ACM/IDS 113. Mathematical Optimization. 12 units (3-0-9); first term. Prerequisites: ACM 11, ACM/IDS 104, or instructor's permission. This class studies mathematical optimization from the viewpoint of convexity. Topics covered include duality and representation of convex sets; linear and semidefinite programming; connections to discrete, network, and robust optimization; relaxation methods for intractable problems; as well as applications to problems arising in graphs and networks, information theory, control, signal processing, and other engineering disciplines.
- ACM/EE/IDS 116 Introduction to Probability Models. 9 units (3-1-5); first term. Prerequisites: Ma 2, Ma 3, some familiarity with MATLAB, e.g. ACM 11 is desired. This course introduces students to the fundamental concepts, methods, and models of applied probability and stochastic processes. The course is application oriented and focuses on the development of probabilistic thinking and intuitive feel of the subject rather than on a more traditional formal approach based on measure theory. The main goal is to equip science and engineering students with necessary probabilistic tools they can use in future studies and research. Topics covered include sample spaces, events, probabilities of events, discrete and continuous random variables, expectation, variance, correlation, joint and marginal distributions, independence, moment generating functions, law of large numbers, central limit theorem, random vectors and matrices, random graphs, Gaussian vectors, branching, Poisson, and counting processes, general discrete- and continuous-timed processes, auto- and cross-correlation functions, stationary processes, power spectral densities.
- ACM 118. Stochastic Processes and Regression. 12 units (3-0-9); second term. Prerequisites: CMS/ACM/IDS 107 or equivalent, CMS 117 or equivalent, or permission of the instructor. Stochastic processes: Branching processes, Poisson point processes, Determinantal point processes, Dirichlet processes and Gaussian processes (including the Brownian motion). Regression: Gaussian vectors, spaces, conditioning, processes, fields and measures will be presented with an emphasis on linear regression. Kernel and variational methods in numerical approximation, signal processing and learning will also be covered through their connections with Gaussian process regression.
- AM/ACM 127. Calculus of Variations. 9 units (3-0-6); third term. Prerequisites: ACM 95/100. First and second variations; Euler-Lagrange equation; Hamiltonian formalism; action principle; Hamilton-Jacobi theory; stability; local and global minima; direct methods and relaxation; isoperimetric inequality; asymptotic methods and gamma convergence; selected applications to mechanics, materials science, control theory and numerical methods.
- Ma/ACM 142. Ordinary and Partial Differential Equations. 9 units (3-0-6); third term. Prerequisite: Ma 108; Ma 109 is desirable. The mathematical theory of ordinary and partial differential equations, including a discussion of elliptic regularity, maximal principles, solubility of equations. The method of characteristics.
- Ma/ACM/IDS 140 ab. Probability. 9 units (3-0-6); first, second terms. Prerequisites: For 144a, Ma 108b is strongly recommended; for 144b, 108b and 144a are prerequisite. Overview of measure theory. Random walks and the Strong law of large numbers via the theory of martingales and Markov chains. Characteristic functions and the central limit theorem. Poisson process and Brownian motion. Topics in statistics.
- ACM/IDS 154. Inverse Problems and Data Assimilation. 9 units (3-0-6); first term. Prerequisites: Basic differential equations, linear algebra, probability and statistics: ACM 104, ACM/EE 106 ab, ACM/EE/IDS 116, IDS/ACM/CS 157 or equivalent. Models in applied mathematics often have input parameters that are uncertain; observed data can be used to learn about these parameters and thereby to improve predictive capability. The purpose of the course is to describe the mathematical and algorithmic principles of this area. The topic lies at the intersection of fields including inverse problems, differential equations, machine learning and uncertainty quantification. Applications will be drawn from the physical, biological and data sciences.
- IDS/ACM/CS 157. Statistical Inference. 9 units (3-2-4); third term. Prerequisites: ACM/EE/IDS 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.
- IDS/ACM/CS 158. Fundamentals of Statistical Learning. 9 units (3-3-3); third term. Prerequisites: Ma 3 or ACM/EE/IDS 116, IDS/ACM/CS 157. The main goal of the course is to provide an introduction to the central concepts and core methods of statistical learning, an interdisciplinary field at the intersection of statistics, machine learning, information and data sciences. The course focuses on the mathematics and statistics of methods developed for learning from data. Students will learn what methods for statistical learning exist, how and why they work (not just what tasks they solve and in what built-in functions they are implemented), and when they are expected to perform poorly. The course is oriented for upper level undergraduate students in IDS, ACM, and CS and graduate students from other disciplines who have sufficient background in probability and statistics. The course can be viewed as a statistical analog of CMS/CS/CNS/EE/IDS 155. Topics covered include supervised and unsupervised learning, regression and classification problems, linear regression, subset selection, shrinkage methods, logistic regression, linear discriminant analysis, resampling techniques, tree-based methods, support-vector machines, and clustering methods.
- ACM/EE/IDS 170. Mathematics of Signal Processing. 12 units (3-0-9); third term. Prerequisites: CMS/ACM 104, CMS/ACM/IDS 113, and CMS/ACM 116; or instructor’s permission. This course covers classical and modern approaches to problems in signal processing. Problems may include denoising, deconvolution, spectral estimation, direction-of-arrival estimation, array processing, independent component analysis, system identification, filter design, and transform coding. Methods rely heavily on linear algebra, convex optimization, and stochastic modeling. In particular, the class will cover techniques based on least-squares and on sparse modeling. Throughout the course, a computational viewpoint will be emphasized.
- CS/ACM 177 ab. Discrete Differential Geometry. 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.
- ACM 190. Reading and Independent Study. Units by arrangement. Graded pass/fail only.
- ACM 201. Partial Differential Equations. 9 units (3-0-6) first term. Prerequisites ACM 95/100 ab, ACM 101 ab, ACM 11 or equivalent. This course offers an introduction to the theory of Partial Differential Equations (PDEs) commonly encountered across mathematics, engineering and science. The goal of the course is to study properties of different classes of linear and nonlinear PDEs (elliptic, parabolic and hyperbolic) and the behavior of their solutions using tools from functional analysis with an emphasis on applications. We will discuss representative models from different areas such as: heat equation, wave equation, advection-reaction-diffusion equation, conservation laws, shocks, predator prey models, Burger’s equation, kinetic equations, gradient flows, transport equations, integral equations, Helmholtz and Schrödinger equations and Stoke’s flow. In this course you will use analytical tools such as Gauss’s theorem, Green’s functions, weak solutions, existence and uniqueness theory, Sobolev spaces, well-posedness theory, asymptotic analysis, Fredholm theory, Fourier transforms and spectral theory. More advanced topics include: Perron’s method, applications to irrotational flow, elasticity, electrostatics, special solutions, vibrations, Huygens’ principle, Eikonal equations, spherical means, retarded potentials, water waves, various approximations, dispersion relations, Maxwell equations, gas dynamics, Riemann problems, single- and double-layer potentials, Navier-Stokes equations, Reynolds number, potential flow, boundary layer theory, subsonic, supersonic and transonic flow.
- ACM/IDS 204. Topics in Linear Algebra and Convexity. 9 units (3-0-6); second term. Prerequisites: ACM/IDS 104 and ACM/EE 106 a, CMS 117, or instructor’s permission. Topic varies by year. 2019-2020: Randomized algorithms for linear algebra. This class offers an introduction to the emerging field of randomized algorithms for solving linear algebra problems. Material may include trace estimation, norm estimation, matrix approximation by sampling, random projections, approximating least-squares problems, randomized SVD algorithms, approximate preconditioners, spectral computations, kernel methods, and fast linear system solvers. Assignments will require mathematical proofs, programming, and computer simulation.
- ACM 210 ab. Numerical Methods for PDEs. 9 units (3-0-6); second, third terms. Prerequisite: ACM 11, 106 or instructor’s permission. Finite difference and finite volume methods for hyperbolic problems. Stability and error analysis of nonoscillatory numerical schemes: i) linear convection: Lax equivalence theorem, consistency, stability, convergence, truncation error, CFL condition, Fourier stability analysis, von Neumann condition, maximum principle, amplitude and phase errors, group velocity, modified equation analysis, Fourier and eigenvalue stability of systems, spectra and pseudospectra of nonnormal matrices, Kreiss matrix theorem, boundary condition analysis, group velocity and GKS normal mode analysis; ii) conservation laws: weak solutions, entropy conditions, Riemann problems, shocks, contacts, rarefactions, discrete conservation, Lax-Wendroff theorem, Godunov’s method, Roe’s linearization, TVD schemes, high-resolution schemes, flux and slope limiters, systems and multiple dimensions, characteristic boundary conditions; iii) adjoint equations: sensitivity analysis, boundary conditions, optimal shape design, error analysis. Interface problems, level set methods for multiphase flows, boundary integral methods, fast summation algorithms, stability issues. Spectral methods: Fourier spectral methods on infinite and periodic domains. Chebyshev spectral methods on finite domains. Spectral element methods and h-p refinement. Multiscale finite element methods for elliptic problems with multiscale coefficients.
- ACM/IDS 213. Topics in Optimization. 9 units (3-0-6); third term. Prerequisites: CMS/ACM 104, CMS/ACM/IDS 113. Material varies year-to-year. Example topics include discrete optimization, convex and computational algebraic geometry, numerical methods for large-scale optimization, and convex geometry.
- ACM/IDS 216. Markov Chains, Discrete Stochastic Processes and Applications. 9 units (3-0-6); second term. Prerequisite: ACM/EE/IDS 116 or equivalent. Stable laws, Markov chains, classification of states, ergodicity, von Neumann ergodic theorem, mixing rate, stationary/equilibrium distributions and convergence of Markov chains, Markov chain Monte Carlo and its applications to scientific computing, Metropolis Hastings algorithm, coupling from the past, martingale theory and discrete time martingales, rare events, law of large deviations, Chernoff bounds.
- ACM/EE/IDS 217. Advanced Topics in Stochastic Analysis. 9 units (3-0-6); third term. Prerequisite: ACM/IDS 216 or equivalent. The topic of this course changes from year to year and is expected to cover areas such as stochastic differential equations, stochastic control, statistical estimation and adaptive filtering, empirical processes and large deviation techniques, concentration inequalities and their applications. Examples of selected topics for stochastic differential equations include continuous time Brownian motion, Ito’s calculus, Girsanov theorem, stopping times, and applications of these ideas to mathematical finance and stochastic control.
- Ae/ACM/ME 232 abc. Computational Fluid Dynamics. 9 units (3-0-6); first, second terms. Prerequisites: Ae/APh/CE/ME 101 abc or equivalent; ACM 100 abc or equivalent. Development and analysis of algorithms used in the solution of fluid mechanics problems. Numerical analysis of discretization schemes for partial differential equations including interpolation, integration, spatial discretization, systems of ordinary differential equations; stability, accuracy, aliasing, Gibbs and Runge phenomena, numerical dissipation and dispersion; boundary conditions. Survey of finite difference, finite element, finite volume and spectral approximations for the numerical solution of the incompressible and compressible Euler and Navier-Stokes equations, including shock-capturing methods.
- ACM 256. Special Topics in Applied Mathematics. 9 units (3-0-6); first term. Prerequisite: ACM 101 or equivalent.Introduction to finite element methods. Development of the most commonly used method—continuous, piecewise-linear finite elements on triangles for scalar elliptic partial differential equations; practical (a posteriori) error estimation techniques and adaptive improvement; formulation of finite element methods, with a few concrete examples of important equations that are not adequately treated by continuous, piecewise-linear finite elements, together with choices of finite elements that are appropriate for those problems. Homogenization and optimal design. Topics covered include periodic homogenization, G- and H-convergence, Gamma-convergence, G-closure problems, bounds on effective properties, and optimal composites.
- ACM 257. Special Topics in Financial Mathematics. 9 units (3-0-6); third term. Prerequisite: ACM 95/100 or instructor’s permission. A basic knowledge of probability and statistics as well as transform methods for solving PDEs is assumed. This course develops some of the techniques of stochastic calculus and applies them to the theory of financial asset modeling. The mathematical concepts/tools developed will include introductions to random walks, Brownian motion, quadratic variation, and Ito-calculus. Connections to PDEs will be made by Feynman-Kac theorems. Concepts of risk-neutral pricing and martingale representation are introduced in the pricing of options. Topics covered will be selected from standard options, exotic options, American derivative securities, term-structure models, and jump processes.
- ACM 270. Advanced Topics in Applied and Computational Mathematics. Hours and units by arrangement; second, third terms. Advanced topics in applied and computational mathematics that will vary according to student and instructor interest. May be repeated for credit.
- ACM 300. Research in Applied and Computational Mathematics. Units by arrangement.
Computer Science Courses
- 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.
- CS 2. Introduction to Programming Methods. 9 units (3-5-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 fundamental algorithms; algorithm design principles, in particular recursion and dynamic programming; 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 projects 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.
- CS 3. Introduction to Software Design. 9 units (1-6-2); third term. Prerequisites: CS 2 or equivalent. CS 3 is a practical introduction to designing large programs in a low-level language. Heavy emphasis is placed on documentation, testing, and software architecture. Students will work in teams in two 5-week long projects. In the first half of the course, teams will focus on testing and extensibility. In the second half of the course, teams will use POSIX APIs, as well as their own code from the first five weeks, to develop a large software deliverable. Software engineering topics covered include code reviews, testing and testability, code readability, API design, refactoring, and documentation.
- CS 4. Fundamentals of Computer Programming. 9 units (3-4-2); second term. Prerequisite: 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.
- Ma/CS 6 abc. Introduction to Discrete Mathematics. 9 units (3-0-6); first, second, third terms. Prerequisite: 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.
- CS 9. Introduction to Computer Science Research. 1 unit (1-0-0); first term. This course will introduce students to research areas in CS through weekly overview talks by Caltech faculty and aimed at first-year undergraduates. Others may wish to take the course to gain an understanding of the scope of research in computer science. Graded pass/fail.
- EE/CS 10 ab. Introduction to Digital Logic and Embedded Systems. 6 units (2-3-1); second, third terms. This course is intended to give the student a basic understanding of the major hardware and software principles involved in the specification and design of embedded systems. The course will cover basic digital logic, programmable logic devices, CPU and embedded system architecture, and embedded systems programming principles (interfacing to hardware, events, user interfaces, and multi-tasking).
- CS 11. Computer Language Shop. 3 units (0-3-0); first, second, third terms. Prerequisite: 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. CS 11 may be repeated for credit of up to a total of nine units.
- CS 19 ab. Introduction to Computer Science in Industry. 2 units (1-0-1); first, second terms. This course will introduce students to CS in industry through weekly overview talks by alums and engineers in industry. It is aimed at second-year undergraduates. Others may wish to take the course to gain an understanding of the scope of computer science in industry. Additionally students will complete short weekly assignments aimed at preparing them for interactions with industry. This course is closed to first and second term freshman for credit. Graded pass/fail.
- CS 21. Decidability and Tractability. 9 units (3-0-6); second term. Prerequisite: 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.
- CS 24. Introduction to Computing Systems. 9 units (3-3-3); first term. Prerequisites: Familiarity with C equivalent to having taken the CS 11 C track or CS 3. 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.
- CS 37. Algorithms in the Real World. 9 units (2-6-1); first term. Prerequisites: CS 2, CS 24, Ma 6 or permission from instructor. This course introduces algorithms in the context of their usage in the real world. The course covers compression, advanced data structures, numerical algorithms, cryptography, computer algebra, and parallelism. The goal of the course is for students to see how to use theoretical algorithms in real-world contexts, focusing both on correctness and the nitty-gritty details and optimizations. Implementations focus on two orthogonal avenues: speed (for which C is used) and algorithmic thinking (for which Python is used).
- CS 38. 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.
- CS 42. Computer Science Education in K-14 Settings. 6 units, (2-2-2); first, second, third terms. This course will focus on computer science education in K-14 settings. Students will gain an understanding of the current state of computer science education within the United States, develop curricula targeted at students from diverse backgrounds, and gain hands on teaching experience. Through readings from educational psychology and neuropsychology, students will become familiar with various pedagogical methods and theories of learning, while applying these in practice as part of a teaching group partnered with a local school or community college. Each week students are expected to spend about 2 hours teaching, 2 hours developing curricula, and 2 hours on readings and individual exercises. Pass/Fail only. May not be repeated.
- 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.
- EE/CS 52 ab. Microprocessor Systems Laboratory. units (3-6-0) second term; 6 units (1-5-0) third term; second, third terms. 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.
- 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.
- CS/EE/ME 75 abc. 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; 12 units (2-9-1), 15 units (2-12-1), or 18 units (2-15-1), with instructor’s permission, second and third terms; units according to project selected. 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.
- CS 80 abc. Undergraduate Thesis. 9 units (1-0-8); first, second, third terms. Prerequisite: 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.
- CS 81 a. 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.
- 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.
- 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. Instructor’s permission required.
- CS 103 abc. Reading in Computer Science. 3, 6, or 9 units as arranged with the instructor. 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.
- 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.
- 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.
- CS 116. Reasoning about Program Correctness. 9 units (3-0-6); first term. Prerequisite: 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.
- Ma/CS 117 abc. Computability Theory. 9 units (3-0-6); first, second, third terms. Prerequisite: 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.
- 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.
- EE/CS 119 abc. Advanced Digital Systems Design. 9 units (3-3-3) first, second term; 9 units (1-8-0) third term. Prerequisites: EE 10 or CS/EE 181 a or CS 24. Advanced digital design as it applies to the design of systems using PLDs and ASICs (in particular, gate arrays and standard cells). The course covers both design and implementation details of various systems and logic device technologies. The emphasis is on the practical aspects of ASIC design, such as timing, testing, and fault grading. Topics include synchronous design, state machine design, ALU and CPU design, application-specific parallel computer design, design for testability, PALs, FPGAs, VHDL, standard cells, timing analysis, fault vectors, and fault grading. Students are expected to design and implement both systems discussed in the class as well as self-proposed systems using a variety of technologies and tools.
- CS/Ph 120 Quantum Cryptography. 9 units (3-0-6); first term. Prerequisites: Ma 1b, CS 21, CS 38 or equivalent recommended and Ph 12b or Ph 2b 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.
- CS/IDS 121. 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.
- CS 122. Database System Implementation. 9 units (3-3-3); second term. Prerequisites: CS2, CS38, CS/IDS 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.
- CS 123. Projects in Database Systems. 9 units (0-0-9); third term. Prerequisites: CS/IDS 121 and CS122. Students are expected to execute a substantial project in databases, write up a report describing their work, and make a presentation.
- CS 124. Operating Systems. 12 units (3-6-3); First 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.
- EE/CS/MedE 125. Digital Electronics and Design with FPGAs and VHDL. 9 units (3-6-0); third term. Prerequisite: basic knowledge of digital electronics. Study of programmable logic devices (CPLDs and FPGAs). Detailed study of the VHDL language, with basic and advanced applications. Review and discussion of digital design principles for combinational-logic, combinational-arithmetic, sequential, and state-machine circuits. Detailed tutorials for synthesis and simulation tools using FPGAs and VHDL. Wide selection of complete, real-world fundamental advanced projects, including theory, design, simulation, and physical implementation. All designs are implemented using state-of-the-art development boards.
- 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/IDS 127, EE/CS 161, and EE/CS/IDS 167, should prepare the student for research in information theory, coding theory, wireless communications, and/or data compression.
- EE/Ma/CS/IDS 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, fountain coding. Emphasis will be placed on the associated encoding and decoding algorithms, and students will be asked to demonstrate their understanding with a software project.
- CS 131. Programming Languages. 9 units (3-0-6); third term. Prerequisites; CS 4. CS 131 is a course on programming languages and their implementation. It teaches students how to program in a number of simplified languages representing the major programming paradigms in use today (imperative, object-oriented, and functional). It will also teach students how to build and modify the implementations of these languages. Emphasis will not be on syntax or parsing but on the essential differences in these languages and their implementations. Both dynamically-typed and statically-typed languages will be implemented. Relevant theory will be covered as needed. Implementations will mostly be interpreters, but some features of compilers will be covered if time permits. Enrollment limited to 20 students.
- ME/CS 132 ab. Advanced Robotics: Navigation and Vision. 9 units (3-6-0); second, third terms. Prerequisite: 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.
- ME/CS/EE 134. Robotic Systems. 9 units (3-6-0); second term. Prerequisites: ME/CS/EE 129, may be taken concurrently, or with permission of instructor. This course covers the basics of robotic systems at the intersection of computer vision, machine learning and control. It includes selected topics from each of these domains, and their integration points. The lectures will be accompanied by a project that will integrate these ideas on hardware, including building a custom robotic, with the end result being a final demonstration of the concepts studied in the course.
- 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.
- EE/Ma/CS/IDS 136. Topics in Information Theory. 9 units (3-0-6); third term. Prerequisites: undergraduate calculus and probability. This class introduces information measures such as entropy, information divergence, mutual information, information density from a probabilistic point of view, and discusses the relations of those quantities to problems in data compression and transmission, statistical inference, language modeling, game theory and control. Topics include information projection, data processing inequalities, sufficient statistics, hypothesis testing, single-shot approach in information theory, large deviations.
- CS 138 Algorithms. 9 units (3-0-6); third term. This course is identical to CS 38. Only graduate students for whom this is the first algorithms course are allowed to register for CS 138. See the CS 38 entry for prerequisites and course description.
- CMS/CS/IDS 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, and CMS/ACM/EE 116 or ACM/CMS 113 or equivalent. This course develops core principles for the analysis and design of algorithms. Basic material includes mathematical techniques for analyzing performance in terms of resources, such as time, space, and randomness. The course introduces the major paradigms for algorithm design, including greedy methods, divide-and-conquer, dynamic programming, linear and semidefinite programming, randomized algorithms, and online learning.
- CS 141. Hack Society: Projects from the Public Sector. 9 units (0-0-9); second term. Prerequisites: CS 142, 143, 144, or permission from instructor. 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 develop 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.
- CS/IDS 142. Distributed Computing. (3-2-4); 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.
- CS/EE/IDS 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.
- CMS/CS/EE/IDS 144. Networks: Structure & Economics. 12 units (3-4-5); 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.
- CS/EE 145. Projects in Networking. 9 units (0-0-9); third term. Prerequisites: Either CMS/CS/EE/IDS 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.
- CS/EE 146. Control and Optimization of Networks. 9 units (3-3-3); first term. Prerequisites: Ma, 2, Ma 3, or instructor 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 in the design, analysis, control, and optimization of networks. Usually offered in odd years. Offered FA 2019-20
- 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.
- EE/CNS/CS 148. Selected Topics in Computational Vision. 9 units (3-0-6); first 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.
- CS/SS/Ec 149. 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.
- CS/IDS 150 ab. Probability and Algorithms. 9 units (3-0-6); first term. Prerequisites: part a: CS 38 and Ma 5 abc; part b: part a or another introductory course in discrete probability. Part a: The probabilistic method and randomized algorithms. Deviation bounds, k-wise independence, graph problems, identity testing, derandomization and parallelization, metric space embeddings, local lemma. Part b: Further topics such as weighted sampling, epsilon-biased sample spaces, advanced deviation inequalities, rapidly mixing Markov chains, analysis of boolean functions, expander graphs, and other gems in the design and analysis of probabilistic algorithms. Parts a & b are offered in alternate years. Part b will be offered in 2019-20.
- 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.
- CS 152. Introduction to cryptography. 12 units (3-0-9); first term. Prerequisites: Ma 1b, CS 21, CS 38 or equivalent recommended. This course is an introduction to the foundations of cryptography. The first part of the course introduces fundamental constructions in private-key cryptography, including one-way functions, pseudo-random generators and authentication, and in public-key cryptography, including trapdoor one-way functions, collision-resistant hash functions and digital signatures. The second part of the course covers selected topics such as interactive protocols and zero knowledge, the learning with errors problem and homomorphic encryption, and quantum cryptography: quantum money, quantum key distribution. The course is mostly theoretical and requires mathematical maturity. There will be a small programming component.
- CS/IDS 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.
- CMS/CS/CNS/EE/IDS 155. Machine Learning & Data Mining. 12 units (3-3-6); second term. Prerequisites: CS 156a. Having a sufficient background in algorithms, linear algebra, calculus, probability, and statistics, is highly recommended. 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. The course will focus on basic foundational concepts underpinning and motivating modern machine learning and data mining approaches. We will also discuss recent research developments.
- CS/CNS/EE 156 ab. Learning Systems. 9 units (3-1-5); 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.
- IDS/ACM/CS 157. Statistical Inference. 9 units (3-2-4); third term. Prerequisites: ACM/EE/IDS 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.
- IDS/ACM/CS 158. Fundamentals of Statistical Learning. 9 units (3-3-3); third term. Prerequisites: Ma 3 or ACM/EE/IDS 116, IDS/ACM/CS 157. The main goal of the course is to provide an introduction to the central concepts and core methods of statistical learning, an interdisciplinary field at the intersection of statistics, machine learning, information and data sciences. The course focuses on the mathematics and statistics of methods developed for learning from data. Students will learn what methods for statistical learning exist, how and why they work (not just what tasks they solve and in what built-in functions they are implemented), and when they are expected to perform poorly. The course is oriented for upper level undergraduate students in IDS, ACM, and CS and graduate students from other disciplines who have sufficient background in probability and statistics. The course can be viewed as a statistical analog of CMS/CS/CNS/EE/IDS 155. Topics covered include supervised and unsupervised learning, regression and classification problems, linear regression, subset selection, shrinkage methods, logistic regression, linear discriminant analysis, resampling techniques, tree-based methods, support-vector machines, and clustering methods.
- CS/CNS/EE/IDS 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.
- EE/CS/IDS 160. Fundamentals of Information Transmission and Storage. 9 units (3-0-6); second term. Basics of information theory: entropy, mutual information, source and channel coding theorems. Basics of coding theory: error-correcting codes for information transmission and storage, block codes, algebraic codes, sparse graph codes. Basics of digital communications: sampling, quantization, digital modulation, matched filters, equalization.
- EE/CS 161. Big Data Networks. 9 units (3-0-6); third term. Prerequisites: Linear Algebra ACM/IDS 104 and Probability and Random Processes ACM/EE/IDS 116 or their equivalents. Next generation networks will have tens of billions of nodes forming cyber-physical systems and the Internet of Things. A number of fundamental scientific and technological challenges must be overcome to deliver on this vision. This course will focus on (1) How to boost efficiency and reliability in large networks; the role of network coding, distributed storage, and distributed caching; (2) How to manage wireless access on a massive scale; modern random access and topology formation techniques; and (3) New vistas in big data networks, including distributed computing over networks and crowdsourcing. A selected subset of these problems, their mathematical underpinnings, state-of-the-art solutions, and challenges ahead will be covered. Given in alternate years.
- CS/IDS 162. Data, Algorithms and Society. 9 units (3-0-6); third term. Prerequisites: CS 38 and CS 155 or 156a. This course examines algorithms and data practices in fields such as machine learning, privacy, and communication networks through a social lens. We will draw upon theory and practices from art, media, computer science and technology studies to critically analyze algorithms and their implementations within society. The course includes projects, lectures, readings, and discussions. Students will learn mathematical formalisms, critical thinking and creative problem solving to connect algorithms to their practical implementations within social, cultural, economic, legal and political contexts. Enrollment by application. Taught concurrently with VC 72 and can only be taken once, as VC 72 or CS/IDS 162.
- CS/CNS/EE/IDS 165. Foundations of Machine Learning and Statistical Inference. 12 units (3-3-6); second term. Prerequisites: CMS/ACM/IDS 113, ACM/EE/IDS 116, CS 156a, IDS/ACM/CS 157 or instructor’s permission. The course assumes students are comfortable with analysis, probability, statistics, and basic programming. This course will cover core concepts in machine learning and statistical inference. The ML concepts covered are spectral methods (matrices and tensors), non-convex optimization, probabilistic models, neural networks, representation theory, and generalization. In statistical inference, the topics covered are detection and estimation, sufficient statistics, Cramer-Rao bounds, Rao-Blackwell theory, variational inference, and multiple testing. In addition to covering the core concepts, the course encourages students to ask critical questions such as: How relevant is theory in the age of deep learning? What are the outstanding open problems? Assignments will include exploring failure modes of popular algorithms, in addition to traditional problem-solving type questions.
- EE/CS/IDS 167. Introduction to Data Compression and Storage. 9 units (3-0-6); third term. Prerequisites: Ma 3 or ACM/EE/IDS 116.The course will introduce the students to the basic principles and techniques of codes for data compression and storage. The students will master the basic algorithms used for lossless and lossy compression of digital and analog data and the major ideas behind coding for flash memories. Topics include the Huffman code, the arithmetic code, Lempel-Ziv dictionary techniques, scalar and vector quantizers, transform coding; codes for constrained storage systems. Given in alternate years.
- CS/CNS 171. Computer Graphics Laboratory. 12 units (3-6-3); first term. Prerequisites: extensive programming experience and proficiency in linear algebra, starting with CS2 and Ma1b. This is a challenging course that introduces the basic ideas behind computer graphics and some of 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 some of the fundamental algorithms of scientific visualization. Students will be required to perform significant implementations.
- CS/CNS 174. Computer Graphics Projects. 12 units (3-6-3); third term. Prerequisites: Extensive programming experience, CS/CNS 171 or instructor’s permission. This laboratory class offers students an opportunity for independent work including 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 possible improvements to the basic methods. May be repeated for credit with instructor’s permission.
- EE/CS/MedE 175. Digital Circuits Analysis and Design with Complete VHDL and RTL Approach. 9 units (3-6-0); third term. Prerequisites: medium to advanced knowledge of digital electronics. A careful balance between synthesis and analysis in the development of digital circuits plus a truly complete coverage of the VHDL language. The RTL (register transfer level) approach. Study of FPGA devices and comparison to ASIC alternatives. Tutorials of software and hard-ware tools employed in the course. VHDL infrastructure, including lexical elements, data types, operators, attributes, and complex data structures. Detailed review of combinational circuits followed by full VHDL coverage for combinational circuits plus recommended design practices. Detailed review of sequential circuits followed by full VHDL coverage for sequential circuits plus recommended design practices. Detailed review of state machines followed by full VHDL coverage and recommended design practices. Construction of VHDL libraries. Hierarchical design and practice on the hard task of project splitting. Automated simulation using VHDL testbenches. Designs are implemented in state-of-the-art FPGA boards.
- CS 176. Computer Graphics Research. 9 units (3-3-3); second term. Prerequisite: 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.
- CS/ACM 177 ab. Discrete Differential Geometry. 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.
- CS/IDS 178. Numerical Algorithms and their Implementation. 9 units (3-3-3); third term. Prerequisite CS 2. This course gives students the understanding necessary to choose and implement basic numerical algorithms as needed in everyday programming practice. Concepts include: sources of numerical error, stability, convergence, ill-conditioning, and efficiency. Algorithms covered include solution of linear systems (direct and iterative methods), orthogonalization, SVD, interpolation and approximation, numerical integration, solution of ODEs and PDEs, transform methods (Fourier, Wavelet), and low rank approximation such as multipole expansions.
- CS 179. GPU Programming. 9 units (3-3-3); third term. Prerequisites: Good working knowledge of C/C++. Some experience with computer graphics algorithms preferred. 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 use nVidia’s parallel computing architecture, CUDA. Labwork requires extensive programming.
- CS 180. Master’s Thesis Research. Units (total of 45) are determined in accordance with work accomplished.
- 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.
- CNS/Bi/EE/CS/NB 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.
- 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.
- BE/CS/CNS/Bi 191 ab. Biomolecular Computation. 9 units (3-0-6) second term; (2-4-3) third term. Prerequisite: 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.
- BE/CS 196 ab. Design and Construction of Programmable Molecular Systems. a = 12 units (3-6-3) second term; b = 12 units (2-8-2) third term. Prerequisites: ChE/BE 163 or BE/CS/CNS/Bi 191a, or instructor’s permission. 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 complex two-dimensional and three-dimensional nanostructures, as well as quantitatively analyze the designs and the experimental data. Students will learn laboratory techniques including gel electrophoresis, fluorescence spectroscopy, and atomic force microscopy, and will use software tools and program in Mathematica or Mat lab. Part b is an open-ended, design-and-build project requiring instructor’s permission for enrollment. Enrollment in both parts a and b is limited to 12 students.
- Ph/CS 219 abc. Quantum Computation. 9 units (3-0-6); first, second, third terms. Prerequisite: 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.
- 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.
- 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.
- CS 274 abc. Topics in Computer Graphics. 9 units (3-3-3); first, second, third terms. Prerequisite: 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.
- CS 280. Research in Computer Science. Units in accordance with work accomplished. Approval of student’s research adviser and option adviser must be obtained before registering.
- CS 286 abc. Seminar in Computer Science. 3, 6, or 9 units, at the instructor’s discretion. Instructor’s permission required.
- CS 287 abc. Center for the Mathematics of Information Seminar. 3, 6, or 9 units, at the instructor’s discretion. Instructor’s permission required.
Computing + Mathematical Sciences Courses
- CMS/ACM/IDS 107. Linear Analysis with Applications. 12 units (3-3-6); first term. Prerequisites: ACM 104 or equivalent, Ma 1b or equivalent. Covers the basic algebraic, geometric, and topological properties of normed linear spaces, inner-product spaces, and linear maps. Emphasis is placed both on rigorous mathematical development and on applications to control theory, data analysis and partial differential equations.
- CMS/ACM/IDS 113. Mathematical Optimization. 12 units (3-0-9); first term. Prerequisites: ACM 11, ACM/IDS 104, or instructor's permission. This class studies mathematical optimization from the viewpoint of convexity. Topics covered include duality and representation of convex sets; linear and semidefinite programming; connections to discrete, network, and robust optimization; relaxation methods for intractable problems; as well as applications to problems arising in graphs and networks, information theory, control, signal processing, and other engineering disciplines.
- CMS 117. Probability Theory and Stochastic Processes. 12 units (3-0-9); first term. Prerequisites: ACM 104, ACM/EE/IDS 116 or instructor’s permission. This course offers a rigorous introduction to probability and stochastic processes. Emphasis is placed on the interaction between inequalities and limit theorems, as well as contemporary applications in computing and mathematical sciences. Topics include probability measures, random variables and expectation, independence, concentration inequalities, distances between probability measures, modes of convergence, laws of large numbers and central limit theorem, Gaussian and Poisson approximation, conditional expectation and conditional distributions, filtrations, and discrete-time martingales.
- CMS/CS/IDS 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, and CMS/ACM/EE 116 or ACM/CMS 113 or equivalent. This course develops core principles for the analysis and design of algorithms. Basic material includes mathematical techniques for analyzing performance in terms of resources, such as time, space, and randomness. The course introduces the major paradigms for algorithm design, including greedy methods, divide-and-conquer, dynamic programming, linear and semidefinite programming, randomized algorithms, and online learning.
- CMS/CS/EE/IDS 144. Networks: Structure & Economics. 12 units (3-4-5); 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.
- CMS/CS/CNS/EE/IDS 155. Machine Learning & Data Mining. 12 units (3-3-6); second term. Prerequisites: CS 156a. Having a sufficient background in algorithms, linear algebra, calculus, probability, and statistics, is highly recommended. 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. The course will focus on basic foundational concepts underpinning and motivating modern machine learning and data mining approaches. We will also discuss recent research developments.
- CMS 290. Computing and Mathematical Sciences Colloquium. 1 unit; first, second, third terms. Registration is limited to graduate students in the CMS department only. This course is a research seminar course covering topics at the intersection of mathematics, computation, and their applications. Students are asked to attend one seminar per week (from any seminar series on campus) on topics related to computing and mathematical sciences. This course is a requirement for first-year PhD students in the CMS department.
- CMS 300 abc. Research in Computing and Mathematical Sciences. Hours and units by arrangement. Research in the field of computing and mathematical science. By arrangement with members of the staff, properly qualified graduate students are directed in research.
Control + Dynamical Systems Courses
- CDS 90 abc. Senior Thesis in Control and Dynamical Systems. 9 units (0-0-9); first, second, third terms. Prerequisite: CDS 110, CDS 112 (may be taken concurrently). Research in control and dynamical systems, supervised by a Caltech faculty member. The topic selection is determined by the adviser and the student and is subject to approval by the CDS faculty. First and second terms: midterm progress report and oral presentation during finals week. Third term: completion of thesis and final presentation.Not offered on a pass/fail basis.
- CDS 110. Introduction to Feedback Control Systems. 9 units (3-3-3) third term. Prerequisites: Ma 1abc and Ma 2/102 or equivalents. An introduction to analysis and design of feedback control systems, including classical control theory in the time and frequency domain. Input/output modeling of dynamical systems using differential equations and transfer functions. Stability and performance of interconnected systems, including use of block diagrams, Bode plots, the Nyquist criterion, and Lyapunov functions. Design of feedback controllers in state space and frequency domain based on stability, performance and robustness specifications.
- CDS 112. Optimal Control and Estimation. 9 units (3-0-6); second term. Prerequisites: CDS 110 (or equivalent) and CDS 131. Optimization-based design of control systems, including optimal control and receding horizon control. Introductory random processes and optimal estimation. Kalman filtering and nonlinear filtering methods for autonomous systems.
- CDS 131. Linear Systems Theory. 9 units (3-0-6); first term. Prerequisites: Ma 1b, Ma 2, ACM 104 or equivalent (may be taken concurrently). Basic system concepts; state-space and I/O representation. Properties of linear systems, including stability, performance, robustness. Reachability, observability, minimality, state and output-feedback.
- CDS 141. Network Control Systems. 9 units (3-2-4); third term. Variety of case studies and projects from control, communication and computing in complex tech, bio, neuro, eco, and socieconomic networks, particularly smargrid, internet, sensorimotor control, cell biology, medical physiology, and human and animal social organization. Emphasis on leveraging universal laws and architectures but adding domain specific details. Can be taken after CDS 231 (to see applications of the theory) or before (to motivate the theory).
- Ma/ACM/IDS 140 ab. Probability. 9 units (3-0-6); first, second terms. Prerequisites: For 144a, Ma 108b is strongly recommended; for 144b, 108b and 144a are prerequisite. Overview of measure theory. Random walks and the Strong law of large numbers via the theory of martingales and Markov chains. Characteristic functions and the central limit theorem. Poisson process and Brownian motion. Topics in statistics.
- CDS 190. Independent Work in Control and Dynamical Systems. Units to be arranged; first, second, third terms; maximum two terms. Prerequisite: CDS 110. Research project in control and dynamical systems, supervised by a CDS faculty member.
- CDS 231. Robust Control Theory. 9 units (3-2-4); second term. Prerequisites: CMS/ACM/IDS 107, CMS/ACM 113, and CDS 131 (or equivalents). Linear input/output models (multi-state difference and differential equations). Stability, input/output norms. Uncertainty, including noise, disturbances, parametric uncertainty, unmodeled dynamics, and structured uncertainty (LTI/LTV). Tradeoffs, robustness versus efficiency, conservation laws and hard limits in time and frequency domain. Synthesis of robust control systems. Co-design of sparse and limited (delayed, quantized, saturating, noisy) sensing, communications, computing, and actuation. Layering, localization, and distributed control. Interplay between automation, optimization, control, modeling and system identification, and machine learning. Computational scalability exploiting sparsity and structure, nonlinear dynamics and sum of squares, global stability, regions of attraction. Motivation throughout from case studies from tech, neuro, bio, and socioeconomic networks, explored in more detail in CDS 141.
- CDS 232. Nonlinear Dynamics. 9 units (3-0-6); second term. Prerequisites: CMS/ACM/IDS 107 and CDS 231. This course studies nonlinear dynamical systems beginning from first principles. Topics include: existence and uniqueness properties of solutions to nonlinear ODEs, stability of nonlinear systems from the perspective of Lyapunov, and behavior unique to nonlinear systems; for example: stability of periodic orbits, Poincaré maps and stability/invariance of sets. The dynamics of robotic systems will be used as a motivating example.
- CDS 233. Nonlinear Control. 9 units (3-0-6); third term. Prerequisites: CDS 231 AND CDS 232. This course studies nonlinear control systems from Lyapunov perspective. Beginning with feedback linearization and the stabilization of feedback linearizable system, these concepts are related to control Lyapunov functions, and corresponding stabilization results in the context of optimization based controllers. Advanced topics that build upon these core results will be discussed including: stability of periodic orbits, controller synthesis through virtual constraints, safety-critical controllers, and the role of physical constraints and actuator limits. The control of robotic systems will be used as a motivating example.
- CDS 242. Hybrid Systems: Dynamics and Control. 9 units (3-2-4) third term. Prerequisites: CDS 231 and CDS 232. This class studies hybrid dynamical systems: systems that display both discrete and continuous dynamics. This includes topics on dynamic properties unique to hybrid system: stability types, hybrid periodic orbits, Zeno equilibria and behavior. Additionally, the nonlinear control of these systems will be considered in the context of feedback linearization and control Lyapunov functions. Applications to mechanical systems undergoing impacts will be considered, with a special emphasis on bipedal robotic walking.
- CDS 243. Adaptive Control. 4 units (2-0-2); third term. Prerequisites: CDS 231 and CDS 232. Specification and design of control systems that operate in the presence of uncertainties and unforeseen events. Robust and optimal linear control methods, including LQR, LQG and LTR control. Design and analysis of model reference adaptive control (MRAC) for nonlinear uncertain dynamical systems with extensions to output feedback. Offered in alternate years.
- CDS 244. System Identification. 4 units (2-0-2); third term. Prerequisites: CDS 231 and CDS 232. Mathematical treatment of system identification methods for dynamical systems, with applications. Nonlinear dynamics and models for parameter identification. Gradient and least-squares estimators and variants. System identification with adaptive predictors and state observers. Parameter estimation in the presence of non-parametric uncertainties. Introduction to adaptive control. Offered in alternate years.
- Ae/CDS/ME 251 ab. Closed Loop Flow Control. 9 units; (3-0-6 a, 1-6-1- b); second, third term. Prerequisites: ACM 100abc, Ae/APh/CE/ME 101abc or equivalent. This course seeks to introduce students to recent developments in theoretical and practical aspects of applying control to flow phenomena and fluid systems. Lecture topics in the second term drawn from: the objectives of flow control; a review of relevant concepts from classical and modern control theory; high-fidelity and reduced-order modeling; principles and design of actuators and sensors. Third term: laboratory work in open- and closed-loop control of boundary layers, turbulence, aerodynamic forces, bluff body drag, combustion oscillations and flow-acoustic oscillations.
- CDS 270. Advanced Topics in Systems and Control. Hours and units by arrangement. Topics dependent on class interests and instructor. May be repeated for credit.
- CDS 270-2. Control and Estimation for Swarm Autonomy. 9 units (3-0-6); Prerequisites: CDS 112 (or Ae103a) and CDS 232, or permission of instructor. Various control and estimation tools for analysis and design of distributed autonomous robots and cooperative control of aerospace vehicles. Input-output stability tools including passivity and contraction theory. Synchronization and consensus theory for networked nonlinear systems. Learning, optimal control, and estimation for distributed autonomous agents.
- CDS 300 abc. Research in Control and Dynamical Systems. Hours and units by arrangement. Research in the field of control and dynamical systems. By arrangement with members of the staff, properly qualified graduate students are directed in research.
Information and Data Sciences
- IDS 9. Introduction to Information and Data Systems Research. 1 unit (1-0-0); second term. This course will introduce students to research areas in IDS through weekly overview talks by Caltech faculty and aimed at first-year undergraduates. Others may wish to take the course to gain an understanding of the scope of research in computer science. Graded pass/fail.
- ACM/IDS 101 ab. Methods of Applied Mathematics. 12 units (4-4-4); first, second, terms. Prerequisites: Math 2/102 and ACM 95ab or equivalent. First term: Brief review of the elements of complex analysis and complex-variable methods. Asymptotic expansions, asymptotic evaluation of integrals (Laplace method, stationary phase, steepest descents), perturbation methods, WKB theory, boundary-layer theory, matched asymptotic expansions with first-order and high-order matching. Method of multiple scales for oscillatory systems. Second term: Applied spectral theory, special functions, generalized eigenfunction expansions, convergence theory. Gibbs and Runge phenomena and their resolution. Chebyshev expansion and Fourier Continuation methods. Review of numerical stability theory for time evolution. Fast spectrally-accurate PDE solvers for linear and nonlinear Partial Differential Equations in general domains. Integral-equations methods for linear partial differential equation in general domains (Laplace, Helmholtz, Schrödinger, Maxwell, Stokes). Homework problems in both 101 a and 101 b include theoretical questions as well as programming implementations of the mathematical and numerical methods studied in class.
- ACM/IDS 104. Applied Linear Algebra. 9 units (3-1-5); first term. Prerequisites: Ma 1 abc, some familiarity with MATLAB, e.g. ACM 11 is desired. This is an intermediate linear algebra course aimed at a diverse group of students, including junior and senior majors in applied mathematics, sciences and engineering. The focus is on applications. Matrix factorizations play a central role. Topics covered include linear systems, vector spaces and bases, inner products, norms, minimization, the Cholesky factorization, least squares approximation, data fitting, interpolation, orthogonality, the QR factorization, ill-conditioned systems, discrete Fourier series and the fast Fourier transform, eigenvalues and eigenvectors, the spectral theorem, optimization principles for eigenvalues, singular value decomposition, condition number, principal component analysis, the Schur decomposition, methods for computing eigenvalues, non-negative matrices, graphs, networks, random walks, the Perron-Frobenius theorem, PageRank algorithm.
- CMS/ACM/IDS 107. Linear Analysis with Applications. 12 units (3-3-6); first term. Prerequisites: ACM 104 or equivalent, Ma 1b or equivalent. Covers the basic algebraic, geometric, and topological properties of normed linear spaces, inner-product spaces, and linear maps. Emphasis is placed both on rigorous mathematical development and on applications to control theory, data analysis and partial differential equations.
- CMS/ACM/IDS 113. Mathematical Optimization. 12 units (3-0-9); first term. Prerequisites: ACM 11, ACM/IDS 104, or instructor's permission. This class studies mathematical optimization from the viewpoint of convexity. Topics covered include duality and representation of convex sets; linear and semidefinite programming; connections to discrete, network, and robust optimization; relaxation methods for intractable problems; as well as applications to problems arising in graphs and networks, information theory, control, signal processing, and other engineering disciplines.
- ACM/EE/IDS 116 Introduction to Probability Models. 9 units (3-1-5); first term. Prerequisites: Ma 2, Ma 3, some familiarity with MATLAB, e.g. ACM 11 is desired. This course introduces students to the fundamental concepts, methods, and models of applied probability and stochastic processes. The course is application oriented and focuses on the development of probabilistic thinking and intuitive feel of the subject rather than on a more traditional formal approach based on measure theory. The main goal is to equip science and engineering students with necessary probabilistic tools they can use in future studies and research. Topics covered include sample spaces, events, probabilities of events, discrete and continuous random variables, expectation, variance, correlation, joint and marginal distributions, independence, moment generating functions, law of large numbers, central limit theorem, random vectors and matrices, random graphs, Gaussian vectors, branching, Poisson, and counting processes, general discrete- and continuous-timed processes, auto- and cross-correlation functions, stationary processes, power spectral densities.
- CS/IDS 121. 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.
- EE/Ma/CS/IDS 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, fountain coding. Emphasis will be placed on the associated encoding and decoding algorithms, and students will be asked to demonstrate their understanding with a software project.
- EE/Ma/CS/IDS 136. Topics in Information Theory. 9 units (3-0-6); third term. Prerequisites: undergraduate calculus and probability. This class introduces information measures such as entropy, information divergence, mutual information, information density from a probabilistic point of view, and discusses the relations of those quantities to problems in data compression and transmission, statistical inference, language modeling, game theory and control. Topics include information projection, data processing inequalities, sufficient statistics, hypothesis testing, single-shot approach in information theory, large deviations.
- CMS/CS/IDS 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, and CMS/ACM/EE 116 or ACM/CMS 113 or equivalent. This course develops core principles for the analysis and design of algorithms. Basic material includes mathematical techniques for analyzing performance in terms of resources, such as time, space, and randomness. The course introduces the major paradigms for algorithm design, including greedy methods, divide-and-conquer, dynamic programming, linear and semidefinite programming, randomized algorithms, and online learning.
- CS/IDS 142. Distributed Computing. (3-2-4); 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.
- CS/EE/IDS 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.
- Ma/ACM/IDS 140 ab. Probability. 9 units (3-0-6); first, second terms. Prerequisites: For 144a, Ma 108b is strongly recommended; for 144b, 108b and 144a are prerequisite. Overview of measure theory. Random walks and the Strong law of large numbers via the theory of martingales and Markov chains. Characteristic functions and the central limit theorem. Poisson process and Brownian motion. Topics in statistics.
- CMS/CS/EE/IDS 144. Networks: Structure & Economics. 12 units (3-4-5); 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.
- CS/IDS 150 ab. Probability and Algorithms. 9 units (3-0-6); first term. Prerequisites: part a: CS 38 and Ma 5 abc; part b: part a or another introductory course in discrete probability. Part a: The probabilistic method and randomized algorithms. Deviation bounds, k-wise independence, graph problems, identity testing, derandomization and parallelization, metric space embeddings, local lemma. Part b: Further topics such as weighted sampling, epsilon-biased sample spaces, advanced deviation inequalities, rapidly mixing Markov chains, analysis of boolean functions, expander graphs, and other gems in the design and analysis of probabilistic algorithms. Parts a & b are offered in alternate years. Part b will be offered in 2019-20.
- CS/IDS 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.
- ACM/IDS 154. Inverse Problems and Data Assimilation. 9 units (3-0-6); first term. Prerequisites: Basic differential equations, linear algebra, probability and statistics: ACM 104, ACM/EE 106 ab, ACM/EE/IDS 116, IDS/ACM/CS 157 or equivalent. Models in applied mathematics often have input parameters that are uncertain; observed data can be used to learn about these parameters and thereby to improve predictive capability. The purpose of the course is to describe the mathematical and algorithmic principles of this area. The topic lies at the intersection of fields including inverse problems, differential equations, machine learning and uncertainty quantification. Applications will be drawn from the physical, biological and data sciences.
- IDS/ACM/CS 157. Statistical Inference. 9 units (3-2-4); third term. Prerequisites: ACM/EE/IDS 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.
- IDS/ACM/CS 158. Fundamentals of Statistical Learning. 9 units (3-3-3); third term. Prerequisites: Ma 3 or ACM/EE/IDS 116, IDS/ACM/CS 157. The main goal of the course is to provide an introduction to the central concepts and core methods of statistical learning, an interdisciplinary field at the intersection of statistics, machine learning, information and data sciences. The course focuses on the mathematics and statistics of methods developed for learning from data. Students will learn what methods for statistical learning exist, how and why they work (not just what tasks they solve and in what built-in functions they are implemented), and when they are expected to perform poorly. The course is oriented for upper level undergraduate students in IDS, ACM, and CS and graduate students from other disciplines who have sufficient background in probability and statistics. The course can be viewed as a statistical analog of CMS/CS/CNS/EE/IDS 155. Topics covered include supervised and unsupervised learning, regression and classification problems, linear regression, subset selection, shrinkage methods, logistic regression, linear discriminant analysis, resampling techniques, tree-based methods, support-vector machines, and clustering methods.
- CS/CNS/EE/IDS 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.
- EE/CS/IDS 160. Fundamentals of Information Transmission and Storage. 9 units (3-0-6); second term. Basics of information theory: entropy, mutual information, source and channel coding theorems. Basics of coding theory: error-correcting codes for information transmission and storage, block codes, algebraic codes, sparse graph codes. Basics of digital communications: sampling, quantization, digital modulation, matched filters, equalization.
- ACM/EE/IDS 170. Mathematics of Signal Processing. 12 units (3-0-9); third term. Prerequisites: CMS/ACM 104, CMS/ACM/IDS 113, and CMS/ACM 116; or instructor’s permission. This course covers classical and modern approaches to problems in signal processing. Problems may include denoising, deconvolution, spectral estimation, direction-of-arrival estimation, array processing, independent component analysis, system identification, filter design, and transform coding. Methods rely heavily on linear algebra, convex optimization, and stochastic modeling. In particular, the class will cover techniques based on least-squares and on sparse modeling. Throughout the course, a computational viewpoint will be emphasized.
- IDS 197. Undergraduate Reading in the Information and Data Sciences. Units are assigned in accordance with work accomplished. Prerequisites: Consent of supervisor is required before registering. Supervised reading in the information and data sciences 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.
- IDS 198. Undergraduate Projects in Information and Data Sciences. Units are assigned in accordance with work accomplished. Prerequisite: Consent of supervisor is required before registering. Supervised research in the information and data sciences. The topic must be approved by the project supervisor and a formal report must be presented upon completion of the research. Graded pass/fail.
- IDS 199. Undergraduate thesis in the Information and Data Sciences. 9 units (1-0-8); first, second, third terms. Prerequisite: 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 faculty member and approved by the option representative. Projects must include significant design effort and a written Report is required. Open only to upperclass students. Not offered on a pass/fail basis.
- ACM/IDS 204. Topics in Linear Algebra and Convexity. 9 units (3-0-6); second term. Prerequisites: ACM/IDS 104 and ACM/EE 106 a, CMS 117, or instructor’s permission. Topic varies by year. 2019-2020: Randomized algorithms for linear algebra. This class offers an introduction to the emerging field of randomized algorithms for solving linear algebra problems. Material may include trace estimation, norm estimation, matrix approximation by sampling, random projections, approximating least-squares problems, randomized SVD algorithms, approximate preconditioners, spectral computations, kernel methods, and fast linear system solvers. Assignments will require mathematical proofs, programming, and computer simulation.
- ACM/IDS 213. Topics in Optimization. 9 units (3-0-6); third term. Prerequisites: CMS/ACM 104, CMS/ACM/IDS 113. Material varies year-to-year. Example topics include discrete optimization, convex and computational algebraic geometry, numerical methods for large-scale optimization, and convex geometry.
- ACM/IDS 216. Markov Chains, Discrete Stochastic Processes and Applications. 9 units (3-0-6); second term. Prerequisite: ACM/EE/IDS 116 or equivalent. Stable laws, Markov chains, classification of states, ergodicity, von Neumann ergodic theorem, mixing rate, stationary/equilibrium distributions and convergence of Markov chains, Markov chain Monte Carlo and its applications to scientific computing, Metropolis Hastings algorithm, coupling from the past, martingale theory and discrete time martingales, rare events, law of large deviations, Chernoff bounds.
- ACM/EE/IDS 217. Advanced Topics in Stochastic Analysis. 9 units (3-0-6); third term. Prerequisite: ACM/IDS 216 or equivalent. The topic of this course changes from year to year and is expected to cover areas such as stochastic differential equations, stochastic control, statistical estimation and adaptive filtering, empirical processes and large deviation techniques, concentration inequalities and their applications. Examples of selected topics for stochastic differential equations include continuous time Brownian motion, Ito’s calculus, Girsanov theorem, stopping times, and applications of these ideas to mathematical finance and stochastic control.