Solutions Manual > University of California, Santa Cruz - CMPS 201mid2solns./ CMPS 201 Analysis of Algorithms Fall 2018 Midterm Exam 2 Solutions

Document Content and Description Below

CMPS 201 Analysis of Algorithms Fall 2018 Midterm Exam 2 Solutions 1. (20 Points) Let ? be a randomly chosen non-negative integer having at most ? decimal digits, i.e. an integer in the range... 0 ≤ ? ≤ 10?- 1. Consider the following problem: determine ? by asking only 5- way questions, i.e. questions with at most 5 possible responses. For instance, one could ask which of 5 specific sets ? belongs to. Prove that any algorithm restricted to such questions, and which correctly solves this problem, runs in time Ω(?). Proof: Since there are exactly 10?possible verdicts, and every question has at most 5 answers, any algorithm solving this problem can be represented by a decision tree whose height ℎ satisfies ℎ ≥ ⌈log5(10?)⌉ = ⌈? ⋅ log5(10)⌉ = Ω(?). Therefore any algorithm that solves this problem runs in time Ω(?). ■ 2. (20 Points) Recall that the average case run time of RandSelect() satisfies the recurrence relation ?(?) = (? - 1) + (??-2 1) ∑ ?(?) ?-1 ?=1 Prove that ?(?) = Θ(?). Proof: First observe that ?(?) ≥ ? - 1 = Ω(?), so ?(?) = Ω(?). We prove now that ?(?) ≤ 2? for all ? ≥ 1 by induction. This shows that ?(?) = ?(?), and hence ?(?) = Θ(?) as required. I. Observe ?(1) = (1 - 1) + 1-1 12 ⋅ (empty sum) = 0 ≤ 2 = 2 ⋅ 1, establishing the base case. II. Let ? > 1, and assume for all ? in the range 1 ≤ ? < ? that ?(?) ≤ 2?. We must show ?(?) ≤ 2?. 3. (20 Points) Assume we are given 3 gold bars (labeled 1, 2, 3), one of which may be counterfeit: either goldplated lead (heavier than gold) or gold-plated tin (lighter than gold). Consider again the problem of finding which, if any, of the bars is counterfeit and what it is made of. The only tool at your disposal is a balance scale. Each use of the scale produces one of three possible outcomes: tilt left, balance, or tilt right. a. (10 Points) Give a decision tree argument establishing a lower bound on the (worst case) number of weighing's performed by any algorithm for this problem. (In your proof, clearly enumerate the set of possible verdicts.) Claim: Any algorithm solving this problem must use the balance at least 2 times. Proof: There are 7 possible verdicts to this problem: {1L, 1H, 2L, 2H, 3L, 3H, AllGold}, and each test has 3 possible outcomes. Thus any algorithm solving this problem can be represented by a decision tree whose height ℎ satisfies ℎ ≥ ⌈log3(7)⌉ = 2. Therefore 2 weighing's are necessary in worst case. ■ b. (10 Points) Design an algorithm that solves this problem by using the balance scale (at most) the number of times you found in (a). Express your algorithm as a decision tree. Solution: In the figure below, a branch left indicates that the scale tilts left, a vertical branch indicates that the scale balances, and branch right indicates the scale tilts right. Note that some outcomes are not possible at certain points in the algorithm, indicated by the absence of a branch right or left. 1 : 2 1 : 3 1 : 3 1 : 3 1H 2L 3L AllGold 3H 2H 1L ::::::::::::::::::::::::::::::::::::::::CONTENT CONTINUED IN THE ATTACHMENT::::::::::::::::::::::::::::::::::::::::::::::::::: [Show More]

Last updated: 1 year ago

Preview 1 out of 4 pages