Skip to main content
  • Courses
  • Programs
  • Help
    Getting Started Discussion Forums Help Center & FAQ
Saylor Academy
    Close
    Toggle search input
  • Log in or Sign up
Courses
Programs
Help
Getting Started
Discussion Forums
Help Center & FAQ
  • CS303: Algorithms
  • Sections
  • Course Introduction
  • Unit 1: Introduction to Algorithms
  • Unit 2: Introduction to Analysis of Algorithms
  • Unit 3: Divide and Conquer Method
  • Unit 4: Sorting Algorithms
  • Unit 5: Dynamic Programming
  • Unit 6: Graph Theory and Graph Algorithms
  • Unit 7: Greedy Algorithms
  • Unit 8: NP-Completeness
  • Final Exam
  • Resources
  • Activities
  • Quizzes
  • Home
  • My programs

CS303: Algorithms

Competencies
  1. Home
  2. Courses
  3. (hidden)
  4. CS303: Algorithms
  5. Sections
  6. Unit 8: NP-Completeness

Learn new skills or earn credit towards a degree at your own pace with no deadlines, using free courses from Saylor Academy. We're committed to removing barriers to education and helping you build essential skills to advance your career goals. Start learning here, or check out our full course catalog.

Log in or Sign up to enroll in courses, track your progress, gain access to final exams, and get a free certificate of completion!

Sign up now
Back to course 'CS303: Algorithms'
  • 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.

Skip Activities
Activities
  • QuizQuizzes
  • Resources
Skip Recent activity
Recent activity
Activity since Sunday, January 29, 2023, 2:03 AM
Full report of recent activity...

No recent activity

Saylor Academy
  • About

  • Partners

  • Blog

  • Contact

Saylor Academy

© Saylor Academy 2010-2023 except as otherwise noted. Excluding course final exams, content authored by Saylor Academy is available under a Creative Commons Attribution 3.0 Unported license. Third-party materials are the copyright of their respective owners and shared under various licenses. See detailed licensing information.

Saylor Academy®, Saylor.org®, and Harnessing Technology to Make Education Free® are trade names of the Constitution Foundation, a 501(c)(3) organization through which our educational activities are conducted.

"CCBY"

Sitemap | Terms of Use | Privacy Policy

Data retention summary
Get the mobile app
Policies