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 12:30 - 1:45pm Spring 2025 and in Rice Hall 130. (Clarification: the course of Prof. Floryan is different.)
Another section of the same course: Prof. Floryan also teaches this course in Spring 2025. 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 18: Computability
We discussed more about some potential variants of Turing machines and how Turing addressed them. We then informally introduced the “computable numbers” and more generally computable functions.
Slides are here.Mar 27, 2025
Update (Mar 27): Problem Set 8 is now released. You can find the Overlead link in the PDF.
Class 17: Turing Machines
We concluded DFAs and regular expressions with the Cloudflare outage. With that, we formally introduced Turing machines. Historically, there were multiple models of computation, and Alan Turing showed that they are all equivalent to Turing machines.
Slides are here. PS7 is now posted and due next Tuesday.
Mar 25, 2025
Older announcements:
Tentative syllabus posted
The enrollment is starting soon. Please take a look at the syllabus if you have any questions (and be forgiving if something changes later).
Oct 27, 2024.