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

Document Content and Description Below

CMPS 201 Analysis of Algorithms Fall 2016 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 which is 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 This study resource was shared via CourseHero.com3. (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 the following problem: determine 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 correct algorithm that solves 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 the fewest number of times, i.e. an algorithm using (at most) the number of weighing's you found in (a). Express your algorithm as a decision tree. [Show More]

Last updated: 1 year ago

Preview 1 out of 4 pages