CSE 6321
Transcript Abbreviation:
Cmptblty & Cmplxty
Course Description:
Turing machines, decidability, recursive enumerability; many-to-one and polynomial-time reductions; NP-completeness, Cook-Levin Theorem; Recursion Theorem.
Course Levels:
Graduate (5000-8000 level)
Designation:
Elective
General Education Course:
(N/A)
Cross-Listings:
(N/A)
Credit Hours (Minimum if “Range”selected):
3.00
Max Credit Hours:
3.00
Select if Repeatable:
Off
Maximum Repeatable Credits:
(N/A)
Total Completions Allowed:
(N/A)
Allow Multiple Enrollments in Term:
No
Course Length:
14 weeks (autumn or spring)
12 weeks (summer only)
Off Campus:
Never
Campus Location:
Columbus
Instruction Modes:
In Person (75-100% campus; 0-24% online)
Prerequisites and Co-requisites:
Prereq: 3321 (625) or 5321.
Electronically Enforced:
No
Exclusions:
Not open to students with credit for 725.
Course Goals / Objectives:
Master the use of reductions to prove certain problems undecidable
Master the use of polynomial time reductions to prove certain problems NP-complete
Be familiar with diagonalization
Be familiar with Church's Thesis
Be familiar with various complexity classes
Be familiar with the Cook-Levin Theorem
Be exposed to theory of cardinalities
Be exposed to approximation results for NP-complete problems
Be exposed to complexity class hierarchies
Be exposed to Savitch's Theorem
Check if concurrence sought:
No
Contact Hours:
| Topic | LEC | REC out-of-class | REC in-class | Weekly LAB out-of-class | Weekly LAB in-class |
|---|---|---|---|---|---|
| Theory of cardinalities. | 6.0 | 0.0 | 0 | 0.0 | 0 |
| Turing machines and variant models of computation. | 6.0 | 0.0 | 0 | 0.0 | 0 |
| Decidabilty, recursive enumerability. | 12.0 | 0.0 | 0 | 0.0 | 0 |
| NP-completeness. | 9.0 | 0.0 | 0 | 0.0 | 0 |
| Approximation algorithms for NP-complete problems. | 3.0 | 0.0 | 0 | 0.0 | 0 |
| Hierarchy theorems, Savitch's Theorem. | 3.0 | 0.0 | 0 | 0.0 | 0 |
| Advanced topics (such as the Recursion Theorem). | 3.0 | 0.0 | 0 | 0.0 | 0 |
| Total | 42 | 0 | 0 | 0 | 0 |
Grading Plan:
Letter Grade
Course Components:
Lecture
Grade Roster Component:
Lecture
Credit by Exam (EM):
No
Grades Breakdown:
| Aspect | Percent |
|---|---|
| Homework | 20% |
| Classroom participation | 10% |
| Midterms, final | 70% |
Representative Textbooks and Other Course Materials:
| Title | Author | Year |
|---|---|---|
| Introduction to the Theory of Computation | Michael Sipser |
ABET-CAC Criterion 3 Outcomes:
(N/A)
ABET-ETAC Criterion 3 Outcomes:
(N/A)
ABET-EAC Criterion 3 Outcomes:
(N/A)
Embedded Literacies Info: