Discrete Mathematics for Computer Science

560 CHAPTER 9 Recurrence Relations

Algortm Seeto Sor

INPUT: A list of distinct values List[]. List[N]

OUTPUT: List[l],.... List[N] with values in increasing order

SelectionSort(List, N) /* Initial call *!

SelectionSort (List, M) /* Recursive procedure *!

if (M = 1) then

return

else

S = index of maximum element of List[ 1 .. M]

Temp = List[S]

List[S] = List[M]

List[M] = Temp

SelectionSort(A, M - 1)

24. For 2 x 2 matrices, the complexity of matrix multiplication can be determined us-
    ing the algorithm described below where the number of arithmetic operations (ad-
    ditions, subtractions, and multiplications) are one measure of complexity. Let A =
    all a12 ) and B = (bill b
    a21 a22 b 212 ) Calculate

mI = (all a2 2)(biI +-b2 2)

m5 = (a 21 + a2 2)bl 1

M = (all - a 22 )(b 21 + b22)

M6= all(b12 - b22)

m3 = (all - a 21 )(bll + b1 2 )

M7= a22(b21 - biI)

m4 = (all +al 2 )bll

Now, letC= ( Cli C12 " where

(C21 C22/

Cll = ml + m 2 - m 4 + m 7

C12 = m4 + m6

C21 = m5 + m7

C22 = ml - m3 - m 5 + m6