The division algorithm

Algorithm: div	
Inputs: a, b where a>=0 and b>0
Output: q and r such that a = q*b + r, and 0 ≤ r < b
if a < b
  q = 0, r = a
else
  q',r' = div(a-b,b)
  q = q'+1, r = r'
return q,r

Problem 1

Trace through the steps of the division algorithm on: $\text{div}(18,5)$.
Note: Show the inputs and local variables for each call to $\text{div}$.

Problem 2

Below is a proof that Algorithm div is correct, i.e. that if you give it inputs that meet its requirements, it produces outputs with the properties it claims. The proof is inductive (of course!). Your job is to determine whether or not this is a valid proof. To do this ...
  1. identify the "size"
  2. circle the base case in the proof
  3. circle the inductive case in the proof
  4. identify where the inductive hypothesis is applied, and ...
  5. verify that the inductive hypothesis is applied correctly, i.e. to a smaller problem!
(Correctness of div) The division algorithm meets is specifications, i.e. given $a\geq 0$ and $b > 0$, calling $\text{div}(a,b)$ returns values $q$,$r$ such that $a = q*b+r$ and $0\leq r \lt b$.
We proceed by induction, where the "size" of $\text{div}(a,b)$ is 0 if $a \lt b$ and $1 + a - b$ otherwise.
If size of $\text{div}(a,b)$ is equal to $0$, then $a \lt b$, so div returns $q=0$,$r = a$ and $q*b+r = 0*b + a = a$. ✓
If size of $\text{div}(a,b)$ is greater than $0$, then $a \geq b$ so the algorithm sets $q',r' = \text{div}(a-b,b)$. Since size $\text{div}(a-b,b)$ is less than size $\text{div}(a,b)$, we can apply the inductive hypothesis, which guarantees that $q',r'$ satisfy $a-b = q'*b + r'$ and $0 \leq r' \lt b$. Adding $b$ to both sides of this gives us
$a = q'*b + r' + b = \underbrace{(q'+1)}_{q}*b + \underbrace{r'}_{r}$
so the $q,r$ returned by div satisfies $a=q*b+r$. ✓