Homework 11
Last updated: Tue, 4 May 2021 16:04:54 -0400
Out: Wed April 28, 00:00 EST Due: Tue May 4 Wed May 5, 23:59 EST
This homework covers material from Chapter 7 of the textbook.
Homework Problems
Graph Components (6 points)
Verifying Graph Components (6 points)
The Bin Packing Problem (6 points)
The Partition Problem (6 points)
Some NP Closure Operations (3 + 3 = 6 points)
README (2 points)
Total: 32 29 points
Submitting
Submit this assignment at Gradescope hw11.
should only include pdf or plain text files,
and each file must be assigned to the correct problem in Gradescope.
1 Graph Components
Updated the problem description on May 5. Edits in bold.
A component in a directed graph is a subgraph in the graph where all the nodes in that subgraph are connected to each other by a path, but not to any nodes not in that subgraph.
Show that the following language is in \textbf{P}:
\textrm{2COMPONENTS} = \{\left\langle G\right\rangle\mid G\textrm{ is a directed graph and has at least two components}\}
2 Verifying Graph Components
Show that the \textrm{2COMPONENTS} language from Graph Components is in \textbf{NP}.
You must use the verifier definition of \textbf{NP}.
3 The Bin Packing Problem
In the bin packing problem, the language \textrm{BIN} is the set of strings \left\langle I, k , b \right\rangle, where:
I is a set of items where each "item" is an integer representing its size;
k is the number of bins;
and b is the size of one bin;
such that I can be divided into k subsets, i.e., "bins", where the total size of each subset is less than or equal to b.
For example, \left\langle\{1,2,3,4,5,6\},3,7\right\rangle\in\textrm{BIN} because the items can be separated into 3 subsets \{1,6\},\{2,5\},\{3,4\}, where the total of each subset is less than or equal to the size of a bin, 7.
Show that the bin packing problem is in \textbf{NP}.
4 The Partition Problem
The \textrm{PARTITION} language contains all sets of integers S such that S can be split into two subsets where adding all the elements of each subset produces the same total.
For example, \{1,2,3,4\}\in\textrm{PARTITION} because it can be divided into two subsets \{1,4\},\{2,3\} whose elements both sum to 5.
Show that if you figure out a polynomial time algorithm for the bin packing problem from The Bin Packing Problem, then \textrm{PARTITION}\in\textbf{P}.
5 Some NP Closure Operations
UPDATE: This question only has one part.
intersection
complement