Algorithms: my recent solutions

Solutions to the questions below:
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
5: Suppose that, in Algorithm 2.1 (line 4), the splitting function is changed to 
   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.)