CS303: Algorithms

Unit 8: NP-Completeness

• 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.