<<<<<<< HEAD ======= >>>>>>> 01f0e34b28f488e71846e1732600bb9224179b9d

1 Course Onboarding Checklist:

  1. Fill out the course registration survey
  2. Join Discord (link in collab)
  3. Get verified on discord by messaging your computing id to Turing
  4. Watch the recording of the first lecture for information on course goals and structure
  5. Begin working on unit 1 by following the unit 1 guide

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

  1. Can it be solved using a machine of a certain type? (computability)
  2. 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.

3 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.

3.1 Eligibility

Official Prerequisites: CS 2102 and CS 2110 (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). (We will waive this prerequisite for students who convince us that they satisfy the expected background below.)

3.2 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