Quiz 3 Review

We will show how to convert any instance of the KNOWN problem to an instance of the MYSTERY problem. We need to show that this conversion process takse polynomial time, that a yes answer to the corresponding MYSTERY problem implies a yes answer to the original KNOWN problem, and that a no answer to the corresponding MYSTERY problem implies a no answer to the original KNOWN problem.

This solution has been deleted.

Given a RUDRATA CYCLE problem, we select an arbitrary vertex v. We create a new vertex u, which is connected to every neighbor of v. We also create new vertices w and x, where w is connected to u alone and x is connected to v alone.

The claim is that this new graph has a Rudrata path if and only if the original graph has a Rudrata cycle. If we find a Rudrata path in the new graph, that path will have have w as an endpoint, since the Rudrata path must include w but it can only enter w from u and then it won't be able to leave because the only way out is to go through u again. The same applies to x. Thus the path is of the form w-u-…-v-x. To get our cycle in the original graph, then, we can start from v, go to whatever follows u in the path (since that vertex is also adjacent to v in the original graph), and continue following the path until it gets back to v.

If the original graph has a Rudrata cycle, then we can get a Rudrata path in the modified graph by starting at x, going to v, then following the Rudrata cycle from v until it returns back to v, at which point we go to u instead, and then we can go to w to cover the last vertex.

For any individual instance of the problem, the algorithm must find some solution in polynomial time, and the solution's value must be at most 1.5 times the best possible solution for that instance.

The approximation ratio is 2. Let T represent the total time for all jobs. The best possible assignment must have a value of at least T / 2, since if both processors had a total of less than T / 2, then the total time of the jobs would be less than T. The value of the assignment computed by our friend's algorithm is of course T, which is at most twice the optimal assignment.

Given a set of weights, let T represent the total number of weights. The optimum assignment will require at least ⌈T / C⌉ knapsacks.

We want to show that our algorithm will use at most 2 ⌈T / C⌉ knapsacks. Let us first consider the first two knapsacks. The first knapsack will be filled with several weights: Let us say these weights total W₁. But then the next weight x doesn't fit into that first knapsack. Note that W₁ + x > C, since otherwise x would fit into the first knapsack. Now x will go into the second knapsack, so it will form part of W₂. Looking just at the first two knapsacks, then, their total weight is W₁ + W₁, which is at least W₁ + x > C.

Now eventually the algorithm will start with the third knapsack. Starting from there, we can again apply the argument from the previous paragraph to see that the total weight in the third and fourth knapsack will be at least C. So will the fifth and sixth; and the seventh and eighth; and so on. This accounts for everything except possibly the final knapsack, if the number of knapsacks used is odd.

The number of such knapsack pairs is ⌊T / C⌋ When we use the ceiling rather than the floor, we are accounting for the possibility of needing to go to an additional knapsack.

The greedy algorithm given in class would select the first four sets above. However, the optimal selection is the last three sets.

Compute the largest weight W in the tree, and replace each edge weight x with the weight (W + 1) − x instead. We then execute Prim's algorithm to find the minimum spanning tree of this modified graph.

The minimum spanning tree will necessarily include n − 1 edges, so any spanning tree of the modified graph will have a weight of (n − 1) (W + 1) − T, where T is the weight of the same tree in the original graph. We are seeking the smallest possible value of this expression; but since the first term is constant over all trees, the expression will be smallest when T is largest. Thus, the discovered tree will be the maximum spanning tree.

makeset(x)

Makes a set containing just the element x.

find(x)

Finds the set containing the element x.

union(x, y)

Removes the set containing x and the set containing y, replacing them the union of these two removed sets.

The makeset operation takes O(1) time, since it has only to create a list with a single element x in it and then add a mapping from x to this list into the hash table. Both creating a list and setting up x's mapping take O(1) time.

The find operation takes O(1) time because it only has to do a hash table lookup, which takes O(1) time.

The union operation takes O(n) time: It must first find the list for x and the list for y. These lists may both have n / 2 elements, and we'd then have to append one onto the end of the other, which requires O(n) time. Also, we'd have to remap all the elements of the appended list to reference the entire list; each remapping takes O(1) time, but there are O(n) remappings to do. The total time taken is O(n).