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 2024

CS 435

Introduction to Cryptography

 by Rishab Goyal
CS 577

Intro to Algorithms

 by Manolis Vlatakis
CS 577

Intro to Algorithms

 by Sandeep Silwal
CS 577

Intro to Algorithms

 by Marc Renault
CS 639

Introduction to Computational Learning Theory

 by Ilias Diakonikolas
CS 710

Computational Complexity

 by Dieter van Melkebeek
CS 787

Advanced Algorithms

 by Eric Bach
CS 880

Topics in Theoretical Computer Science

 by Jin-Yi Cai

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

Rishab Goyal - Fall 2024
Rishab Goyal - Spring 2023
Eric Bach - Fall 2022
···

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 2023
Eric Bach - Spring 2022
Eric Bach - Spring 2021
···

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

Manolis Vlatakis - Fall 2024
Sandeep Silwal - Fall 2024
Marc Renault - Fall 2024
···

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 - Fall 2024
Jin-Yi Cai - Spring 2024
Dieter van Melkebeek - Spring 2022
···

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

Eric Bach - Fall 2024
Eric Bach - Spring 2023
Christos Tzamos - Spring 2022
···

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

CS 880 - Topics in Theoretical Computer Science

Topics vary per semester

Latest Offerings

Jin-Yi Cai - Fall 2024
Cryptography - Rishab Goyal - Fall 2023
Robust Statistics - Ilias Diakonikolas - Fall 2023
···

Show Courses Offered by Semester