Worksheet solutions, Data Structures and Algorithms, Week 6 -- Thurs Nov 1 2001

  1. Write the negation of each of these boolean expressions, without using the negation operator !:
    b.  x == y b.  x < y c.  a > b d.  x < y && a > b
    x != y x >= y a <= b x >= y !! a <= b
    (!= is not !) (apply DeMorgan's law)

  2. Assume this boolean expression is true: 
    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
    true false false true
    (One conjunct is false) (One disjunct is true)
    e.  !(x < y && a > b) f.  x >= y || a <= b g.  x < y && !(a > b) h.  x < y && a <= b
    true true true true
    (negation of d.) (DeMorgan applied to f.) (Same as g., rewrite negation)
    i.  c == y*z + x j.  y*y <= a && a < (y+1)*(y+1)
    true true
    (Integer division: 7 = 2*3 + 1) (Integer square root: 2*2 <= 4 < 3*3)
    i.  y*y <= b && b < (y+1)*(y+1) j.  z*z <= b && b < (z+1)*(z+1)
    true false
    (Integer square root: 2*2 <= 6 < 3*3) (Integer square root: not 3*3 <= 6 < 4*4)

  3. In each code fragment, assume the boolean expression in the first comment is true when execution reaches the first statement in the fragment. Is the boolean expression in the second comment necessarily true when execution exits the fragment?
    a. 
    // true

x = 1

// x == 1
    Yes (true here means "start in any state")     		b. 
    
// x == 1

x = x + 1

// x == 2
    Yes     		c. 
    
// true

x = 1 

x = x + 1

// x == 2
    Yes (a., then b.)     		d. 
    
// true

x = x + 1

// x == 2
    No (Only necessarily true when x == 1 initially)
    e. 
    
// x == 1 

x = x + 1

// x > 2
    No (x ==2, see b.)     		f. 
    
// x > 1 

x = x + 1

// x ==  2
    No (x > 2)     		g. 
    
// true 

r = n

q = 0

// n = q*d + r
    Yes (n = 0*d + n)     		h. 
    
// n = q*d + r

r = r - d

q = q + 1

// n = q*d + r
    Yes (n = (q+1)*d + (r - d))