1 Course Description

The goal of this course is to understand the fundamental limits on what can be efficiently computed in our universe and other possible (or imaginary) universes. These limits reveal deep and mysterious properties about information, communication, and computing, as well as practical issues about how to solve problems.

Two fundamental questions about any problem are:

Can it be solved using a machine of a certain type? (computability)
How much does it cost to solve it? (complexity)

We explore these questions by developing abstract models of computing machines and reasoning about what they can and cannot compute efficiently. We will also look at some applications in cryptography that take advantage of problems being hard to solve, and what can be done when a problem cannot be solved or is too expensive to solve.

2 Course Objectives

Students who complete the course will:

Improve their mathematical thinking skill and habits, including thinking precisely about definitions, stating assumptions carefully, critically reading arguments, and being able to write convincingly.
Be able to understand both finite and infinite formal models of computation and to reason about what they can and cannot compute.
Understand both intuitively and formally what makes some problems too expensive to solve, and what can be done in practice when an unsolvable or intractable problem is encountered.
Reason formally about the cost of computation, and be able to prove useful bounds on the costs of solving problems, including showing that certain problems are intractable.
Learn about some interesting aspects of theoretical computer science, including cryptography and machine learning.

2.1 Eligibility

Official Prerequisites: CS 2102/2120 and CS 2110/2100 (or comparable courses) with grades of at least a C- (if taken for a grade) or CR (if taken using the COVID Credit/No Credit option).

2.2 Background

This course will assume knowledge of several topics from discrete math (CS2102 or CS2120 at UVA), and object-oriented Java programming (taught in CS2110 or CS2100 at UVA).

In particular, we assume knowledge of (with recommended resources for review):

Sets (CS2120 Sets Primer)
Functions (Section 4.3 of this text)
Proof Techniques (CS2120 Proof Techniques)
Proof Styles, we’ll mostly be using prose proofs (CS2120 Proof style guide)
Logic and Notation (CS2120 Glossary of logical terms)
Recursion (CS2100 Recursion Slides)

For each of the Discrete Math topics, you can view the Fall 2019 lectures for more information