Homework 2
due Wed 1/31 in class

Show your work or otherwise explain where your answers come from - unsupported answers (just giving a big-Oh) will receive little or no credit.

1. Give the Θ running time for bubble sort. Identify best- and worst-case times separately if there is a difference.

   algorithm bubbleSort ( A, n ) :
     input: array A storing n items
     output: items in A are sorted in increasing order
   
     repeat
       swapped ← false
       for ( j ← 0 ; j < n-1 ; j++ ) do
         if A[j] > A[j+1] then	 // if elements are reversed...
           temp ← A[j]		 // ...swap them
           A[j] ← A[j+1]
           A[j+1] ← temp
           swapped ← true
     until swapped is false
   

2. We try to improve bubble sort by allowing elements that are far out of place to move more than one spot at a time - 'gap' defines this amount, and shrinks as elements (presumably) get closer to their final spots as the algorithm progresses.

   Give the Θ running time for comb sort. Identify best- and worst-case times separately if there is a difference.

   algorithm combSort ( A, n ) :
     input: array A storing n items
     output: items in A are sorted in increasing order
   
     gap ← n
     repeat
       gap ← gap/s
       swapped ← false
       for ( j ← 0 ; j < n-gap ; j++ ) do
         if A[j] > A[j+gap] then // if elements are reversed...
           temp ← A[j]		  // ...swap them
           A[j] ← A[j+gap]
           A[j+gap] ← temp
           swapped ← true
     until gap == 1 and swapped is false
   

3. A matrix is a 2D array of numbers. A key operation involving matrices is matrix multiplication.

   This problem involves two algorithms for matrix multiplication. Both algorithms involve partitioning, in which an n✕n matrix is split into four n/2✕n/2 matrices as shown.

   

   For each of the following matrix multiplication algorithms, write the recurrence relation for and give the running time of multiply. The operations extractBlock, assembleBlocks, add, and subtract all take Θ(n²) time when applied to n✕n matrices.

   1. The basic algorithm for multiply(A,B) computes C as follows:

      

      This can be written in pseudocode as shown:

        algorithm multiply ( A, B ) :
           input: A, B are nxn arrays
           output: C = A✕B
      
           A11 = extractBlock(A,0,0)
           A12 = extractBlock(A,0,n/2)
           A21 = extractBlock(A,n/2,0)
           A22 = extractBlock(A,n/2,n/2)
      
           B11 = extractBlock(B,0,0)
           B12 = extractBlock(B,0,n/2)
           B21 = extractBlock(B,n/2,0)
           B22 = extractBlock(B,n/2,n/2)
      
           C11 = add(multiply(A11,B11),multiply(A12,B21))
           C12 = add(multiply(A11,B12),multiply(A12,B22))
           C21 = add(multiply(A21,B11),multiply(A22,B21))
           C22 = add(multiply(A21,B12),multiply(A22,B22))
      
           C = assembleBlocks(C11,C12,C21,C22);
      

   2. A more clever approach for multiply(A,B) instead computes C as follows:

      

      where the M_i are n/2✕n/2 matrices computed as follows:

      

      This can be written in pseudocode as shown:

        algorithm multiply ( A, B ) :
           input: A, B are nxn arrays
           output: C = A✕B
            
           A11 = extractBlock(A,0,0)
           A12 = extractBlock(A,0,n/2)
           A21 = extractBlock(A,n/2,0)
           A22 = extractBlock(A,n/2,n/2)
      
           B11 = extractBlock(B,0,0)
           B12 = extractBlock(B,0,n/2)
           B21 = extractBlock(B,n/2,0)
           B22 = extractBlock(B,n/2,n/2)
      
           M1 = multiply(add(A11,A22),add(B11,B22))
           M2 = multiply(add(A21,A22),B11)
           M3 = multiply(A11,subtract(B12,B22))
           M4 = multiply(A22,subtract(B21,B11))
           M5 = multiply(add(A11,A12),B22)
           M6 = multiply(subtract(A21,A11),add(B11,B12))
           M7 = multiply(subtract(A12,A22),add(B21,B22))
        
           C11 = subtract(add(M1,M4),add(M5,M7))
           C12 = add(M3,M5)
           C21 = add(M2,M4)
           C22 = add(subtract(M1,M2),add(M3,M6))
      
           C = assembleBlocks(C11,C12,C21,C22);