#title Algorithms - Preparation for 1st Exam

<contents>

* Solving recurrences

** Method 1: Substitution

 - Guess the form of the solution.
 - Verify your guess using induction.
 - Solve for the constants.

*** Example

<code>T(n) = 4*T(n/2) + n, T(1)
 = phi(n)</code>

phi(n) means tight asymptotic bound.

 1. Guess =O(n^2)=.
 2. Prove =O= (upper bound) and =omega= (lower bound) separately.
 3. Assume that <code>T(k) <= c*k^2</code> for =k < n=.  This is our
    inductive hypothesis.
 4. Prove <code>T(n) <= c*n^2</code> by induction.

In this case, we will try substituting =c*n^2= for =T(n)=.

<example>
T(n) = 4*T(n/2) + n
T(n) <= 4*c*(n/2)^2 + n
T(n) = c*n^2 + n
</example>

Now we want to put this in the form =(desired - residual)=.  Then,
reduce to the desired form if possible.

<example>
T(n) = c*n^2 - (-n)
Test k<n:
  T(n) <= c*n^2 for no choice of c
</example>

Since the inductive basis fails, we have to introduce a low-order
term.  Let's call it =-d^k=.  Change our inductive hypothesis
appropriately.

<example>
Inductive hypothesis: T(k) <= c*k^2 - d*k, for k < n
T(n) = 4*T(n/2) + n
T(n) <= 4*(c*(n/2)^2 - d*(n/2)) + n
T(n) = c*n^2 - 2*d*n + n
T(n) = c*n^2 - d*n - (d*n - n)
T(n) <= c*n^2 - d*n, if d >= 1 
</example>

Then, pick a c that is big enough to handle the initial conditions.

** Method 2: Recursion tree

A recursion tree is good for generating guesses for the substitution
method.

 - Build a recursion tree.
 - Determine height of tree as a function of input size.
 - Determine size of each tree level.
 - Add the sizes of each level.
 - Multiply by the height of the tree.

** Method 3: Master Theorem

The Master Theorem applies to recurrences of the following form, where
=a>1=, =b>1=, and f is positive.

<code>T(n) = a*T(n/b) + f(n)</code>

We do the Apprentice Theorem for recurrences of the following form,
where =a>1=, =b>1=, =c>1=.

<code>T(n) = a*T(n/b) + c*n^d</code>

The Apprentice Theorem is the only subset of the Master Theorem that
we are shown how to use.

*** Methodology

This applies to recurrences of the following form.

<code>T(n) = a*T(n/b) + c*n^d, T(1) = c</code>

After much thrashing, the following is also true.

<code>T(n) = c*n^d * (u^(k+1) - 1) / (u-1); u = a / b^d</code>

Three cases arise from this.

 - <code>a = b^d, u = 1</code>.  We get a factor of log (b,n).

   <code>T(n) = O(n^d * log(n))</code>

 - <code>a > b^d, u > 1</code>.  This is a diverging series.

   <code>T(n) = O(n^(log(b,a)))</code>

 - <code>a < b^d, u < 1</code>.  This is a convergent series.

   <code>T(n) = O(n^d)</code>

*** Examples

Quicksort ::

    <code>T(n) = 2*T(n/2) + c*n</code>

    Case 1: <code>u=1</code>.

    Solution: <code>T(n) = O(n*log(n))</code>

Binary search ::

    <code>T(n) = T(n/2) + c</code>

    Case 1: <code>u=1</code>.

    Solution: <code>T(n) = O(log(n))</code>

Median finding[1] ::

    <code>T(n) = T(3*n/4) + c*n</code>

    Case 3: <code>u<1</code>.

    Solution: <code>T(n) = O(n)</code>

Footnotes: 
[1] Assumes lucky partition.

* Path computations

We consider 3 algorithms.

 - Transitive Closure
 - All-Pairs Shortest Path
 - Warshal's Algorithm

These algorithms are essentially the same.  They are based on
organizing all paths of a directed graph in a certain manner.

** Transitive closure

Given a finite set S and a relation R on S, add the pairs that are
necessary in order to make R transitive.  This means that if =iRk= and
=kRj=, require that =iRj=.

Here is some pseudocode that accomplishes this.

<example>
function path-exists (M)
  foreach i in all rows in M
    foreach j in all cols in M
      if M[i,j] is defined
         new-m[i,j] = true
      else
         new-m[i,j] = false
  return new-m

function transitive-closure (weight-matrix)
  M = path-exists (weight-matrix)
  n = row-length (M)
  for k=0 upto n
    for i=0 upto n
      for j=0 upto n
        M[i,j] = or (M[i,j]
                     and (M[i,k],
                          M[k,j]))
  return M
</example>

The complexity of this operation is =O(n^3)=.

** How to find all paths of a graph

Given a graph G, find all paths in G.

This is accomplished by organizing the paths by the highest numbered
vertex that is on the path as an intermediate step.

 - Assume the vertices are numbered =1..n=.
 - =P(0,i,j)= is defined as all paths that have no intermediate step and
   lead from vertex i to vertex j.
 - =P(k,i,j)= is defined as all paths of arbitrary length in which the
   intermediate vertices are in the set ={1..k}=, and the path leads
   from vertex i to vertex j.

Here is some pseudocode that accomplishes this.

<example>
function weight (M)
  foreach i in all rows in M
    foreach j in all cols in M
      if M[i,j] is defined
         new-m[i,j] = M[i,j]
      else
         new-m[i,j] = INF
  return new-m

function all-pairs (weight-matrix)
  M = weight (weight-matrix)
  n = row-length (M)
  for k=0 upto n
    for i=0 upto n
      for j=0 upto n
        M[i,j] = min (M[i,j],
                      M[i,k] + M[k,j])
  return M
</example>

The complexity of this operation is =O(n^3)=.

* Sources

 - MIT OpenCourseware lecture notes (Copyright Charles E. Lieserson)
 - Prof. Christoph Hoffman's lecture notes