CSI 2101 Study Guide - Quiz Guide: Loop Invariant, Quadratic Equation, Liquid Oxygen
9 Oct 2021
School
Department
Course
Professor
Document Summary
Due: thursday, april 5, at 1:00pm (in lecture) Program veri cation, recurrence relations: consider the following program that computes quotients and remainders: r a; q 0; while r d do begin r r d; q q + 1; end. To show that p is a loop invariant, we must show that: p is true before the loop executes. Since a is a positive integer and r a before the loop executes, we have that r 0. Since q 0 before the loop executes, then qd + r = 0d + a = a. Thus, p is true before the loop executes: if p is true before the loop is executed, then p is true after the loop executes. Assume that p is true before the loop is executed. Then, after the loop executes, we have the new values rn = r d and qn = q + 1.
