Description
Objective:
(1) Understand the backtracking algorithms
(2) Enhance the concept of Intractability and the theory of NP.
1. [15%] Given the following sum of subset problem. S=10, and the integers are 3, 9, 2, 6, 7.
a) [5%] If no pruning is made on the whole state space tree. How many nodes does it contain?
b) [10%] Apply the backtracking algorithm. Whenever you find that a node is not promising backtrack. How many nodes does your tree contain? Draw the pruned state space tree.
2. [18%]
(1) [9%] Given a knapsack of size 28, and the following 3 items: Item 1, has profit 32 and size 8. Item 2, has profit 110 and size 20. Item 3, has profit 50 and size 5. Solve the problem using the backtracking algorithm. Show the complete pruned state space tree. Show for every node, the current profit, the current weight and the bound. Show also the maxprofit after each node is generated. Show the order that the nodes to be checked.
(2) [9%] Using the best-first search algorithm (Branch-and-Bound) to solve the above problem. Show the order that the nodes to be checked.
3. [12%] Given an array A. Consider the following decision problem: is the 5000th largest element in the array greater than 100000?
a) Does this problem belong to the class P? Explain if no, or describe and analyze a polynomial bound algorithm that solves it. [4%]
b) Does the problem belong to the class NP? Explain [4%]
c) Does it belong to the class NPC (the class of NP-Complete problems)? (yes, no, probably) Explain [4%]
4.[10%] Professor Green showed a polynomial reduction of the famous decision problem CC to an NP-Complete problem. He also wrote an 80 page paper showing a polynomial bound algorithm for solving CC.
a) Is CC in P? Is CC in NP? [5%]
b) Should Professor Green get the $1,000,000 prize for showing that P = NP? Explain your answer. [5 %]
5. [10%] Professor Watson showed a polynomial reduction of satisfiability to the famous decision problem YY. He also showed a polynomial bound verification algorithm for YY.
a. What does Professor Watson know about YY? [5%]
b. Assume that the professor find a polynomial bound algorithm for YY. Should Professor Watson get the $1,000,000 prize for showing that P = NP? Explain your answer. [5 %]
6. [9%] A clique is a complete graph — every vertex is connected to every other vertex. Here is the formal definition from many textbooks: “A clique in a graph is a set of pair-wise adjacent vertices, or in other words, an induced sub-graph which is a complete graph. In the following graph, vertices 1, 2 and 5 form a clique, because each has an edge to all the others”.
Then, the decision-clique problem is the problem of determining whether a graph G contains a clique of at least a given size k. This problem is NP-complete.
Professor Bartlett has designed an algorithm that can take any graph G with n vertices and determine in time whether or not G contains a clique of size k. Has Professor Bartlett showed that P = NP? Explain your answer.
7. [7%] Is the sum of subsets the decision problem or the optimization problem? Is it in NP? Explain why.
8. [7%] Show that 0-1 knapsack decision problem is NP-Complete (hint: sum of subsets is NP-Complete).
9. [12%] For each of the following problems, indicate which are in P and which are in NP. For those you think are in P, give an outline of the algorithm to solve them. For those you think are in NP, explain why you think they are not solvable in polynomial time. (Hint: think about an algorithm to solve these problems, and then determine if it is polynomial.)
a. The Smarandache function, S(k), gives the smallest integer m, so that m! can be evenly divided by k. For example, S(9) = 6 because 6!=720 and 9 does not divide any smaller factorial. Calculate the Smarandache function for any number.
b. You have to seat N children in the smallest number of rows in an auditorium. For each child, you have a list of who that child dislikes. Experience shows that if a child is in the same row or any row behind a child that he or she dislikes, he or she will throw things at the other child. Given this list, determine in which row to seat each child, or determine that they cannot be seated.
c. You are in front of a wall that stretches infinitely in both directions. You know that there is a door in the wall, but it is dark, and you have only a dim flashlight that allows you to see no more than one step in either direction. Find the door.
10. (Optional: Extra point 12%) using the best-first search algorithm to give a solution of the following traveling salesman problem. Show the state space tree and the optimal tour [6%], and write a program to implement it [6%].
