Tutorial 9, CPSC 331, Winter 2012

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23

 Term Test 1 Review

About This Exercise

This exercise can be used by students as part of their efforts to prepare for Term Test #1.

Students should work through this exercise and be ready to discuss it (or ask questions about it) before attending the tutorial.

Expected Background

It is expected that students have studied the material introduced in class, including and ending with the lecture 15 and tutorial on queues.

Sample Problems

Here are a few problems that resemble ones that have been used in term tests for this course in the past.

There is, of course, no guarantee that similar ones will be used again this year — but they do test your understanding and ability to apply the material that is to be assessed on the upcoming term test, and they are reasonable test questions.

  1. Consider the problem of finding the smallest entry of an integer array. This problem might be specified as follows.

    Precondition:

    1. A is an integer array with positive length.

    Postcondition:

    1. The value returned is the smallest entry of the array A.
    2. The array A has not been changed.

    An algorithm that solves this problem is as follows.

    int minElement(int[] A) { int current = A[0]; int i = 1; while (i < A.length) { if (A[i] < current) { current = A[i]; }; i++; }; return current }

    1. State the definition of a loop invariant.
    2. Give a (correct!) loop invariant for the while loop in the above program.
    3. State the definition of a loop variant.
    4. Give a (correct!) loop variant for the while loop in the above program.

  2. Give two tests that could be used during dynamic testing of the above program. Try to make your tests varied — that is, make sure that they are not checking the same thing.

    For each of your tests, describe what it is that is being checked.

  3. Consider the following program, which can be used to determine whether the entries of a given nonempty integer array are listed in increasing order.

    boolean isSorted(int[] A) { int i = 0; /* * Loop Invariant: * a) i is an integer such that 0 ≤ i < A.length−1 * b) A[j] ≤ A[j+1] for every integer j * such that 0 ≤ j < i * c) A has not been changed * * Loop Variant: A.length−i−1 * */ while (i < A.length−1) { if (A[i] ≤ A[i+1]) { i++ } else { return false }; }; return true; }

    1. State the definition of the worst-case running time of an algorithm (or program).
    2. Suppose that the documentation for the above program is accurate. Use this to give an upper bound for the worst-case running time for this program, and say briefly how you found your answer.
    3. Now find a lower bound for the worst-case running time of this algorithm as well, and say briefly how you found that.

    Of course, you should make sure that the bounds you give are accurate — and (asymptotically) as tight as you can make them.

  4. Prove that n2−2n+1 ∈ Θ(n2).

    1. Describe a stack, including the operations that this supports as part of your answer.
    2. The lecture on stacks included details about an implementation of a stack using a static array as well as an implementation using a linked list. Describe an advantage that each implementation has over the other (that might influence your decision about which implementation to use).

  6. Describe the main difference(s) between a stack and a (simple) queue, and give a very brief description of an interesting (or important) application of each.

See the previous exercises (including the warmup problems, as well as the longer problems that were discussed during the tutorials for additional kinds of problems you should be ready to solve on the test. Binary trees may also be included, but only basic definitions and properties.

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial9.html