CS Theory – Theory of Computation
Join Lecture (Tues/Thurs at 3:30pm)

1 Course Overview

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.

1.1 Learning Outcomes

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.

1.2 Eligibility

You should take this course if and only if

  1. You have credit (or passed the placement test) for CS 2110
  2. You have credit for CS 2102

1.2.1 Background

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):

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