SUNY Geneseo Department of Computer Science

Introduction to Proof

Return to List of Lectures

Misc

Revised office hours for Mondays: 3:00 - 4:00 PM

Problem set 1 grading may be tight today, if no times work for you, grade it tomorrow

Questions?

Grading lab? Bring executable copy e.g., on your own laptop or we'll go to lab

Theoretical Reasoning about Algorithms

Sections 3.1 - 3.4, 3.6

• Proofs, theorems
• "Important Latin words" = modus ponens
  • Deductive reasoning
  • If a implies b, and you know a, then you conclude b
• Initialization
• Efficiency of programs

Example

• Two common mathematical ideas that appear in computer arithmetic, but are often misunderstood and/or mis-implemented.
  • floor(x) = the largest integer ≤ x
    • floor(3.11) = 3, floor(3.99) = 3, floor(3) = 3
    • Often implicit in integer division
    • i.e., x/y in a program returns mathematical floor(x/y) if x and y are ints
  • a mod b = the integer m such that 0 ≤ m < b and there is some other integer k such that a = kb + m. Defined for integers a, b, b > 0
    • i.e., the remainder when a is divided by b
    • Implemented as % operator in many languages, e.g., a % b
    • Except % often produces a negative result if a is negative
• Prove that, given preconditions that x and y are integers, y > 0,

        ( x - x mod y ) / y

• is an algorithm for computing floor(x/y)
• Testing
  • x = 4, y = 2, floor(4/2) = 2
    • Check: ( x - x mod y ) / y
    • = ( 4 - 4 mod 2 ) / 2
    • = 4 / 2
    • = 2
  • Test where floor truncates. x = 7, y = 3, floor(7/3) = 2
    • Check: ( x - x mod y ) / y
    • = ( 7 - 7 mod 3 ) / 3
    • = ( 7 - 1 ) / 3
    • = 6 / 3 = 2
• Intuition: x mod y is remainder from x/y, subtracting remainder from x gives a whole multiple of y, thus division produces integer
• Proof: go step by step through algorithm, showing steps lead to postcondition
  • Think of x as ky + (x mod y), k integer
  • Therefore x - x mod y = ky
  • Therefore ( x - x mod y ) / y = ky / y = k
  • Which is an integer
  • But is k the biggest such integer?
    • Suppose k wasn't biggest, c > k is an integer such that cy + r = x
    • c is at least k+1
    • if ky + (x mod y) = x, then (x mod y) is at least y + r
      • i.e., cy + r ≥ (k+1)y + r = ky + 1y + r
      • So x mod y ≥ y + r
    • If r ≥ 0, then x mod y ≥ y + r ≥ y, impossible
    • If r < 0, then cy > x, c not floor x/y
    • Proof by contradiction

Hand out problem set 2

Hand out lab 2

Next

The scientific method and algorithms

Read sections 4.1 through 4.7