Describe the main ideas behind greedy algorithms.
A greedy algorithm works by making a sequence of decision. Each decision is made by optimizing locally, asking what is the best thing to do for the next step. Once a decision is made, it is final, and will not be undone. The algorithm commits to its decisions.
What problem does Dijkstra's algorithm solve?
Dijkstra's algorithm finds shortest paths in a graph from all vertices to a given vertex.
Is the vertex cover problem known to be NP-complete, or is that only conjectured? Is it known whether the vertex cover problem is in the class P? Is it known whether the vertex cover problem is in the class NP?
The vertex cover problem is known to be NP-complete. (We proved it in class.) The vertex cover problem is known to be in NP. (There is a nondeterministic polynomial time algorithm to solve it.) If P and NP are different classes, then the vertex cover problem is not in P. However, nobody knows whether P and NP are different; that is only conjectured. So it is only a conjecture that leads to the conclusion that the vertex cover problem is not in P.
Do problem 17.2-5.
This one I will leave to you. If you solved the Professor Midas problem above it, you should have no problem with this one.
The partition problem is as follows. You are given a list of positive integers. You would like to create two sublists of the input list, with each number in exactly one of the sublists, so that the sum of the numbers in each sublist is the same. Describe a nondeterministic polynomial time algorithm for the partition problem.
Guess a way to partition the input list into two piles. If there are n values in the list, this is just a matter of selecting n bits, each telling whether one of the numbers goes into the first or second pile.
Compute the sum of each pile. If the two sums are the same, then answer yes. If not, answer "I don't know".
Remark. Notice that the bits selected in step 1 are NOT selected at random. There is no randomization here. Randomized algorithms are a completely different class of algorithms. Here, you should think of the bits as being selected by an oracle who knows how to select them to make the answer be yes, when that is possible.
Suppose that A and B are two sets that belong to the class NP. Show that the intersection of A and B is also a member of NP.
Since A and B are in NP, there is a nondeterministic algorithm for each of them. That is, every member of A has an easily checked certificate showing that it is in A, and every member of B has an easily checked certificate showing that it is in B. We need to find an easily checked certificate showing that a given value is in both A and B. Just take the certificates for membership in A and membership in B and combine them. So a certificate for membership in A intersected with B has the form (C1,C2), where C1 is a certificate that the given value is in A, and C2 is a certificate that the given value is in B.
To check certificate (C1,C2), check that both certificates are valid. (Of course, C1 is checked using the checking algorithm for A and C2 is checked using the checking algorithm for B.)
By the way: If A is a set of strings then the complement of a set A is the set of all strings that do not belong to A. The same kind argument does not work to show that if A is in NP then the complement of A is also in NP. Can you see why? It is conjectured that, if A is NP-complete, then the complement of A is not in NP.
The independent set problem is as follows. The input consists of an undirected graph G and a positive integer k. You are asked whether graph G has an independent set of size at least k. An independent set in a graph is a set of vertices that are mutually nonadjacent. That is, none of them are adjacent to any of the other ones. Prove that the vertex cover problem reduces to the independent set problem.
The reduction from vertex cover to independent set is function f given by f(G,k) = (G,n-k) where n is the number of vertices in G.
Function f is clearly computable in polynomial time. All that is required is to count the number of vertices in G, and do a little arithmetic.
We need to show that G has a vertex cover of size k if and only if G has an independent set of size n-k. It suffices to show a correspondence between vertex covers and independent sets.
Choose a vertex cover S of G having size k. Take the set I of vertices not in S. There cannot be an edge between any two members of I, because if there were, S would not cover all of the edges. Hence, I must be an independent set. Since I has size n-k, G has an independent set of size n-k.
Choose an independent set I of G having size n-k. Take the set S of all vertices that are not in I. Then S must be a vertex cover of G. Any edge not covered by S would have to be between two vertices that are not in S. But there are no such edges, since I is an independent set. Since S has size n-(n-k) = k, G must have a vertex cover of size k.
So f is a polynomial time reduction from the vertex cover problem to the independent set problem.