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 |
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.
It is expected that students have studied the material introduced in class, including and ending with the lecture 15 and tutorial on queues.
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.
Consider the problem of finding the smallest entry of an integer array. This problem might be specified as follows.
Precondition:
- A is an integer array with positive length.
Postcondition:
- The value returned is the smallest entry of the array A.
- 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 }
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.
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; }
Of course, you should make sure that the bounds you give are accurate — and (asymptotically) as tight as you can make them.
Prove that n2−2n+1 ∈ Θ(n2).
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 |