Please let me know via email (chew@cs.cornell.edu) if you discover mistakes in my solutions. Past experience indicates that I may have made some.
The review questions given here are not meant to exhaust the possible topics for exam questions. Check the previous set of review questions (Solutions to Review Questions for Midterm) the online schedule, and consider reviewing the homework assignments.
Note that the findMin operation can be done quickly (O(1)) because there is no operation that deletes an item. Thus, we can always know the min by simply holding it in a single word; whenever there is an Insert, we update the min.
| Data Structure | insert | member | findMin |
|---|---|---|---|
| sorted array | O(n) | O(log n) | O(1) |
| unsorted array | O(1) | O(n) | O(1) |
| balanced tree (red/black tree) | O(log n) | O(log n) | O(1) |
| hashing | O(1) | O(1) | O(1) |
| priority queue using a heap | O(log n) | O(n) | O(1) |
| sorted linked list | O(n) | O(n) | O(1) |
| unsorted linked list | O(1) | O(n) | O(1) |
(e) (f)
| |
| |
|17 |15
| |
3 | 10 | 1
(A)-------------(c)-------------(g)---------(h)
| | | /
| | | /
|7 |9 |11 /5
| | | /
| 12 | 14 | /
(b)-------------(d)-------------(i)
(e)------------>(t)
^ 8 ^
| |
|17 |15
| |
3 | 10 | 1
(a)------------>(c)------------>(g)<--------(h)
^ ^ ^ ^
| | | |
|7 |9 |11 |5
| | | |
| 12 | 14 | |
(s)------------>(d)------------>(i)----------
There are two things that have to be proved: (1) B is in NP and (2) HC<B. The first part is easy; we simply observe that if we are given a claimed-solution to problem B then we can check that the solution is a cycle of length floor(n/2) in polynomial time. Thus, B is in NP.
For the other part, we assume that we are given an instance of HC (i.e., we have a graph G with n vertices). Now we show how to solve HC by making use of an imaginary program for B. We create a new graph G' that is made of 2 copies of G; each copy is unconnected to the other. Note that the original graph G has a Hamiltonian cycle iff the new graph G' has a simple cycle of length exactly half the number of vertices in G'. Thus HC<B and B is NP-complete.
It's easy to see that VCE (Vertex Cover with only Even-degree vertices) is in NP. The harder part is to show that some NP-complete problem reduces to VCE. The obvious candidate for the reduction is VC (Vertex Cover). Thus, we need to find a way to solve a VC problem (input: a graph G and a bound b) by making use of an imaginary program for VCE. One idea is to add an edge to each odd-degree vertex to make it have even degree. But where should each such edge go? We'll send them all to a single new vertex v.
Fortunately, if we do this, the degree of v turns out to be even. This is because the sum of all vertex degrees in a graph is always even (the sum is equal to the number of endpoints and, since each edge has two endpoints, the total number of endpoints is even); thus, the number of odd-degree vertices must be even.
This looks good so far. We have a new graph with one new vertex, it's closely related to the old graph, and all the vertex degrees are even. If we can find a vertex cover of size b+1 and if that cover uses the new vertex v then we can simply remove v and we've got a vertex cover of size b for our original graph. But to make this work, we have to know that v is used in our vertex cover; it clearly doesn't have to be used since all the edges to v might be covered by choosing their other endpoints.
So now we need a way to force v to be part of the vertex cover. Instead of using a single vertex we can use a triangle of vertices v, v1, and v2. G' is a graph in which all the odd-degree vertices of the original graph are connected to v and v forms a triangle with v1 and v2. Consider a vertex cover of G' and assume this cover does not include v. Then it must include both v1 and v2 or some triangle edge would be uncovered. If we take v1 out of the cover and replace it with v then, since the triangle vertices remain covered, we still have a vertex cover. Thus any vertex cover of G' either includes v or, if it doesn't include v, it can be changed into a same-size vertex cover that does include v.
So here's our algorithm for VC. Use G to build the graph G' as described above. Now a vertex cover of G of size b can be made into a vertex cover of G' of size b+2 just by adding vertices v and v2 (observe that all the new edges of G' are covered). Also a vertex cover of size b+2 of G' either uses v or it can be made into a same-size cover that uses v. Observe that at least one of v1 and v2 must be in the cover. We can remove v and either v1 or v2 from the cover of G' and we still have a cover of the edges of G. Thus, G has a cover of size b iff G' has a cover of size b+2.
The easy part is to show that SC (Set Cover) is in NP by observing that a solution for SC can be easily checked in polynomial time. Now we have to show VC<SC by showing how to solve VC by using an imaginary program for SC. Consider a VC instance (graph G and bound b). Number all the edges from 1 to m. Our set of SC elements will be the set of edge numbers {1,2,...,m}. Our subsets will correspond to vertices, one subset for each vertex. The subset for vertex v will consist of all the numbers corresponding to the edges that use vertex v.
Observe that if VC has a vertex cover of size b then the subsets corresponding to those vertices form a set cover also of size b. If we start with a set cover of size k then the subsets used in the set cover correspond to a vertex cover of same size. Thus, G has a set cover of size b iff the derived SC problem has a set cover of size b. This means that VC<SC and SC is NP-complete.