Analyzing Code

Algorithmic Design §

• To design sophisticated algorithms, you must get really sophisticated at _communicating _about algorithms.
  • Listening and Speaking
• How do we formally and rigorously discuss the correctness of code?

Divide and Conquer §

• There are two main styles of D&C algorithms, both of which should be familiar
  • Mergesort
    • Divide into two subproblems
    • Recursively solve both subproblems
    • Cleverly merge the solutions
  • Binary Search
    • Cleverly split into 2 subproblems
    • Recursively solve 1 subproblem
• Both styles are clever in different places. Mergesort style is clever about merging solutions, only after both subproblems have been solved
• Binary Search style is clever about picking which subproblem to solve, and then simply making recursive calls
• These are the styles of algorithms that we will start exploring first

Intuition -> Formalization §

• Learn how to formalize concepts that you already are familiar/intuitive so that you can analyze new and unique algorithms.
• This formalization is a form of communication about the very nature of algorithms. How better to convince others about the nature and correctness of your algorithm if not through formalized, provable. communication.
• Visualize a spectrum of communication, with intuition on the left, and formalization on the right. Learn how to intentionally shift your method of communication from one direction to the other, depending on your context and audience.
• How would you argue the correctness of Mergesort?
  • A feature of Mergesort is that it is fast, but analyzing the speed of an algorithm is different from analyzing its correctness
• Induction is how we can cleanly and compactly analyze long sequences of operations.
  • Previously, induction was used to argue claims about numbers, formulas, and relations.
  • How can induction be used to prove things about code?
  • Code execution is a dynamic process. Variables change at every step.
  • How to cleanly capture this with an Inductive Hypothesis, and perform an Inductive Step to draw a conclusion about the correctness?
• A standard Inductive Hypothesis for recursive code is:
  • “my function is correct on all smaller inputs”
  • Where exactly what is meant by “correct” and “smaller” will depend on the specifics of the code
  • e.g., Mergesort Inductive Hypothesis:
    • “Mergesort correctly sorts all arrays of length < n”

Code Example: Iterative Preview §

Func(n):
x <- 5
for i <- 1 to n
  x <- x + 2
output x

• How can induction show that $\text{Func(n)}$ outputs $2n+5$?
• This code is very similar to the recursive definition of a sequence
• Let $F(0)=5$; $F(i+1)=F(i)+2$ for all $i\ge 0$;
• Inductive Hypothesis: ”$F(n)=2n+5$”
• Base Case: choose $n=0$; $F(0)=5$; $F(n)=2(0)+5=5$;
• Inductive Step: $F(n+1)$
  • $=F(n)+2$ (by definition of the recurrence for $F$)
  • $=2n+5+2$ (substitute the induction hypothesis for $F(n)$ )
  • $=2(n+1)+5$ (simple algebra)
• Thus, the Inductive Hypothesis has been shown for $n+1$. Since the base case and IH have for $n$ implies the IH for $n+1$, it is concluded (by induction) that the IH is true for all $n\ge 0$.
• Induction is a subtle but powerful tool that should become very comfortable
• Performing induction on code is requires choosing a clever Inductive Hypothesis
• The Induction Hypothesis should capture the state of your code at key moments
• To understand how to induct on this code, look first an example on how to induct on the recursive version

Induction on a Positional Game §

					LAVA
					LAVA
C					Monster					T
					LAVA
					LAVA

• Imagine you are playing a game (picture above), where you, the character, denoted as $C$, are trying to reach a treasure, located at position $T$
• Your character can move up/down/left/right. You may not step on any locations occupied by Lava or a monster.
• How can it be proven that the player cannot reach the treasure?
  • Show that for any time $n$, the character $C$ cannot be at the treasure location $T$ at time $n$
• What is a good Inductive Hypothesis for this scenario?
  • One idea, use a statement to describe the state of the game
  • IH: “At time $n$, the character is not at location $T$”
  • The base case is true, since at time $n=0$, the character $C$ starts far from $T$
  • However, this Inductive Hypothesis is not useful for the Inductive Step.
  • The character could be located anywhere except location $T$ at time $n$, even directly adjacent to $T$
  • There is no way to prove $C$ is not at $T$ at time $n+1$
• Take a step back and reevaluate, determine a state of the game that is always true at time $n$ and allows for an inductive step to be made at time $n+1$
  • IH: “At time $n$, $C$ is to the left of $\text{Monster}$”
  • The base case, once again is true at time $n=0$
  • Inductive Step: Assume by the Inductive Hypothesis that $C$ is to the left of the bridge at time $n$. Next, $C$ can move up/down/left/right, but $C$ cannot step on the bridge since $\text{Monster}$ is there, and $C$ cannot get to the right of the bridge without first stepping on the bridge. Therefore, at time $n+1$, the character $C$ must still be to the left of the bridge
  • By Induction, at all times $n\ge 0$, $C$ must be to the left of the bridge, and since the treasure is at $T$ which is to the right of the bridge, $C$ will never reach the treasure

Revisiting Code Example: Recursive Preview §

Func2(n):
if n == 0, return 5
else, return Func(n-1) + 2

• For recursive code, the standard Inductive Hypothesis is:
  • ” my function is correct on all smaller inputs”
  • what is meant by “correct” and “smaller” depends on the specific context of the code
• For the recursive example $\text{Func2}$, induction will be performed on $n$, and the Inductive Hypothesis will be something like:
  • “for all $k<n$, $\text{Func2}(k)$ returns $2k+5$”
• The proof of induction here is similar to the mathematical proof from above

Finish Iterative Code Example §

Func(n):
x <- 5
for i <- 1 to n
  x <- x + 2
output x

• Proving the correctness of this original “for” loop code in $\text{Func}$, it is tempting to say “clearly $\text{Func}$ and $\text{Func2}$ are the same code, thus I will analyze $\text{Func2}$ instead of $\text{Func}$”

• DO NOT DO THIS

• When asked to analyze a particular piece of code, it is crucial that the code is analyzed EXACTLY as-is, instead of analyzing a different piece of code and hoping it is “close enough”

• “reductions”, a formal method for relating one piece of code to another, will be discussed later in the course

• To prove the correctness of $\text{Func}$, you can construct a complicated (induction) proof analyzing the outputs of $\text{Func2}$; but it will be much easier to analyze the outputs of $\text{Func}$ instead of this process

• TLDR: Analyze the code given, and refer to the particular lines of the code in the analysis

• The challenge for proving the correctness of $\text{Func}$ is to use intuition about $\text{Func}$ (which may be aided by the knowledge from $\text{Func2}$), to come up with an Inductive Hypothesis that “tells the story” of the “for” loop in $\text{Func}$

• In this iterative example, perform induction on the variable $i$, since $i$ is the index variable of the “for” loop

• Tell the story of the code by describing the state of the variables (in this case, $x$) at each iteration of the “for” loop

• The goal of the Inductive Hypothesis is to describe the state of things at the $i$‘th iteration of the “for” loop, in enough detail to use the IH to understand the result of the $i+1$‘st iteration and draw a conclusion about the overall behavior of the code after the entire “for” loop as ended

• What is the value of $x$ after the $i$‘th loop iteration?

• After some though, it can be guessed that $x=2i+5$

• Inductive Hypothesis: “After the $i$‘th iteration of the “for” loop, $x$ will equal $2i+5$”

  • this can be proven using induction

• As a base case, choose $i=0$, which might seem weird because there is not $0$‘th iteration of the “for” loop

  • However, this can be interpreted as “what is the value of $x$ before the loop begins, for which $x=5$”
  • The base case is true

• Now, perform the Inductive Step.

  • Suppose the IH is true for a given $i$, show the IH is true for $i+1$
  • Because IH is true for $i$, this means that after the $i$‘th iteration of the “for” loop, $x=2i+5$
  • Now, the $i+1$‘st iteration of the “for” loop will execute next, which will execute add $2$ to the value of $x$
  • After the $i+1$‘st iteration, $x=2i+5+2$, which equals $2(i+1)+5$, proving the Inductive Step

• Plugging in $i=n$, it can be shown that after all $n$ iterations of the “for” loop, $x=2n+5$

• Thus, the value of $2n+5$ will be the output of the program, showing the code is correct

• It is necessary to perform “clean up” after induction is complete, after all the code doesn’t end with the “for” loop

• It is a good sign if the structure of the proof mirrors the structure of the code, touching on every line of the code

• Keep this template in mind when things get more complicated later on