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.
Applied + Computational Mathematics Courses
- ACM 11. Introduction to Matlab and Mathematica. 6 units (2-2-2); first term. Prerequisites: Ma 1 abc, Ma 2 ab, 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 95/100 abc. Introductory Methods of Applied Mathematics. 12 units (4-0-8); first, second, third terms. Prerequisites: Ma 1 abc, Ma 2 ab (may be taken concurrently), or equivalent. First term: Complex analysis: analyticity, Laurent series, singularities, branch cuts, contour integration, residue calculus. Second term: Ordinary differential equations. Linear initial value problems: Laplace transforms, series solutions. Linear boundary value problems: eigenvalue problems, Fourier series, Sturm-Liouville theory, eigenfunction expansions, the Fredholm alternative, Greens functions, nonlinear equations, stability theory, Lyapunov functions, numerical methods, Third term: Linear partial differential equations: heat equation separation of variables, Fourier transforms, special functions, Green's functions, wave equation, Laplace equation, method of characteristics, numerical methods.
- ACM 101 ab. Methods of Applied Mathematics I. 12 units (4-0-8); first, second, terms. Prerequisites: Math 2/102 and ACM 95abc. 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, Hilbert spaces and linear operators, generalized eigenfunction expansions, convergence theory. Transform methods, distributions, Fourier Transform and Sobolev Spaces. Eigensystems and spectral theory for self-adjoint second order operators with variable coefficients in n-dimensional domains. Integral equations, Fredholm theorem, application to Laplace and Maxwell's equations, harmonicity at infinity, Kelvin transform, conditions of radiation at infinity.
- ACM/CMS 104. Linear Algebra and Applied Operator Theory. 12 units (3-0-9); first term. Undergraduate prerequisites: Ma 1abc (analytic track), Ma 2, and ACM 95abc; or instructor's permission. Graduate prerequisites: ACM 100abc; or instructor’s permission.This course introduces the theory and applications of linear algebra and linear analysis. Lectures and homework will require the ability to understand and produce mathematical proofs. Theoretical topics may include topology of metric spaces, structure of Banach and Hilbert spaces, examples of normed spaces, duality, structure of linear operators, spectral theory, functional calculus for linear operators, and calculus in Banach spaces. Applications will be drawn from signal processing, numerical analysis, optimization, approximation, differential equations, control, and other areas. Emphasis will be placed on geometry and convexity.
- ACM 105. Applied Real and Functional Analysis. 9 units (3-0-6); second term. Prerequisite: ACM 100 abc or instructor's permission. Lebesgue integral on the line, general measure and integration theory; Lebesgue integral in n-dimensions, convergence theorems, Fubini, Tonelli, and the transformation theorem; normed vector spaces, completeness, Banach spaces, Hilbert spaces; dual spaces, Hahn-Banach Theorem, Riesz-Frechet Theorem, weak convergence and weak solvability theory of boundary value problems; linear operators, existence of the adjoint. Self-adjoint operators, polar decomposition, positive operators, unitary operators; dense subspaces and approximation, the Baire, Banach-Steinhaus, open mapping and closed graph theorems with applications to differential and integral equations; spectral theory of compact operators; LP spaces, convolution; Fourier transform, Fourier series; Sobolev spaces with application to PDEs, the convolution theorem, Friedrich's mollifiers. ↑ top
- ACM 106 ab. Introductory Methods of Computational Mathematics.12 units (3-0-9); second, third terms. Prerequisites: Ma 1 abc, Ma2, Ma 3, ACM 11, ACM 95/100 abc 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.
- ACM/CMS 113. Introduction to Optimization. 9 units (3-0-6); first term. Prerequisites: ACM 95/100 abc, ACM 11, or instructor's permission. Corequisite: It is suggested that students take ACM/CMS 104 concurrently.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/CS 114. Parallel Algorithms for Scientific Applications. 9 units (3-0-6); second term. Prerequisites: ACM 11, ACM 106 or equivalent. Introduction to parallel program design for numerically intensive scientific applications. Parallel programming methods; distributed-memory model with message passing using the message passing interface; shared-memory model with threads using open MP, CUDA; object-based models using a problem-solving environment with parallel objects. Parallel numerical algorithms: numerical methods for linear algebraic systems, such as LU decomposition, QR method, CG solvers; parallel implementations of numerical methods for PDEs, including finite-difference, finite-element; particle-based simulations. Performance measurement, scaling and parallel efficiency, load balancing strategies.
- ACM/EE/CMS 116. Introduction to Stochastic Processes and Modeling. 9 units (3-0-6); first term. Prerequisite: Ma 2 and Ma 3, or instructor's permission. Introduction to fundamental ideas and techniques of stochastic analysis and modeling. Random variables; expectation and conditional expectation; joint distributions; covariance; moment generating function; central limit theorem; weak and strong laws of large numbers; discrete time stochastic processes; stationarity; power spectral densities and the Wiener-Khinchine theorem; Gaussian processes; Poisson processes; Brownian motion. The course develops applications in selected areas such as signal processing (Wiener filter), information theory, genetics, queueing and waiting line theory, finance.
- Ma/ACM 142 abc. Ordinary and Partial Differential Equations. 9 units (3-0-6); first, second, third terms. 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 144 ab. Probability. 9 units (3-0-6); first, second terms. 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 151 ab. Asymptotic and Perturbation Methods. 9 units (3-0-6); first, second terms. Approximation methods for formulating and solving applied problems, with examples taken from various fields of science. Applications to various linear and nonlinear ordinary and partial differential equations. Singular and multiscale perturbation techniques, boundary-layer theory, coordinate straining, a method of averaging. Bifurcation theory, amplitude equations, and nonlinear stability.
- ACM/EE/CMS 170. Mathematics of Signal Processing. 12 units (3-0-9); third term. Prerequisites: ACM/CMS 104, ACM/CMS 113, and ACM/EE/CMS 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.
- ACM 190. Reading and Independent Study. Units by arrangement. Graded pass/fail only. ↑ top
- ACM 201 ab. Partial Differential Equations. 12 units (4-0-8); second, third terms. Prerequisite: ACM 11, ACM 101, or instructor's permission. Fully nonlinear first-order PDEs, shocks, eikonal equations. Classification of second-order linear equations: elliptic, parabolic, hyperbolic. Well-posed problems. Laplace and Poisson equations; Gauss’s theorem, Green’s function. Existence and uniqueness theorems (Sobolev spaces methods, Perron’s method). Applications to irrotational flow, elasticity, electrostatics, etc. Heat equation, existence and uniqueness theorems, Green’s function, special solutions. Wave equation and vibrations. Huygens’ principle. Spherical means. Retarded potentials. Water waves and various approximations, dispersion relations. Symmetric hyper-bolic systems and waves. Maxwell equations, Helmholtz equation, Schrödinger equation. Radiation conditions. Gas dynamics. Riemann invariants. Shocks, Riemann problem. Local existence theory for general symmetric hyperbolic systems. Global existence and uniqueness for the inviscid Burgers’ equation. Integral equations, single- and double-layer potentials. Fredholm theory. Navier Stokes equations. Stokes flow, Reynolds number. Potential flow; connection with complex variables. Blasius formulae. Boundary layers. Subsonic, supersonic, and transonic flow.
- ACM 204. Topics in Convexity. 9 units (3-0-6); second term. Prerequisites: ACM/CMS 104 and ACM/CMS 113; or instructor's permission. The content of this course varies from year to year among advanced subjects in linear algebra, convex analysis, and related fields. Specific topics for the class include matrix analysis, operator theory, convex geometry, or convex algebraic geometry. Lectures and homework will require the ability to understand and produce mathematical proofs.
- ACM 210 ab. Numerical Methods for PDEs. 9 units (3-0-6); second, third terms. Prerequisites: ACM 11, ACM 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 216. Markov Chains, Discrete Stochastic Processes and Applications. 9 units (3-0-6); second term. Prerequisite: ACM/EE/CMS 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 their 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 217/EE 164. Advanced Topics in Stochastic Analysis. 9 units (3-0-6); third term. Prerequisite: ACM 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. Example 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.
- ACM/CS/EE/CMS 218. Statistical Inference. 12 units (3-0-9); second term. Prerequisites: ACM/CMS 104, ACM/CMS 113, and ACM/EE/CMS 116; or instructor's permission. Fundamentals of estimation theory and hypothesis testing; Bayesian and non-Bayesian approaches; minimax analysis, Cramer-Rao bounds, shrinkage in high dimensions; Kalman filtering, basics of graphical models; statistical model selection. Throughout the course, a computational viewpoint will be emphasized.
- Ae/ACM/ME 232 abc. Computational Fluid Dynamics. 9 units (3-0-6); first, second, third 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 interpolition, 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 ab. Special Topics in Applied Mathematics. 9 units (3-0-6); third term. ITopics will vary according to student and instructor interest. May be repeated for credit.
- AM 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. 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 (2-6-1); second term. Prerequisite: CS 1 or equivalent. CS2 is a demanding course in programming languages and computer science. Topics covered include data structures, including lists, trees, and graphs; implementation and performance analysis of common algorithms; algorithm design principles, in particular recursion and dynamic programming; concurrency and network programming; basic numerical computation methods. Heavy emphasis is placed on the use of compiled languages and development tools, including source control and debugging. The course includes weekly laboratory exercises and written homework covering the lecture material and program design. The course is intended to establish a foundation for further work in many topics in the computer science option.
- CS 3. Introduction to Software Engineering. 9 units (2-4-3); third term. Prerequisite: CS 2 or equivalent. CS 3 is an advanced introduction to the fundamentals of computer science and software engineering methodology. Topics will be chosen from the following: abstract data types; object-oriented models and methods; logic, specification, and program composition; abstract models of computation; probabilistic algorithms; nondeterminism; distributed algorithms and data structures. The weekly laboratory exercises allow the students to investigate the lecture material by writing nontrivial applications.
- 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 the research areas of the computer science faculty, through weekly overview talks by the faculty aimed at first-year undergraduates. Others may wish to take the course to gain an understanding of the scope of the field. Graded pass/fail.
- 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 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); third term. Prerequisites: Familiarity with C equivalent to having taken the CS 11 C track. Basic introduction to computer systems, including hardware-software interface, computer architecture, and operating systems. Course emphasizes computer system abstractions and the hardware and software techniques necessary to support them, including virtualization (e.g., memory, processing, communication), dynamic resource management, and common-case optimization, isolation, and naming.
- CS 38. Introduction to Algorithms. 9 units (3-0-6); third term. Prerequisites: CS 2; Ma/CS 6 a or Ma 121 a; and CS 21 or CS/EE/Ma 129 a. This course introduces techniques for the design and analysis of efficient algorithms. Major design techniques (the greedy approach, divide and conquer, dynamic programming, linear programming) will be introduced through a variety of algebraic, graph, and optimization problems. Methods for identifying intractability (via NP-completeness) will be discussed. ↑ top
- 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. Microprocessor Systems Laboratory. 12 units (1-11-0); second term. Prerequisite: 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. Prerequisite: EE/CS 52 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.
- CS/EE/ME 75 abc. Introduction to Multidisciplinary Systems Engineering. 3 units (2-0-1) , 6 units (2-0-4), or 9 units (2-0-7) first term; 6 units (2-3-1), 9 units (2-6-1), or 12 units (2-9-1) second term; 12 units (2-9-1), 15 units (2-12-1), or 18 units (2-15-1), with instructor’s permission, third term. This course presents the fundamentals of modern multidisciplinary systems engineering in the context of a substantial design project. Students from a variety of disciplines will conceive, design, implement, and operate a system involving electrical, information, and mechanical engineering components. Specific tools will be provided for setting project goals and objectives, managing interfaces between component subsystems, working in design teams, and tracking progress against tasks. Students will be expected to apply knowledge from other courses at Caltech in designing and implementing specific subsystems. During the first two terms of the course, students will attend project meetings and learn some basic tools for project design, while taking courses in CS, EE, and ME that are related to the course project. During the third term, the entire team will build, document, and demonstrate the course design project, which will differ from year to year. Freshmen must receive permission from the lead instructor to enroll.
- CS 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 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 abc. Undergraduate Projects in Computer Science. Units are assigned in accordance with work accomplished. Prerequisites: Consent of supervisor is required before registering. Supervised research or development in computer science by undergraduates. The topic must be approved by the project supervisor, and a formal final report must be presented on completion of research. This course can (with approval) be used to satisfy the project requirement for the CS major. Graded pass/fail. Instructor: Staff.
- CS 90. Undergraduate Reading in Computer Science. Units are assigned in accordance with work accomplished. Prerequisites: Consent of supervisor is required before registering. Supervised reading in computer science by undergraduates. The topic must be approved by the reading supervisor, and a formal final report must be presented on completion of the term. Graded pass/fail. Instructor: Staff.
- CS 101 abc. Special Topics in Computer Science. Units in accordance with work accomplished; offered by announcement. Prerequisites: CS 21 and CS 38, or instructor's permission. The topics covered vary from year to year, depending on the students and staff. Primarily for undergraduates.
- CS 102 abc. Seminar in Computer Science. 3, 6, or 9 units as arranged with the instructor. 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.
- ACM/CS 114. Parallel Algorithms for Scientific Applications. 9 units (3-0-6); second term. Prerequisites: ACM 11, 106 or equivalent. Introduction to parallel program design for numerically intensive scientific applications. Parallel programming methods; distributed-memory model with message passing using the message passing interface; shared-memory model with threads using open MP, CUDA; object-based models using a problem-solving environment with parallel objects. Parallel numerical algorithms: numerical methods for linear algebraic systems, such as LU decomposition, QR method, CG solvers; parallel implementations of numerical methods for PDEs, including finite-difference, finite-element; particle-based simulations. Performance measurement, scaling and parallel efficiency, load balancing strategies. ↑ top
- CS 115. Functional programming. 9 units (3-4-2); third term. Prerequisites: CS 1, 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.
- CS 119. Reliable Software: Testing and Monitoring. 9 units (3-3-3); third term. Prerequisites: CS 1 or equivalent; CS 116 and CS 118 are recommended. The class discusses theoretical and practical aspects of software testing and monitoring. Topics include finite state machine testing algorithms, random testing, constraint-based testing, coverage measures, automated debugging, logics and algorithms for runtime monitoring, and aspect-oriented approaches to monitoring. Emphasis is placed on automation. Students will be expected to develop and use software testing and monitoring tools to develop reliable software systems.
- CS 121. Introduction to Relational Databases. 9 units (3-0-6); first term. Prerequisites: CS 1 or equivalent. Introduction to the basic theory and usage of relational database systems. It covers the relational data model, relational algebra, and the Structured Query Language (SQL). The course introduces the basics of database schema design and covers the entity-relationship model, functional dependency analysis, and normal forms. Additional topics include other query languages based on the relational calculi, data-warehousing and dimensional analysis, writing and using stored procedures, working with hierarchies and graphs within relational databases, and an overview of transaction processing and query evaluation. Extensive hands-on work with SQL databases. Instructor: Pinkston.
- CS 122. Database System Implementation. 9 units (3-3-3); second term. Prerequisites: CS 2, CS 38, CS 121 and familiarity with Java, or instructor’s permission. This course explores the theory, algorithms, and approaches behind modern relational database systems. Topics include file storage formats, query planning and optimization, query evaluation, indexes, transaction processing, concurrency control, and recovery. Assignments consist of a series of programming projects extending a working relational database, giving hands-on experience with the topics covered in class. The course also has a strong focus on proper software engineering practices, including version control, testing, and documentation. Instructor: Pinkston.
- CS 123. Projects in Database Systems. 9 units (0-0-9); third term. Prerequisites: CS 121 and CS 122. 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. 9 units (3-6-0); third term. Prerequisite: 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 CS24 is strongly advised before attempting this course.
- EE/Ma/CS 126 ab. Information Theory. 9 units (3-0-6); first, second terms. Prerequisite: Ma 2. 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, firstorder Markov, ergodic, and Gaussian. Calculation of capacity and rate-distortion functions. Kolmogorov complexity and universal source codes. Side information in source coding and communications. Network information theory, including multiuser data compression, multiple access channels, broadcast channels, and multiterminal networks. Discussion of philosophical and practical implications of the theory. This course, when combined with EE 112, EE/Ma/CS 127, EE 161, and/or EE 167 should prepare the student for research in information theory, coding theory, wireless communications, and/or data compression.
- EE/Ma/CS 127. Error-Correcting Codes. 9 units (3-0-6); third term. Prerequisite: Ma 2. This course, a sequel to EE/Ma 126 a, may be taken independently; it will develop 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, Golay, Fire, 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, 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/EE/Ma 129 abc. Information and Complexity. 9 units (3-0-6), first and second terms; (1-4-4) third term. Prerequisite: basic knowledge of probability and discrete mathematics. A basic course in information theory and computational complexity with emphasis on fundamental concepts and tools that equip the student for research and provide a foundation for pattern recognition and learning theory. First term: what information is and what computation is; entropy, source coding, Turing machines, uncomputability. Second term: topics in information and complexity; Kolmogorov complexity, channel coding, circuit complexity, NP-completeness. Third term: theoretical and experimental projects on current research topics.
- 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.
- Ec/CS 133. Electricity Markets. 9 units (3-0-6); first term. Prerequisites: Ec 11 or Ec 172. This in depth introductory course provides an overview of the industry focusing on the linkages between power system engineering, markets, and regulatory policy. We will analyze the fundamentals of Economics various electricity markets including locational marginal pricing, bilateral, day-ahead, real-time, capacity, emissions markets and risk markets. We will identify the basic components, design, and operation of electric power systems. We will examine how markets should be designed to be consistent with the engineering fundamentals of electric power systems. We will discuss sensors, metering devices, communication, and computation required to enable markets to function.
- CS 138 abc. Computer Algorithms. 9 units (3-0-6); first, second, third terms. Prerequisites: CS 21 and CS 38, or instructor's permission. Design and analysis of algorithms. Techniques for problems concerning graphs, flows, number theory, string matching, data compression, geometry, linear algebra and coding theory. Optimization, including linear programming. Randomization. Basic complexity theory and cryptography.
- CS/CMS 139. Analysis and Design of Algorithms.12 units (3-0-9); third term. Prerequisites: Ma 2, Ma 3, Ma/CS 6a, CS 21, CS 38/138, ACM/EE/CMS 116, or instructor’s permission. This course covers advanced topics in the design and analysis of algorithms. Topics are drawn from approximation algorithms, randomized algorithms, online algorithms, streaming algorithms, and other areas of current research interest in algorithms.
- CS 142. Distributed Computing. 3-0-6; third term. Prerequisites: CS 24, CS 38. Programming distributed systems. Mechanics for cooperation among concurrent agents. Programming sensor networks and cloud computing applications. Applications of machine learning and statistics by using parallel computers to aggregate and analyze data streams from sensors.
- CS/EE 143. Communication Networks. 9 units (3-3-3); first term. Prerequisite: Ma 2 ab. This course introduces the basic mechanisms and protocols in communication networks, and mathematical models for their analysis. It covers topics such as digitization, switching, switch design, routing, error control (ARQ), congestion control, layering, queuing models, optimization models, basics of protocols in the Internet, wireless networks, and optical networks. This course can be combined with CS/EE 144 and CS/EE 145 to satisfy the project requirement for CS undergraduate degree. ↑ top
- CS/EE/CMS 144. Networks: Structure & Economics. 12 units (3-3-6); second term. Prerequisites: Ma 2, Ma 3, Ma/CS 6a, and CS 38, or instructor permission. Social networks, the web, and the internet are essential parts of our lives and we all depend on them every day, but do you really know what makes them work? This course studies the "big" ideas behind our networked lives. Things like, what do networks actually look like (and why do they all look the same)? How do search engines work? Why do memes spread the way they do? How does web advertising work? For all these questions and more, the course will provide a mixture of both mathematical analysis and hands-on labs. The course assumes students are comfortable with graph theory, probability, and basic programming.
- CS/EE 145. Projects in Networking. 9 units (0-0-9); third term. Prerequisites: CS/EE 143, CS/EE 144. Students are expected to execute a substantial project in networking, write up a report describing their work, and make a presentation. This course can be combined with CS/EE 143 and CS/EE 144 to satisfy the project requirement for CS undergraduate degree.
- CS/EE 146. Advanced Networking. 9 units (3-3-3). Prerequisites: CS/EE 143 or instructor's permission. This is a research-oriented course meant for undergraduates and beginning graduate students who want to learn about current research topics in networks such as the Internet, power networks, social networks, etc. The topics covered in the course will vary, but will be pulled from current research topics in the design, analysis, control, and optimization of networks, protocols, and Internet applications. Usually offered in alternate years.
- CS/EE 147. Network Performance Analysis. 9 units (3-0-6); third term. Prerequisite: Ma 2 ab is required. CS/EE 143, CS/EE 144, and ACM 116 are recommended. When designing a network protocol, distributed system, etc., it is essential to be able to quantify the performance impacts of design choices along the way. For example, should we invest in more buffer space or a faster processor? One fast disk or multiple slower disks? How should requests be scheduled? What dispatching policy will work best? Ideally, one would like to make these choices before investing the time and money to build a system. This class will teach students how to answer this type of "what if" question by introducing students to analytic performance modeling, the tools necessary for rigorous system design. The course will focus on the mathematical tools of performance analysis (which include stochastic modeling, scheduling theory, and queueing theory) but will also highlight applications of these tools to real systems. Usually offered in alternate years.
- EE/CNS/CS 148 ab. Selected Topics in Computational Vision. 9 units (3-0-6); first, third terms. 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.
- SS/CS 149. Introduction to Algorithmic Economics. 9 units (3-0-6); first term. Ma 3, CS 24 and CS 38, or instructor permission. This course will equip students to engage with current topics of active research at the intersection of social and information sciences, including: algorithmic mechanism design; auctions; existence and computation of equilibria; and learning and games.
- CS 150. Probability and Algorithms. 9 units (3-0-6); second term. Prerequisites: CS 38 a and Ma 5 abc. Elementary randomized algorithms and algebraic bounds in communication, hashing, and identity testing. Game tree evaluation. Topics may include randomized parallel computation; independence, k-wise independence and derandomization; rapidly mixing Markov chains; expander graphs and their applications; clustering algorithms.
- 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/SS 152. Introduction to Data Privacy. 3-0-6; first term; Prerequisites: Ma 3, CS 24 and CS 38, or instructor's permission. How should we define privacy? What are the tradeoffs between useful computation on large datasets and the privacy of those from whom the data is derived? This course will take a mathematically rigorous approach to addressing these and other questions at the frontier of research in data privacy. We will draw connections with a wide variety of topics, including economics, statistics, information theory, game theory, probability, learning theory, geometry, and approximation algorithms.
- CS 153. Current Topics in Theoretical Computer Science will not be offered second term. 9 units (3-0-6); third 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. Offered in alternate years.
- CS/CNS/EE 154. Artificial Intelligence. 9 units (3-3-3); first term. Prerequisites: Ma 2 b or equivalent, and CS 1 or equivalent. How can we build systems that perform well in unknown environments and unforeseen situations? How can we develop systems that exhibit “intelligent” behavior, without prescribing explicit rules? How can we build systems that learn from experience in order to improve their performance? We will study core modeling techniques and algorithms from statistics, optimization, planning, and control and study applications in areas such as sensor networks, robotics, and the Internet. The course is designed for upper-level undergraduate and graduate students.
- CS/CNS/EE 155. Machine Learning & Data Mining 9 Units (3-3-3); second term. Prerequisites: background in algorithms and statistics (CS/CNS/EE/NB 154 or CS/CNS/EE 156a or instructor’s permission). This course will cover popular methods in machine learning and data mining, with an emphasis on developing a working understanding of how to apply these methods in practice. This course will also cover core foundational concepts underpinning and motivating modern machine learning and data mining approaches. This course will be research-oriented, and will cover recent research developments.
- CS/CNS/EE 156 ab. Learning Systems. 9 units (3-0-6); first, second 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.
- CS/CNS/EE 159. Projects in Machine Learning and AI. 9 units (0-0-9); third term. Prerequisite: CS/CNS/EE 154 or CS/CNS/EE 156 b. Students are expected to execute a substantial project in AI and/or machine learning, write up a report describing their work, and make a presentation. This course can be combined with CS/CNS/EE 154/155 or with CS/CNS/EE 156 ab to satisfy the project requirement for the CS undergraduate degree. ↑ top
- CS/CNS 171. Introduction to Computer Graphics Laboratory. 12 units (3-6-3); first term. Prerequisites: Ma 2 and extensive programming experience. This course introduces the basic ideas behind computer graphics and its fundamental algorithms. Topics include graphics input and output, the graphics pipeline, sampling and image manipulation, three-dimensional transformations and interactive modeling, basics of physically based modeling and animation, simple shading models and their hardware implementation, and fundamental algorithms of scientific visualization. Students will be required to perform significant implementations.
- CS/CNS 174. Computer Graphics Projects. 12 units (3-6-3); third term. Prerequisites: Ma 2 and CS/CNS 171 or instructor's permission. This laboratory class offers students an opportunity for independent work covering recent computer graphics research. In coordination with the instructor, students select a computer graphics modeling, rendering, interaction, or related algorithm and implement it. Students are required to present their work in class and discuss the results of their implementation and any possible improvements to the basic methods. May be repeated for credit with instructor’s permission.
- CS 176. Introduction to 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 177. Discrete Differential Geometry: Theory and Applications. 9 units (3-3-3); first term. Topics include, but are not limited to, discrete exterior calculus; Whitney forms; DeRham and Whitney complexes; Morse theory; computational and algebraic topology; discrete simulation of thin shells, fluids, electromagnetism, elasticity; surface parameterization; Hodge decomposition.
- CS 179. GPU Programming. 9 units (3-3-3); third term. Prerequisites: Working knowledge of C. Some experience with computer graphics algorithms preferred, but not required. The use of Graphics Processing Units for computer graphics rendering is well known, but their power for general parallel computation is only recently being explored. Parallel algorithms running on GPUs can often achieve up to 100x speedup over similar CPU algorithms. This course covers programming techniques for the Graphics processing unit, focusing on visualization and simulation of various systems. Labs will cover specific applications in graphics, mechanics, and signal processing. The course will introduce the OpenGL Shader Language (GLSL) and nVidia’s parallel computing architecture, CUDA. Labwork will require extensive programming.
- CS 180. Master's Thesis Research. Units (total of 45) are determined in accordance with work accomplished.
- CS/EE 181 abc. VLSI Design Laboratory. 12 units (3-6-3); first, second, third terms. Digital integrated system design, with projects involving the design, verification, and testing of high-complexity CMOS microcircuits. First-term lecture and homework topics emphasize disciplined design, and include CMOS logic, layout, and timing; computer-aided design and analysis tools; and electrical and performance considerations. Each student is required in the first term to complete individually the design, layout, and verification of a moderately complex integrated circuit. Advanced topics second and third terms include self-timed design, computer architecture, and other topics that vary year by year. Projects are large-scale designs done by teams.
- 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. Given in alternate years.
- CNS/Bi/Ph/CS 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.
- CNS/CS/EE 188. Topics in Computation and Biological Systems. 9 units (3-0-6); second term. Prerequisite: Ma 2 or IST 4. Advanced topics related to computational methods in biology. Topics might change from year to year. Examples include spectral analysis techniques and their applications in threshold circuits complexity and in computational learning theory. The role of feedback in computation. The logic of computation in gene regulation networks. The class includes a project that has the goal of learning how to understand, criticize, and present the ideas and results in research papers.
- BE/CS/CNS/Bi 191 ab. Biomolecular Computation. 9 units (3-0-6) second term; (2-4-3) third term. Prerequisite: ChE/BE 163. Recommended: 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.
- Ph/CS 219 abc. Quantum Computation. 9 units (3-0-6); first, second 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. Advanced 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. ↑ top
- CS/CNS/EE 253. Special Topics in Machine Learning. 9 units (3-3-3). Prerequisite: CS/CNS/EE 154 or CS/CNS/EE 156 a or instructor's permission. This course is an advanced, research-oriented seminar in machine learning and AI meant for graduate students and advanced undergraduates. The topics covered in the course will vary, but will always come from the cutting edge of machine learning and AI research. Examples of possible topics are active learning and optimized information gathering, AI in distributed systems, computational learning theory, machine learning applications (on the Web, in sensor networks and robotics).
- 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 282 abc. Reading in Computer Science. 6 units or more by arrangement; first, second, third terms. Instructor's permission required.
- CS 286 abc. Seminar in Computer Science. 3, 6, or 9 units, at the instructor’s discretion. Instructor's permission required.
Computing + Mathematical Sciences Courses
- ACM/CMS 104. Linear Algebra and Applied Operator Theory. 12 units (3-0-9); first term. Undergraduate prerequisites: Ma 1abc (analytic track), Ma 2, and ACM 95abc; or instructor's permission. Graduate prerequisites: ACM 100abc; or instructor’s permission. This course introduces the theory and applications of linear algebra and linear analysis. Lectures and homework will require the ability to understand and produce mathematical proofs. Theoretical topics may include topology of metric spaces, structure of Banach and Hilbert spaces, examples of normed spaces, duality, structure of linear operators, spectral theory, functional calculus for linear operators, and calculus in Banach spaces. Applications will be drawn from signal processing, numerical analysis, optimization, approximation, differential equations, control, and other areas. Emphasis will be placed on geometry and convexity.
- ACM/CMS 113. Mathematical Optimization. 9 units (3-0-6); first term. Prerequisites: ACM 95/100 abc, ACM 11, or instructor's permission. Corequisite: It is suggested that students take ACM/CMS 104 concurrently. 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/CMS 116. Introduction to Stochastic Processes and Modeling. 9 units (3-0-6); first term. Prerequisite: Ma 2 and Ma 3, or instructor's permission. Introduction to fundamental ideas and techniques of stochastic analysis and modeling. Random variables; expectation and conditional expectation; joint distributions; covariance; moment generating function; central limit theorem; weak and strong laws of large numbers; discrete time stochastic processes; stationarity; power spectral densities and the Wiener-Khinchine theorem; Gaussian processes; Poisson processes; Brownian motion. The course develops applications in selected areas such as signal processing (Wiener filter), information theory, genetics, queueing and waiting line theory, finance.
- CS/CMS 139. Analysis and Design of Algorithms. 12 units (3-0-9); third term. Prerequisites: Ma 2, Ma 3, Ma/CS 6a, CS 21, CS 38/138, ACM/EE/CMS 116, or instructor’s permission. This course covers advanced topics in the design and analysis of algorithms. Topics are drawn from approximation algorithms, randomized algorithms, online algorithms, streaming algorithms, and other areas of current research interest in algorithms.
- CS/EE/CMS 144. Networks: Structure & Economics. 12 units (3-3-6); second term. Prerequisites: Ma 2, Ma 3, Ma/CS 6a, and CS 38, or instructor permission. Social networks, the web, and the internet are essential parts of our lives and we all depend on them every day, but do you really know what makes them work? This course studies the "big" ideas behind our networked lives. Things like, what do networks actually look like (and why do they all look the same)? How do search engines work? Why do memes spread the way they do? How does web advertising work? For all these questions and more, the course will provide a mixture of both mathematical analysis and hands-on labs. The course assumes students are comfortable with graph theory, probability, and basic programming.
- ACM/EE/CMS 170. Mathematics of Signal Processing. 12 units (3-0-9); third term. Prerequisites: ACM/CMS 104, ACM/CMS 113, and ACM/EE/CMS 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.
- ACM/CS/EE/CMS 218. Statistical Inference. 12 units (3-0-9); second term. Prerequisites: ACM/CMS 104, ACM/CMS 113, and ACM/EE/CMS 116; or instructor's permission. Fundamentals of estimation theory and hypothesis testing; Bayesian and non-Bayesian approaches; minimax analysis, Cramer-Rao bounds, shrinkage in high dimensions; Kalman filtering, basics of graphical models; statistical model selection. Throughout the course, a computational viewpoint will be emphasized.
- CMS 290abc. Computing & Mathematical Sciences Colloquium. 1 unit (1-0-0); first, second, and third term. Registration open to Graduate Students only. This course is a research seminar covering topics at the intersection of mathematics, computation, and their applications. Speakers are internationally recognized researchers from mathematics, applied mathematics, statistics, computer science, electrical engineering, control theory, and related disciplines. Attendance is required.
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 ab or CDS 140 ab (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 101. Design and Analysis of Feedback Systems. 6 units (2-0-4); first term. Prerequisites: Ma 1 and Ma 2 or equivalent. An introduction to feedback and control in physical, biological, engineering, and information sciences. Basic principles of feedback and its use as a tool for altering the dynamics of systems and managing uncertainty. Key themes throughout the course will include input/output response, modeling and model reduction, linear vs. nonlinear models, and local vs. global behavior. This course is taught concurrently with CDS 110 a, but is intended for students who are interested primarily in the concepts and tools of control theory and not the analytical techniques for design and synthesis of control systems.
- CDS 110. Introduction to Feedback Control Systems. 12 units (3-0-9) first 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. Control System Design. 9 units (3-0-6); second term. Prerequisite: CDS 110. Optimization-based design of control systems, including optimal control and receding horizon control. Robustness and uncertainty management in feedback systems through stochastic and deterministic methods. Introductory random processes, Kalman filtering, and norms of signals and systems.
- CDS 140. Introduction to Dynamics. 9 units (3-0-6); second term. Prerequisites: Ma 2/102 or equivalent, ACM/CMS 104. Basics topics in dynamics for continuous state systems in continuous and discrete time, using linear and nonlinear differential equations and maps. Topics include equilibria/invariant sets, stability, Lyapunov functions/invariants, attractors and periodic solutions. Introduction to structural stability, bifurcations and eigenvalue crossing conditions.
- CDS 140 ab. Introduction to Dynamics. 9 units (3-0-6); second, third terms. Prerequisite: ACM 95/100 ab or equivalent. Basics topics in dynamics in Euclidean space, including equilibria, stability, Lyapunov functions, periodic solutions, Poincaré-Bendixon theory, Poincaré maps. Attractors and structural stability. Introduction to simple bifurcations and eigenvalue crossing conditions. Discussion of bifurcations in applications, invariant manifolds, the method of averaging and singular perturbation theory. Additional topics may include Hamiltonian and Lagrangian systems.
- ACM/CDS 202. Geometry of Nonlinear Systems. 9 units (3-0-6); second term. Prerequisite: CDS 201 or AM 125 a. Basic differential geometry, oriented toward applications in control and dynamical systems. Topics include smooth manifolds and mappings, tangent and normal bundles. Vector fields and flows. Distributions and Frobenius’s theorem. Matrix Lie groups and Lie algebras. Exterior differential forms, Stokes’ theorem.
- CDS 212. Introduction to Modern Control. 9 units (3-0-6); first term. Prerequisites: ACM 95/100 abc or equivalent; CDS 110 ab or equivalent. Introduction to modern control systems with emphasis on the role of control in overall system analysis and design. Examples drawn from throughout engineering and science. Open versus closed loop control. State-space methods, time and frequency domain, stability and stabilization, realization theory. Time-varying and nonlinear models. Uncertainty and robustness.
- CDS 213. Robust Control. 9 units (3-0-6); third term. Prerequisites: CDS 212, CDS 201. Linear systems, realization theory, time and frequency response, norms and performance, stochastic noise models, robust stability and performance, linear fractional transformations, structured uncertainty, optimal control, model reduction, m analysis and synthesis, real parametric uncertainty, Kharitonov’s theorem, uncertainty modeling.
- CDS 240. Nonlinear Dynamical Systems. 9 units (3-0-6); third term. Prerequisites: CDS 140. Analysis of nonlinear dynamical systems modeled using differential equations, including invariant and center manifolds, bifurcations, limit cycles, regular and singular perturbations, the method of averaging, input/output stability. Additional advanced topics may be included based on student and instructor interests.
- 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 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.