2012-13 Catalog | Caltech Academic Catalog

CS 1

Introduction to Computer Programming

9 units (3-4-2) | first term

A course on computer programming emphasizing the program design process and pragmatic programming skills. It will use the Python programming language and will not assume previous programming experience. Material covered will include data types, variables, assignment, control structures, functions, scoping, compound data, string processing, modules, basic input/output (terminal and file), as well as more advanced topics such as recursion, exception handling and object-oriented programming. Program development and maintenance skills including debugging, testing, and documentation will also be taught. Assignments will include problems drawn from fields such as graphics, numerics, networking, and games. At the end of the course, students will be ready to learn other programming languages in courses such as CS 11, and will also be ready to take more in-depth courses such as CS 2 and CS 4.

Instructor: Vanier

CS 2

Introduction to Programming Methods

9 units (2-4-3) | second term

Prerequisites: CS 1 or equivalent.

CS 2 is a challenging course in programming languages and computer science, emphasizing modes of algorithmic expression. The course will include such topics as performance analysis of algorithms; proofs of program correctness; recursive and higher-order procedures; data structures, including lists, trees, graphs, and arrays; objects and abstract data types. The course includes weekly laboratory exercises and written homework covering the lecture material and program design.

Instructors: Barr, Desbrun

CS 3

Introduction to Software Engineering

9 units (2-4-3) | third term

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

Instructor: Staff

CS 4

Fundamentals of Computer Programming

9 units (3-4-2) | second term

Prerequisites: CS 1 or instructor's permission.

This course gives students the conceptual background necessary to construct and analyze programs, which includes specifying computations, understanding evaluation models, and using major programming language constructs (functions and procedures, conditionals, recursion and looping, scoping and environments, compound data, side effects, higher-order functions and functional programming, and object-oriented programming). It emphasizes key issues that arise in programming and in computation in general, including time and space complexity, choice of data representation, and abstraction management. This course is intended for students with some programming background who want a deeper understanding of the conceptual issues involved in computer programming.

Instructor: Vanier

Ma/CS 6 abc

Introduction to Discrete Mathematics

9 units (3-0-6) | first, second, third terms

Prerequisites: for Ma/CS 6 c, Ma/CS 6 a or Ma 5 a or instructor's permission.

First term: a survey emphasizing graph theory, algorithms, and applications of algebraic structures. Graphs: paths, trees, circuits, breadth-first and depth-first searches, colorings, matchings. Enumeration techniques; formal power series; combinatorial interpretations. Topics from coding and cryptography, including Hamming codes and RSA. Second term: directed graphs; networks; combinatorial optimization; linear programming. Permutation groups; counting nonisomorphic structures. Topics from extremal graph and set theory, and partially ordered sets. Third term: elements of computability theory and computational complexity. Discussion of the P=NP problem, syntax and semantics of propositional and first-order logic. Introduction to the Godel completeness and incompleteness theorems.

Instructors: Omar, Wilson, Williams

CS 9

Introduction to Computer Science Research

1 unit (1-0-0) | first term

This course will introduce the research areas of the computer science faculty, through weekly overview talks by the faculty aimed at first-year undergraduates. Others may wish to take the course to gain an understanding of the scope of the field. Graded pass/fail.

Instructor: Umans

CS 11

Computer Language Shop

3 units (0-3-0) | first, second, third terms

Prerequisites: CS 1 or instructor's permission.

A self-paced lab that provides students with extra practice and supervision in transferring their programming skills to a particular programming language; the course can be used for any language of the student's choosing, subject to approval by the instructor. A series of exercises guide the student through the pragmatic use of the chosen language, building his or her familiarity, experience, and style. More advanced students may propose their own programming project as the target demonstration of their new language skills. CS 11 may be repeated for credit of up to a total of nine units.

Instructors: Pinkston, Vanier

CS 21

Decidability and Tractability

9 units (3-0-6) | second term

Prerequisites: CS 2 (may be taken concurrently).

This course introduces the formal foundations of computer science, the fundamental limits of computation, and the limits of efficient computation. Topics will include automata and Turing machines, decidability and undecidability, reductions between computational problems, and the theory of NP-completeness.

Instructor: Umans

CS 24

Introduction to Computing Systems

9 units (3-3-3) | third term

Prerequisites: Familiarity with C equivalent to having taken the CS 11 C track.

Basic introduction to computer systems, including hardware-software interface, computer architecture, and operating systems. Course emphasizes computer system abstractions and the hardware and software techniques necessary to support them, including virtualization (e.g., memory, processing, communication), dynamic resource management, and common-case optimization, isolation, and naming.

Instructor: Pinkston

CS 38

Introduction to Algorithms

9 units (3-0-6) | third term

Prerequisites: CS 2; Ma/CS 6 a or Ma 121 a; and CS 21 or CS/EE/Ma 129 a.

This course introduces techniques for the design and analysis of efficient algorithms. Major design techniques (the greedy approach, divide and conquer, dynamic programming, linear programming) will be introduced through a variety of algebraic, graph, and optimization problems. Methods for identifying intractability (via NP-completeness) will be discussed.

Instructor: Schulman

EE/CS 51

Principles of Microprocessor Systems

12 units (4-5-3) | first term

The principles and design of microprocessor-based computer systems. Lectures cover both hardware and software aspects of microprocessor system design such as interfacing to input and output devices, user interface design, real-time systems, and table-driven software. The homework emphasis is on software development, especially interfacing with hardware, in assembly language.

Instructor: George

EE/CS 52

Microprocessor Systems Laboratory

12 units (1-11-0) | second term

Prerequisites: EE/CS 51 or equivalent.

The student will design, build, and program a specified microprocessor-based system. This structured laboratory is organized to familiarize the student with electronic circuit construction techniques, modern development facilities, and standard design techniques. The lectures cover topics in microprocessor system design such as display technologies, interfacing with analog systems, and programming microprocessors in high-level languages.

Instructor: George

EE/CS 53

Microprocessor Project Laboratory

12 units (0-12-0) | first, second, third terms

Prerequisites: EE/CS 52 or equivalent.

A project laboratory to permit the student to select, design, and build a microprocessor-based system. The student is expected to take a project from proposal through design and implementation (possibly including PCB fabrication) to final review and documentation. May be repeated for credit.

Instructor: George

CS/EE/ME 75 abc

Introduction to Multidisciplinary Systems Engineering

3 units (2-0-1) , 6 units (2-0-4), or 9 units (2-0-7) first term; 6 units (2-3-1), 9 units (2-6-1), or 12 units (2-9-1) second term | 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.

Instructors: Hunt, Atwater, Murray

CS 80 abc

Undergraduate Thesis

9 units | first, second, third terms

Prerequisites: instructor's permission, which should be obtained sufficiently early to allow time for planning the research.

Individual research project, carried out under the supervision of a member of the computer science faculty (or other faculty as approved by the computer science undergraduate option representative). Projects must include significant design effort. Written report required. Open only to upperclass students. Not offered on a pass/fail basis.

Instructor: Staff

CS 81 abc

Undergraduate Projects in Computer Science

Units are assigned in accordance with work accomplished

Prerequisites: Consent of supervisor is required before registering.

Supervised research or development in computer science by undergraduates. The topic must be approved by the project supervisor, and a formal final report must be presented on completion of research. This course can (with approval) be used to satisfy the project requirement for the CS major. Graded pass/fail.

Instructor: Staff

CS 90

Undergraduate Reading in Computer Science

Units are assigned in accordance with work accomplished

Prerequisites: Consent of supervisor is required before registering.

Supervised reading in computer science by undergraduates. The topic must be approved by the reading supervisor, and a formal final report must be presented on completion of the term. Graded pass/fail.

Instructor: Staff

CS 101 abc

Special Topics in Computer Science

Units in accordance with work accomplished | offered by announcement

Prerequisites: CS 21 and CS 38, or instructor's permission.

The topics covered vary from year to year, depending on the students and staff. Primarily for undergraduates.

CS 102 abc

Seminar in Computer Science

3, 6, or 9 units as arranged with the instructor. 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. Not offered 2012-13.

CS 116

Reasoning about Program Correctness

9 units (3-0-6) | first term

Prerequisites: CS 1 or equivalent.

This course presents the use of logic and formal reasoning to prove the correctness of sequential and concurrent programs. Topics in logic include propositional logic, basics of first-order logic, and the use of logic notations for specifying programs. The course presents a programming notation and its formal semantics, Hoare logic and its use in proving program correctness, predicate transformers and weakest preconditions, and fixed-point theory and its application to proofs of programs. Not offered 2012-13.

Ma/CS 117 abc

Computability Theory

9 units (3-0-6) | first, second, third terms

Prerequisites: Ma 5 or equivalent, or instructor's permission.

Various approaches to computability theory, e.g., Turing machines, recursive functions, Markov algorithms; proof of their equivalence. Church's thesis. Theory of computable functions and effectively enumerable sets. Decision problems. Undecidable problems: word problems for groups, solvability of Diophantine equations (Hilbert's 10th problem). Relations with mathematical logic and the Godel incompleteness theorems. Decidable problems, from number theory, algebra, combinatorics, and logic. Complexity of decision procedures. Inherently complex problems of exponential and superexponential difficulty. Feasible (polynomial time) computations. Polynomial deterministic vs. nondeterministic algorithms, NP-complete problems and the P = NP question.

Instructors: Kechris, Sokic

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. Not offered 2012-13.

CS 119

Reliable Software: Testing and Monitoring

9 units (3-3-3) | third term

Prerequisites: CS 1 or equivalent; CS 116 and CS 118 are recommended.

The class discusses theoretical and practical aspects of software testing and monitoring. Topics include finite state machine testing algorithms, random testing, constraint-based testing, coverage measures, automated debugging, logics and algorithms for runtime monitoring, and aspect-oriented approaches to monitoring. Emphasis is placed on automation. Students will be expected to develop and use software testing and monitoring tools to develop reliable software systems. Not offered 2012-13.

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.

Instructor: Pinkston

EE/Ma/CS 127

Error-Correcting Codes

9 units (3-0-6) | third 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.

Instructor: Ho

CS/EE/Ma 129 abc

Information and Complexity

9 units (3-0-6), first and second terms | (1-4-4) third term

Prerequisites: basic knowledge of probability and discrete mathematics.

A basic course in information theory and computational complexity with emphasis on fundamental concepts and tools that equip the student for research and provide a foundation for pattern recognition and learning theory. First term: what information is and what computation is; entropy, source coding, Turing machines, uncomputability. Second term: topics in information and complexity; Kolmogorov complexity, channel coding, circuit complexity, NP-completeness. Third term: theoretical and experimental projects on current research topics. Not offered 2012-13.

ME/CS 132 ab

Advanced Robotics: Navigation and Vision

9 units (3-6-0) | first, second terms

Prerequisites: ME 115 ab.

The course focuses on current topics in robotics research in the area of autonomous navigation and vision. Topics will include mobile robots, multilegged walking machines, use of vision in navigation systems. The lectures will be divided between a review of the appropriate analytical techniques and a survey of the current research literature. Course work will focus on an independent research project chosen by the student.

Instructor: Matthies

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 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 functions. Not offered 2012-13.

EE/CS/EST 135

Power System Analysis

9 units (3-0-6) | second term

Prerequisites: EE 44, Ma 2 a, or equivalent..

Phasor representation, 3-phase transmission system, per-phase analysis; power system modeling, transmission line, transformer, generator; network matrix, power flow solution, optimal power flow; Swing equation, stability, protection; demand response, power markets.

Instructor: Low

CS 138 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. Not offered 2012-13.

CS 139 abc

Concurrency in Computation

9 units (3-0-6) | first, second, third terms

Prerequisites: CS 21 and CS 38, or instructor's permission.

Design and verification of concurrent algorithms. Topics: different models of concurrent computations; process synchronization by shared variables and synchronization primitives; distributed processes communicating by message exchange; the concepts of synchronization, indivisible actions, deadlock, and fairness; semantics and correctness proofs; implementation issues; and application to VLSI algorithm design. Parallel machine architecture issues include mapping a parallel algorithm on a network of processors, and classical parallel algorithms and their complexity. Not offered 2012-13.

CS 141 abc

Distributed Computation Laboratory

9 units (3-3-3) | first, second terms

Prerequisites: CS 3, CS 21 and CS 38, or instructor's permission.

This laboratory course deals with the systematic design and implementation of high-confidence scalable networks of communicating objects that discover other objects, configure themselves into collaborating groups of objects, and adapt to their environment. Teams of students explore theories and methods of implementation to obtain predictability and adaptability in distributed systems. Each team of students is expected to submit a research paper at the end of the third term, schedule demonstrations periodically, and maintain documents describing their project status. Part c not offered 2012-13.

Instructor: Chandy

CS/EE 143

Communication Networks

9 units (3-3-3) | first term

Prerequisites: Ma 2 ab, CS 24 and CS 38, or instructor permission.

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.

Instructor: Low

CS/EE 144

Ideas behind the Web

9 units (3-0-6) | second term

Prerequisites: Ma 2 ab, CS 24 and CS 38, or instructor permission.

The Web is an essential part of our lives, and we all depend on it every day, but do you really know what makes it work? This course studies the "big" ideas behind the Web: How do search engines work? How can search engines make so much money from putting ads next to their search results? Are there ways to prevent spammers from accumulating lots of e-mail addresses? What does the Web actually look like? How big is the Web? For all these questions and more, the course will provide a mixture of both mathematical models and real-world, hands-on labs.

Instructor: Wierman

CS/EE 145

Projects in Networking

9 units (0-0-9) | third term

Prerequisites: Either CS/EE 144 or CS 141 b 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.

Instructors: Chandy, Low, Wierman

CS/EE 146

Advanced Networking

9 units (3-3-3) | second term

Prerequisites: CS/EE 143 or instructor's permission.

This is a research-oriented course meant for undergraduates and beginning graduate students who want to learn about current research topics in networks such as the Internet, power networks, social networks, etc. The topics covered in the course will vary, but will be pulled from current research topics in the design, analysis, control, and optimization of networks, protocols, and Internet applications. Usually offered in alternate years. Not offered 2012-13.

CS/EE 147

Network Performance Analysis

9 units (3-0-6) | third term

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

Instructor: Wierman

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. Part a not offered 2012-13; Part b offered 2012-13.

Instructor: Perona

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. Not offered 2012-13.

CS 151

Complexity Theory

12 units (3-0-9) | third term

Prerequisites: CS 21 and CS 38, or instructor's permission.

This course describes a diverse array of complexity classes that are used to classify problems according to the computational resources (such as time, space, randomness, or parallelism) required for their solution. The course examines problems whose fundamental nature is exposed by this framework, the known relationships between complexity classes, and the numerous open problems in the area.

Instructor: Umans

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

Instructor: Schulman

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 unk nown 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. Not offered 2012-13.

CS/CNS/EE 155

Probabilistic Graphical Models

9 units (3-3-3) | second term

Prerequisites: background in algorithms and statistics (CS/CNS/EE 154 or CS/CNS/EE 156 a or instructor's permission).

Many real-world problems in AI, computer vision, robotics, computer systems, computational neuroscience, computational biology, and natural language processing require one to reason about highly uncertain, structured data, and draw global insight from local observations. Probabilistic graphical models allow addressing these challenges in a unified framework. These models generalize approaches such as hidden Markov models and Kalman filters, factor analysis, and Markov random fields. In this course, we will study the problem of learning such models from data, performing inference (both exact and approximate), and using these models for making decisions. The techniques draw from statistics, algorithms, and discrete and convex optimization. The course will be heavily research- oriented, covering current developments such as probabilistic relational models, models for naturally combining logical and probabilistic inference, and nonparametric Bayesian methods. Not offered 2012-13.

CS/CNS/EE 156 ab

Learning Systems

9 units (3-0-6) | first term

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

Instructor: Abu-Mostafa; Part b Not offered 2012-13

CS/CNS/EE 159

Projects in Machine Learning and AI

9 units (0-0-9) | third term

Prerequisites: Two terms from the "Learning & Vision" project sequence.

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. Not offered 2012-13.

CS/CNS 171

Introduction to Computer Graphics Laboratory

12 units (3-6-3) | first term

Prerequisites: Ma 2 and extensive programming experience.

This course introduces the basic ideas behind computer graphics and its fundamental algorithms. Topics include graphics input and output, the graphics pipeline, sampling and image manipulation, three-dimensional transformations and interactive modeling, basics of physically based modeling and animation, simple shading models and their hardware implementation, and fundamental algorithms of scientific visualization. Students will be required to perform significant implementations.

Instructor: Barr

CS/CNS 174

Computer Graphics Projects

12 units (3-6-3) | third term

Prerequisites: Ma 2 and CS/CNS 171 or instructor's permission.

This laboratory class offers students an opportunity for independent work covering recent computer graphics research. In coordination with the instructor, students select a computer graphics modeling, rendering, interaction, or related algorithm and implement it. Students are required to present their work in class and discuss the results of their implementation and any possible improvements to the basic methods. May be repeated for credit with instructor's permission.

Instructor: Barr

CS 176

Introduction to Computer Graphics Research

9 units (3-3-3) | second term

Prerequisites: CS/CNS 171, or 173, or 174.

The course will go over recent research results in computer graphics, covering subjects from mesh processing (acquisition, compression, smoothing, parameterization, adaptive meshing), simulation for purposes of animation, rendering (both photo- and nonphotorealistic), geometric modeling primitives (image based, point based), and motion capture and editing. Other subjects may be treated as they appear in the recent literature. The goal of the course is to bring students up to the frontiers of computer graphics research and prepare them for their own research. Not offered 2012-13.

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.

Instructors: Desbrun, Schroeder

CS 179

GPU Programming

9 units (3-3-3) | third term

Prerequisites: Working knowledge of C. Some experience with computer graphics algorithms preferred, but not required.

The use of Graphics Processing Units for computer graphics rendering is well known, but their power for general parallel computation is only recently being explored. Parallel algorithms running on GPUs can often achieve up to 100x speedup over similar CPU algorithms. This course covers programming techniques for the Graphics processing unit, focusing on visualization and simulation of various systems. Labs will cover specific applications in graphics, mechanics, and signal processing. The course will introduce the OpenGL Shader Language (GLSL) and nVidia's parallel computing architecture, CUDA. Labwork will require extensive programming.

Instructor: Barr

CS 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 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. Part c not offered 2012-13.

Instructor: Martin

CS 185 abc

Asynchronous VLSI Design Laboratory

9 units (3-3-3) | first, second, third terms

Prerequisites: CS 139.

The design of digital integrated circuits whose correct operation is independent of delays in wires and gates. (Such circuits do not use clocks.) Emphasis is placed on high-level synthesis, design by program transformations, and correctness by construction. The first term introduces delay-insensitive design techniques, description of circuits as concurrent programs, circuit compilation, standard-cell layout and other computer-aided design tools, and electrical optimizations. The second term is reserved for advanced topics, and for the presentation and review of mid-size projects, which will be fabricated in CMOS or GaAs technologies, and tested. Not offered 2012-13.

CNS/Bi/EE/CS 186

Vision: From Computational Theory to Neuronal Mechanisms

12 units (4-4-4) | second term

Lecture, laboratory, and project course aimed at understanding visual information processing, in both machines and the mammalian visual system. The course will emphasize an interdisciplinary approach aimed at understanding vision at several levels: computational theory, algorithms, psychophysics, and hardware (i.e., neuroanatomy and neurophysiology of the mammalian visual system). The course will focus on early vision processes, in particular motion analysis, binocular stereo, brightness, color and texture analysis, visual attention and boundary detection. Students will be required to hand in approximately three homework assignments as well as complete one project integrating aspects of mathematical analysis, modeling, physiology, psychophysics, and engineering. Given in alternate years; not offered 2012-13.

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.

Instructor: Perona

CNS/CS/EE 188

Topics in Computation and Biological Systems

9 units (3-0-6) | second term

Prerequisites: 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. Not offered 2012-13.

BE/CS/CNS/Bi 191 ab

Biomolecular Computation

9 units (3-0-6) second term | (2-4-3) third term

Prerequisites: none. Recommended: ChE/BE 163, CS 21, CS 129 ab, or equivalent.

This course investigates computation by molecular systems, emphasizing models of computation based on the underlying physics, chemistry, and organization of biological cells. We will explore programmability, complexity, simulation of and reasoning about abstract models of chemical reaction networks, molecular folding, molecular self-assembly, and molecular motors, with an emphasis on universal architectures for computation, control, and construction within molecular systems. If time permits, we will also discuss biological example systems such as signal transduction, genetic regulatory networks, and the cytoskeleton; physical limits of computation, reversibility, reliability, and the role of noise, DNA-based computers and DNA nanotechnology. Part a develops fundamental results; part b is a reading and research course: classic and current papers will be discussed, and students will do projects on current research topics.

Instructor: Winfree

Ph/CS 219 abc

Quantum Computation

9 units (3-0-6) | first, second terms

Prerequisites: Ph 129 abc or equivalent.

The theory of quantum information and quantum computation. Overview of classical information theory, compression of quantum information, transmission of quantum information through noisy channels, quantum error-correcting codes, quantum cryptography and teleportation. Overview of classical complexity theory, quantum complexity, efficient quantum algorithms, fault-tolerant quantum computation, physical implementations of quantum computation. Not offered 2012-13.

SS/CS 241 ab

Introduction to Social and Information Sciences

9 units (3-0-6); second, third terms | Undergraduates cannot use this course towards fulfilling the core Institute social science requirement

Introduction to techniques and methods used in research at the intersection of social and information sciences: aggregation of dispersed information and optimal allocation of resources through markets, networks, and other social systems; formation and off-equilibrium behavior of these systems; distributed cognition; related computational issues; aggregation, allocation, formation, and equilibration enhancements through technology-hardware and software, economic theory applied to the design of communication networks and computational systems; distributed information systems supporting economic activity. Not offered 2012-13.

Instructor: EAS and HSS faculty

CS/CNS/EE 253

Special Topics in Machine Learning

9 units (3-3-3)

Prerequisites: 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).

Instructor: Staff

CS 274 abc

Topics in Computer Graphics

9 units (3-3-3) | first, second, third terms

Prerequisites: instructor's permission.

Each term will focus on some topic in computer graphics, such as geometric modeling, rendering, animation, human-computer interaction, or mathematical foundations. The topics will vary from year to year. May be repeated for credit with instructor's permission. Not offered 2012-13.

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

Published Date: July 28, 2022