An accelerated introduction to theoretical computer science for students with strong mathematical preparation, to be taken in place of both Computer Science 121 and 124. Algorithm design methods, including graph algorithms, approximation algorithms, and randomized algorithms. Models of computation, computability theory, and computational complexity, including the P vs. NP question.

Big data is data so large that it does not fit in the main memory of a single machine, and the need to process big data by efficient algorithms arises in Internet search, network traffic monitoring, machine learning, scientific computing, signal processing, and several other...

Optimization is the problem of making decisions to maximize or minimize an objective in the presence of complicating constraints. The class will take you on a journey through the theory, methods, and application of linear programming, integer programming, Markov chains, and Markov decision...

Fundamental concepts of information theory, Entropy, Kullback-Leibler divergence, Mutual information; typical sequences and their applications, Loss-less data compression, Huffman codes, Elias Codes, Arithmetic Codes, Discrete Memory-less Channels, Channel Coding and Capacity, Differential...

Plan to attend all of the first class and put the course on your study card immediately. If there are more than 16 applicants, we will give priority to the following:

Current or prospective CS concentrators who plan to take CS 121 and/or 124 and who will take this course instead of CS 20...

This course is an introduction to the theory of computation, teaching: • How to reason precisely about computation and prove mathematical theorems about its capabilities and limitations. • Models of computation. These range from weak but useful models (such as finite-state machines) to...