Sample Final Examination

This is a sample examination intended to provide an overview of the types of problems that will appear on the final examination. These problems are not intended to give a comprehensive view of topics. As the sample exam suggests, problems may cover a variety of approaches.

The sample exam also provides the draft policies for the final examination. Although the sample policies indicate that you may not discuss the actual final exam, you should feel free to discuss this sample final examination with anyone you’d like.

Policies for the final examination

1. This is a closed book examination. You may not rely on notebooks, papers, computers, colleagues, or anything similar. You may, however, refer to two 8.5 x 11 inch or A4, double sided, normal thickness, set of notes that you brought to this exam. You may also refer to printed copies of the course textbooks; a few will be available in the classroom.

2. This is also a paper examination. Answer all problems in pen or pencil on blank pieces of paper and then staple them together. You may use additional blank pieces of paper as scratch, provided you turn them in at the end of the examination.

3. You have received a cover sheet for this exam with a number on it. Please write your name on the cover sheet. Please write your number (not your name) on each of the non-scratch pages you turn in.

4. There are five problems on this exam. They are not necessarily of equal difficulty.

   Five correct or mostly correct solutions will earn you an A. Four correct or mostly correct solutions will earn you a B. Three correct or mostly correct solutions will earn you a C. Two correct or mostly correct solution will earn you a D. One correct or mostly correct solutions will earn you an F. Zero correct or mostly correct solutions will earn you a zero.

   Partially correct solutions may or may not earn you a higher grade, at the discretion of the grader.

5. Many of the problems ask you to write code. Although you need not write correct working code, your code should be of sufficient quality that the grader can be confident that you would be able to make it work correctly with minimal effort.

6. Other people may be taking this exam (or a similar exam) at another time. You may not discuss this examination with anyone.

7. After you have completed the examination, please write, sign, and date the following statements on the cover sheet:

   I have neither received nor given inappropriate assistance on this examination.

   I am not aware of any other students who have given or received inappropriate assistance on this examination.

   If you do not feel that you can sign either of these statements, please arrange to meet with me as soon as possible.

8. Please arrange the remaining sheets in order by problem number, make sure you’ve written your number and the page number on the top of each sheet, and then staple them together without the cover sheet.

9. Please turn in this examination, the cover sheet, the stapled pages, your notes (if used), and your scrap paper.

Problem 1: Algorithm design techniques

We have considered a wide variety of algorithm design techniques this semester (other than just “work an example by hand” and “think about it for awhile”). List four and give an example of each.

Problem 2: Insertion in 2-3 Trees

Consider the following 2-3 tree

                        +---+---+
                        | H | S |
                        +---+---+
                 
        +---+           +---+---+             +---+
        | E |           | J | M |             | U |
        +---+           +---+---+             +---+

+---+---+   +---+   +---+ +---+ +---+---+   +---+  +---+---+
| A | D |   | F |   | I | | K | | O | R |   | T |  | W | Z |
+---+---+   +---+   +---+ +---+ +---+---+   +---+  +---+---+

a. Show the steps involved in inserting B.

b. Show the steps involved in inserting G.

c. Show the steps involved in inserting Q.

d. Show the steps involved in inserting C.

Problem 3: Approximate string matching

Note: This example was generated quickly. You may want to come up with your own.

Suppose that insert, delete, and swap all cost 1 and replace costs 2. Complete the approximate matching table that allows us to find the optimal alignment of ababa in the string abbacaabbbaabba.

        a   b   a   b   a
  +---+---+---+---+---+---+
  | 0 |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
c |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
b |   |   |   |   |   |   |
  +---+---+---+---+---+---+
a |   |   |   |   |   |   |
  +---+---+---+---+---+---+

Problem 4: Efficiency

If we treat the number of stamp prices as a constant, the dynamic programming solution to the problem of finding the minimum number of stamps for a price of n is O(n). Explain why that makes it an algorithm that is exponential in the problem size.

Problem 5: Maximum flow

Note: This example was generated quickly. You may want to come up with your own.

Sketch the following graph and then show the steps that the Ford-Fulkerson algorithm takes in finding the maximum flow from A to Z in that graph. Assume that the breadth-first-search algorithm (used to determine an augmenting path from A to Z) visits neighbors in alphabetical order.

• A->B: 5
• A->C: 4
• A->D: 2
• A->E: 2
• B->C: 2
• B->G: 3
• C->D: 1
• D->H: 4
• E->D: 1
• C->I: 5
• H->C: 2
• G->Z: 3
• H->Z: 4
• I->Z: 5

Problem 6: Longest path

Assume that G is an acyclic graph. Write an efficient algorithm to find the longest path from s to t in G.

Problem 7: 0/1 knapsack problem

A greedy solution to the 0/1 knapsack problem is to repeatedly take the item with the best cost/weight ratio. Provide an example in which the that algorithm does not find the optimal solution.

Extra credit: What is the upper bound, if any, of the ratio of the value of the optimal solution to the value of the greedy solution? Give an example that provides that ratio (or close to it).

Problem 8: Loop invariants

Consider the following partial implementation of insertion sort in C.

void
insertion_sort (int values[], int n)
{
  for (int pos = 1; pos < n; pos++)
    {
      // Insert the value at position pos into the left subarray
      int i = pos;
      // INVARIANT NEEDED
      while (TEST)
        {
          // CODE AND INVARIANT CHECKS NEEDED
        } // while
      // SOME USEFUL CONCLUSION
    } // for pos
} // insertion_sort

Add the invariant, loop test, and code to the inner loop. Indicate how the steps maintain the invariant and lead to loop termination. Then provide a conclusion that is useful for insertion sort.