Due: Tuesday, June 22.
Redo question 8 from the second exam. For part (a), write clear equations. Make sure your equations are correct. Try them on examples. For part (b), write a program. A vague description of an algorithm will not do. For part (c), analyze your algorithm in terms of both x and n. Do not just write the answer. Explain how you got the answer.
Redo question 9 from the second exam. For part (a), write a program, not a vague description of an algorithm. Design your program so that it runs in time O(n + m). For part (b), give a clear and convincing reason behind your analysis. It will not do just to say that the time is O(n + m) just because I asked for that. Make sure that the time really is O(n + m).
Problem 34.2-1, page 982. Two graphs are isomorphic if it is possible to number the vertices so that they have edges between exactly the same numbered vertices. That is, after renumbering the vertices, there is an edge between vertices i and j in the first graph if and only if there is an edge between vertices i and j in the second graph. (Hint. What should the evidence be? Describe how to prosecute your case. What algorithm does the jury use to check the evidence? Are you sure that the jury cannot be fooled? If the correct answer is yes, does there always exist evidence that the prosecutor can present that will convince the jury?)
Problem 34.2-6, page 983.
Problem 34.5-1, page 1017. You get a subgraph of a graph by removing zero or more edges and zero or more vertices. If you remove a vertex, then you must remove all of the edges that hit that vertex. (Hint. You need to show that the subgraph isomorphism problem is in NP, and that some known NP-complete problem transforms to it. Be careful about proving this problem is in NP. Make sure that the jury is not asked to solve a difficult problem. The prosecutor must present enough evidence to make the jury's job easy. What evidence will help? For the second part, try transforming the clique problem to the subgraph isomorphism problem. If you know how to tell whether graph H is isomorphic to a subgraph of graph G, for any graphs H and G, how can you determine whether a graph G contains a clique of a given size K? What subgraph should you look for?)
Problem 34.5-7, page 1017. For this problem, use the following statement of the longest simple cycle problem.
Input. An undirected graph G and a positive integer K.
Question. Is there a simple cycle in G whose length is at least K? A simple cycle is a path from a vertex back to itself that does not go through any vertex more than once. The length of a simple cycle is the number of vertices in it.
(Hint. First show that this problem is in NP. Then show that the Hamilton cycle problem transforms to it. If you know how to determine whether a graph has a cycle of a given length, how can you determine whether a graph has a Hamilton cycle?)