CS 48300: Introduction To The Theory Of Computation

3 Credits

Spring 2024Lecture
Spring 2024 Instructors(1)
Simina Branzei
3.48
RedditReddit
Purdue CatalogCatalog

Turing machines and the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; decidability of logical theories; Kolmogorov complexity; time classes; P, NP, NP-complete; space classes; Savitch's theorem, PSPACE-completeness, NL-completeness; hierarchy theorems; approximation theorems; probabilistic algorithms; applications of complexity to parallel computation and cryptography.

Course CS 483 from Purdue University - West Lafayette.

Prerequisites

Course Overview

Course GPA

GPA: 3.24
Grade Distribution% of Students
A
B
C
A: 46%
B: 35%
C: 18%
D: 2%

Data Averaged From:

Instructors3 instructors
Semesters3 semesters

Instructor Metrics

Select an instructor to view metrics

Add instructors using the search bar above or the list on this page

No data!

GPA Trends

No instructors selected

Select instructors to compare their GPAs.

Fall 2025 Schedule:

BoilerClassesis an unofficial catalog for Purdue courses made by Purdue students, based in West Lafayette, Indiana. We'd love to hear your feedback!