Problem 1(a)(b)(c)Problem 2(a)(b)(c)Problem 3Problem 4GraphsFull Binary TreesAsymptotic NotationMassachusetts Institute of Technology6.042J/18.062J, Spring ’02: Mathematics for Computer Science March 22Professor Albert Meyer and Dr. Radhika Nagpal revised April 28, 2002, 860 minutesQuiz 2Your name:Circle the name of your Tutorial Instructor:Ashish Carole Christos EricGeorge Jack Nick Tina• This quiz is closed book. There is an Appendix that repeats some key definitions.• There are four (4) problems totaling 100 points. Problems are labeled with theirpoint values.• Put your name on the top of every page – these pages may be separated for grading.• Write your solutions in the space provided. If you need more space, write on theback of the sheet containing the problem. Please keep your entire answer to a prob-lem on that problem’s page.• You may assume any of the results presented in class or in the lecture notes.• Be neat and write legibly. You will be graded not only on the correctness of youranswer, but also on the clarity with which you express it.• GOOD LUCK!DO NOT WRITE BELOW THIS LINEProblem Points Grade Grader1 202 263 244 30Total 100Copyrightc 2002, Prof. Albert R. Meyer and Dr. Radhika Nagpal. All rights reserved.Quiz 2 Your name: 2Problem 1 (20 points). (a) (3 points) Prove that if every simple cycle in a simple graphis 2-colorable, then the whole graph is 2-colorable. You may cite without proof any of theresults from class, Course Notes and Problem Sets.(b) (7 points) Draw a small counter-example to the following false theoremFalse Theorem. If every simple cycle in a simple graph is 3-colorable, then the whole graph is3-colorable.Quiz 2 Your name: 3(c) (10 points) We know that a graph containing K4(the complete subgraph on 4vertices) is not 3-colorable.1. Give an example of a graph that does not contain K4, but is still not 3-colorable.2. Briefly, but carefully, explain why it is not 3-colorable.Quiz 2 Your name: 4Problem 2 (26 points). The Massachusetts Turnpike Authority is concerned about the in-tegrity of the new Leonard Zakim bridge. Their consulting architect has warned that thebridge may collapse if more than 500 cars are on it at the same time. The Authority hasalso been warned by their traffic consultants that the rate of accidents from cars speedingacross bridges has been increasing.Both to lighten traffic and to discourage speeding, the Authority has decided to makethe bridge one-way and to put tolls at both ends of the bride (don’t laugh, this is Mas-sachusetts). A car pays $3.00 at the entry toll booth and another $3.00 at the exit tollbooth. To be sure that there are never too many cars on the bridge, the Authority will leta car onto the bridge only if the difference between the amount of money currently at the entrytoll booth minus the amount at the exit toll booth is strictly less than $1500.The Authority has asked their engineering consultants to verify that this policy will keepthe number of cars from exceeding 500. The consultants have decided to model this sce-nario with a state machine whose states are triples of natural numbers, (A, B, C), where• A ∈ N is an amount of money at the entry booth,• B ∈ N is an amount of money at the exit booth, and• C ∈ N is a number of cars on the bridge.Since the toll booth collectors may need to start off with some amount of money in orderto make change, and there may also be some number of “official” cars already on thebridge when it is opened to the public, the consultants must be ready to analyze thesystem started at any state, not necessarily with a start state (0, 0, 0).(a) (4 points) Give a mathematical description of the Authority’s rules for lettingcars on and off the bridge by specifying a transition relation between states of the form(A, B, C) above.Quiz 2 Your name: 5(b) (8 points) Characterize each of the following derived variablesA + BA − B1501A − B3C − AC −A3−B3C −A3+B3as one of the followingconstant Cstrictly increasing SIstrictly decreasing SDweakly increasing but not constant WIweakly decreasing but not constant WDnone of the above Nby entering the corresponding code next to the variable.Quiz 2 Your name: 6(c) (14 points) The engineering consultants plan to use the Invariant Method to provethat the bridge will never collapse under the assumption that the bridge opens to thepublic with no cars on it and no money at the toll booths. That is, the start state is (0, 0, 0).They realize that in such a proof, they musn’t confuse the following properties of predi-cates, P , on states:R P happens to be true in all the states reachable from the start state (0, 0, 0).I P is invariant, that is, if P ((A, B, C)) is true, and there is a transition from (A, B, C)to (A0, B0, C0), then P ((A0, B0, C0)) is true.G P guarantees the bridge won’t collapse, that is, if P ((A, B, C)) is true, and there is asequence of zero or more transitions from (A, B, C) to (A0, B0, C0), then C0≤ 500.For example, the predicate [A −B ≤ 1500] has property R, but not property I or G becausethere is an (unreachable) state, namely, (1499, 0, 500) in which 1499 − 0 ≤ 1500 but thisstate has a transition to (1502, 0, 501) where the property fails and the bridge collapses.Indicate for each of the following predicates, exactly which of properties R,I, and G it has.1. C ≤ 5002. A ≥ B.3. A − B = 3C.4. A − B < 3C.5. A − B = 3C ∧ A − B ≤ 1500.6. A − B ≤ 3C ∧ C ≤ 500.Quiz 2 Your name: 7Problem 3 (24 points). Indicate which of the following holds for each pair of functionsf(n) and g(n) in the table below. Note that ln denotes the natural logarithm.f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f ∼ g6n + 6 nn4ln n n4.012 ln(n3) + 2Pni=16/in!nenP∞i=n1/i21/2P10i=1i2n3Quiz 2 Your name: 8Problem 4 (30 points). In class and in the Course Notes we have introduced the notionof a full binary tree and we have also defined the functions numnodes(·) and depth(·) thatreturn the number of nodes and the depth of such a tree, respectively. (You can look up theexact definitions in the Appendix.)Use structural induction to prove that in a full binary tree t,numnodes(t) + 1 ≤ 2depth(t)+1.You may not cite the result for binary trees given in lecture slides, unless you prove it.Quiz 2 Your name: 9AppendixA GraphsDefinition. A simple graph is a pair of sets G = (V, E) such that E is a set of two-elementsubsets of V . Elements of V are called vertices or nodes;
View Full Document
Unlocking...