Undergraduate / Computer Science Major (BS/BA) / CS Core, Breadth, and Depth RequirementsCS Depth: Theory
The courses below fulfill the Depth: Theory requirement in computer science.
Introduction to numerical methods; numerical differentiation, numerical integration, solution of ordinary and partial differential equations. Students write programs in C++, FORTRAN, C, or Matlab using methods presented in class.
This course gives an introduction to the mathematical foundations of computation. The course will look at Turing machines, universal computation, the Church-Turing thesis, the halting problem and general undecidability, Rice’s theorem, the recursion theorem, efficient computation models, time and space (memory) bounds, deterministic and nondeterministic computation and their relationships, the P versus NP problem and hard problems for NP and beyond. Note: This course will replace Math 374 (Theory of Computability and Turing Machines) which is listed as a recommended way to fulfill the undergraduate theory breadth requirement in CS but hasn’t been taught in several years. The Math department is happy to give it up.
Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study optimization. This course provides an introduction to algorithm design through a survey of the common algorithm design paradigms of greedy optimization, divide and conquer, dynamic programming, network flows, reductions, and randomized algorithms. Important themes that will be developed in the course include the algorithmic abstraction-design-analysis process and computational tractability (e.g., NP-completeness).
Basic concepts in VLSI CAD with emphasis on physical design, fundamental algorithms for CAD problems, development of CAD tools.
This course explains applications of probability in electrical engineering and computer science: PageRank, multiplexing, digital link, tracking, speech recognition, and more. Topics include Markov chains, detection, coding, estimation, Viterbi algorithm, Kalman filter, Markov decision problems, LQG, and channel capacity. Matlab examples are used to simulate models and to implement the algorithms. The necessary concepts from basic probability and linear algebra are reviewed.
Information measures and their properties: entropy, divergence, mutual information, channel capacity. Shannon's fundamental theorems for data compression and coding for noisy channels. Applications in communications, statistical inference, probability, physics. Prerequisites by course: EECS 302 (Probabilities Systems and Random Signals). Prerequisites by topic: Good understanding of basic probability. (A review of probability theory will be given in Week 1.) This course fulfills the Theory Depth requirement.
Design and analysis of advanced algorithms: graph algorithms; maximal network flows; min-cost flow algorithms; convex cost flows.
Introduction to advanced topics in synthesis and modeling of complex VLSI systems at behavioral and logic level. Topics include resource allocation, resource binding, scheduling, and controller design in high level synthesis, C to hardware compilation flows, logic synthesis, survey of stat-of-the-art in high level and system level design methods and tools.
Mechanisms mediate the strategic interaction between individuals within computer systems and beyond. Participants in such a system may have an interest in the outcome of the system and may interact strategically so as to obtain a more desired outcome. Importantly the rules of these systems, which specify how the system outcome (output) is obtained from the actions (input) of participants of the system, must be carefully designed so that desirable outcomes are obtained even if participants strategize whenever it is in their interest. This class combines the fields of algorithms and microeconomics to give a theory of mechanism design. A central theme will be the tradeoff between optimality and other desirable properties such as simplicity, robustness, computational tractability, and practicality. This tradeoff will be quantified by a theory of approximation which measures the loss of performance of a simple, robust, and practical approximation mechanism in comparison to the complicated, delicate, and impractical optimal mechanism.