Unit 8: NP-Completeness
In this last unit, we will study a special class of problems called the NP-complete problems. Many interesting computational problems are NP-complete, but there are no polynomial-time algorithms known for solving any of them. The unit presents techniques for determining when a problem is NP-complete.
Completing this unit should take you approximately 11 hours.
Upon successful completion of this unit, the student will be able to:
- Explain the classification of difficult computer science problems as belonging to P, NP, and NP-hard classes.
8.1: Introduction to NP-Completeness
Read Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
8.2: NP-Completeness - Part I
Watch this video to learn about NP-Complete problems in the context of computer algorithms.
8.3: NP-Completeness - Part II
Watch this video to learn about NP-Complete problems in the context of computer algorithms.
8.4: NP-Completeness - Part III
Watch this video to learn about NP-Complete problems in the context of computer algorithms.
8.5: NP-Completeness - Part IV
Watch this video to learn about NP-Complete problems in the context of computer algorithms.
8.6: NP-Completeness - Part V
Watch this video to learn about NP-Complete problems in the context of computer algorithms.
Complete all questions in this assignment. There are two questions that are both related to proving NP-Completeness of a given problem. You can check your answers against the Answer Key.