Introduction to Computational Complexity Theory
Introduction to Computational Complexity Theory
Lecture #19: Introduction to Computational Complexity Theory
Lecture Notes
Review Questions
Reading Exercise #6: Review of Turing Machines
Assigned Reading
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
Review Questions
Tutorial Exercise #20: Proving Membership of a Language in NP
Problems To Be Solved
Lecture #21: Reductions and Reducibilities
Lecture Notes
Review Questions
Reading Exercise #7: Oracle Turing Machines and Oracle Reducibiity
Assigned Reading
Tutorial Exercise #21: Establishing Polynomial-Time Many-One Reductions
Problems To Be Solved
Lecture #22: The Cook-Levin Theorem
Lecture Notes
Review Questions
Lecture #23: The NP-Completeness of Other Formula Problems
Lecture Notes
Review Questions
Tutorial #22: NP-Completeness
Problems To Be Solved
Lecture #24: The NP-Completenes of Graph Problems
Lecture Notes
Leccture #25: More About NP-Completeness
Lecture Notes
Tutorial Exercise #23: More About NP-Completeness
Problem To Be Solved
Assignment #5: NP-Completeness
Problems To Be Solved
LaTeX Source for This Assignment
widget.eps:
This should be placed in a subdirectory of the one where you put the LaTeX source for this assignment named “Figures”.
cpsc 413
computer science
faculty of science
u of c
CPSC 413
Introduction
Analysis of Algorithms
Divide and Conquer
Dynamic Programming
Greedy Algorithms
Computational Complexity
Information about Assignments
Information about Tests