Computer Science 413: Introduction to Computational Complexity Theory

Introduction to Computational Complexity Theory

Reading Exercise #6: Review of Turing Machines

• Assigned Reading

Lecture #19: Introduction to Computational Complexity Theory

• Lecture Notes
• Questions for Review

Tutorial Exercise #19: Deterministic Turing Machines and the Complexity Class P

• Problems To Be Solved

Lecture #20: Nondeterministic Computation and the Complexity Class NP

• Lecture Notes
• Questions for Review

Tutorial Exercise #20: Proving Membership of a Language in NP

• Problems To Be Solved

Lecture #21: Reductions and Reducibilities

• Lecture Notes
• Questions for Review

Tutorial Exercise #21: Establishing Polynomial-Time Many-One Reductions

• Problems To Be Solved

Reading Exercise #7: Oracle Turing Machines and Oracle Reducibility

• Assigned Reading

Lecture #22: The Cook-Levin Theorem

• Lecture Notes
• Questions for Review

Tutorial Exercise #22: NP-Completeness

• Problems To Be Solved

Lecture #23: The NP-Completeness of Other Formula Problems

• Lecture Notes
• Questions for Review

Tutorial Exercise #23: More About NP-Completeness

• Problems To Be Solved

Lecture #24: The NP-Completeness of Graph Problems

• Lecture Notes

Lecture #25: More About NP-Completeness

• Lecture Notes

Assignment #5: NP-Completeness

• Problems To Be Solved
• A List of NP-Complete Decision Problems

cpsc 413 computer science faculty of science u of c

CPSC 413 introduction and math review analysis of algorithms divide and conquer dynamic programming greedy algorithms complexity theory assignments tests