\documentclass{slides}
%\usepackage{a4}
%\usepackage{graphicx}
\newcommand{\binomial}[2]
{\left( \begin{array}{c}#1\\#2\\ \end{array} \right)}
\begin{document}
\begin{small}
%These slides are not self-explanatory. They are used to guide the
%lectures through a pre-determined path. You MUST LISTEN during the
%lectures and make notes AFTER THE LECTURE either on a copy of these
%slides or in your note book.
%
% Induction 3
% Proving program properties 3
% Running times Big Oh notation 3
% Recurrence Relations 3
% Combinatorics 2
% Propositional logic 2
% Graph Algorithms 2
% ---
% TOTAL: 18
% ---
%------------------------------------------------------------------
% LECTURE 1
\begin{slide}
\centerline{MATHEMATICAL INDUCTION}
\begin{itemize}
\item Induction and Deduction
\item Mathematical Induction (its strength)
\item Examples
\begin{itemize}
\item Sum of first n naturual numbers
Prove by induction that the sum of the first n natural
numbers is $n(n+1)/2$. i.e.
$$
S(i): \sum\limits_{i=1}^{n} i = \frac{n \times (n+1)}{2}
$$
\item Sum of powers of two
Prove by induction that the sum of the first n powers
of two (0..n) is $2^{n+1}-1$. i.e.
$$
S(i): \sum\limits_{i=0}^{n} 2^i = 2^{n+1}-1
$$
\item nth derivative of $e^{kx}$
Prove by induction that the nth derivative of $e^{kx}$ is
$k^n e^{kx}$. i.e.
$$
S(n): \frac{d^n}{dx^n} e^{kx} = k^n e^{kx}
$$
\end{itemize}
\end{itemize}
\end{slide}
%------------------------------------------------------------
% LECTURE 2
\begin{slide}
\begin{itemize}
\item Arithmetic and Geometric progressions.
\begin{itemize}
\item Derivations of general forms
\item Proofs by induction
\item An expression for the sum of the first n odd numbers and prove
it using Mathematical Induction.
\item Procedure for deriving an expression for the sum of a
polynomial series: $\sum_{i=0}^{n} p(n_k)$ where $p(n_k)$ is a
polynomial in $n$ of order $k: a_1 n^k + a_2 n^{k-1} + \cdots + a_k$
\end{itemize}
\item General template for Induction proofs:
\item One more example: Error correcting codes
S(n): $C_n$ is any set of bit strings of length n that is
{\em error detecting}, then $C_n$ contains at most $2^{n-1}$
strings.
\begin{itemize}
\item Assume S(n)
\item Divide $C_{n+1}$ into two sets of strings 1x and 0y
\item x \& y obviously be error detecting themselves.
\item By hypothesis, x/y contain no more than $2^{n-1}$ strings.
\item Thus maximum total number of strings is $2 \times 2^{n-1}$ =
$2^{n+1-1}$
\end{itemize}
\end{itemize}
\end{slide}
%------------------------------------------------------------
\begin{slide}
% END OF LECTURE 1
% ----------------------------------------------------------------------
% LECTURE 2
\centerline{Complete (strong) Vs Weak induction}
\begin{itemize}
\item Complete (or strong) induction: Uses two or more assumptions
from the basis up to $n$.
\item Examples:
Prove that there exist integers a and b such that
$\forall n \in {\bf \rm Z} \cap n > 0: n = 2a + 3b $.
Prove that there exist no integers $x, y, z$ such
that $\forall n \in {\bf \rm Z} \cap n > 2: x^n + y^n = z^n$.
\item Fallacies and getting carried away with induction
(All marbles are red, $\forall n \in {\bf \rm Z}: a^n = 1$)
\item Structural induction: Proving properties about a structure by
using a basis case and an inductive assumption.
\item Examples:
In a colony of aphids reproducing asexually, let the status of an aphid
be represented by the number of its children. Show that the total
number of aphids in the colony is one more than the sum of the statuses
of all the aphids.
Assume that a particular implementation of Binary trees uses the
Node with right and left child pointers. In such a binary tree,
prove that the number of NULL pointers is one more than the total
number of nodes.
\end{itemize}
% END OF LECTURE 2
% ----------------------------------------------------------------------
% LECTURE 3
\end{slide}
%------------------------------------------------------------
\begin{slide}
\centerline{Proving Program Properties}
What are loop invariants?
{\bf A Selection Sort program:}
\begin{verbatim}
(1) for (i = 0; i < n-1; i++) {
(2) small = i;
(3) for (j = i+1; j < n; j++)
(4) if (A[j] < A[small])
(5) small = j;
(6) swap(&A[small], &A[i]);
(7) }
\end{verbatim}
$S(k)$: If we reach the test for $j < n$ on line (3) with $j=k$
then $small$ indexes smallest of $A[i..k-1]$.
\end{slide}
%------------------------------------------------------------
\begin{slide}
{\bf Basis:} $S(i+1)$: $small$ indexes smallest of $A[i..i]$.
{\bf Induction:} Proof of $S(k+1)$ assuming $S(k)$.
$S(k)$: When testing for $j < n$ at line (3), $small$ indexes
smallest of $A[i..k-1]$.
Now consider what happens in the loop body when $j = k$, specifically
in the ``if'' statement of lines (4) and (5).
if $A[k]$ is less than the smallest of $A[i+1..k-1]$ then $small = k$.
Then $small$ indexes smallest of $A[i+1..k]$.
If $A[k]$ is not less than the smallest of $A[i+1..k-1]$ then the value
of small is unchanged. So small will now be the index of the smallest
of $A[i+1..k]$.
Thus, in either case, if the loop test is reached subsequently with
the value of $j$ incremented from $k$ to $k+1$, $small$ indexes
the smallest of $A[i+1..k]$ which proves $S(k)$ holds for all values
of $k \ge i+1$.
{\bf Question:} what is the truth value of $S(k)$ when $k > n$)
\end{slide}
%------------------------------------------------------------
\begin{slide}
Now consider the whole SelectionSort function. The following
assertion is made about it.
$T(m)$: If we reach the test $inext = MakeList();
pNewCell->element = x;
return pNewCell;
}
}
LIST MergeSort(LIST list) {
LIST SecondList;
if (!list || !list->next) return list;
else {
SecondList = split(list);
return merge(MergeSort(list), MergeSort(SecondList));
}
}
\end{verbatim}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
\begin{verbatim}
LIST merge(LIST list1, LIST list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1->element <= list2->element) {
list1->next = merge(list1->next, list2);
return list1;
} else {
list2->next = merge(list2->next, list1);
return list2;
}
}
LIST split(LIST list) {
LIST pSecondCell;
if (!list || !list->next) return NULL;
else {
pSecondCell = list->next;
list->next = pSecondCell->next;
pSecondCell->next = split(pSecondCell->next);
return pSecondCell;
}
}
\end{verbatim}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
\centerline{\bf Running Times}
\begin{enumerate}
\item Log means $\log_2$ in this module.
\item About counting machine instructions...
\item The 90--10 rule: (Eg. Experiment using gprof/gmon under Unix)
\item Why is it pointless to count the actual number of seconds?
\item Benchmarking Vs Analysis
\item Running time is conventionally denoted by $T(n)$ (no units)
\end{enumerate}
{\bf A selection sort program fragment:}
\begin{verbatim}
(2) small = i;
(3) for (j = i+1; j < n; j++) {
(4) if (A[j] < A[small])
(5) small = j;
\end{verbatim}
Total time spent in this loop is $4(n-i-1)+1$.
What is meant by quadratic and linear time?
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Big-Oh notation:}
$T(n)$ is $O(f(n))$ if there exists some
integer $n_0 > 0$ and constant $c > 0$ such that
$\forall n > n_0: T(n) \le cf(n)$
{\bf Example:} Find the Big-oh for $T(n) = (n+1)^2$ (Hint: 3,2 or 1,4)
{\bf Question:} Can $T(n)$ be considered $O(n^2/1000)$?
{\bf Show that:} $\log n$ is $\sqrt n$ etc.
\begin{enumerate}
\item Constant factors don't matter
\item Low order terms don't matter
\end{enumerate}
{\bf Thumbrule:}
if $\lim\limits_{n \rightarrow \infty} \frac{h(n)}{g(n)} = 0$
then $O(g(n) + h(n)) = O(g(n))$.
{\bf The Transitive Law:}
if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$, then $f(n)$ is $O(h(n))$.
{\bf Some useful points:}
\begin{enumerate}
\item if $p$ and $q$ are polynomials in $n$ and $degree(p) \le
degree(q)$ then $p$ is $O(q)$
\item if $degree(p) > degree(q)$ then $p$ is {\em not} $O(q)$
\item Every exponential grows faster than any polynomial
\item No exponential is $O(p)$ where p is a polynomial
\end{enumerate}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Some common expressions and their names:}
\begin{center}
\begin{tabular}{l|l}\hline
BIG-OH & INFORMAL NAME \\ \hline\hline
$O(1)$ & constant\\
$O(\log n)$ & logarithmic\\
$O(n)$ & linear\\
$O(n \log n)$ & $n \log n$\\
$O(n^2)$ & quadratic\\
$O(n^3)$ & cubic \\
$O(2^n)$ & exponential\\ \hline
\end{tabular}
\end{center}
{\bf Example:} What is the time complexity of the following fragment:
\begin{verbatim}
(1) scanf(``%d'', &n);
(2) for (i = 0; i < n; i++)
(3) for (j = 0; j < n; j++)
(4) A[i][j] = 0;
(5) for (i = 0; i < n; i++)
(6) A[i][i] = 1;
\end{verbatim}
{\bf Discuss program running times for:}
\begin{enumerate}
\item Primitive operations
\item for/while loops (simple and complex)
\item if/switch statements
\item function calls (in loops (in init/tests/body))
\end{enumerate}
Drawing a parse tree for a statement and finding the running time.
Use as example the Selection sort fragment.
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Analysing recursive functions:}
For the factorial function,
{\bf Basis:} $T(1) = O(1)$
{\bf Induction:} $T(n) = O(1) + T(n-1)$
Let the basis take $a$ units of time.
And the inductive step take $b + T(n-1)$ units of time.
\begin{eqnarray*}
T(1) & = & a\\
T(2) & = & a + b \\
T(3) & = & a + b + b = a+2b\\
& \vdots &\\
T(n) & = & a + (n-1)b
\end{eqnarray*}
{\bf Solving by repeated substitution:}
We have the sequence of equations
\begin{eqnarray*}
T(n) & = & b + T(n-1)\\
T(n-1) & = & b + T(n-2)\\
& \vdots & \\
T(2) & = & b + T(1)
\end{eqnarray*}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Substituting repeatedly, we get $T(n) = (n-1)b + a$
Consider T(n) = b + T(n-1) to be the first substitution.
We want to prove by induction on the number of substitutions $i$
(something not stated explicitly in the book):
$S(i)$: If $1 \le i < n$, then $T(n) = ib + T(n-i)$
so that we can assert that after (n-1) substitutions,
$T(n) = (n-1)b + T(1)$.
{\bf Basis:} $i = 1$, We know $T(n) = b + T(n-1)$ is true from its
definition.
{\bf Induction:} Consider $i < n-1$. Then,
$S(i): T(n) = ib + T(n-i)$.
$S(i+1)$ is the $(i+1)$th substitution. So substitute once more
in $S(i)$, i.e. Substitute for $T(n-i)$ in $S(i)$.
$T(n) = ib + b + T(n-i-1) = (i+1)b + T(n-(i+1)) = S(i+1)$ Q.E.D.
{\bf Analysis of Merge sort:}
Simple to show that merge() takes $O(n)$ time on a list length $n$
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Consider split()
$T(0) = O(1)$ and $T(1) = O(1)$. Let them be $a$ and $b$ resp.
$T(n) = O(1) + T(n-2)$, i.e. $T(n) = c + T(n-2)$ Why?
\begin{eqnarray*}
T(2) & = & c + T(0) = a + c\\
T(3) & = & c + T(1) = b + c\\
T(4) & = & c + T(2) = a + 2c\\
& \vdots &\\
\end{eqnarray*}
$T(n) = a + cn/2$ for even $n$ and $T(n) = b + c(n-1)/2$
for odd $n$.
Proof by induction on the number of substitutions:
\begin{eqnarray*}
T(n) & = & c + T(n-2)\\
& = & 2c + T(n-4)\\
& \vdots &\\
\end{eqnarray*}
$S(i)$: If $1 \le i < n/2$, then $T(n) = ic + T(n - 2i)$
Substitute once more for $T(n-2i)$ to get the $(i+1)$th substitution.
\begin{eqnarray*}
T(n) & = & ic + c + T(n - 2i - 2)\\
& = & (i+1)c + T(n - 2(i+1))\\
& = & S(i+1)\qquad Q.E.D.\\
\end{eqnarray*}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Now consider the function MergeSort()
Easy to see that
$T(n) = 2T(n/2) + O(n)$, i.e. $T(n) = 2T(n/2) + bn$
Let's begin the substitutions
\begin{eqnarray*}
T(1) & = & a\\
T(2) & = & 2T(1) + 2b = 2a + 2b\\
T(4) & = & 2T(2) + 4b = 4a + 8b\\
T(8) & = & 2T(4) + 8b = 8a + 24b\\
T(16) & = & 2T(8) + 16b = 16a + 64b\\
& \vdots &\\
\end{eqnarray*}
Generalising we get, $T(n) = an + bn\log_2 n$
An induction on the number of substitutions we need to make to $T(n)$
before ending up with $T(1)$. This will obviously be $\log_2 n$ since
$n$ is halved at each stage. (How many times can we cut a number to
half its size before ending up with a number $<= 1$?)
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
To intuit $S(i)$, consider the following substitutions
\begin{eqnarray*}
T(n) & = & 2T(n/2) + bn\\
& = & 2(2T(n/4) + bn/2) + bn = 4T(n/4) + 2bn\\
& = & 4(2T(n/8) + bn/4) + 2bn = 8T(n/8) + 3bn\\
& \vdots &\\
\end{eqnarray*}
So in general,
$S(i)$: If $1 \le i \le \log_2 n$, then $T(n) = 2^iT(n/2^i) + ibn$
{\bf Proof:}
{\bf Basis:} $T(n) = 2T(n/2) + bn$, true from the definition.
{\bf Induction:} Assume $S(i): T(n) = 2^iT(n/2^i) + ibn$
Consider the next substitution into $S(i)$,
\begin{eqnarray*}
T(n) & = & 2^iT(n/2^i) + ibn\\
& = & 2^i (2 T((n/2^i)/2) + bn/2^i) + ibn\\
& = & 2^{i+1}T(n/2^{i+1}) +(i+1)bn\\
& = & S(i+1) \qquad Q.E.D.\\
\end{eqnarray*}
Making $\log_2 n$ substitutions to $T(n)$, we end up with the base
case: $T(n) = an + bn\log_2 n$ and so $T(n)$ is $O(n\log n)$.
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
\centerline{\bf Solving Recurrence Relations}
{\bf Two methods:}
\begin{enumerate}
\item Repeated substitution
\item Guessing and proving (Don't freak out!!)
\end{enumerate}
{\bf Example of first type (Repeated substitution)}
Try $T(1) = a, T(n) = T(n-1) + g(n)$
We can show by repeated substitution, $i$ times,
$T(n) = T(n-i) + \sum\limits_{j=0}^{i-1} g(n-j)$
To get the basis case (where no more subs can be made, we
must use $i = n-1$. This gives:
$T(n) = T(1) + \sum\limits_{j=0}^{n-2} g(n-j)$
For factorial, $g(n) = O(1) = b$
For recursive selection sort, $g(n) = O(n) = bn$
Try to derive the complexities of the two functions.
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Merge sort:}
\begin{eqnarray*}
T(n)& = & 2T(n/2) + g(n)\\
& = & 4T(n/4) + 2g(n/2) + g(n)\\
& = & 8T(n/8) + 4g(n/4) + 2g(n/2) + g(n)\\
& \vdots & \\
& = & 2^iT(n/2^i) + \sum\limits_{j=0}{i-1} 2^j g(j/2^j)\\
\end{eqnarray*}
The base case when no more subs are to be made is reached after
$\log_2 n$ substitutions.
So, $T(n) = an + \sum\limits_{j=0}^{\log_2 n - 1} 2^j g(j/2^j)$
For merge sort, $g(n) = bn$ (recall)
So,
\begin{eqnarray*}
T(n) & = & an + \sum\limits_{j=0}^{\log_2 n - 1} bn\\
& = & an + bn\log_2 n\\
& & is\, O(n\log n) \qquad Q.E.D.
\end{eqnarray*}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Example of second type (by guessing)}
Try to prove the complexity of merge sort.
Guess that $T(n)$ is bounded by $cn\log n + d$
Now proceed along the following lines.
Prove the following by induction.
$S(n):$ For merge sort, $T(n) \le f(n)$ where $f(n) = cn\log n + d$
where $n \ge 1$ is a power of 2.
Basis: $S(1)$ is true if $a \le d$ (Recall that $T(1) = a$ and
$T(n) = 2T(n/2) + bn$.
Now assume $S(i)$ for $1 \le i < n$ and prove $S(n)$ as below:
We want to prove $T(n) \le cn\log n + d$ for some $c, d$, that is
there exists some value of $c$ and $d$ for which the above inequality
is true; can we find them?
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
\begin{eqnarray*}
T(n) & = &2T(n/2) + bn\\
&\le &2(c\frac{n}{2} \log \frac{n}{2} + d) + bn\\
&\le &cn(\log n - \log 2) + 2d + bn\\
&\le &cn\log n -cn + 2d + bn\\
&\le &cn\log n + d \quad + n(b-c) + d\\
\end{eqnarray*}
Can we find a $b, c$ and $d$ such that for $n \ge 1$, $n(b-c) + d \le 0$?
If so, the above inequality will hold.
Since $n(b-c) + d \le 0, n(b-c) \le -d$. Also, since $n \ge 1$, this
is only true if $b-c \le -d$. Also, since $a \ge d$, assume $a = d$
then we have $b-c \le -a$ or $a + b \ge c$. Letting $c = a+b$, and $d
= a$, we have
$T(n) \le (a+b)\log n + a$
Thus $T(n)$ is $O(n\log n)$
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
{\bf Some common recurrences and their running times:}
\begin{center}
\begin{tabular}{|l|l|}\hline
$T(n)$ & BIG-OH \\ \hline\hline
$T(n-1) + bn^k$ & $O(n^{k+1})$\\
$cT(n-1) + bn^k, c>1$ & $O(c^n)$\\
$cT(n/d) + bn^k, c>d^k$ & $O(n^{\log_d c})$\\
$cT(n/d) + bn^k, c 1$.
{\bf Hints:}
\begin{enumerate}
\item First expand $G(n)$ by repeated substitution to get the
dominant term in the expression.
\item Don't forget the constant term ($d$)
\end{enumerate}
\end{slide}
%------------------------------------------------------------------
\begin{slide}
\centerline{Combinatorics}
Counting assignments -- Colours to houses, etc. $k^n rule$ (Also
called selections with replacement)
\begin{itemize}
\item[] Example: How many bits do you need to uniquely address every
byte in a memory bank of 100 MB? ($2^n = 100*1000*1024$).
\end{itemize}
Counting permutations -- $\prod(n)$
Ordered selections without replacement: $\prod(n,m) = $ number of ways
we can select $m$ items from $n$ such that order matters for the selected
items only. $(\prod(n,m) = n(n-1)(n-2)\cdots(n-m+1) =
\frac{n!}{(n-m)!})$
Computing logs of large factorials
Unordered selections (also called combinations)
$\binomial{n}{m} = \frac{\prod(n,m)}{\prod(m)}$
\begin{itemize}
\item[] Example: Number of poker hands (5 cards)
\end{itemize}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Important properties of $\binomial{n}{m}$
\begin{itemize}
\item for $0 < m < n, \binomial{n}{m} = \binomial{n-1}{m} +
\binomial{n-1}{m-1}$
\item $\binomial{n}{m} = \binomial{n}{n-m}$
\end{itemize}
Pascal's triangle:
$\binomial{n}{m} = P[n+1][m+1]$
($m$th entry in the $n$th row, numbering from 0)
Computing ratios of large factorials
Running times of functions to compute permutations and combinations.
(Contrast with running times of functions to list all the permutations
and combinations, Recursive and iterative versions.)
Why $\binomial{n}{m}$ must yield an integer
Shape of the function $f(m) = \binomial{k}{m}$
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Binomial co-efficients: Consider $(x+y)^n$ for $n = 1,2,...,i$
\begin{eqnarray*}
(x+y)^n = \sum\limits_{m=0}{n} \binomial{n}{m} x^m y^{n-m}
\end{eqnarray*}
Consider special cases of above when $y = 0, 1$ or $x = y = 1$
Multinomials: Permutations with identical elements.
Distribution of objects to bins
Distributing distinguishable objects in $k$ classes
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
\centerline{DIJKSTRA'S SHORTEST-PATH ALGORITHM}
This will be the last lecture from me this semester
for this course. I will, however, see you again
after the Easter break for the mid-semester test.
The plan of this lecture:
\begin{enumerate}
\item Attempt to find your own shortest
path algorithm.
\item Description and discussion of
Dijkstra's algorithm
\item Proof of the algorithm and why it
works.
\item Silent admiration and appreciation
of the beauty, elegance and simplicity of the
algorithm.
\end{enumerate}
Example graph:
\begin{eqnarray*}
A \rightarrow B = 15\\
B \rightarrow C = 12\\
A \rightarrow C = 20\\
B \rightarrow D = 28\\
D \rightarrow E = 24\\
E \rightarrow F = 11\\
C \rightarrow F = 13\\
\end{eqnarray*}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
Start off by assuming that all other nodes are at
distance infinity from the source node and gradually
adjust these distances as we go on.
The shortest distances are discovered from the
source node to every other node, in the order of
nearness, i.e. nearest nodes are decided before
looking at farther nodes.
Some definitions:
\begin{itemize}
\item A node is called {\em settled}\/ if the
minimum distance to it from the source is known.
\item The {\em shortest special path}\/ (SSP) to an
unsettled node, if it exists, is a path that
travels only through settled nodes except at the
last step.
\item We maintain a value $dist(u)$ for every node
$u$ such that if the node gets settled, then
$dist(u) = $ length of shortest path to $u$. If $u$
is not settled, then $dist(u) =$ length of shortest
special path to $u$.
\end{itemize}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
HOW TO SETTLE A NODE:
Adjust the value of $dist(u)$ for all nodes $u$
that remain unsettled and are affected by the
settled node.
i.e. To settle node $v$, for each arc
$v\rightarrow u$, if $dist(v) +
len(v\rightarrow u) < dist(u)$, then $dist(u) :=
dist(v) + len(v\rightarrow u)$
At the start of the algorithm, no nodes are
settled and there exists a special path of length
zero from the source node to itself.
At each pass, settle one unsettled node with the
least value of $dist(u)$ as described above.
The algorithm terminates when all nodes have been
settled.
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
IMPORTANT POINT:
At the beginning of any pass over the nodes in the
algorithm, the shortest of all special paths is THE
shortest path to the node it goes to. Note that
this is not the case with the other special paths
(non-shortest special paths). That is why this is
the node that is settled next.
To see why, let the shortest of all special paths
go to node $v$ and another special path, (not the
shortest one) go to node $u$.
{\bf THERE IS A POSSIBILITY} that there might be a
path from $v$ to $u$, such that going to $v$ and
thence to $u$ is shorter than going to $u$
directly. However, {\bf THERE IS NO POSSIBILITY}
that going to $u$ and thence to $v$ is shorter than
going to $v$ directly since going to $u$ is itself
longer than going to $v$. So there is {\bf A RISK}
in settling $u$ before $v$, but there is {\bf NO
RISK} in settling $v$ before $u$. Spend a few
minutes on this point and understand this
completely and you will feel absolutely comfortable
with the inductive proof.
ALTERNATELY, PONDER:
Why should nodes be settled in the order of
nearness? This is in fact a critical requirement
for the algorithm. Consider the scenario when
there exist special paths of length 10 and 20 from
the source $s$ to two nodes $u$ and $v$. What
guarantees that the algorithm will work: Settling
$u$ first or $v$?
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
PROOF BY INDUCTION:
S(k): When there are $k$ settled nodes,
\begin{itemize}
\item[a] For each settled node, $u, dist(u)$ gives the
minimum distance from $s$ to $u$ and the shortest path
$s\rightarrow u$ consists entirely of settled nodes.
\item[b] For each unsettled node $u, dist(u)$ is the
minimum distance of any special path from
$s\rightarrow u$ or $\infty$ if no such path exists.
\end{itemize}
\begin{tiny}
First prove that (a) holds after the $(k+1)$th node,
$v$ is settled: Proof is by contradiction: Assume
that $dist(u)$ is not the shortest path to $v$.
Then there must have existed some non-special path
that is shorter than the special path since {\bf by
the Inductive Hypothesis (b),} we know that when $k$
nodes were settled, the shortest special path to $v$
is the shortest of all special paths to $v$. But we
can't have an unsettled $w$ be on a non-special path
to $v$ because (see Ponder point above) $w$ should
have been settled before $v$. Therefore (a) holds.
Then prove that (b) also holds after $v$ is settled:
Consider an arbitrary unsettled node $u$ after $v$
is settled. Either there is no special path to $u$
or there is one. If the former, then $dist(u) =
\infty$ is indeed the shortest of special paths to
it by definition. If the latter, then either $v$ is
part of the special path or not. If $v$ is part of
the special path, then it {\bf must} be the
penultimate node (Why?). In this case, the $len(s
\rightarrow u) = dist(v) + len(v \rightarrow u)$.
If $v$ is not part of the special path, then the
settling of $v$ has no effect on the length of the
path to $u$. Since the algorithm sets $dist(u)$ to
the smaller of the old value of $dist(u)$ and
$dist(v) + length(v \rightarrow u)$, if settling $v$
changes the shortest path to $u$ then it {\bf will}
reset $dist(u)$ accordingly. Q.E.D.
\end{tiny}
\end{slide}
%----------------------------------------------------------------------
\begin{slide}
COMMON POINT OF CONFUSION:
Do not confuse ``Shortest of all special paths to A
NODE'' with ``Shortest of all special paths.'' The
former is used when we have more than one special
path to a given node (typically upon a settling a
new node). We reset the dist() for that node to be
the shortest of all special paths to it. The
latter is the shortest of all special paths to any
unsettled node. This points to the next node to be
settled.
Final note:
Investigate the following web site:
http://www.MapsOnUs.com
Try planning the shortest route from Tom Bradley
Intl Airport, LA to Wall street, NY. What about
the fastest? Why are they different?
\end{small}
\end{document}