https://motifsbyvincent.blogspot.com/p/foundationofalgorithms.html
1: Use recursive Binary Search to search for the integer 120 in the following list (array)
of integers.
2: Suppose that, even unrealistically, we are to search a list of 700 million items
using recursive Binary Search. What is the maximum number of comparisons that this
algorithm must perform before finding a given item or concluding that it is not in the
list?
3: Let us assume that we always perform a successful search. That is, the item x can
always be found in the list S. Improve Algorithm 2.1 by removing all unnecessary
operations.
4: Show that the recurrence equation for W(n) is given by
W(n) = 1 + W((n/2))
W(1) = 1
mid = low. Explain the new search strategy. Analyze the performance of this strategy
and show the results using order notation.
6: Write an algorithm that searches a sorted list of n items by dividing it into three
sublists of almost n/3 items. This algorithm finds the sublist that might contain the
given item and divides it into three smaller sublists of almost equal size. The
algorithm repeats this process until it finds the item or concludes that the item is
not in the list.
7: Use the divide-and-conquer approach to write an algorithm that finds the largest item
in a list of n items.
8: Use Mergesort to sort the following list.
123 34 189 56 150 12 9 240
9: Give the tree of recursive calls
11: Write an Mergesort algorithm
12: Show that the recurrence equation for the worst-case time complexity for MergeSort is
given by W(n) = W(n/2) + W(n/2) + n - 1
13: Given the recurrence relation
14: Consider algorithm solve given below. This algorithm solves problem P by finding the
output (solution) O corresponding to any input I.
15: Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size
n of a problem into 10 substances of size n/3, and the dividing and combining steps
take a time in Theta(n^2). Write a recurrence equation for the running time T(n),
and solve the equation for T(n).
16: Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of
Hanoi problem consists of three pegs and n disks of different sizes. The object
is to move the disks that are stacked, in decreasing order of their size, on one of
the three pegs to a new peg using the third one as a temporary peg. The problem should
be solved according to the following rules:
(1) When a disk is moved, it must be placed on one of the three pegs
(2) Only one disk may be moved at a time, and it must be the top disk on one of the
pegs;
(3) A larger disk may never be placed on top of a smaller disk.
(a) Show for your algorithm that S(n)=2^n - 1.(Here S(n) denotes the number of steps
(moves), given an input of n disks.)