SUNY Geneseo Department of Computer Science

Proving Loop Invariants and Loop Performance

Return to List of Lectures

Misc

Problem Set 9 due today, Lab 6 tomorrow

I'm out of town Wednesday through Friday this week

• Lectures covered by David Meisel
  • Wednesday: Feedback re course progress
  • Friday: Algorithmic issues in Dr. Meisel's work
• Lab done more or less on your own, except...
  • I should be accessible via e-mail
  • CS Learning Center available for questions
    • In printer room between labs

Questions?

isPowerOf2(n)

• Invariant: n₀ = n_i 2ⁱ
• Example: consider isPowerOf2( 13 )
  • n₀ = 13
• Typo! If i is the iteration number, invariant should be n₀ = n_i 2^i-1
• Think about start of first iteration, i.e., i = 1
  • n_i = value of n where loop invariant holds in iteration i, i.e., value of n at beginning of i-th iteration of loop
  • n₁ = 13 because n hasn't changed since start
  • Loop invariant? n₀ = n_i 2^i-1? 13 = 13 2^1-1 = 13 2⁰ = 13
• Induction step for proving invariant
  • If invariant holds at start of iteration i
    • n₀ = n_i 2^i-1
  • Does invariant hold at start of iteration i+1?
    • i.e., n₀ = n_i+1 2ⁱ
  • Does n_i 2^i-1= n_i+1 2ⁱ
    • Express n_i+1 in terms of n_i
      • n_i+1 = n_i / 2
    • n_i+1 2ⁱ = n_i / 2 2ⁱ = n_i 2^i-1

Analyzing Loops' Performance

Section 9.1 through 9.1.3

• Number of steps executed in loop
• Best vs worst cases
• Number of iterations needed
• Number of steps per iteration also needed
• Same number of steps in each iteration -> multiply number of steps by number of iterations
• Otherwise do explicit sum of steps over iterations, find closed form
• Number of steps depends on what you want to measure

Hand out Lab 7

• Is this Θ(n²) time good, bad, irrelevant, ...?

Next

Dr. Meisel Wednesday and Friday

After break (!)

• Analysis of insertion sort