The final exam will be cover all of the topics I listed for the first two midterms, with the exception of proof of correctness and dynamic programming.
Of the new material we covered since the second midterm, the only two chapters I am going to ask questions about are chapter 16 (Amortized Analysis) and chapter 26 (Parallel Algorithms).
Here are some end-of-section problems from the text for you to review in preparation for the final:
16.1-3
16.3-3
16.3-5
16.4-4
26.2-4
Since there are not many good questions in chapter 26, here are a couple of additional practice problems for that chapter:
Consider the algorithm that I asked you to implement for the chapter 20 homework problem. Are there any opportunities in this algorithm to take advantage of parallel processing? Try writing out pseudocode for this algorithm making use of spawn/sync and/or parallel for loops in places where you think it is appropriate to do so.
Read about the Counting Sort algorithm in section 8.2 in the textbook. Are there any opportunities in this algorithm to take advantage of parallel processing? Rewrite the psuedocode for this algorithm making use of spawn/sync and/or parallel for loops in places where you think it is appropriate to do so.
// Counting sort from chapter 8 Counting-Sort(A,n,k) let B[1:n] and C[0:k] be new arrays for i = 0 to k C[i] = 0 for j = 1 to n C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i for i = 1 to k C[i] = C[i] + C[i-1] // C[i] now contains the number of elements less than // or equal to i. // Copy A to B, starting from the end of A // "Simplified" Counting sort Counting-Sort(A,n,k) let B[1:n], C[0:k], CC[0:k] be new arrays for i = 0 to k C[i] = 0 for j = 1 to n C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i CC[0] = 0 for i = 1 to k CC[i] = C[i] + CC[i-1] // CC[i] now contains the number of elements less than // or equal to i. // Copy A to B for i = 1 to k for j = 1 to C[i] B[CC[i-1] + j] = i // The parallel solution Count(A,p,q,k) let C[0:k] be a new array parallel for i = 0 to k C[i] = 0 for j = p to q C[A[j]] = C[A[j]] + 1 return C Parallel-Counting-Sort(A,n,k) let B[1:n], C[0:k], CC[0:k] be new arrays parallel for i = 0 to k C[i] = 0 C1 = Count(A,1,n/2) spawn C2 = Count(A,n/2+1,n) sync parallel for i = 0 to k C[i] = C1[i] + C2[i] // C[i] now contains the number of elements equal to i CC[0] = 0 for i = 1 to k // Ok as is, 1 to k is not many numbers CC[i] = C[i] + CC[i-1] // CC[i] now contains the number of elements less than // or equal to i. // Copy A to B parallel for i = 1 to k parallel for j = 1 to C[i] B[CC[i-1] + j] = i