# Computer Science

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

**CS 2. Introduction to Programming Methods. ***9 units (2-6-1); second term. Prerequisites: CS 1 or equivalent. *CS 2 is a demanding course in programming languages and computer science. Topics covered include data structures, including lists, trees, and graphs; implementation and performance analysis of common algorithms; algorithm design principles, in particular recursion and dynamic programming; concurrency and network programming; basic numerical computation methods. Heavy emphasis is placed on the use of compiled languages and development tools, including source control and debugging. The course includes weekly laboratory exercises and written homework covering the lecture material and program design. The course is intended to establish a foundation for further work in many topics in the computer science option. Instructors: Blank, Desbrun.

**CS 3. Introduction to Software Engineering. ***9 units (2-4-3); third term. Prerequisites: CS 2 or equivalent.* CS 3 is a practical introduction to software engineering with an emphasis on understanding and minimizing risk in large software projects. Students will work in teams on a course-long project. Topics covered include revision control, code reviews, testing and testability, code readability, API design, refactoring, and documentation. The course provides opportunities to present your work to the class, and emphasizes working with other people’s code, both that of classmates and pre-existing frameworks. Not offered 2018–19.

**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. Instructor: Vanier.

**Ma/CS 6/106 abc. Introduction to Discrete Mathematics. ***9 units (3-0-6). *For course description, see Mathematics.

**CS 9. Introduction to Computer Science Research. ***1 unit (1-0-0); first term. *This course will introduce students to research areas in CS through weekly overview talks by Caltech faculty and aimed at first-year undergraduates. More senior students may wish to take the course to gain an understanding of the scope of research in computer science. Graded pass/fail. Instructors: Blank, Ralph.

**EE/CS 10 ab. Introduction to Digital Logic and Embedded Systems.** 6 units (*2-3-1). *For course description, see Electrical Engineering.

**CS 11. Computer Language Lab. ***3 units (0-3-0); first, second, third terms. Prerequisites: CS 1 or instructor’s permission. *A self-paced lab that provides students with extra practice and supervision in transferring their programming skills to a particular programming language. The course can be used for any language of the student’s choosing, subject to approval by the instructor. A series of exercises guide the student through the pragmatic use of the chosen language, building his or her familiarity, experience, and style. More advanced students may propose their own programming project as the target demonstration of their new language skills. This course is available for undergraduate students only. Graduate students should register for CS 111. CS 11 may be repeated for credit of up to a total of nine units. Instructors: Blank, Pinkston, Vanier.

**CS 19 ab. Introduction to Computer Science in Industry. ***2 units (1-0-1); first, second terms. *This course will introduce students to CS in industry through weekly overview talks by alums and engineers in industry. It is aimed at second-year undergraduates. Others may wish to take the course to gain an understanding of the scope of computer science in industry. Additionally students will complete short weekly assignments aimed at preparing them for interactions with industry. This course is closed to first and second term freshman for credit. Graded pass/fail. Instructor: Ralph.

**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. 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. Instructors: Blank, Pinkston.

**CS 37. Algorithms in the Real World. ***9 units (2-6-1); first term. Prerequisites: CS 2, CS 24, Ma 6 or permission from instructor. *This course introduces algorithms in the context of their usage in the real world. The course covers compression, advanced data structures, numerical algorithms, cryptography, computer algebra, and parallelism. The goal of the course is for students to see how to use theoretical algorithms in real-world contexts, focusing both on correctness and the nitty-gritty details and optimizations. Implementations focus on two orthogonal avenues: speed (for which C is used) and algorithmic thinking (for which Python is used). Instructor: Blank.

**CS 38. Algorithms.** *9 units (3-0-6); third term. Prerequisites: CS 2; Ma/CS 6 a or Ma 121 a; and CS 21.* 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 53. Microprocessor Project Laboratory. ***12 units (0-12-0). *For course description, see Electrical Engineering.

**CS/EE/ME 75 abc. Multidisciplinary Systems Engineering. ***3 units (2-0-1), 6 units (2-0-4), or 9 units (2-0-7) first term; 6 units (2-3-1), 9 units (2-6-1), or 12 units (2-9-1) second and third terms; units according to project selected. *This course presents the fundamentals of modern multidisciplinary systems engineering in the context of a substantial design project. Students from a variety of disciplines will conceive, design, implement, and operate a system involving electrical, information, and mechanical engineering components. Specific tools will be provided for setting project goals and objectives, managing interfaces between component subsystems, working in design teams, and tracking progress against tasks. Students will be expected to apply knowledge from other courses at Caltech in designing and implementing specific subsystems. During the first two terms of the course, students will attend project meetings and learn some basic tools for project design, while taking courses in CS, EE, and ME that are related to the course project. During the third term, the entire team will build, document, and demonstrate the course design project, which will differ from year to year. Freshmen must receive permission from the lead instructor to enroll. Instructor: Not offered 2018–19.

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

**HPS/Pl/CS 110. Causation and Explanation. ***9 units (3-0-6). *For course description, see History and Philosophy of Science.

**CS 111. Graduate Programming Practicum. ***3 units (0-3-0); first, second, third terms. Prerequisites: CS 1 or equivalent. *A self-paced lab that provides students with extra practice and supervision in transferring their programming skills to a particular programming language. The course can be used for any language of the student’s choosing, subject to approval by the instructor. A series of exercises guide the student through the pragmatic use of the chosen language, building his or her familiarity, experience, and style. More advanced students may propose their own programming project as the target demonstration of their new language skills. This course is available for graduate students only. Undergraduates should register for CS 11. Not offered 2018–19.

**Ec/ACM/CS 112. Bayesian Statistics. ***9 units (3-0-6). *For course description, see Economics.

**ACM/CS/IDS 114. Parallel Algorithms for Scientific Applications. ***9 units (3-0-6). *For course description, see Applied and Computational Mathematics.

**CS 115. Functional Programming.** *9 units (3-4-2); third term. Prerequisites: CS 1 and CS 4. *This course is a both a theoretical and practical introduction to functional programming, a paradigm which allows programmers to work at an extremely high level of abstraction while simultaneously avoiding large classes of bugs that plague more conventional imperative and object-oriented languages. The course will introduce and use the lazy functional language Haskell exclusively. Topics include: recursion, first-class functions, higher-order functions, algebraic data types, polymorphic types, function composition, point-free style, proving functions correct, lazy evaluation, pattern matching, lexical scoping, type classes, and modules. Some advanced topics such as monad transformers, parser combinators, dynamic typing, and existential types are also covered. Instructor: Vanier.

**CS 116. Reasoning about Program Correctness.** *9 units (3-0-6); first term. 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. Not offered 2018–19.

**Ma/CS 117 abc. Computability Theory. ***9 units (3-0-6). *For course description, see Mathematics.

**CS 118. Logic Model Checking for Formal Software Verification. ***9 units (3-3-3); second term. *An introduction to the theory and practice of logic model checking as an aid in the formal proofs of correctness of concurrent programs and system designs. The specific focus is on automata-theoretic verification. The course includes a study of the theory underlying formal verification, the correctness of programs, and the use of software tools in designs. Instructor: Holzmann.

**EE/CS 119 abc. Advanced Digital Systems Design. ***9 units (3-3-3). *For course description, see Electrical Engineering.

**CS/Ph 120. Quantum Cryptography. ***9 units (3-0-6); first term. Prerequisites: Ma 1b, Ph 2b or Ph 12b, CS 21, CS 38 or equivalent recommended (or instructor’s permission). *This course is an introduction to quantum cryptography: how to use quantum effects, such as quantum entanglement and uncertainty, to implement cryptographic tasks with levels of security that are impossible to achieve classically. The course covers the fundamental ideas of quantum information that form the basis for quantum cryptography, such as entanglement and quantifying quantum knowledge. We will introduce the security definition for quantum key distribution and see protocols and proofs of security for this task. We will also discuss the basics of device-independent quantum cryptography as well as other cryptographic tasks and protocols, such as bit commitment or position-based cryptography. Not offered 2018–19.

**CS/IDS 121. Relational Databases. ***9 units (3-0-6); first term. Prerequisites: CS 1 or equivalent. *Introduction to the basic theory and usage of relational database systems. It covers the relational data model, relational algebra, and the Structured Query Language (SQL). The course introduces the basics of database schema design and covers the entity-relationship model, functional dependency analysis, and normal forms. Additional topics include other query languages based on the relational calculi, data-warehousing and dimensional analysis, writing and using stored procedures, working with hierarchies and graphs within relational databases, and an overview of transaction processing and query evaluation. Extensive hands-on work with SQL databases. Instructor: Pinkston.

**CS/IDS 122. Database System Implementation. ***9 units (3-3-3); second term. Prerequisites: CS 2, CS 38, CS/IDS 121 and familiarity with Java, or instructor’s permission. *This course explores the theory, algorithms, and approaches behind modern relational database systems. Topics include file storage formats, query planning and optimization, query evaluation, indexes, transaction processing, concurrency control, and recovery. Assignments consist of a series of programming projects extending a working relational database, giving hands-on experience with the topics covered in class. The course also has a strong focus on proper software engineering practices, including version control, testing, and documentation. Instructor: Pinkston.

**CS 123. Projects in Database Systems. ***9 units (0-0-9); third term. Prerequisites: CS/IDS 121 and CS/IDS 122. *Students are expected to execute a substantial project in databases, write up a report describing their work, and make a presentation. Instructor: Pinkston.

**CS 124. Operating Systems. ***12 units (3-6-3); first term. Prerequisites: CS 24. *This course explores the major themes and components of modern operating systems, such as kernel architectures, the process abstraction and process scheduling, system calls, concurrency within the OS, virtual memory management, and file systems. Students must work in groups to complete a series of challenging programming projects, implementing major components of an instructional operating system. Most programming is in C, although some IA32 assembly language programming is also necessary. Familiarity with the material in CS 24 is strongly advised before attempting this course. Instructor: Pinkston.

EE**/CS/MedE 125. Digital Electronics and Design with FPGAs and VHDL. ***9 units (3-6-0). *For course description, see Electrical Engineering.

**EE/Ma/CS 126 ab. Information Theory. ***9 units (3-0-6); first, second terms. Prerequisites: Ma 3. *For course description, see Electrical Engineering.

**EE/Ma/CS/IDS 127. Error-Correcting Codes. ***9 units (3-0-6). *For course description, see Electrical Engineering.

**CS 131. Programming Languages.** *9 units (3-0-6); third term. Prerequisites: CS 4.* CS 131 is a course on programming languages and their implementation. It teaches students how to program in a number of simplified languages representing the major programming paradigms in use today (imperative, object-oriented, and functional). It will also teach students how to build and modify the implementations of these languages. Emphasis will not be on syntax or parsing but on the essential differences in these languages and their implementations. Both dynamically-typed and statically-typed languages will be implemented. Relevant theory will be covered as needed. Implementations will mostly be interpreters, but some features of compilers will be covered if time permits. Enrollment limited to 20 students. Instructor: Vanier.

**ME/CS 133 ab. Robotics.** *9 units (3-6-0); first, second terms.* For course description, see Mechanical Engineering.

**CS/EE/ME 134. Autonomy.** *9 units (3-0-6); third term.* This course covers the basics of autonomy at the intersection of computer vision, machine learning and robotics. It includes selected topics from each of these domains, and their integration points. The lectures will be accompanied by a project that will integrate these ideas on hardware and result in a final demonstration of the concepts studied in the course. Not offered 2018–19.

**EE/CS/EST 135. Power System Analysis. ***9 units (3-3-3); second term. *For course description, see Electrical Engineering.

**EE/Ma/CS/IDS 136. Topics in Information Theory. ***9 units (3-0-6). *For course description, see Electrical Engineering.

**CS 138. Computer Algorithms. ***9 units (3-0-6); third term. Prerequisites: CS 21, or instructor’s permission. *Design and analysis of algorithms. Techniques for problems concerning graphs, flows, number theory, string matching, data compression, geometry, linear algebra and coding theory. Optimization, including linear programming. Randomization. Basic complexity theory and cryptography. Instructor: Schulman.

**CMS/CS/IDS 139. Analysis and Design of Algorithms. ***12 units (3-0-9). *For course description, see Computation and Mathematical Sciences.

**CS 141. Hack Society: Projects from the Public Sector.** *9 units (0-0-9); second term. Prerequisites: CS/IDS 142, 143, CMS/CS/EE/IDS 144, or permission from instructor. *There is a large gap between the public and private sectors’ effective use of technology. This gap presents an opportunity for the development of innovative solutions to problems faced by society. Students will develop technology-based projects that address this gap. Course material will offer an introduction to the design, development, and analysis of digital technology with examples derived from services typically found in the public sector. Instructor: Ralph.

**CS/IDS 142. Distributed Computing. ***9 units (3-0-6); third term. Prerequisites: CS 24, CS 38. *Programming distributed systems. Mechanics for cooperation among concurrent agents. Programming sensor networks and cloud computing applications. Applications of machine learning and statistics by using parallel computers to aggregate and analyze data streams from sensors. Not offered 2018–19.

**CS/EE/IDS 143. Communication Networks. **9* units (3-3-3); first term. Prerequisites: Ma 2, Ma 3, CS 24 and CS 38, or instructor permission. *This course focuses on the link layer (two) through the transport layer (four) of Internet protocols. It has two distinct components, analytical and systems. In the analytical part, after a quick summary of basic mechanisms on the Internet, we will focus on congestion control and explain: (1) How to model congestion control algorithms? (2) Is the model well defined? (3) How to characterize the equilibrium points of the model? (4) How to prove the stability of the equilibrium points? We will study basic results in ordinary differential equations, convex optimization, Lyapunov stability theorems, passivity theorems, gradient descent, contraction mapping, and Nyquist stability theory. We will apply these results to prove equilibrium and stability properties of the congestion control models and explore their practical implications. In the systems part, the students will build a software simulator of Internet routing and congestion control algorithms. The goal is not only to expose students to basic analytical tools that are applicable beyond congestion control, but also to demonstrate in depth the entire process of understanding a physical system, building mathematical models of the system, analyzing the models, exploring the practical implications of the analysis, and using the insights to improve the design. Instructors: Low, Murray, Ralph.

**CMS/CS/EE/IDS 144. Networks: Structure & Economics. ***12 units (3-3-6). *For course description, see Computing and Mathematical Sciences.

**CS/EE 145. Projects in Networking. ***9 units (0-0-9); third term. Prerequisites: Either CMS/CS/EE/IDS 144 or CS/IDS 142 in the preceding term, or instructor permission. *Students are expected to execute a substantial project in networking, write up a report describing their work, and make a presentation. Instructors: Ralph, Wierman.

**CS/EE 146. Advanced Networking. ***9 units (3-3-3); third term. Prerequisites: CS/EE/IDS 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 2018–19.

**EE/CS 147. Digital Ventures Design. **9 units (3-3-3); first term. Prerequisites: none. For course description, see Electrical Engineering.

**EE/CNS/CS 148. Selected Topics in Computational Vision.*** 9 units (3-0-6); third term. *For course description, see Electrical Engineering.

**CS/SS/Ec 149. Algorithmic Economics. ***9 units (3-0-6); second term. *This course will equip students to engage with active research at the intersection of social and information sciences, including: algorithmic game theory and mechanism design; auctions; matching markets; and learning in games. Not offered 2018–19.

**CS/IDS 150. Probability and Algorithms. ***9 units (3-0-6); first 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. Instructors: Schulman.

**CS 151. Complexity Theory.*** 12 units (3-0-9); third term. Prerequisites: CS 21 and CS 38, or instructor’s permission. *This course describes a diverse array of complexity classes that are used to classify problems according to the computational resources (such as time, space, randomness, or parallelism) required for their solution. The course examines problems whose fundamental nature is exposed by this framework, the known relationships between complexity classes, and the numerous open problems in the area. Instructor: Umans.

**CS 152. Introduction to Cryptography. ***12 units (3-0-9); first term. Prerequisites: Ma 1b, CS 21, CS 38 or equivalent recommended. *This course is an introduction to the foundations of cryptography. The first part of the course introduces fundamental constructions in private-key cryptography, including one-way functions, pseudo-random generators and authentication, and in public-key cryptography, including trapdoor one-way functions, collision-resistant hash functions and digital signatures. The second part of the course covers selected topics such as interactive protocols and zero knowledge, the learning with errors problem and homomorphic encryption, and quantum cryptography: quantum money, quantum key distribution. The course is mostly theoretical and requires mathematical maturity. There will be a small programming component. Instructor: Vidick.

**CS/IDS 153. Current Topics in Theoretical Computer Science. ***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. Not offered 2018–19

**CMS/CS/CNS/EE/IDS 155. Machine Learning & Data Mining. ***12 units (3-3-6). *For course description see Computing and Mathematical Sciences.

**CS/CNS/EE 156 ab. Learning Systems. ***9 units (3-0-6); first, third terms. Prerequisites: Ma 2 and CS 2, or equivalent. *Introduction to the theory, algorithms, and applications of automated learning. How much information is needed to learn a task, how much computation is involved, and how it can be accomplished. Special emphasis will be given to unifying the different approaches to the subject coming from statistics, function approximation, optimization, pattern recognition, and neural networks. Instructor: Abu-Mostafa.

**ACM/CS/IDS 157. Statistical Inference. ***9 units (3-2-4). *For course description, see Applied and Computational Mathematics.

**ACM/CS/EE/IDS 158. Mathematical Statistics. ***9 units (3-0-6). *For course description, see Applied and Computational Mathematics.

**CS/CNS/EE/IDS 159. Advanced Topics in Machine Learning.*** 9 units (3-0-6); third term. Prerequisites: CS 155; strong background in statistics, probability theory, algorithms, and linear algebra; background in optimization is a plus as well. *This course focuses on current topics in machine learning research. This is a paper reading course, and students are expected to understand material directly from research articles. Students are also expected to present in class, and to do a final project. Instructor: Yue.

**EE/CS/IDS 160. Fundamentals of Information Transmission and Storage. ***9 units (3-0-6). *For course description, see Electrical Engineering.

**EE/CS 161. Big Data Networks.** *9 units (3-0-6); third term. *For course description, see Electrical Engineering.

**CS/CNS/EE/IDS 165. Foundations of Machine Learning. ***12 units (3-3-6); second term. Prerequisites: Ma 108a, ACM/IDS 104 or CMS/ACM/IDS 107, CMS/ACM/IDS 113, ACM/EE/IDS 116 or CMS/ACM/EE/IDS 117, CMS/CS/CNS/EE/IDS 155 or CMS 156ab, programming experience.* Machine learning is promising to revolutionize every domain. Beyond the media hype, what are the basic foundations? Are the theoretical underpinnings irrelevant given the success of deep learning? What does success even mean? In addition to covering the core concepts, the course aims to ask such critical questions and foster a healthy debate among the students. Assignments will include exploring failure modes of popular algorithms, in addition to traditional problem-solving type questions. The core concepts covered include: linear models, kernel methods, probabilistic models, spectral methods (matrices and tensors), neural networks representation theory, non-convex optimization, generalization in deep neural networks, causality etc. The course assumes students are comfortable with analysis, probability, statistics, and basic programming. Instructor: Anandkumar.

**EE/CS/IDS 167. Introduction to Data Compression and Storage. ***9 units (3-0-6). *For course description, see Electrical Engineering.

**CS/CNS 171. Computer Graphics Laboratory. ***12 units (3-6-3); first term. Prerequisites: Extensive programming experience and proficiency in linear algebra, starting with CS2 and Ma1b. *This is a challenging course that introduces the basic ideas behind computer graphics and some of its fundamental algorithms. Topics include graphics input and output, the graphics pipeline, sampling and image manipulation, three-dimensional transformations and interactive modeling, basics of physically based modeling and animation, simple shading models and their hardware implementation, and some of the fundamental algorithms of scientific visualization. Students will be required to perform significant implementations. Instructor: Barr.

**CS/CNS 174. Computer Graphics Projects.** *12 units (3-6-3); third term. Prerequisites: Extensive programming experience, CS/CNS 171 or instructor’s permission. *This laboratory class offers students an opportunity for independent work including recent computer graphics research. In coordination with the instructor, students select a computer graphics modeling, rendering, interaction, or related algorithm and implement it. Students are required to present their work in class and discuss the results of their implementation and possible improvements to the basic methods. May be repeated for credit with instructor’s permission. Instructor: Barr.

**EE/CS/MedE 175. Digital Circuits Analysis and Design with Complete VHDL and RTL Approach. ***9 units (3-6-0). *For course description, see Electrical Engineering.

**CS 176. 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 2018–19.

**CS/ACM 177 ab. Discrete Differential Geometry: Theory and Applications. ***9 units (3-3-3); second, third terms. Working knowledge of multivariate calculus and linear algebra as well as fluency in some implementation language is expected.* Subject matter covered: differential geometry of curves and surfaces, classical exterior calculus, discrete exterior calculus, sampling and reconstruction of differential forms, low dimensional algebraic and computational topology, Morse theory, Noether’s theorem, Helmholtz-Hodge decomposition, structure preserving time integration, connections and their curvatures on complex line bundles. Applications include elastica and rods, surface parameterization, conformal surface deformations, computation of geodesics, tangent vector field design, connections, discrete thin shells, fluids, electromagnetism, and elasticity. Instructor: Schröder.

**CS/IDS 178. Numerical Algorithms and their Implementation. ***9 units (3-3-3); second term. Prerequisites: CS 2. *This course gives students the understanding necessary to choose and implement basic numerical algorithms as needed in everyday programming practice. Concepts include: sources of numerical error, stability, convergence, ill-conditioning, and efficiency. Algorithms covered include solution of linear systems (direct and iterative methods), orthogonalization, SVD, interpolation and approximation, numerical integration, solution of ODEs and PDEs, transform methods (Fourier, Wavelet), and low rank approximation such as multipole expansions Instructor: Desbrun.

**CS 179. GPU Programming. ***9 units (3-3-3); third term. Prerequisites: Good working knowledge of C/C++. Some experience with computer graphics algorithms preferred.* The use of Graphics Processing Units for computer graphics rendering is well known, but their power for general parallel computation is only recently being explored. Parallel algorithms running on GPUs can often achieve up to 100x speedup over similar CPU algorithms. This course covers programming techniques for the Graphics processing unit, focusing on visualization and simulation of various systems. Labs will cover specific applications in graphics, mechanics, and signal processing. The course will use nVidia’s parallel computing architecture, CUDA. Labwork requires extensive programming. Instructor: Barr

**CS 180. Master’s Thesis Research. ***Units (total of 45) are determined in accordance with work accomplished. *

**Bi/BE/CS 183. Introduction to Computational Biology and Bioinformatics. **9 units (3-0-6). For course description, see Biology.

**CNS/Bi/EE/CS/NB 186. Vision: From Computational Theory to Neuronal Mechanisms. ***12 units (4-4-4). *For course description, see Computation and Neural Systems.

**CNS/Bi/Ph/CS/NB 187. Neural Computation. ***9 units (3-0-6). *For course description, see Computation and Neural Systems.

**BE/CS/CNS/Bi 191 ab. Biomolecular Computation. ***9 units (3-0-6). *For course description, see Bioengineering.

**BE/CS 196 ab. Design and Construction of Programmable Molecular Systems. ***12 units ; a (3-6-3) second term; b (2-8-2). *For course description, see Bioengineering.

**Ph/CS 219 abc. Quantum Computation. ***9 units (3-0-6); first, second, third terms. *For course description, see Physics.

**SS/CS 241. Topics in Algorithmic Economics. ***9 units (3-0-6). *For course description, see Social Science.

**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. Not offered 2018–19.

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