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.

Your experience will provide an understanding of:

- Formal definitions of computing and computers
- What
problems

can and cannot be computed according to those definitions (*computability*) - Formal definitons of computational efficiency
- What
problems

can and cannot be computed efficiently according to those definitions (*complexity*) - How theoretical formalisms inspire and are inspired by the practice of computer science.

At the conclusion of this course, a successful student will be able to:

- Write convincing arguments using formal definitions and mathematical reasoning.
- Reason about the differences between finite and infinite models of computation and what they can and cannot compute.
- Express 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.

You should take this course if and only if

- You have credit (or passed the placement test) for CS 2110
- You have credit for CS 2102

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

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

- Sets (CS2102 Sets Primer)
- Functions (Section 4.3 of this text)
- Proof Techniques (CS2102 Proof Techniques)
- Proof Styles, we’ll mostly be using
prose proofs

(CS2102 Proof style guide) - Logic and Notation (CS2102 Glossary of logical terms)
- Java Programming (Java wikibook)

For each of the CS2102 topics, you can view last semester’s lectures for more information