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).