2.
a) What is the largest number of key comparisons made by binary search in searching for a key in the following array?
b.) Find the average number of key comparisons made by binary search in a
successfulsearch 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
unsuccessfulsearch 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