Spring 2027

Introduction to Theory of Computing

Covers basics of computation including finite automata, regular languages, computability, complexity theory, context-free grammars, and complexity-theoretic cryptography.

no offering record for this termCredits unavailable
Recorded instructors · Spring 2027 No instructors listed

Summary

1 / 7

Past student reviews · Jin-Yi Cai, Eric Bach

The course was described as very hard, with abstract content like P-NP and decidability that required significant effort and time to understand well.

What you’ll be able to do

  • Design and implement deterministic finite automata to capture specified regular languages.

  • Differentiate between deterministic and nondeterministic finite automata and apply finite automata theory to express those computation tasks that can be captured by regular languages.

  • Express and interpret computational models that lead to and capture algorithmic thinking.

  • Design and implement a pushdown automata to capture specified context-free languages.

  • Identify and explain reasoning about formalization of computation, formulated as various models of computation and make transformations between finite automata and regular languages, pushdown automata and context-free languages.

  • Construct clear, concise, and sound proofs for statements regarding different models of computation, their relative strengths and weaknesses.

  • Reason with Turing machines, and the various equivalent formulations of computability theory, for example to explain how the formalization captures everyday computational processes.

  • Reason about computational intractability, applying the concepts of NP-hardness and NP-completeness to classify computational problems.

Source: UW Guide

Grade history

↗
average GPA
letter grades
A
AB
B
BC
C
D
F

All recorded terms · compare terms & instructors

Prerequisites

Course map

(MATH/​COMP SCI 240 or STAT/​COMP SCI/​MATH 475) and (COMP SCI 367 or 400), or graduate/professional standing, or declared in the Capstone Certificate in Computer Sciences for Professionals

COMPSCI 520

This is a best-effort interpretation; check the catalog requirements above.

Prerequisite text tree

Professors

Spring 2027

No instructors recorded for this selection.

Historical instructors & teaching patterns

DEBORAH JOSEPH is recorded teaching in Spring 2013, Fall 2013. Recorded history may be incomplete and does not establish a future schedule.

ERIC BACH is recorded teaching in Fall 2011, Fall 2017, Spring 2022. Recorded history may be incomplete and does not establish a future schedule.

JIN-YI CAI is recorded teaching in Spring 2007, Spring 2009, Spring 2010, Fall 2010, Spring 2014, Fall 2014, Spring 2015, Fall 2015, Fall 2016, Fall 2018, Spring 2019, Fall 2019, Fall 2023, Spring 2025, Spring 2026. Recorded history may be incomplete and does not establish a future schedule.

Recorded history may be incomplete and does not establish a future schedule.

Calendar & sections

Spring 2027

Schedule loads here as you scroll.

SectionModeEnrolled / capacityWaitlist

Times are Central. Select a meeting for details; export includes recorded dates for the selected sections.

Meeting source records
Download part 1

Student experience

the class

Past student reviews · Jin-Yi Cai

Students found Jin-Yi Cai's lectures engaging and insightful, often praising his charisma and passion for the material despite its theoretical nature.

Recent recorded grades — Fall 2023: 3.19 GPA, 64.1% A/AB (n=39 letter grades); Spring 2025: 2.79 GPA, 36.8% A/AB (n=57 letter grades); Spring 2026: 2.73 GPA, 32.4% A/AB (n=37 letter grades).

difficulty & workload

Past student reviews · Jin-Yi Cai, Eric Bach

The course was described as very hard, with abstract content like P-NP and decidability that required significant effort and time to understand well.

Past student reviews · Jin-Yi Cai

Opinions on teaching effectiveness were divided; some found Cai muffled and difficult to follow, while others appreciated that exams allowed for creative, informal arguments.

Topics

  • Finite automata and regular languages
  • Computability theory
  • Computational complexity theory
  • Context-free grammars and languages
  • Complexity-theoretic cryptography

Skills

  • Design and implement deterministic finite automata.
  • Differentiate between deterministic and nondeterministic finite automata.
  • Design and implement pushdown automata.
  • Construct proofs regarding models of computation.
  • Reason with Turing machines and computability theory.
  • Apply NP-hardness and NP-completeness to classify problems.

Grades

Latest available · Spring 2026— not enough history to project Spring 2027.

average GPA
A / AB grades
letter grades
Instructor

Grade distribution · % of letter grades

A
AB
B
BC
C
D
F

Grades over time

Through Spring 2026

More grade details Grade mix, volume & source data

Where this course fits relative to

Latest available grades · Spring 2026 · all course levels

GPA

Higher than % of other courses in this group.

Course GPAs · red marks this course’s range

letter grades

More recorded grades than % of other courses in this group.

Typical course in this group: letter grades.

About this comparison

1280 courses over the same term, each with at least 30 recorded letter grades. Cross-listed courses count once. GPA is not a measure of difficulty or teaching quality. The typical course is the median by recorded grade count; tied values are not counted as lower. Grade counts describe course scale, not unique students or typical section size.

Descriptions compare GPA with this group’s average: at least 0.20 higher or lower; otherwise close to average. Section size uses median recorded enrollment: small up to 30, mid-sized 31–99, large 100+. Lectures and discussion/lab sections are described separately.

Sources & history

UW–Madison

Catalog & offerings

Descriptions, prerequisites, and recorded course offerings.

Catalog observation history

Observations at scan time; dates do not imply when a catalog change took effect.

Download part 1
Selected offering source records

No offering records for the selected term.

Raw records 
[]
Rate My Professors

Student reviews

Original comments behind the course and instructor summaries.

Read original reviews
Download part 1
Madgrades

Grade history

Recorded grade distributions by term, section, and instructor.

Explore recorded grades
Dataset & model

Recorded 2026-10-14

View the dataset on Hugging Face
Model outputs & technical records
Qwen/Qwen3.8-27B
LLM outputs across runs
Download part 1
Full model traces

Recorded model configuration, reasoning, and tool conversations.

Download part 1Download part 2
Model & dataset provenance 
{
  "model": "Qwen/Qwen3.8-27B",
  "model_revision": "1d4bf0f2ff6012fd82039f2fa52739d0dd7c60c0",
  "task_version": "17",
  "output_id": "6e0654fb01a5d558e7b9ecd9beeeadf7d6c66742f55241e693896ec9762d4cfb",
  "requirements_status": "needs_review",
  "dataset_revision": "fc1811fa52e581ea57a35c0cf3343f8740a8ffbf",
  "observed_at": "2026-10-14 17:50:09.728220+00:00"
}