CPSC 327 Data Structures and Algorithms Spring 2024

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 nn 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 Θ(n2) time when applied to nn 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 Mi 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);