2. a) What is the largest number of key comparisons made by binary search in searching for a key in the following array? 1 3 5 7 9 11 13 b.) Find the average number of key comparisons made by binary...

1 answer below »
2.
a) What is the largest number of key comparisons made by binary search in searching for a key in the following array?













135791113


b.) Find the average number of key comparisons made by binary search in a
successful
search in this particular array. Don't use any formula from the book but instead, find out how many times it takes for each key 1,3,5,7,9,11,13 and take the average. (Assume that each key is searched for with the same probability.)
c.) Find the average number of key comparisons made by binary search in an
unsuccessful
search in this array. Again, don't use any formula from the book but find out how many key comparisons for 0,2,4,6,8,10,12,14 and take the average.


3. Traverse the binary tree above
a.) in preorder.
b.) in inorder.
c.) in postorder.
4. a.) Traverse the graph below by depth-first search, resolving ties by alphabetical order.
b.) Traverse the graph below by breadth-first search, resolving ties by alphabetical order..


8. a.) Apply the left-to-right binary exponentiation algorithm to compute .
Present your answer similar to Example 2 below.


b.) Apply the right-to-left binary exponentiation algorithm to compute .
Present your answer similar to Example 3 below.



Document Preview:

1.Find the order of growth for solutions of the following recurrences.a.)b.)c.)2.a)What is the largest number of key comparisons made by binary search in searching for a key in the following array?135791113b.)Find the average number of key comparisons made by binary search in a successful search in this particular array. Don't use any formula from the book but instead, find out how many times it takes for each key 1,3,5,7,9,11,13 and take the average. (Assume that each key is searched for with the same probability.)c.)Find the average number of key comparisons made by binary search in an unsuccessful search in this array. Again, don't use any formula from the book but find out how many key comparisons for 0,2,4,6,8,10,12,14 and take the average.3.Traverse the binary tree abovea.)in preorder.b.)in inorder.c.)in postorder.4.a.)Traverse the graph below by depth-first search, resolving ties by alphabetical order. b.)Traverse the graph below by breadth-first search, resolving ties by alphabetical order..8.a.)Apply the left-to-right binary exponentiation algorithm to compute .Present your answer similar to Example 2 below.b.)Apply the right-to-left binary exponentiation algorithm to compute .Present your answer similar to Example 3 below.1



Answered Same DayDec 20, 2021

Answer To: 2. a) What is the largest number of key comparisons made by binary search in searching for a key in...

David answered on Dec 20 2021
118 Votes
Q1.
The Master Theorem. The recurrence T(n) = aT(n/b) + f (n) can be solved as follows.
If a f (n/
b) = K*f (n) for some constant K < 1, then T(n) = O(f (n))
If a f (n/b) = K*f (n) for some constant K > 1, then T(n) = O(n^(logb a))
If a f (n/b) = f (n), then T(n) = O(f (n)logb n)
a)

T(n) = 2*T(n/2) + n^0.5

a=2,b=2,f(n) = n^0.5

a*f(n/b) = (2n)^0.5 , here K>1 ,
T(n) = O(n)

b)

T(n) = 2*T(n/2) + n

a=2,b=2,f(n)=n

a*f(n/b) = 2*f(n/2) =...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here