Quiz Solutions, Data Structures and Algorithms, Week 6 -- Tues Nov 6 2001

  1. Write the negation of each of these boolean expressions, without using the negation operator !:
    a.  a == b b.  x > y c.  a <= b d.  x > y && a <= b
      a != b   x <= y   a > b   x <= y || a > b
    (!= is not the same operator as !) (not x < y, which is also false when x == y) (not a >= b, which is also true when x == y) (Apply DeMorgan's law, then use b. and c.)

  2. Assume this boolean expression is true: 
    w == 0 && x == 1 && y == 2 && z == 3 && a == 4 && b == 6 && c == 7
    Write the value of each of the following boolean expressions:
    a.  x > y b.  a < b c.  x > y && a < b d.  x > y || a < b
    false (1 > 2 is false) true (4 < 6 is true) false (because operator is and and one operand is false, see a.) true (because operator is or and one operand is true, see b.)

    e.  b == y*z + w f.  c == y*z + x
    true (6 == 2*3 + 0, from integer division example) true (7 == 2*3 + 1, from integer division example)

    g.  y*y <= a && a < (y+1)*(y+1) h.  z*z <= b && b < (z+1)*(z+1)
    true (2*2 <= 4 && 4 < 3*3, from integer square root example) false (3*3 <= 6 && 6 < 4*4 is false, from integer square root example)

  3. In each code fragment, assume the boolean expression in the first comment is true before the program executes the statement. Is the boolean expression in the second commentnecessarily true after the program executes the statement? (Answer yes or no)
    a. 
    // true

x = 1

// x == 1
    		b. 
    
// x > 0

x = x + 1

// x == 2
    		c. 
    
// x == 1

x = x + 1

// x == 2
    Yes No (true only if x == 1 initially) Yes
  4. In each code fragment, assume the boolean expression in the first comment is true before the program executes the statement. Write a boolean expression which is true after the program executes the statement.
    a. 
    // true

x = 3
    // x == 3     		b. 
    
// x > 3

x = x + 1
    // x > 4     		c. 
    
// x > i

x = x + 1
    // x > i + 1

    In each case, I show the strongest (most specific) boolean expression that is true after the statement. (By strongest, I mean the one that allows the fewest possible values of x). There are many other correct answers where the boolean expression is weaker (less specific), for example the expression true is always a correct answer. In b., x > 3 or even x > 0 is also correct, etc.

  5. In each code fragment, assume the boolean expression in the first comment is true before the program executes the missing statement. Write a statement that makes the boolean expression in the second comment true after the program executes the statement.
    a. 
    // true
    x = 6 
    
// x == 6
    		b. 
    
// x > 1
    x = x + 2 
    
// x > 3
    		c. 
    
// x > 2
    x = x + i 
    
// x > i + 2

    In each case, I show the most general statement that ensures the truth of the following boolean expression. (By most general, I mean the one that allows the final value of x to vary over the largest possible range, when the initial value of x varies.) There are many other correct answers where the statement is less general. In b., x = 4 or x = 10 is also correct, etc.

  6. In each code fragment, assume the program executes the statement, and that makes the boolean expression in the following comment true. Write a boolean expression that must be true before the program executes the statement in order for this to be so.
    a.

    // true 
    
x = 4

// x == 4
    		b.

    // x > 2 
    
x = x + 3

// x > 5
    		c.

    // x > 3 
    
x = x + i

// x > i + 3

    In each case, I show the weakest (most general) boolean expression that must be true to ensure that the following statement causes the final expression to be true. (By weakest, I mean the one that allows the largest range of values for x.) There are many other correct answers where the expressions are stronger. In a., any initial boolean expression at all is correct, since the final expression does not depend on the initial expression. In b., x == 3 (or any number larger than 2) is correct.

    The expression before the statement is called the precondition and the expression after is called the postcondition. My solutions show the weakest precondition. These examples are simple enough to see the weakest precondition by intuition (or trial and error), but it is always possible to calculate the weakest precondition for an assignment statement by substituting the expression on the right side of the assignment for the same variable in the postcondition. For example in c., substituting x + i for x in x > i + 3 yields (x + i) > i + 3, which is equivalent to x > 3. This same procedure can be used to confirm the correctness of the solutions to problems 3. and 4.

    Calculating the weakest precondition of a statement (or block of statements) is used extensively in proving code correct, or deriving code from a specification.