COURSES

List of Theory Courses

The Theory of Computing group offers several regular courses in algorithm design and computational complexity as well as more advanced research oriented topic courses.


Courses

Current Courses Offered - Spring 2020

CS 577

Intro to Algorithms Section 1

by Shuchi Chawla
CS 577

Intro to Algorithms Section 2

by Christos Tzamos
CS 710

Computational Complexity

by Jin-Yi Cai
CS 812

Arithmetic Algorithms

by Eric Bach
CS 880

Quantum Computing

by Dieter van Melkebeek

List of Courses

Undergraduate

CS 240 - Discrete Mathematics

Basic concepts of logic, sets, partial order and other relations, and functions. Basic concepts of mathematics (definitions, proofs, sets, functions, and relations) with a focus on discrete structures: integers, bits, strings, trees, and graphs. Propositional logic, Boolean algebra, and predicate logic. Mathematical induction and recursion. Invariants and algorithmic correctness. Recurrences and asymptotic growth analysis. Fundamentals of counting.

Latest Offerings

Beck Hasti - Fall 2019
Beck Hasti - Fall 2018
Beck Hasti - Fall 2017
···

CS 435 - Introduction to Cryptography

Cryptography is the art and science of transmitting digital information in a secure manner. Provides an introduction to its technical aspects.

Latest Offerings

Eric Bach - Spring 2019
Nigel Boston - Spring 2014
Eric Bach - Spring 2011
···

CS 520 - Theory of Computing

Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.

Latest Offerings

Jin-Yi Cai - Fall 2019
Jin-Yi Cai - Spring 2019
Jin-Yi Cai - Fall 2018
···

CS 577 - Intro to Algorithms

Basic paradigms for the design and analysis of efficient algorithms: greed, divide-and-conquer, dynamic programming, reductions, and the use of randomness. Computational intractability including typical NP-complete problems and ways to deal with them.

Latest Offerings

Shuchi Chawla - Spring 2020 Section 1
Christos Tzamos - Spring 2020 Section 2
Eric Bach - Fall 2019 Section 1
···

CS 578 - Contest-Level Programming

Training in computer programming for competitions: assessing the coding difficulty and complexity of computational problems, recognizing the applicability of known algorithms, fast coding and testing, team work.

Informally offered every fall by Dieter van Melkebeek

Graduate

CS 710 - Computational Complexity

Study of the capabilities and limitations of efficient computation. Relationships between models representing capabilities such as parallelism, randomness, quantum effects, and non-uniformity; and models based on the notions of nondeterminism, alternation, and counting, which capture the complexity of important problems. Knowledge of the theory of computation is strongly encouraged, such as CS 520.

Latest Offerings

Jin-Yi Cai - Spring 2020
Dieter van Melkebeek - Spring 2019
Dieter van Melkebeek - Fall 2017
···

CS 787 - Advanced Algorithms

Advanced paradigms for the design and analysis of efficient algorithms, including the use of randomness, linear programming, and semi-definite programming. Applications to data structures, approximating NP-hard optimization problems, learning, on-line and distributed problems. Students are strongly encouraged to have introductory knowledge of algorithms (e.g., CS 577)

Latest Offerings

Christos Tzamos - Fall 2019
Shuchi Chawla - Spring 2019
Eric Bach - Spring 2018
···

CS 809 - Mathematical Techniques for the Analysis of Algorithms

Techniques for quantitative analysis of algorithms. Charging arguments, amortization, probabilistic methods. Adversary and information lower bounds. Use of methods from combinatorics, complex analysis, and asymptotics in obtaining precise analyses of quicksort, chained hashing, and other algorithms. Students are strongly encouraged to have knowledge of algorithms (e.g., COMP SCI 577) or applied math analysis (e.g., MATH 321) and theory of probability (e.g., MATH/​STAT 431).

Latest Offerings

Eric Bach - Fall 2018
Eric Bach - Spring 2009

CS 812 - Arithmetic Algorithms

Survey of algorithms and design paradigms for exact arithmetic, as used in public-key cryptography, computer algebra, and pseudo-random number generation. Topics include primality testing, factorization of integers and polynomials, discrete logarithms, and (optionally) elliptic curves and integer lattices. Students are strongly encourage to have knowledge of basic abstract algebra (e.g., MATH 541), and intermediate programming ability (e.g., COMP SCI 367 or COMP SCI 300)

Latest Offerings

Eric Bach - Spring 2020
Eric Bach - Spring 2017
Eric Bach - Spring 2014
···

CS 880 - Topics in Theoretical Computer Science

Topics vary per semester

Latest Offerings

Quantum Computing - Dieter van Melkebeek - Spring 2020
Advanced Learning Theory - Ilias Diakonikolas - Fall 2019
Approximation and Online Algorithms - Shuchi Chawla - Fall 2019
···


Show Courses Offered by Semester