|
![]() |
![]() |
![]() |
![]() |
Due: Wednesday, Jan. 18, at 11 pm.
Sunday, Jan. 22, at 11 pm; no late days allowed and no assignments accepted after that time. You may turn in part 1 on paper during office hours Friday Jan. 20 from 3:30-4:30, or in the lab on Sunday Jan. 22 from noon to 1:30. Part two should be turned in online by the deadline, and you can also turn in an electronic copy of your solutions to part 1 online by that time instead of handing in a paper copy.
Answer the following questions on paper. In questions that ask for proofs of algorithms or code you only need to show that the code is correct; you do not need to prove termination. You do not need to show all of your intermediate work, but your answers and proofs should be clear and easy to follow.
items[0..size-1]
. In our code, the loop had the following invariant:
max = largest value in items[0..k-1]Suppose we had used the following slightly different invariant instead:
max = largest value in items[0..k](The difference is that the upper bound of the array section is
k
instead of k-1
.)int expt(int x, int y) { int z = 1; while (y > 0) { if (y % 2 == 0) { y = y/2; x = x*x; } else { z = z*x; y = y-1; } } return z; }Give a proof that this code is correct. A suitable precondition for the function would be
x==X && y==Y && X>=0 && Y>=0
, and an appropriate postcondition would be that the returned value z==X^Y
. (We define 0^0 to be 1.) You will need to develop a loop invariant and pre- and post-conditions for the statements inside the loop
, and verify that the code has the necessary properties to ensure that these assertions hold. You are not required to give pre- and post-conditions for each individual assignment statement inside the if
if these are not needed to clearly show the code is correct, but you should include whatever is needed so that the grader can follow your proof and see that it is valid.a
containing n
elements and would like to develop an algorithm
to rearrange the array elements as follows and prove that the algorithm is correct.
If the original elements of the array are A[0], A[1], ..., A[n-1],
we would like to rearrange the array so that all of the elements less than or equal to the
original value in A[0] are at the beginning of the array, followed by the value originally stored in A[0],
followed by all the elements in the original array that are larger than A[0].
In pictures, the postcondition we want is the following:
0 n +-------------+----+---------------+ a| <= A[0] |A[0]| >A[0] | +-------------+----+---------------+The operation
swap(a[i],a[j])
can be used to interchange any pair of elements
in the array, and this is the only operation that can be used to modify the contents of the array.
(As a result of this restriction, the array will be a permutation of its original contents, so you do not need
to prove this.) Your code should run in linear (O(n)) time.A[0]
into new locations. Try different invariants and see which one makes things simplest. Also remember that you can include additional statements before and after the main loop if useful to establish the loop invariant or the postcondition.a
containing n
integer values. The precondition is that the array contains n
integer values in some unknown order. The postcondition is that the array holds a permutation of the original values such that a[0] <= a[1] <= ... <= a[n-1]
. As in the previous problem you should use the operation swap(a[i],a[j])
to interchange array elements when needed.a[0]
. (If a[0]
is the smallest element in the original array it is fine to swap it with itself to avoid having additional special cases in the code.) Next we find the smallest element in the remaining part of the array beginning at a[1]
and swap it with a[1]
. Then we find the smallest element in the remaining part of the array starting at a[2]
and move it to the front of that part of the array. This search-and-swap operation continues on the successively smaller remaining parts of the array until all elements are sorted.
![]() |
Computer Science & Engineering Box 352350, University of Washington Seattle, WA 98195-2350 (206) 543-1695 [comments to Hal Perkins] Privacy policy and terms of use |