CSCI 3384 Computability and Computational Complexity
This is a course in the theoretical foundations of computer science, centered around the theme of fundamental limits on computation. Topics include: Turing Machines, universal computation, undecidability of the halting problem, solvable and unsolvable algorithmic problems, recursive functions, Goedel's Incompleteness Theorem, time- and space-bounded computations, Cook's Theorem, NP-complete problems, problems solvable in polynomial space, randomized computation, application to cryptography, practical approaches to computationally intractable problems (such as SAT solvers), quantum computing, and Shor's Theorem.
Course overview
- Department
- Computer Science
- School
- MCAS
- Credits
- 3
- Level
- Undergraduate
- Offered
- Every Fall, Periodically in the Spring
Catalog details
Requirements fulfilled
- Computer Science B.A.: CSCI 2000-level-or-higher elective (Current University Catalog; students should confirm their catalog year)
- Computer Science B.A.: CSCI 3000-level-or-higher elective (Current University Catalog; students should confirm their catalog year)
- Computer Science B.S.: CSCI 3000-level-or-higher elective (Current University Catalog; students should confirm their catalog year)
- Mathematics B.S.: Natural science, computer science, or economics corequisites (Current University Catalog; students should confirm their catalog year)
Course evaluations
- Course rating
- 3.95 / 5 · Very Good
- Instructor rating
- 4.36 / 5 · Very Good
- Terms evaluated
- 4
| Term | Instructor | Course overall | Instructor overall | Well organized | Clear learning objectives | Intellectually challenging | Helpful assignments | Applicable beyond course | Attendance necessary | Weekly effort | Responses |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Spring 2026 | Alexander Creiner | 4.2 | 4.6 | 4.6 | 4.4 | 4.8 | 4.9 | 4.4 | 4.7 | 4–6 hrs/week | 10 of 16 |
| Spring 2025 | Alexander Creiner | 3.8 | 4.3 | 3.9 | 4.1 | 4.8 | 4.5 | 4.0 | 4.4 | 7–9 hrs/week | 36 of 45 |
| Fall 2023 | Howard Straubing | 4.5 | 4.7 | 4.6 | 4.8 | 4.8 | 4.8 | 4.6 | 4.7 | 7–9 hrs/week | 11 of 20 |
| Spring 2022 | Howard Straubing | 3.8 | 4.2 | 4.5 | 4.3 | 4.7 | 4.5 | 4.2 | 4.2 | 4–6 hrs/week | 20 of 29 |