No Title

CSE 101 Practice Midterm Questions
(Not to be turned in)

Each problem specifies the answer you should give. If a particular question does not ask for explanations, proofs, running time analyses, etc., you do not need to give them to obtain full credit. But brief explanations may help to understand your answer and give credit when grading.

This question refers to the following algorithm. A is an nxn matrix of integers, accessed as with indices i and j ranging from 1 to n; i specifies the row and j specifies the column of the matrix.
```
 
L(A,n)

1 		  for   to n

2 		 		  do 

3 		 		 		  for   to n

4 		 		 		 		  do 

5 		 		 		  if t = 2n

6 		 		 		 		  then return i

7 		  return NULL
```
(a)
When n=3 and , what does L(A,n) return?

(b)
Give the worst-case running time using notation.

(c)
Give the best-case running time using notation.
The mode of a sequence of numbers is the number that occurs most frequently among the elements of the sequence. So, for example, the mode of is 2, because it occurs 3 times in the sequence, which is more frequently than any other element.
Write an algorithm (using pseudocode) to find the mode of a sequence A of integers. Your algorithm should take time, where n is the number of elements of A. If necessary, you may make calls to any of the algorithms we have discussed in class.
Here is a modified version of MERGE-SORT, that partitions sequences into 3 parts rather than 2. For purposes of this problem, you may assume that the number of elements in the input sequence A is a power of 3.
```
 
MERGE-SORT-THREE(A,p,r)

1 		  if p<r

2 		 		  then 

3 		 		 		 MERGE-SORT-THREE(A,p,a)

4 		 		 		 MERGE-SORT-THREE(A,a,2a)

5 		 		 		 MERGE-SORT-THREE(A,2a,r)

6 		 		 		 MERGE(A,p,a,2a)

7 		 		 		 MERGE(A,p,2a,r)
```
Recall that MERGE(A,i,j,k) merges the sorted elements from i to j, and the sorted elements from j+1 to k, into a single sorted sequence from i to k.
Write a recurrence for the running time of MERGE-SORT-THREE on a sequence A consisting of n elements, and solve it to obtain the running time using notation.
Recall the algorithm RANDOMIZED-SELECT:
```
 
RANDOMIZED-SELECT(A,p,r, i)

1 		  if p=r

2 		 		  then return A[p]

3 		  RANDOMIZED-PARTITION(A,p,r)

4 		 

5 		  if 

6 		 		  then return RANDOMIZED-SELECT(A,p,q,i)

7 		 		  else return RANDOMIZED-SELECT(A,q+1,r,i-k)
```
In class, we showed that RANDOMIZED-PARTITION is correct: it permutes its input and returns q, such that for all and satisfying , . Furthermore, the partition is nontrivial: .
Using the correctness of RANDOMIZED-PARTITION, show that RANDOMIZED-SELECT correctly returns the i'th order statistic among elements p through r of sequence A.
Recall the MATRIX-CHAIN-ORDER algorithm:
```
 
MATRIX-CHAIN-ORDER(p)

1 		  length-1

2 		  for   to n

3 		 		  do 

4 		  for   to n

5 		 		  do for   to n-l+1

6 		 		 		  do 

7 		 		 		 		 

8 		 		 		 		  for   to j-1

9 		 		 		 		 		  do 

10 		 		 		 		 		 		  if 

11 		 		 		 		 		 		 		  then 

12 		 		 		 		 		 		 		 		 

13  return m and s 
```
Upon termination, contains the minimum number of multiplications required to multiply the matrices in the given chain p. Modify the algorithm so that it computes an additional matrix a, such that upon termination, contains the number of distinct ways there are to obtain this minimum number of multiplications. That is, you want to compute the number of different ways there are to parenthesize the chain of matrices and still obtain the minimal number of multiplies.
If you want, you can just specify modifications to the pseudocode, but be precise (for example, ``modify line 3 to read... include the following line between lines 12 and 13 so that it is within the scope of the then on line 11...'').