\documentstyle[12pt,overhead]{article}
\begin{document}
\input{epsf}
%\input rotate
\epsfverbosetrue
%\baselineskip=24pt
\large
\slabel{}



\begin{slide}{}{}
\begin{center}
\section{\bf \LARGE OVERVIEW}
\end{center}
\begin{itemize}
\item MOTIVATION\\

 \item ALGO DEF.\\
\item ANALYSIS - Seq. Search\\ 
\item TIME\\
    WORK DONE\\
    WORST, AV CASE\\
\item SPACE\\
\item  OPTIMALITY\\
\item ORDER NOTATION\\
\item DESIGN - Bin Search.

\end{itemize}
\end{slide}


\begin{slide}{}{}
\subsection{\bf MOTIVATION}
\begin{itemize}
    \begin{itemize}
      \item Algorithms: How to do things on a computer?
      \item Other application areas study specialized algorithms.
        \begin{description}
          \item e.g.\\
             Operating Systems\\
             Compiler Design\\
             Artificial Intelligence\\
             Data Base Management Systems
        \end{description}
      \item Algorithm Design Techniques\\
         Divide and conquer, greedy, Dynamic Programming etc.
      \item Basic Algorithms\\
         sorting, graph algo, matrix multiplication, NP-Complete problems, parallel         algos.
    \end{itemize}
\end{itemize}
\end{slide}


\begin{slide}{}{}
\subsection{\bf HISTORY}
Phrase Algorithm; Persian Author\\
\begin{itemize}
\item Abu Jafar Mohammed ibn Musa {\em al Khowarizmi} (825 AD)
\item wrote a Math textbook
\item al Khowarizmi: from the town of Khowarazm (now Khiva, Uzbekistan)
\end{itemize}

\subsection{\bf ALGORITHM DEFINITION}
     An algorithm is composed of a finite number of steps, each of which may require one or more operations.\\
     \begin{itemize}
       \item each OPERATION executable on a computer.
       \item compute 5/0 is not WELL DEFINED.\\
       \item algorithms must TERMINATE after a finite number of operations.
       \item PROCEDURE: a nonterminating algorithm.\\
             e.g. OS.
     \end{itemize}
\end{slide}


\begin{slide}{}{}
\begin{center}
\section{\bf \LARGE DESIGN AND ANALYSIS}
\end{center}
\begin{itemize}
 \item 
     GOAL - Distinguish Algorithms.\\
 \item TIME - Computer Dependent.\\
     AMOUNT OF WORK - COST
       \begin{itemize}
          \item proportional to the number of {\bf basic operations}.
          \item computer independent.
       \end{itemize}
     e.g. matrix multiplication\\
	 basic operation - multiplication \& addition.
\end{itemize}

\subsection{\bf EXAMPLE PROBLEM: Sequential Search}
\begin{description}
  \item [Problem:] Given an array $L[1..n]$, containing $n$ DISTINCT entries, find the index of $x$, if $x \in L$, else return 0.
  \item [Input:] array $L$, array size $n$, search item $x$.
  \item [Output:] If $x \in L$ then index of $x$ in $L$, else 0.
 \item [Algorithm:].\\ 
    Abstract Level Description: Scan $L$ left to right looking for $x$ in
$L$ \& return index. 
\end{description}
\end{slide}

\begin{slide}{}{}
\subsubsection{\bf Algorithm}
    \paragraph{Abstract Level Description:} Scan $L$ left to right looking for $x$ in
     $L$ \& return index.
    \paragraph{Pseudocode:}
    \begin{enumerate}
      \item index $\leftarrow$ 1
      \item {\bf While} index $\leq n$
      \item $\ \ \ \ \ ${\bf if} $L$[index] = $x$
      \item $\ \ \ \ \ \ \ \ \ \ $return (index)
      \item $\ \ \ \ \ ${\bf else}
      \item $\ \ \ \ \ \ \ \ \ \  $index $\leftarrow$ index + 1
      \item return (0)
    \end{enumerate}


\paragraph{\bf Work done:}
   Steps:\\
   1. assignment to a register variable\\

    {\em While loop}, $\ \ \ \ \ $if $x = L[k]$\\

    $\ \ \ \ \ \ $2. $k$ comparisons of register variables

    $\ \ \ \ \ \ $3. $k$ comparisons of $x$ with $L$ entry.

    $\ \ \ \ \ \ $6. $k-1$ increments of register variable.\\[0.5cm]
\end{slide}

\begin{slide}{}{}
\paragraph{Basic Operation of Sequential Search:}
    Since step 3 is costliest \& other steps are executed no more times, basic operation is {\em comparison of a memory and a register variable}.\\[0.5cm]
    {\bf cost = $k$},\ \ \ \ \ \ if $x = L[k]$\\
    {\bf cost = $n$},\ \ \ \ \ \ if $x \not \in L$\\
\end{slide}


\begin{slide}{}{}
\subsection{\bf TIME COMPLEXITY}
\begin{description}
  \item {\bf Best Case time}
	\begin{itemize}
    	\item $k = 1, \ \ \ x = L[1],\ \ \  $ best-case input.
    	\item $B(n) = 1$, \ \ \ as a function of input size.
	\end{itemize}
  \item {\bf Worst Case time}
	\begin{itemize}
    	\item $x = L(n)$ or $x \not \in L$
    	\item $W(n) = n$
	\end{itemize}
\end{description}
\end{slide}

\begin{slide}{}{}
\subsection{\bf AVERAGE-CASE COST?}
	\begin{itemize}
    	\item Let $x \in L$
    	\item Further, let $x$ is equally likely to be in any position 1 through $n$.
    \item $E_{k}$: event that $x = L[k]$
    \item Probability of $E_k$ happening 

    \begin{eqnarray*}
       P(E_{k}) & = &1/n, \ \ \ \ \ 1 \leq k \leq n\\
       t(E_{k}) & = &\mbox{cost or time when $L[k] = x$}\\
                & = &k
    \end{eqnarray*}
    Thus, average cost
    \begin{eqnarray*}
       A(n) &=  &P(E_{1})t(E_{1})+P(E_{2})t(E_{2})+ \ldots +P(E_{n})t(E_{n})\\
              &=& \sum_{k=1}^{n} P(E_{k})t(E_{k})\\
              &=& \sum_{k=1}^{n} \frac{1}{n}k\\
	      &=& \frac{1}{n} \sum_{k=1}^{n} k\\
              &=& \frac{1}{n}\left (\frac{n(n+1)}{2}\right)\\ 
	      &=& \frac{n+1}{2}
    \end{eqnarray*}
\end{itemize}
\end{slide}

\begin{slide}{}{}
\subsection{\bf DID WE AVERAGE OVER ALL POSSIBLE INPUTS?}
    Let us allow the possibility that $x$ might not be in $L$.
    \begin{eqnarray*}
       E_{0} = \mbox{event that $x \not\in L$}
    \end{eqnarray*}


    Let \begin{eqnarray*}
           P(x \in L) & = & q\\
           P(x \not\in L) & = & 1-q = P(E_{0})
        \end{eqnarray*}
    For $k\geq 1$, \begin{eqnarray*}
       P(E_{k}) & = &P(x \in L \ \  \mbox{and}\ \  x = L[k])\\
                & = &P(x \in L)P(x = L[k]\  \mbox{given that } x \in L )\\
                & = &q\ \frac{1}{n} = \frac{q}{n}
    \end{eqnarray*}
    Thus, \begin{eqnarray*}
            A(n) & = &\sum_{k=0}^{n} P(E_{k})t(E_{k})\\
                 & = &\sum_{k=1}^{n} P(E_{k})t(E_{k}) + P(E_{0})t(E_{0})\\
                 & = &\sum_{k=1}^{n} \frac{q}{n}k \  +\   (1-q)n\\
                 & = &\frac{q}{n}\sum_{k=1}^nk\   + \  (1-q)n\\
                 & = &\frac{q}{n} \frac{n(n+1)}{2}\   +\   (1-q)n\\
                 & = &q\frac{n+1}{2} + (1-q)n
          \end{eqnarray*}


    \begin{description}
       \item Thus, 
	\begin{itemize}
         \item if $q = 1,\ \  x \in L, \ \ A(n) = \frac{n+1}{2}$
         \item if $q = 0, \ \  x \not\in L,  \ \ A(n) = n$
         \item if $q = 1/2$, 
            \begin{eqnarray*}
               A(n) & = &\frac{1}{2}\ \frac{n+1}{2} + \frac{1}{2}n\\
                    & = &\frac{n+1+2n}{4}\\
                    & = &\frac{3n}{4} + \frac{1}{4}
            \end{eqnarray*}
	\end{itemize}
       \item {\bf Cost, Work = time complexity}.
     \end{description}
\end{slide}

\begin{slide}{}{}
\subsection{\bf SPACE COMPLEXITY}
           Extra space used apart from the input and the program
		(and the output, if required by specification).\\
           \begin{center}
             $S(n) = 1$\\
	   (1 register variable)
           \end{center}
\subsubsection{\bf Trade-off between time \& space}\\
           If number are between $1$ and $100$, then a prepared index
           array$A[1\ldots 100]$ such that \\[0.5cm]
		$A[i]=j$, if $L[j]=i$; else $A[i]=0$\\[0.5cm]
		 can yield $W(n)=O(1)$.\\[0.5cm]
({\em characteristic array}) 
\end{slide}


\begin{slide}{}{}
\subsection{\bf OPTIMALITY}\\
\begin{itemize}
           \item Is the sequential search algo. optimal?
           \item Is there another algo. which solves the same problem using
           fewer number of comparisons?
           \item Theorem: In the worst case,
           \[W(n)=n\]
       \item Proof by contradiction\\
	\begin{itemize}
           \item If there is another algo B whose $W(n)<n$, then the element not
	   seen by B may be $x$ \& $B$ would be incorrect.\\

           ($O(\log n)$ on an ordered list \& $O(1)$ in a characteristic
           vector alternatives only when performing multiple searches.)
           \item $\Rightarrow \ ${\bf Lower Bound} on the number of comparisons for 
	   searching in an unordered list is $n$.
	\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{}{}
\subsection{\bf PROBLEM COMPLEXITY}\\
             \paragraph{Def:} (Worst case) Complexity of a problem is the min
                   number of operations
                   needed to solve the problem in the worst case using 
	particular resources.
	

         eg. Matrix Multiplication\\
           $C_{nn}=A_{\mbox{n x n} }*B_{\mbox{n x n}}$\\
           $C_{ij}=A_{i1}B_{1j}+A_{i2}B_{2j}+\cdots +A_{in}B_{nj}$\\
           \begin{description}
    	      \item for $i \leftarrow$ 1 to $n$\\ 
      	         for $j \leftarrow$ 1 to $n$
                 \begin{description}
 	  	   \item $C_{ij}\leftarrow 0$
  		   \item for $k\leftarrow 1$ to $n$\\
			 $C_{ij}=C_{ij}+A_{ik}B_{kj}$
		 \end{description}
           \end{description}      

	\begin{itemize}
	\item Basic operation: Multiplication (addition can be ignored)
           \item $W(n)=n^{3}$
	   \item lower bound on number of multiplications $=n^{2}$\\
		{\bf lower bound on the problem complexity of matrix multiplication = $n^2$.}
 	   \item best algorithm found has time complexity $n^{2.367}$
	\end{itemize}
\end{slide}

\begin{slide}{}{}
\begin{description}
\item[Average-Case Problem Complexity]\\
             \item [Space complexity of a problem]\\
\begin{itemize}
		\item matrix multiplication $O(1)$
	        \item sorting on comparison model $O(1)$.
                \item matching parentheses $O(n)$.
\end{itemize}
 \end{description}
\end{slide}
\end{document}
