Iterative Algorithms

HTTAA describes the iterative algorithms as being like a long journey where you can't see the entire route and could possibly take a misstep and fall into a ditch, so you need a way to know that you're making progress as well as a way to know you haven't veered off the road. Since we're dealing with repetitions I kind of think a racetrack might make more sense, or at least something that loops, but anyway…

There are some basic questions we have to be able to answer to make a successful trip:

• How do I get onto the road?
• How do I take a step without falling off the road?
• How do I know when I've gone far enough?
• Once I've gone far enough, how do I get off the road and to my ultimate destination?

Too answer these questions we'll be using some basic parts:

• Our starting point is our Preconditions and to get onto the road we need some pre-loop code to set up the Loop-Invariant.
• We take a step with our loop-code and keep from falling off the road by maintaining the Loop-Invariant.
• We know we've gone far enough when our Exit-Condition is met.
• Once we've gone far enough we use some post-loop code to clean up and end up at our Postconditions.

Translating that to mathishness shorthand:

• \( \langle \textit{Pre-Conditions} \rangle \land \text{Code}_\textit{Pre-Loop} \Rightarrow \langle \textit{Loop-Invariant} \rangle \)
• \( \langle \textit{Loop-Invariant} \rangle \land \lnot \langle \textit{Exit-Condition} \rangle \land \text{Code}_\textit{Loop} \Rightarrow \langle \textit{Loop-Invariant'} \rangle \)
• \( \langle \textit{Loop-Invariant} \rangle \land \langle \textit{Exit-Condition} \rangle \land \text{Code}_\textit{Post-Loop} \Rightarrow \langle \textit{Post-Conditions} \rangle \)

• How To Think About Algorithms