CS303: Algorithms, Topic: Unit 8: NP-Completeness

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
  - University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's "NP-Complete Problems" URL
    Read Chapter 8 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
- 8.2: NP-Completeness - Part I
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "NP-Completeness - Part I" Page
    Watch this video to learn about NP-Complete problems in the context of computer algorithms.
- 8.3: NP-Completeness - Part II
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "NP-Completeness - Part II" Page
    Watch this video to learn about NP-Complete problems in the context of computer algorithms.
- 8.4: NP-Completeness - Part III
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "NP-Completeness - Part III" Page
    Watch this video to learn about NP-Complete problems in the context of computer algorithms.
- 8.5: NP-Completeness - Part IV
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "NP-Completeness - Part IV" Page
    Watch this video to learn about NP-Complete problems in the context of computer algorithms.
- 8.6: NP-Completeness - Part V
  - Indian Institute of Technology, Bombay: Dr. Sunder Viswanathan's "NP-Completeness - Part V" Page
    Watch this video to learn about NP-Complete problems in the context of computer algorithms.
  - NP-Completeness Assignment URL
    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.