UVA CS 3120 Theory of Computation (Wei-Kai Lin)

This is the course website of CS 3120 (also called Discrete Mathematics and Theory 2), instructed by Prof. Lin. The meetings are Tuesdays and Thursdays at 9:30 - 10:45pm Spring 2026 and in Olsson 120.

Another section of the same course: Prof. Pettit also teaches this course in this Spring 2026. The two sections use different textbooks and proceed with slightly different topics although the overall goals are similar. The workload of this section shall be similar to the other section, but it is up to the staff’s discretion.

Recent Announcements

Class 4: Cantor’s Theorem, Finite Automata

(Jan 27, 2026)

We proved Cantor’s Theorem, and then we introduced finite automata as the beginning of the next module. Slides are here. Quiz 2 is posted on Gradescope.

Class 3: Infinity

(Jan 22, 2026)

We defined Infinity, countable, and showed there are uncountable sets. Slides are here. Quiz 1 is posted on Gradescope. Homework 1 is posted.

We skipped a proof of the following theorem. Here is it.

Theorem: If a set \(S\) is countably infinite, then \(\card{S} = \card{\N}\).

  1. We will prove that \(\card{S} \le \card{\N}\) and \(\card{S} \ge \card{\N}\) holds, which implies \(\card{S} = \card{\N}\) by (Cantor-)Schröder–Bernstein Theorem.
  2. We have \(\card{S} \le \card{\N}\) by \(S\) is countable.
  3. It remains to prove that \(\card{S} \ge \card{\N}\). That is, we want to show a surjective function \(g: S \to \N\). Such \(g\) is constructed (or described) below.
    1. By \(S\) is Dedekind infinite, there exists a strict subset \(T\subsetneq S\) such that \(\card{S} = \card{T}\).
    2. By \(\card{S} = \card{T}\), there is a bijection \(f: S \to T\).
    3. Let \(U_0 = S\), and let \(U_i = \{f(x) \mid x \in U_{i-1} \}\) for all natural numbers \(i > 0\). That is, \(U_i\) is the set of elements that are mapped from \(U_{i-1}\) by \(f\). Note that \(U_1 = T\).
    4. By strict subset, there exists \(a_0 \in T, a_0 \notin S\).
    5. Let \(a_i = f(a_{i-1})\) for all natural numbers \(i > 0\). We have \(a_i \in U_i\) for all \(i \in \N\) by definition of \(U_i\) and \(a_i\) (an induction is needed to be strictly formal).
    6. Let \(g\) to be the partial function that maps \(a_i\) to \(i\) (there may exists an element in \(S\) that is not mapped to anything, so it is partial). This is the construction of \(g\)
  4. It remains to argue \(g\) is surjective.
  5. Clearly, each \(i\in\N\) is mapped from (or receives) exactly one element in \(S\).
  6. We want to argue that \(a_i \neq a_j\) for all \(i\neq j\), which implies that each element in \(S\) is mapped to at most one natural number and that \(g\) is surjective.
  7. We claim that \(a_i \notin U_{i+1}\) for all \(i \in \N\).
  8. Because \(U_{j+1}\subseteq U_j\) for all \(j\in\N\), the claim implies \(a_i \notin U_j\) for all \(i < j\).
  9. Given that \(a_j \in U_j\), the claim implies \(a_i \neq a_j\) for all \(i < j\).
    1. To prove the claim, assume for contradiction, there exists \(a_i \in U_{i+1}\) for some \(i\) (for some \(S\), bijection \(f\), element \(a_0\)). Let \(k\) be the smallest natural number satisfying such Property.
    2. We have \(k > 0\) as \(a_0 \notin U_1\).
    3. Since \(f\) is a bijection, we have a unique \(f^{-1}(a_k) = a_{k-1}\).
    4. Since \(f\) is a bijection and \(f\) maps from \(U_k\) to \(U_{k+1}\), \(f\) is also a bijection between \(U_k\) and \(U_{k+1}\).
    5. By \(a_k \in U_{k+1}\) and \(f\) is bijective between \(U_k\) and \(U_{k+1}\), we have \(f^{-1}(a_k) \in U_k\).
    6. But \(f^{-1}(a_k) = a_{k-1} \in U_k\) means \(k-1\) also satisfy the Property, contradicting that $k$ is the smallest. This concludes the claim and the theorem.

Class 2: Cardinality

(Jan 20, 2026)

We talked about why study theory, infinite binary strings, and cardinality. Slides are here. Quiz 1 is coming in 24 hours.

Class 1: Definitions

(Jan 15, 2026)

We talked about constructive definitions, natural numbers, binary strings, and sets. Slides are here. Homework 0 is [posted](

https://colab.research.google.com/drive/1F4idQXXtNHKJ1MWNKlg4U66Z2o1YgK1f?usp=sharing), which shall be submitted to Gradescope.

Class 0: Goals and grading

(Jan 13, 2026)

We talked about Karatsuba’s multiplication and grading. Slides are here. Quiz 0 is posted on Gradescope.

Tentative syllabus posted

(Jan 9, 2026)

Please take a look at the syllabus although it could change later.