Problem 1Problem 2Problem 3Problem 4Problem 5Problem 6Problem 7Problem 8Problem 9Problem 10Massachusetts Institute of Technology 6.042J/18.062J, Spring ’10: Mathematics for Computer Science May 18 Prof. Albert R. Meyer revised May 18, 2010, 1101 minutes Final Examination Your name: • This exam is closed book except for a three page, 2-sided crib sheet. Total time is 3 hours. • Write your solutions in the space provided with your name on every page. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a problem on that problem’s page. • GOOD LUCK! DO NOT WRITE BELOW THIS LINE Problem Points Grade Grader 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 10 Total 100 Creative Commons 2010, Prof. Albert R. Meyer.2 Your name: Final Examination Problem 1 (Probable Satisfiability) (10 points). A literal is a propositional variable or its negation. A k-clause is an OR of k literals, with no variable occurring more than once in the clause. For example, P OR Q OR R OR V, is a 4-clause, but V OR Q OR X OR V, is not, since V appears twice. Let S be a set of n distinct k-clauses involving v variables. The variables in different k-clauses may overlap or be completely different, so k ≤ v ≤ nk. A random assignment of true/false values will be made independently to each of the v variables, with true and false assignments equally likely. Write formulas in n, k, and v in answer to the first two parts below. (a) (2 points) What is the probability that the last k-clause in S is true under the random assign-ment? (b) (3 points) What is the expected number of true k-clauses in S?3 Final Examination Your name: (c) (5 points) A set of propositions is satisfiable iff there is an assignment to the variables that makes all of the propositions true. Use your answer to part (b) to prove that if n < 2k, then S is satisfiable.4 Your name: Final Examination Problem 2 (Asymptotic Bounds and Partial Orders) (10 points). For each of the relations below, indicate whether it is transitive but not a partial order (Tr), a total order (Tot), a strict partial order that is not total (S), a weak partial order that is not total (W), or none of the above (N). • the “is a subgraph of” relation on graphs. (Note that every graph is considered a subgraph of itself.) Let f, g be nonnegative functions on the real numbers. • the “Big Oh” relation, f = O(g), • the “Little Oh” relation, f = o(g), • the “asymptotically equal” relation, f ∼ g.5 Final Examination Your name: Problem 3 (Graph Coloring & Induction) (10 points). Recall that a coloring of a graph is an assignment of a color to each vertex such that no two adjacent vertices have the same color. A k-coloring is a coloring that uses at most k colors. False Claim. Let G be a graph whose vertex degrees are all ≤ k. If G has a vertex of degree strictly less than k, then G is k-colorable. (a) (2 points) Give a counterexample to the False Claim when k = 2. (b) (4 points) Underline the exact sentence or part of a sentence that is the first unjustified step in the following “proof” of the False Claim. False proof. Proof by induction on the number n of vertices: Induction hypothesis: P (n)::= “Let G be an n-vertex graph whose vertex degrees are all ≤ k. If G also has a vertex of degree strictly less than k, then G is k-colorable.” Base case: (n = 1) G has one vertex, the degree of which is 0. Since G is 1-colorable, P (1) holds. Inductive step: We may assume P (n). To prove P (n + 1), let Gn+1 be a graph with n + 1 vertices whose vertex degrees are all k or less. Also, suppose Gn+1 has a vertex, v, of degree strictly less than k. Now we only need to prove that Gn+1 is k-colorable. To do this, first remove the vertex v to produce a graph, Gn, with n vertices. Let u be a vertex that is adjacent to v in Gn+1. Removing v reduces the degree of u by 1. So in Gn, vertex u has degree strictly less than k. Since no edges were added, the vertex degrees of Gn remain ≤ k. So Gn satisfies the conditions of the induction hypothesis, P (n), and so we conclude that Gn is k-colorable. Now a k-coloring of Gn gives a coloring of all the vertices of Gn+1, except for v. Since v has degree less than k, there will be fewer than k colors assigned to the nodes adjacent to v. So among the k possible colors, there will be a color not used to color these adjacent nodes, and this color can be assigned to v to form a k-coloring of Gn+1. �6 Your name: Final Examination (c) (4 points) With a slightly strengthened condition, the preceding proof of the False Claim could be revised into a sound proof of the following Claim: Claim. Let G be a graph whose vertex degrees are all ≤ k. If �statement inserted from below� has a vertex of degree strictly less than k, then G is k-colorable. Circle each of the statements below that could be inserted to make the Claim true. • G is connected and • G has no vertex of degree zero and • G does not contain a complete graph on k vertices and • every connected component of G • some connected component of G7 Final Examination Your name: Problem 4 (Planar Embeddings) (10 points). The planar graph embeddings in class (repeated in the Appendix) were only defined for connected planar graphs. The definition can be extended to planar graphs that are not necessarily connected by adding the following additional constructor case to the definition: • Constructor Case: (collect disjoint graphs) Suppose E and F are planar embeddings with no vertices in common. Then E ∪ F is a planar embedding. Euler’s Planar Graph Theorem now generalizes to unconnected graphs as follows: if a planar embedding, E, has v vertices, e edges, f faces, and c connected components, then v − e + f − 2c = 0. (1) This can be proved by structural induction on the definition of planar embedding. (a) (4 points) State and prove the base case of the structural induction. (b) (2 points) Carefully state what must be proved in the new constructor case (collect disjoint graphs) of the structural induction. (c) (4 points) Prove the (collect disjoint graphs) case of the structural induction.8 Your name: Final Examination Problem 5 (Euler’s Function) (10 points). (a) (2 points) What is the value of φ(175), where φ is Euler’s function? (b) (3 points) Call a number from 0 to 174 powerful iff
View Full Document
Unlocking...