Computer Science (CS) Courses (2024-25)
Ma/CS 6/106 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: syntax and semantics of propositional and first-order logic. Introduction to the Godel completeness and incompleteness theorems. Elements of computability theory and computational complexity. Discussion of the P=NP problem.
Instructors: T. Yu, Babecki, Ervin.
Ma/CS 117 abc.
Computability Theory.
9 units (3-0-6):
first, second 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 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.
Part c not offered 2024-25.
Instructor: Ervin.
CS/Ph 120.
Quantum Cryptography.
9 units (3-0-6):
first term.
Prerequisites: Ma 1 b, Ph 2 b or Ph 12 b, 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 2024-25.
Instructor: Staff.
EE/Ma/CS 126 ab.
Information Theory.
9 units (3-0-6):
first, second terms.
Prerequisites: Ma 3.
This class treats Shannon's mathematical theory of communication and the tools used to derive and understand it. The class is organized around fundamental questions and their solutions, leading to central results such as Shannon's source coding, channel coding, and rate-distortion theorems. Quantities that arise en route to these solutions include entropy, relative entropy, and mutual information for discrete and continuous random variables. The course explores the calculation of fundamental communication limits like entropy rate, capacity, and rate-distortion functions under a variety of source and communication channel models (e.g., memoryless, Markov, ergodic, and Gaussian). The course begins with a foundational discussion of the simplest communication scenarios and then expands to include topics like universal source coding, the role of side information in source coding and communications, and the generalization of earlier results to network systems. Network information theory topics include multiuser data compression and communication over multiple access channels, broadcast channels, and multiterminal networks. Philosophical and practical implications of the theory are also explored. This course, when combined with EE 112, EE/Ma/CS/IDS 127, EE/CS 161, and EE/CS/IDS 167, should prepare the student for research in information theory, coding theory, wireless communications, and/or data compression.
Part b not offered 2024-25
Instructor: Effros.
EE/Ma/CS/IDS 127.
Error-Correcting Codes.
9 units (3-0-6):
third term.
Prerequisites: EE 55 or equivalent.
This course develops from first principles the theory and practical implementation of the most important techniques for combating errors in digital transmission and storage systems. Topics include highly symmetric linear codes, such as Hamming, Reed-Muller, and Polar codes; algebraic block codes, such as Reed-Solomon and BCH codes, including a self-contained introduction to the theory of finite fields; and low-density parity-check codes. Students will become acquainted with encoding and decoding algorithms, design principles and performance evaluation of codes.
not offered 2024-25.
Instructor: Kostina.
EE/Ma/CS/IDS 136.
Information Theory and Applications.
9 units (3-0-6):
third term.
Prerequisites: EE 55 or equivalent.
This class introduces information measures such as entropy, information divergence, mutual information, information density, and establishes the fundamental importance of those measures in data compression, statistical inference, and error control. The course does not require a prior exposure to information theory; it is complementary to EE 126a.
Instructor: Kostina.
CNS/Bi/Ph/CS/NB 187.
Neural Computation.
9 units (3-0-6):
third term.
Prerequisites: introductory neuroscience (Bi 150 or equivalent); mathematical methods (Bi 195 or equivalent); scientific programming.
This course aims at a quantitative understanding of how the nervous system computes. The goal is to link phenomena across scales from membrane proteins to cells, circuits, brain systems, and behavior. We will learn how to formulate these connections in terms of mathematical models, how to test these models experimentally, and how to interpret experimental data quantitatively. The concepts will be developed with motivation from some of the fascinating phenomena of animal behavior, such as: aerobatic control of insect flight, precise localization of sounds, sensing of single photons, reliable navigation and homing, rapid decision-making during escape, one-shot learning, and large-capacity recognition memory.
Not offered 2024-25.
Instructor: Meister.
Ph/CS 219 abc.
Quantum Computation.
9 units (3-0-6):
first, second, third terms.
Prerequisites: Ph 125 ab 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.
Instructors: Kitaev, Preskill.