What the final exam will cover

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).

Additional sample questions

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:

Parallel problem one

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.

Parallel problem two

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.

Solution

// 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