Skip to content

Lab 9

The exercises for this week are available below for download as a PDF file.

Download Exercises File

Green Exercises

  • Exercise 1 aims to familiarise you with the satisfiability problem (SAT).
  • Exercises 2 and 3 walk you through mostly completed proofs of NP-completeness of two simple problems.
  • Exercises 4--6 introduce you to three popular NP-complete problems: CLIQUE, VERTEX-COVER, and HAMILTONIAN CYCLE.

Orange Exercises

  • Exercise 7 asks you to show that the Subset-Sum Problem (SSP) is NP-complete.
  • Exercise 8 asks you to show that CLIQUE is NP-complete, using reduction from VERTEX-COVER.
  • Exercise 9 asks you to show that a modification of CLIQUE, called HALF-CLIQUE, is NP-complete.
  • Exercise 10 asks you to show that the class P is closed under union, concatenation and complementation operations (like the regular languages).

There are no red exercises this week.

Todo

In advance of your lab session, you need to:

  1. Refresh your knowledge of the key concepts covered in the lecture videos.
  2. Attempt to solve the green exercises.
  3. Then attempt the orange exercises.
  4. Highlight any challenging exercises to ask about them during your lab sessions.
  5. If you want to attempt the advanced/optional (red/blue) exercises then do so.