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
- Prerequisites
- CSCI2243 or MATH2216
- Corequisites
- CSCI2244 or MATH4426
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)
Official evaluation summary
3.95 / 5
Data freshness
Instructors
Sections
- Section 01