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

Document Content and Description Below

CMPS 201 Analysis of Algorithms Fall 2017 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 Use induction to prove that ?(?) ≤ 2? for all ? ≥ 1. Proof: 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 that ?(?) ≤ 2?. We have as required. It follows that ?(?) ≤ 2? for all ? ≥ 1. ■ This study resource was shared via CourseHero.com 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 This study resource was shared via CourseHero.com 4. (20 Points) Recall the decision problems Hamiltonian Cycle (HC) and Travelling Salesman (TSP). HC: Given a graph G, determine whether or not G contains a Hamiltonian cycle (a cycle that visits every vertex in G). TSP: Given a complete graph ??, a weight function ?: ?(??) → ℝ, and a bound ? ≥ 0, determine whether or not ?? contains a Hamiltonian cycle of total ::::::::::::::::::::::::::::::::::::::::CONTENT CONTINUED IN THE ATTACHMENT::::::::::::::::::::::::::::::::::::::::::::::::::: [Show More]

Last updated: 1 year ago

Preview 1 out of 4 pages