FUNDAMENTAL ALGORITHMS
HOMWOWRK 8

DUE April 5
  1. An algorithm that processes lists of keys has the following properties: When presented with a list of n keys, it performs a constant (independent of n) number of comparisons C resulting in the splitting of the list into 2 sublists of sizes n1 and n2 such that n1+n2=n. The algorithm then processes the two n1 and n2 lists recursively until the remaining lists to be processed are of size 1. Let T(n) be the complexity of this algorithm with T(1)=1. a. Write down the recurring equations for T(n). b. Show that T(n)=(C+1)*n - C.

  2. Let A be a list of n positive integers such that A[1]< A[2]<...< A[n]. Write an algorithm that finds an index i such that A[i]=i provided that such an index exists. What is the complexity of your algorithm in terms of comparisons? (Try to minimize this complexity).

  3. Exercise 3.2 p.402 in the book. Hint. Use a balaced binary search tree combined with linked lists of integers.

  4. Assume that you have a computer with an unbounded number of processors that can work in parallel. Write a parallel algorithm that sorts n keys, based on the sequential mergesort algorithm, using as many processors as possible in each sorting round, so as to minimize the number of rounds required until all the keys at input are sorted. Assume that n is a power of 2. Write your algorithm in schematic form only.

    a. How many rounds are required by your algorithm?

    b.What is the parallel complexity of every eound? (Count the maximal number of comparisons performed by a single processor activated in that round).

    c. What is the parallel complexity of your algorithm (summing up the parallel complexities of all the rounds)?