401 21a 1 COMP 401 Spring 2008 Exercises for Stanat Weiss Chapter 2 These 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 as possible 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 I 1 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 2 10 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 0 14 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 2 18 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 1 21 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 0 22 The values stored in C 0 n are successive powers of 2 beginning with C 0 2 1 i Ai 0 i n C i 2 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 count Ni 0 i n B i 0 Hint Use the quantifier N 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 one of the array B 0 n is the sum of all the preceding entries Ai 0 i n B i Sj 0 j i B j Part II Assume that all variables …
View Full Document
Unlocking...