Programming > SOLUTIONS MANUAL > Solutions Manual > University of California, Santa Cruz - CMPS 201 Mid2solns: CMPS 201 Analysis of A (All)
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
Buy this document to get the full access instantly
Instant Download Access after purchase
Add to cartInstant download
We Accept:
Connected school, study & course
About the document
Uploaded On
Feb 10, 2021
Number of pages
4
Written in
This document has been written for:
Uploaded
Feb 10, 2021
Downloads
0
Views
97
In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.
We're available through e-mail, Twitter, Facebook, and live chat.
FAQ
Questions? Leave a message!
Copyright © Browsegrades · High quality services·