COMP 401Spring 2008401-21a.1COMP 401Spring 2008Exercises for Stanat & Weiss, Chapter 2These exercises are intended to develop your skill in reading and understanding simple assertions. In each of the following, letters represent integer or real program variables. Translate each assertion to an appropriate boolean expression. Note that Java does not allow, for example, expressions such as 'x < y < z.' Give your answer in as simple a form aspossible. Although Java does not support the implication operator, you can use P => Q in your answers as a shorthand for (! P || Q). While they are equivalent, the shorthand form is a lot more illustrative of what’s intended.Part I1. x is equal to the smaller of y and z. (Hint: use Math.min)x = Math.min(y,z) also (x == y && y <= z) || (x == z && z <= y)2. 3 is not a divisor of x.x % 3 != 0.3. x is greater than y or x is less than z, and possibly both.(x > y) || (x < z)4. x is not the smallest value of x, y and z.(x >= y) || (x >= z) also: !((x < y) && (x < z)) 5. not both x and y are greater than z.(x <= z) || (y <= z) also: !((x>z) && (y>z))6. If x is not larger than y, then the value of w is 10. (This asserts (x <= y) implies (w == 10) )((x<=y)) => (w == 10) also: (x > y) or (w == 10)7. When x is less than y, then y is less than z, and when x is at least as large as y, then y is equal to w.((x < y) => (y < z)) && ((x >= y) => (y == w)) also ((x >= y) || (y < z)) && ((x < y) || (y == w)) 8. y is not even if x is even . (Hint: Use the mod (%) operation.)x % 2 == 0 => !(y % 2 == 0)9. x is not a divisor of y when y is a multiple of 3(y % 3 == 0) =>!(y % x == 0) also (y % 3 == 0) =>(y % x != 0)In the following, B and C are integer arrays. Assume the arrays and all variables have been declared and initialized so that all the following statements make sense. Variables used to specify subarrays (e.g., lo, hi, n, etc.) are all initialized and within the range of the array indices. Moreover, in any reference such as B[r...s], assume that r s+1. (Note that if r = s+1, then the expression B[r...s] denotes the empty array. If r > s+1, the expression B[r...s] is undefined.) Using the quantifiers defined in the chapter on assertions, express the following assertions formally.Example: All the entries of B[0..10] are zero. (Ai: 0 <= i <= 10: B[i] == 0)401-21a.210. Some entry of B[lo...hi] is negative.(Ei: lo <= i <= hi: B[i] < 0)11. All entries in C[0...10] are equal.(Ai,j: 0 <= i,j <= 10: C[i] == C[j)) 12. Not all entries in C[0...10] are equal.(Ei,j: 0 <= i, j <= 10: C[i] != C[j]) also: !(Ai,j: 0 <= i,j <= 10: C[i] == C[j])13. The two first entries of B[0...10] are zero. B[0] == 0 && B[1] == 014. The entries of B[0...2] are sorted in increasing order. B[0] <= B[1] <= B[2]15. The entries of B[0...100] are sorted in increasing order.(Ai: 0 <= i < 100: B[i] <= B[i+1]) also (Ai,j: 0 <= i < j <= 100: B[i] <= B[j]) also (Ai,j: 0 <= i,j <= 100: (i < j) => (B[i] <= B[j]))16. The entries of B[0...100] are all between low and high. (Ai : 0 <= i <= 100 : low < B[i] < high) Note: 'between' is often ambiguous. This might have meant either < or <=17. C[lo...hi] contains at least two zeroes. Hint: requires two variables.Ei,j: lo <= i < j <= hi: C[i] == 0 && C[j] == 0) also: Ni: (lo <= i <= hi) : C[i] == 0) >= 218. Every value of B[0...k] occurs in C[r...s].(Ai : 0 <= i <= k : (Ej : r <= j <= s : B[i] == C[j])) also (Ai Ej : (0 <= i <= k) && ( r <= j <= s) : B[i] == C[j])) 19. Each of the entries of B[low1...high1] is larger than any entry of C[low2...high2]Ai,j : (low1 <= i <= high1) && (low2 <= j <= high2) : B[i] > C[j]20. One value in B[0...100] is larger than all the others.(Ei: 0 <= i <= 100: (Aj: 0 <= j <= 100 && j != i : B[i] > B[j])) also (EiAj: 0 <= i ,j<= 100: (B[i] >= B[j]) && (B[i] == B[j] => (i == j)))also (Ni: 0 <= i <= 100: B[i] == (Max k: 0 <= k <= 100: B[k])) == 121. The values in C[0...r] are all larger than the values in C[r+1...n].Ai,j : (0 <= i <= r < j <= n) : C[i] > C[j]22. The values stored in C[0...n] are successive powers of 2, beginning with C[0] == 20 == 1.(Ai : 0 <= i <= n : C[i] == 2i) 23. Each of the integers 0 through n is stored in some location of the array C[0...n].(Ai : 0 <= i <= n : (Ej : 0 <= j <= n : C[j] == i))24. If any of the entries of B[0...n] is 0, then k == 1.(Ei: 0 <= i <= n: B[i] == 0) => (k == 1) also (Ai: 0 <= i <= n: (B[i] = 0) => k = 1)25 For B[0...n], whenever B[i] is equal to i, C[i] is 0.401-21a.3(Ai : 0 <= i <= n : ((B[i] == i) => (C[i] == 0))) 26. The value of the variable named count is the number of zeroes stored in B[0...n] Hint: Use the quantifier 'N'count == (Ni : 0 <= i <= n : B[i] == 0)27. For 0 <= i <= n, the value of B[i] is the sum of the first i entries of C[0...n] (Ai : 0 <= i <= n : B[i] == (Sj : 0 <= j <= i: C[j]))28. The value stored in the variable named biggest is at least as large as any entry in B[0...k]. Hint: Use the quantifier 'Max'biggest >= (Max i: 0 <= i <= k : B[i]) also (Ai : 0 <= i <= k : biggest >= B[i])29. For every i from 0 to k, the value stored in B[i] is the number of occurrences of the integer i in the array C[0...n].(Ai : 0 <= i <= k : B[i] == (Nj : 0 <= j <= n : C[j] == i))30. The array A[0...100] has an entry that is larger than any of the entries of C[0...100](Max i:0 <= i <= 100: B[i]) > (Max i:0 <= i <= 100: C[i]) 31. Each entry (except the last) of the array B[0...n] is a divisor of the next one.(Ai: 0 <= i < n : B[i+1] % B[i] == 0)32. Each entry (except the first …
View Full Document
Unlocking...