20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

Complexity

Due: xxx, 2011

  1. Consider the following algorithm for searching a list L of integers for the element of maximum value:
           function MAX (L[1:n])
           input:   L[1:n] (array of integer list elements)
           output:  The location max_element_location of the maximum 
                    number in L
    
           max_element_value := L[1]
           max_element_location := 1
           for j := 2 to n do
              if L[j] > max_element_value then do the following:
                  max_element_value := L[j];
                  max_element_location := j
              endif
           endfor
           return(max_element_location)
    
    1. If L={1,2,3} then how many times does the value of max_element_location change in MAX(L)?

    2. Repeat for L={1,3,2}, L={2,1,3}, L={2,3,1}, L={3,1,2}, L={3,2,1}

    3. From the first two parts above you have the number of times max_element_location changes for each possible input list of three elements. Summing all these numbers and dividing by 6 (the number of possible inputs) gives the average number of times max_element_location changes for lists of three elements. What is that number?

    4. What is the average number of times max_element_location changes for lists of four elements?

    5. What is the average number of times max_element_location changes for lists of eight elements? Do you see a trend?

    6. Find a function f(n) which is the average number of times max_element_location changes for lists of n elements.

  2. Let M be a 2 x n matrix of numbers. Suppose you are given an optimal sorting algorithm A which runs in time n log(n). Use A as a subroutine and devise an algorithm that permutes the columns of M so that neither row of the rearranged matrix has a decreasing subsequence of length exceeeding sqrt{n}. Present and verify an algorithm which runs in time proportional to n log(n).