\documentclass[12pt]{article}

\input{cps130.tex}

\begin{document}

% \htmlimage{scale=2}

\title{Introduction to Algorithms (1)}
\author{Michael L. Littman}
\date{September 1st, 1998}

\maketitle 

\section{ADMINISTRATION}

\subsection{Course Background}

\noindent Basic Information:
\ul
\li CPS130: Introduction to the Design and Analysis of Algorithms
\li Instructor: Michael Littman (me)
\li Class meets twice a week in this room at this time.
\el

\noindent Prerequisites:
\ul
\li Four semesters of math listed.  Should know notation, basic
probability theory, the idea of limits, the concept of proofs. 
\li Knowledge of programming:  How to express the solution to a
problem in a computer language, how to structure complex programs in
modules, recursion. 
\li Some modifying and running of C++ programs.
\el


\subsection{Grading}

\noindent Class grade will be based on: 
\ul
\li written homework assignments (30\%), 
\li participation (10\%), 
\li two in-class exams (40\%), and 
\li a final exam (20\%).
\el

\subsection{Resources}

\noindent Traditional:
\ul
\li Textbook: ``Big White Book'' (useful resource)
\li Handouts of lecture notes.
\li TA office hours.
\li My office hours (or by appointment).
\el

\noindent Electronic:
\ul
\li web page: \htmladdnormallink{http://www.cs.duke.edu/\%7emlittman/courses/cps130/}{http://www.cs.duke.edu/\%7emlittman/courses/cps130/}
\li mailing list: send me your address!
\li newsgroup: \htmladdnormallink{duke.cs.cps130}{news:duke.cs.cps130}
(for class discussion) 
\li email: Me (Michael Littman)
(\htmladdnormallink{mlittman@cs.duke.edu}{mailto:mlittman@cs.duke.edu}),
TA and UTAs (see web page)
\el

\subsection{Homeworks}

\noindent Homework cycle:
\ul
\li Homework problems mentioned during lecture (Tuesday or Thursday).
\li Written (or online) answers due at the {\em beginning of class} the following Thursday.
\li Partial credit for late homeworks at my discretion.
\li We'll try to get them back to you by the following Thursday.
\el

\noindent Philosophy:
\ul
\li Practice trying out the concepts we discuss.
\li Opportunity to get feedback on your work.
\li Chance for me to see how you are participating.
\el

\noindent Collaboration:
\ul
\li homework: discuss, but write up separately!
\li tests: do not discuss!!
\el

\subsection{Teaching Goals}

\noindent Algorithms:
\ul
\li Separate us from the ``beasts.''
\li Are important practically.
\li Give us a chance to ``think'' (puzzles, fun!).
\el

\noindent Take Home Lessons:
\ul
\li Algorithms matter,
\li Some classic algorithms and their analyses,
\li How to analyze algorithms
\li How to invent new algorithms
\li Empirical evaluation of algorithms.
\el

\section{ALGORITHM BACKGROUND}

\subsection{Need for Speed}

\noindent World-wide web:
\ul
\li \htmladdnormallink{Driving directions to Long Beach Island, NJ.}{http://www.mapquest.com/cgi-bin/parser?uid=d0da3vc0c00ndtx&avoid_mj_hwy=&avoid_mn_hwy=&avoid_thruways=&avoid_local=&avoid_frontage=&avoid_ramps=&avoid_walk=&route_type=fastest&link=\%2Ftq\%2Ftq_frames&uid=d0da3vc0c00ndtx&avoid_ferry=1&avoid_allfire=1&OPC=null&ADDR_ORIGIN=&CITY_ORIGIN=Durham&STATE_ORIGIN=NC&DPC=null&ADDR_DESTINATION=&CITY_DESTINATION=Beach+Haven&STATE_DESTINATION=NJ&quest_mode=trip&results_display_mode=overview}: Database lookup, shortest path, range computation
\li \htmladdnormallink{Zip+4}{http://www.usps.gov/ncsc/lookups/lookup_zip+4.html} for my new address in Durham: spell correction, fast lookup, rule-based.
\li Search for web pages mentioning \htmladdnormallink{a particular article}{http://av.yahoo.com/bin/query?p=\%22Interactions+between+learning+and+evolution\%22&hc=0&hs=0}.
\li Compute and manipulate \htmladdnormallink{travel
information}{http://travel.yahoo.com/destinations/travelocity_air/yfinal_flts_roundtrip.html}
for an upcoming trip: another kind of shortest path, database lookup.
\el

\noindent It's gotta be fast or it's nearly useless.

\subsection{Writing Fast Programs}

\noindent How do you make a program fly?
\ul
\li Careful program design is important.
\li Tweaking loops and stuff can help.
\li Most important and general thing is good {\em algorithm design}.
\el

\noindent We'll study this process throughout the semester.

\noindent (Algorithm just means a way of doing something.)

\subsection{Algorithm Development Algorithm}

\begin{algorithm}{AlgorithmDesign}{\mbox{informal problem}}
 \mbox{formalize problem (mathematically) [Step 0]} \\
 \begin{REPEAT} \\
   \mbox{devise algorithm [Step 1]} \\
   \mbox{analyze correctness [Step 2]}\\
   \mbox{analyze efficiency [Step 3]}\\
   \mbox{refine}
  \end{REPEAT}{\mbox{algorithm good enough}} \\
 \RETURN \mbox{algorithm}
\end{algorithm}

\subsection{The Need for Mathematics}

\noindent Theory (math stuff) helps in three ways:
\ul
\li formal notation for a problem,
\li analyze correctness,
\li analyze efficiency.
\el

\noindent Sounds important, yes?

\noindent Efficiency:
\ul
\li {\bf time}, 
\li memory,
\li processors.
\el

\subsection{Kinds of Studied Algorithms}

\noindent The algorithms studied by researchers can be categorized as:
\ul
\li A. How to do something faster.
\li B. How to do something at all.
\li C. Prove a point (to help us understand the mathematical underpinnings).
\el

\noindent Courses often focus on C, for obvious reasons.  I'm going to
try hard to focus on A, which I think is the one that is the most
useful for the average computer scientist.


\section{ALGORITHM CASE STUDY}

\subsection{What Does This Do?}

\noindent Assume $a$ and $b$ positive integers.

\begin{verbatim}
int Naive(int a, int b)
// Naive algorithm
{
   int x = a, y = b, z = 0;
   while (x > 0)
   {
      z += y;
      x--;
   }
   return z;           
}
\end{verbatim}


\noindent \htmladdnormallink{Animated example.}{../../animations/naive.html}

\subsection{Algorithm Development}

\ul
\li 1. Devise algorithm.
\li 2. Analyze correctness.
\li 3. Analyze efficiency.
\el

\noindent Homework: For Naive multiplication, carry out Step 2.


\subsection{Russian Peasants' Algorithm}

\begin{verbatim}
int Russian(int a, int b)
//  implements Russian Peasant Algorithm
{
   int x = a, y = b, z = 0;
   while (x > 0)
   {
      if ( 1 == x % 2)
         z += y;
      y <<= 1;
      x >>= 1;
   }
   return z;        
}
\end{verbatim}

\subsection{Concrete Example}

\noindent Compute $71 \times 43$:

\begin{tabular}{rr}
$x$ & $y$ \\ \hline
71 &   [43] \\
35 &   [86] \\
17 &  [172] \\
 8 &   344 \\
 4 &   688 \\
 2 &  1376 \\
 1 & [2752]
\end{tabular}

\noindent Now sum.

\begin{tabular}{r}
2752 \\
 172 \\
  86 \\
  43 \\
\hline
3053
\end{tabular}

\noindent \htmladdnormallink{Animated example.}{../../animations/russian.html}

\subsection{Why Does It Work? [Step 2]}

\ul
\li 1. Initially $x y +z = a b$.
\li 2. Inductive Step
 \ul
 \li Let $x$, $y$, $z$ be values at the top of the loop.
 \li Assume $x y + z = a b$ holds.
 \li Let $x'$, $y'$, $z'$ be the values after the loop.
 \li If $x$ is odd:
  \ul
  \li $x' = (x-1)/2$
  \li $y' = 2 y$
  \li $z' = z + y$
  \li $x' y' + z' = (x-1)/2 (2 y) + z + y$ \\
      $= (x-1) y + z + y = x y - y + z + y = x y + z = a b$
  \el
 \li if $x$ is even:
  \ul
  \li $x' = x/2$
  \li $y' = 2 y$
  \li $z' = z$
  \li $x' y' + z' = (x/2) (2 y) + z = x y + z = a b$
  \el
 \li Therefore $x'y'+z' = ab$.
 \el
\li 3. Variable $x$ starts at at least one and decreases on each
iteration down to zero.  Therefore, algorithm terminates.
\li 4. At termination, $x y + z = a b$, but $x = 0$, so $z = a b$.
\el

\subsection{Which Is Better?}

\noindent How can we choose between the two algorithms (Naive and
Russian)? 

\noindent What do you think?

\noindent \htmladdnormallink{Animated comparison.}{../../animations/mults.html}

\subsection{Issues}

\noindent Depends on what it is for.  Naive is perhaps clearer.
Probably what matters is speed.

\noindent Which is faster?  How can we find out? [Step 3]

\section{EMPIRICAL EVALUATION}

\subsection{Experiment}

\noindent Choose a bunch of numbers and square them.  Measure run time.

\noindent For practical reasons, we'll rerun the algorithm a million
times and measure the total time.

\subsection{Results}

% From s-mlittman

\epsfig{file=figs01/vs1.ps,height=3.5in}

\subsection{Discussion}

\noindent For small numbers, Naive performs slightly better.  For
larger numbers Russian performs {\em much} better.

\noindent In fact, there's a detectable trend.  Can we characterize
it?

\subsection{Growth Rates}

\epsfig{file=figs01/vs1.ps,height=3.5in} \\
\epsfig{file=figs01/russ.ps,height=3.5in}

\ni Guess the growth functions?

\subsection{Direct Route}

\ni What if we just compute $a b$ by letting the computer multiply the
two numbers together?

\ni Takes approximately constant time (about 45 milliseconds per a
million multiplications, independent of the size of the numbers being
multiplied).

\epsfig{file=figs01/mult3.ps,height=3.5in}

\ni Rule \#1 of Good Algorithm Design: If you already have a good
subroutine to solve the problem, use it!


\section{EFFICIENCY ANALYSIS}

\ni A simple experiment suggested that the time it takes to multiply
$a$ by itself  
\ul
\item using Naive is some linear function of $a$,
\item using Russian is some logarithmic function of $a$.
\el

\noindent As a result, it appears Russian outperform Naive on large
problems.


\subsection{Explaining the Growth Rates}

\ni No analytic function predicts these curves exactly: too many
unmeasurable influences and complex relationships (caching, compiler,
pipelining).

\ni Furthermore, we can't use these algorithms to square numbers
larger than a million or so because we run out of room in our integer
variables.


\subsection{Measuring Time}

\ni We'd like a method for taking a program and producing a
mathematical function representing the amount of time it takes to run
it.

\ni We can't do this, in general.

\ni However, we can begin to make simplifying assumptions that let us
do this approximately.  In order of decreasing accuracy:

\ul

\li Simplifying assumption \#1: The time it takes to execute a simple
statement like $x \leftarrow x + 1$ depends only on the statement (not
the processor load, the amount of memory in the computer, the time of
day, the number of users, the value of $x$...).

\li Simplifying assumption \#2: The time it takes to execute a pair of
statements is the sum of the times to execute the individual
statements (ignoring issues like pipelining, etc.).

\li Simplifying assumption \#3: Any simple statement takes ``unit''
time (evaluating any arithmetic expression, assigning a variable,
initializing a loop, etc.).

\li Simplifying assumption \#4 (for later): Any constant-length (i.e.,
independent of the input) sequence of statements takes ``unit'' time.

\el

\noindent This will be enough to get us started.  We'll need to make
some even stronger assumptions later!


\subsection{Simple Programming Model}

\ni Time(Prog): 
\ul
\li Prog = statement; Prog': Time(statement) + Time (Prog')
\li Prog = ``var = expr'': 1 + Time(expr)
\li Prog = ``expr1 op expr2'': 1 + Time(expr1) + Time(expr2) for primitive ops
\li Prog = ``array[expr]'': 1 + Time(expr)
\li Prog = ``for i = 1 to n, do Prog' '': $n$ times Time(Prog')
\li Prog = function call: Time(function)
\li Prog = ``while(expr), do Prog' '': Time(expr) + Time(Prog') times executions
\el

\ni Analyze by inspection, multiplication, recurrences, potential
functions.

\subsection{Algorithms as a Science}

\ni Science:
\ul
\li Make Observations
\li Build Theories
\el

\noindent Theories are useful inasmuch as they predict reality.

\noindent In fact, no single theory is right for all classes of algorithms.


\subsection{Experiment vs. Theory}

\noindent Theory pros:
\ul
\li general
\li implementation independent
\li input independent
\li can be carried out before anything is built
\el

\noindent Experiment pros:
\ul
\li matches reality (time, task, computer system)
\li less mathematical
\el

\section{ANALYZING RUSSIAN}

\subsection{Counting Iterations}

\noindent From the simplifying assumptions, we can reason that the
important determinant of runtime in Naive is the number of times the
body of the loop is executed.

\ni So, how many iterations does Naive do, as a function of $a$?
Well, we subtract one from it over and over again until we get down to
zero.  How many times can we do that?

\ni What about Russian?  That one's a bit more interesting.
There, we divide $a$ by two (and round down) over and over again until
we get down to zero.  How many times can we do that?


\subsection{Fun With Logarithms}

\noindent Base 2 logarithms come up everywhere in this class (and CS).

\noindent Some characterizations of $\log(n)$:
\ul
\item The number of times we can divide $n$ by 2 before we get 1 or
less.
\item The number of bits in the binary representation of $n$.
\item A way to turn multiplication into addition: $\log(ab) =
\log(a)+\log(b)$.
\item The inverse function of $2^n$.
\el

\ni The function $\log(n)$ grows much more slowly than $n$ or $1/100
n$ or even $\sqrt{n}$.

\ni The book lists a bunch of amazing properties of this function.
I'll introduce them as needed.


\subsection{Iteration Count for Russian}

\ni From this little aside, it is apparent that the number of
iterations it takes to square $a$ is $\log(a)$.

\noindent To be more precise, the exact number of iterations is
$1+\lfloor \log(a)\rfloor$.

\noindent Here, the ``floor'' function, $\lfloor x \rfloor$ is the
largest integer not exceeding $x$ (rounding down).  This is in
contrast to the ``ceiling'' function $\lceil x \rceil$, which rounds
up.

\noindent We will prove this bound next time, and introduce another
(recursive) way of writing the algorithm.



\end{document}

1998: Finished very early, although I didn't have web access or
animations, so things might have gone extra fast.

