- (a)
- 2. Explanation: This algorithm finds the first row whose elements add up to 2n. It returns NULL if there is no such row. L(A,n) returns 2, since the second row's elements sum to 6 = 2n.
- (b)
-
.
Explanation: The outer for loop goes through at most n iterations.
The inner for loop
always goes through n values of j, taking constant time in lines
4-6 each iteration. So the inner loop uses a total of 
time to complete its execution. In the worst case, when the outer loop
iterates n times, executing this complete inner loop each time, total
time is 
.
- (c)
-
.
Explanation: In the best case, the very first row sums to
2n, so that we return before trying any other values of i. We
only execute the inner loop once, for a total of 
time.
MODE(A)1 MERGE-SORT(A,1,length
)
2
3
4
5 for
to
6 do if
7 then
8 if d>m
9 then
10
11 else
12
13 return l
Explanation: We can find the mode by sorting the sequence: then, all duplicates will be next to each other, so that we can easily count how many times each element occurs. In the algorithm above, c holds the current element for which we are counting number of occurrences, d holds the number of occurrences of this element so far, m holds the maximum number of occurrences of any element so far, and l holds this maximally-occurring element.
Line 1, MERGE-SORT, takes 
time, and the remainder
of the algorithm loops through the elements once, spending constant time
on each, for a total of 
time. So, total time is 
as required.
Using the master method, case 2 applies, since 
, which is the same as 
here. The solution given by
case 2 is:
Explanation:
Let 
be the time to sort a sequence of length n.
Lines 1-2 take constant time. Each of lines 3-5 is a recursive call
on exactly 
elements (this is always possible since n is
assumed to be a power of 3). Lines 6-7 take 
time, as shown
in class. This gives the recurrence:
The master theorem is then applied with a=3, b=3, and 
.
Since 
, 
, so
we are in case 2 of the master theorem, which tells us:
Now assume that RANDOMIZED-SELECT is correct for less than n elements
(this is the induction hypothesis), and show it is
correct for n elements (with n>1 now). Line 1's check fails, so execution
continues on line 3. By the correctness of RANDOMIZED-PARTITION, 
holds the smallest k elements of 
after line 3,
and 
holds the n-k largest elements. Since the
partition is nontrivial, 
,
so the recursive calls on lines 6-7 are on fewer than n
elements and therefore return correct values by the induction
hypothesis. We are looking for the i'th smallest
element of 
. So, if
then this is the i'th smallest element among the k
smallest elements of 
:
in this case, the recursive call on line 6
returns this value. Otherwise, the i'th smallest element
is the i-k'th smallest among the n-k largest elements of
: line 7 correctly returns this value in this case.
By induction, RANDOMIZED-SELECT is correct for all values of n.
Insert the following line between lines 11 and 12:
Insert the following two lines between lines 12 and 13; the else here is attached to the if on line 10:
else if
then
Finally, change line 13 to be:
13 return m and s and a
Explanation: Initialize each 
to one since there is only one
way to parenthesize a single matrix. When a new minimum number of
multiplications is found, initialize the corresponding a entry with
the total number of ways to combine a minimal parenthesization on the
left side of the split with a minimal parenthesization on the right side. The
total number of ways to combine these is the product of the numbers of optimal
parenthesizations on either side of the split. When a different split
yields the same number of multiplications as the minimum, increase the
corresponding a count by this product of the numbers on either side of
the split.