Course Descriptions and Websites

CS 1. Introduction to Computation. 9 units (3-4-2); first term. CS 1 is an introduction to the automated processing of information, including computer programming. This course gives students the conceptual background necessary to understand and construct programs (i.e., specify computations, understand evaluation models, use and understand major constructs, including functions and procedures, scoping and environments, data storage, side-effects, conditionals, recursion and looping, and higher-order functions). CS 1 introduces key issues that arise in computation (e.g., universality, computability, complexity, representation, abstraction management). This course puts the components of computer science in context, serving as an overview for students specializing in computational disciplines and alerting all students to important subtleties that may arise when applying computation in their studies, research, and work. At the end of this course, students should be able to read and write (synthesize, analyze, understand) small programs (100 lines) and have the intellectual framework necessary to rapidly assimilate new computer languages as the need arises. Instructors: Pinkston, Vanier.

CS 2. Introduction to Programming Methods. 9 units (2-4-3); second term. Prerequisite: 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. Instructor: Barr.

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. Instructor: Vanderwaart.

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. Instructors: Farley, Ku, Kechris.

CS 11. Computer Language Shop. 3 units (0-3-0); first, second, third terms. Prerequisite: CS 1 strongly recommended. CS 11 is 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. Lab staff will critique the student’s technique and craftsmanship, offering expert feedback on areas for attention and helping the student with any conceptual difficulties that may arise while mastering the particular language. CS 11 may be repeated for credit of up to a total of 9 units. Instructors: Vanier, Pinkston.

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: CS 2; and CS 21 or CS/EE/Ma 129 a. 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: Vanderwaart.

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

CS 40/140 ab. Programming Laboratory. 9 units (1-8-0); second, third terms. Prerequisite: CS 21 and CS 38, or instructor’s permission. Undergraduates must enroll for CS 40; graduates must enroll for CS 140. This laboratory course is meant to expose students to programming in the large. The lectures cover both object-oriented program design techniques and other methodologies with the goal of demonstrating proper design techniques for large programming projects. These methodologies are then applied to the design and implementation of a significant programming project. This project is of a large enough scale that the students must work in large teams in order to design and implement the system in the two-term course. Throughout the course, students will be expected to present their designs and implementations at scheduled design reviews. The emphasis in the course is not only on achieving the task, but also on properly analyzing the problem space, presenting a clear problem specification, and implementing a modular and a maintainable design. Not offered 2007–08.

CS 47/147. Advanced Object-Oriented Programming.
9 units (3-3-3); first term. Prerequisites: CS 2, and CS 21 and CS 38, or instructor’s permission. Undergraduates must enroll for CS 47; graduates must enroll for CS 147. This course covers the advanced object-oriented programming techniques typically used in large programming projects. Fundamental programming techniques such as object design, inheritance of implementation and/or interface, and polymorphism are also discussed. Other, more advanced, programming concepts covered include smart pointers, garbage collection, object permanence, patterns, and Internet programming. Not offered 2007–08.

EE/CS 51. Principles of Microprocessor Systems.
9 units (3-0-6); second 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); third 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. Instructor: George.

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. Instructor: George.

EE/CS 54. Advanced Microprocessor Projects Laboratory. units (0-9-0) or 12 units (0-12-0) as arranged with the instructor; first, second, third terms. Prerequisite: instructor’s permission. A project laboratory to permit the student to design and build a microprocessor-based system of significant complexity. The student must propose, design, implement, and document a project that uses microprocessors and includes a significant hardware and/or software component. The laboratory is for the experienced student who can work independently and who has taken or has had experience equivalent to EE/CS 53. Instructor: George.

CS/EE/ME 75 abc. Introduction to Multidisciplinary Systems Engineering. 3 units (2-0-1) first term; 3–6 units second term; 12 units (2-9-1) or up to 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. Not offered 2007–08.

EE/CS 80 abc. Senior Thesis. 9 units; first, second, third terms. Prerequisite: instructor’s permission, which should be obtained during the junior year to allow sufficient time for planning the research. Individual research project, carried out under the supervision of a member of the electrical engineering or computer science faculty. Project must include significant design effort. Written report required. Open only to senior electrical engineering, computer science, or electrical and computer engineering majors. Not offered on a pass/fail basis. Instructor: Potter.

CS 81 abc. Undergraduate Laboratory in Computer Science. Units in accordance with work accomplished. Consent of both research adviser and course supervisor required before registering. Supervised experimental research in computer science by undergraduates. Topic must be approved by the supervisor, and a formal final report must be presented on completion of research. Graded pass/fail. Instructor: Staff.

CS 90. Undergraduate Research in Computer Science. Units in accordance with work accomplished. Consent of both research adviser and course supervisor required before registering. Supervised research in computer science by undergraduates. Topic must be approved by the supervisor, and a formal final report must be presented on completion of research. 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 ab. Parallel Algorithms for Scientific Applications. 9 units (3-0-6); second, third terms. Prerequisites: ACM 106 or equivalent. Introduction to parallel program design for numerically intensive scientific applications. First term: parallel programming methods; distributed-memory model with message passing using the message passing interface; shared-memory model with threads using open MP; 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, Lanczos and Arnoldi methods, pseudospectra, CG solvers. Second term: parallel implementations of numerical methods for PDEs, including finite-difference, finite-element, and shock-capturing schemes; particle-based simulations of complex systems. Implementation of adaptive mesh refinement. Grid-based computing, load balancing strategies. Not offered 2007–08.

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. Instructors: Kechris, Caicedo.

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 2007–08.

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. Instructor: Winfree.

ME/CS 132. Advanced Robotics: Navigation and Vision.
9 units (3-6-0); second term. 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. Not offered 2007–08.

CS 134 a. Computing Systems. 9 units (3-3-3); first term. Prerequisite: CS 21 and CS 24 or instructor’s permission. Operating systems, monolithic and microkernels, virtual machines. Naming, memory management, segmentation, paging, and virtual memory. File systems and I/O. Threads, processes, scheduling, locks, semaphores, and mutual exclusion. Security policies, access-control, capabilities, and language-based security. Not offered 2007–08.

CS 134 b. Computing Systems, Compilers, and Languages Laboratory. 12 units (3-6-3); second term. Prerequisite: CS 134 a or instructor’s permission. Programming models and languages for operating systems. Execution environments, storage management, and operating system interfaces. Binding mechanisms, abstraction, optimization, and code generation. Parsing and lexical analysis. Students will build a working compiler. Not offered 2007–08.

CS 134 c. Computing Systems Laboratory. 12 units (3-6-3); third term. Prerequisite: CS 134 b or instructor’s permission. This laboratory class offers students the opportunity for independent work covering recent research in operating systems and programming languages. In coordination with the instructor, students select a laboratory project to be implemented during the term. Not offered 2007–08.

CS 136 abc. Programming Languages Laboratory. 9 units (3-3-3) first term; 12 units (3-6-3) second term; 12 units (2-9-1) third term. Design and analysis of programming languages and compilers. Topics include type systems and type theory, binding mechanisms, control-flow mechanisms, abstraction mechanisms, high-level languages, functional languages, object-oriented languages, logic programming. Advanced interpreter and compiler construction, optimization, native code generation, storage management, execution environments, run-time security, byte-code interpreters and verifiers. Logical frameworks and automated theorem provers. Instructor: Hickey.

CS/EE 137 ab. Electronic Design Automation. 9 units (3-3-3); first, second terms. Prerequisites: basic algorithms and computational theory (CS 138 a, may take CS 138 b concurrently), some exposure to VLSI and/or architecture (CS 181 or CS 184), or instructor’s permission. Formulation, automation, and analysis of design mapping problems, with emphasis on VLSI and computational realizations. Major themes include formulating and abstracting problems, figures of merit (e.g., energy, delay, throughput, area, mapping time), representation, traditional decomposition of flow (logic optimization, covering, scheduling, retiming, assignment, partitioning, placement, routing), and techniques for solving problems (e.g., greedy, dynamic programming, search, [integer] linear programming, graph algorithms, randomization). This is a two-term sequence. The first term will cover the major intellectual ground and present students with a series of contained projects as a chance to exercise their understanding of the material. In the second term, students will work through all the phases of formulation, design, automation, and analysis of some particular automation problem, preferably one that arises in the student’s own research. Not offered 2007–08.

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 2007–08.

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 2007–08.

CS 141 abc. Distributed Computation Laboratory. 9 units (3-3-3); first, second, third 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. Instructor: Chandy. Given in alternate years; offered 2007–08.

CS/EE 145 abc. Networking. 9 units (3-3-3) first, second terms; (0-0-9) third term. Prerequisite: Ma 2 ab; instructor’s permission required for part c. This course introduces the basic mechanisms and protocols in communication networks, and mathematical models for their analysis. Part a covers topics such as digitization, switching, switch design, routing, error control (ARQ), flow control, layering, queuing models, optimization models, basics of protocols in the Internet, wireless networks, and optical networks. Part b covers current research topics in the design, analysis, control, and optimization of networks, protocols, and applications. In part c, students are expected to execute a substantial project in networking, write up a report describing their work, and make a presentation. CS 145 b may be repeated for credit with the instructor’s permission. Instructor: Ho.

EE/CNS/CS 148. 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. Instructor: Perona.

CS 150. Probability and Algorithms. 9 units (3-0-6); second term. Prerequisites: CS 138 a and Ma 5 abc. Elementary randomized algorithms and algebraic bounds in communication, hashing, and identity testing. Game tree evaluation. Topics may include randomized parallel computation; independence, k-wise independence and derandomization; rapidly mixing Markov chains; expander graphs and their applications; clustering algorithms. Instructor: Schulman.

CS 151. Complexity Theory. 9 units (3-0-6); 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. Not offered 2007–08.

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. Instructor: Abu-Mostafa.

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 CS 175 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 175. Geometric Modeling. 9 units (3-3-3); third term. Prerequisite: instructor’s permission. This course will cover both classical and state-of-the-art approaches to geometric modeling as needed in computer-aided geometric design and graphics. Subjects treated include classical splines and their theory and practice (Bernstein Bezier form, de Casteljau algorithm, knot insertion, polar forms and blossoming, degree elevation) as well as more recent approaches based on subdivision (Chaikin’s algorithm, subdivision schemes of Loop, Catmull-Clark, and Butterfly). Both the underlying mathematical theory and its implementation in the form of highly efficient algorithms will be taught. Not offered 2007–08.

CS 176. Introduction to Computer Graphics Research.
9 units (3-3-3); second term. Prerequisite: CS/CNS 171, or 173, or 174, or CS 175. The course will go over recent research results in computer graphics, covering subjects from mesh processing (acquisition, compression, smoothing, parameterization, adaptive meshing), simulation for purposes of animation, rendering (both photo- and nonphotorealistic), geometric modeling primitives (image based, point based), and motion capture and editing. Other subjects may be treated as they appear in the recent literature. The goal of the course is to bring students up to the frontiers of computer graphics research and prepare them for their own research. Instructor: Desbrun.

CS 177. 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. Instructor: Desbrun.

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. Not offered 2007–08.

CS/EE 184 ab. Computer Architecture. 9 units (3-3-3); second, third terms. Prerequisites: CS 21 and CS 24, or instructor’s permission. Organization and design of physical computational systems, basic building blocks for computations, understanding and exploiting structure in computational problems, design space, costs, and trade-offs in computer organization, common machine abstractions, and implementation/optimization techniques. The course will develop the fundamental issues and trade-offs that define computer organizational and architectural styles, including RISC, VLIW, Super Scalar, EPIC, SIMD, Vector, MIMD, reconfigurable, FPGA, PIM, and SoC. Basic topics in the design of computational units, instruction organization, memory systems, control and data flow, interconnect, and the hardware-software abstraction will also be covered. Not offered 2007–08.

CS 185 abc. Asynchronous VLSI Design Laboratory.
9 units (3-3-3); first, second, third terms. Prerequisite: 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. Instructor: Martin. Part c not offered 2007–08.

CNS/Bi/Ph/CS 187. Neural Computation. 9 units (3-0-6); first term. Prerequisite: 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. Instructors: Perona, Winfree.

CNS/CS/EE 188 a. Computation Theory and Neural Systems. 9 units (3-0-6); second term. Prerequisite: Ma 2. Introduction to computational models and methods that are inspired by, and related to, neural systems. Specific topics include computing elementary and symmetric Boolean functions with neural/linear threshold (LT) circuits and AND, OR, NOT (AON) circuits. Computing arithmetic functions with LT circuits and AON circuits, including COMPARISON, ADDITION, PRODUCT, SORTING, and COUNTING. Algebraic techniques and their applications in the construction of minimal weight linear threshold functions. The class includes a project that focuses on creating an interactive Web-based linear threshold calculator. Instructor: Bruck. Not offered 2007–08.

CNS/CS/EE 188 b. Topics in Computation and Biological Systems. 9 units (3-0-6); third term. Prerequisite: CNS/CS/EE 188 a. 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. Instructor: Bruck. Not offered 2007–08.

CS/CNS/Bi 191 ab. Biomolecular Computation.
9 units (3-0-6) second term; (2-4-3) third term. This course investigates computation by molecular systems, emphasizing models of computation based on the underlying physics, chemistry, and organization of biological cells. Topics will be selected from computation by self-assembly, molecular folding, signal transduction, genetic regulatory networks, and transcription; simulation and design of biochemical systems; physical limits of computation, reliability, and the role of noise; reversible computation; DNA-based computers; in vitro evolution; molecular ecosystems. 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. Given in alternate years; not offered 2007–08.

Ph/CS 219 abc. Quantum Computation. 9 units (3-0-6); first, second, third terms. Prerequisite: Ph 129 abc or equivalent. The theory of quantum information and quantum computation. Overview of classical information theory, compression of quantum information, transmission of quantum information through noisy channels, quantum error-correcting codes, quantum cryptography and teleportation. Overview of classical complexity theory, quantum complexity, efficient quantum algorithms, fault-tolerant quantum computation, physical implementations of quantum computation. Not offered 2007–08.

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. Instructors: EAS and HSS faculty.

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 2007–08.

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.

| top |