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 - Fall 2022

CS 435

Introduction to Cryptography

 by Eric Bach
CS 577

Intro to Algorithms

 by Marc Renault
CS 577

Intro to Algorithms Section 3

 by Dieter van Melkebeek
CS 760

Machine Learning

 by Ilias Diakonikolas
CS 880

Cryptography

 by Rishab Goyal

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 - Fall 2022
Eric Bach - Spring 2019
Nigel Boston - Spring 2014
···

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

Eric Bach - Spring 2022
Eric Bach - Spring 2021
Jin-Yi Cai - Fall 2019
···

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

Marc Renault - Fall 2022
Dieter van Melkebeek - Fall 2022 Section 3
Jin-Yi Cai - Spring 2022 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

Dieter van Melkebeek - Spring 2022
Jin-Yi Cai - Spring 2021
Jin-Yi Cai - Spring 2020
···

CS 760 - Machine Learning

Computational approaches to learning: including inductive inference, explanation-based learning, analogical learning, connectionism, and formal models. What it means to learn. Algorithms for learning. Comparison and evaluation of learning algorithms. Cognitive modeling and relevant psychological results.

Latest Offerings

Ilias Diakonikolas - Fall 2022

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 - Spring 2022
Christos Tzamos - Fall 2020
Christos Tzamos - Fall 2019
···

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 - Fall 2020
Eric Bach - Spring 2020
Eric Bach - Spring 2017
···

CS 880 - Topics in Theoretical Computer Science

Topics vary per semester

Latest Offerings

Cryptography - Rishab Goyal - Fall 2022
Complexity of Counting Problems - Jin-Yi Cai - Fall 2021
Quantum Computing - Dieter van Melkebeek - Spring 2021
···

Show Courses Offered by Semester