Chapters for the second midterm

The second midterm exam will cover proof of correctness, and chapters 14 and 26.

Topics to review

Here are more specific topics you should review:

• Using a loop invariant to prove that an iterative algorithm is correct.
• Solving a problem by recursion, and then converting that solution to a dynamic programming solution.
• Using the span, sync, and parallel for constructs to write pseudocode for a parallel algorithm.

Exam format

The exam will be a written, in-class exam. The exam is a closed book exam, but I will allow you to bring a single page of notes with you to the exam.

Review problems

Here is a list of problems from the text that you can review to prepare for the exam:

2.1-4, 2.2-2, 2-2

14.1-3, 14-2

Sample question

Since the book does not contain any good sample questions for chapter 26, here is a sample question for that chapter:

Suppose we wanted to construct a parallel version of Quicksort. A key step in doing this would be to prepare a version of the partition operation that could take advantage of parallel processing to do the partition step more quickly than the non-parallel version of the partition algorithm. Here is a strategy for doing this:

1. Before starting the Quicksort algorithm, make a temporary array with the same size as the original array and pass this temporary array to both the Quicksort function and the partition function in addition to the usual parameters.
2. Count the number of items greater than the pivot in the subarray you are working with.
3. Copy the items that are less than or equal to the pivot, the pivot, and the items greater than the pivot over to the corresponding portion of the temporary array. As you do so, be sure to place the small items to the left and the large items to the right.
4. Copy all of the items from the temporary array back to the original array.

Write out the pseudocode for the parallel partition algorithm. You may need to write one or more additional functions to help you do what needs to be done here. Supposing you have four cores at your disposal, make the best possible use of all available cores.