CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Show your work or otherwise explain where your answers come from - unsupported answers (just giving a big-Oh) will receive little or no credit.
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
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
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 Θ(n2) time when applied to n✕n matrices.
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);
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);