asymptotic-talk-1/talk.tex

% Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>
% Copyright (C) 2008 Karta24

% This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 
% International License. To view a copy of this license, visit 
% http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative 
% Commons, PO Box 1866, Mountain View, CA 94042, USA.

% Karta's attribution applies to the image '2-generals-dead-messenger.svg', per
% the requirements of the CC-BY-SA license.

\documentclass[style=fyma]{powerdot}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage[font={itshape},begintext={``},endtext={''}]{quoting}
\usepackage{algpseudocode}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{booktabs}

\newcommand\redsout{\bgroup\markoverwith{\textcolor{red}{\rule[0.5ex]{2pt}{0.4pt}}}\ULon}

\newtheorem*{theorem}{Theorem}
\newtheorem*{observation}{Observation}

\pdsetup{theslide=,
  palette=gray}

\begin{document}

\begin{slide}[toc=]{}
  \begin{center}
    {\LARGE \textbf{Introduction to asymptotic analysis} \par}
    {\Large Or: How computer science is like cooking \par}
    \vspace{1cm}    
    \includegraphics[scale=0.75]{logo.eps}
    \vspace{1cm}
    \linebreak
    Koz Ross

    \medskip

    March 30, 2017

  \end{center}
\end{slide}

\begin{slide}[toc=]{Overview}
  \tableofcontents[content=sections]
\end{slide}

\section{What are algorithms, and why do we care?}

\begin{slide}{Definition of an algorithm}
  \begin{quoting}
    A procedure, described in a finite number of instructions, for transforming
    inputs into an output to solve a specific problem. The instructions must be 
    unambiguous, guaranteed to terminate, and solve the problem correctly in all 
    cases. 
  \end{quoting}\pause{}

 \medskip

  Alternatively, you can think of an algorithm as a {\em recipe\/}:\pause{}
  \begin{itemize}
    \item The ingredients are the {\em inputs\/}\pause{}
    \item The recipe directions are the {\em instructions\/}\pause{}
    \item The (hopefully!) resulting food is the {\em output\/}
  \end{itemize}
\end{slide}

\begin{slide}{Why we care}
  \begin{itemize}
    \item Algorithms are {\em very\/} fundamental to computer science (which is
      why it's all about cooking!)\pause{}
    \item They define what we can do {\em at all}, and what we can do {\em
      efficiently\/}\pause{}
    \item Improved algorithms lead to improved everything-else\pause{}
    \item `Ready-baked' efficient solutions to many problems (theoretical {\em
      and\/} practical)\pause{}
    \item If you don't know this stuff, everything you do on a computer will run
      like hot garbage, and you won't know {\em why}, or what to do about 
      it\pause{}
  \end{itemize}

  \medskip

  Thus, we really need to be able to {\em compare\/} algorithms to each other,
  and also {\em understand\/} why they run the way they do, if we have any hope
  of making them do our bidding.
\end{slide}

\begin{slide}{What do we mean by `efficient'?}

  \vspace{1cm}
  {\em Efficiency\/} is ultimately doing more with less effort. We can measure
  the `effort' required to run an algorithm in two ways:\pause{}

  \begin{itemize}
    \item How much {\em time\/} we need to solve a problem instance; and\pause{}
    \item How much {\em space\/} (in terms of memory) we would have to use as
      part of this process.\pause{}
  \end{itemize}

  \medskip

  Determining these two factors is an important part of {\em algorithm
  analysis}.\pause{} Additionally, any method we use must explain {\em why\/} we
  get the performance it claims.
\end{slide}

\section{Building up}

\begin{slide}{Analysis by implementation}
  \begin{quoting}
    To analyze the efficiency of an algorithm, implement it, run it on some inputs, 
    and measure the time required and the memory used.
  \end{quoting}\pause{}

  \medskip

  Not bad {\em per se}, but has a few notable downsides:\pause{}

  \begin{itemize}
    \item Very labour-intensive (programming is hard!)\pause{}
    \item Too many external factors (programmer skill, language, OS, hardware,
      workload$\ldots$)\pause{}
    \item The test data problem (what do we test against?)\pause{}
  \end{itemize}

  \medskip

  While this method is useful at the {\em end\/} of the process, it's not a very 
  good analytical tool in general.\pause{} To do better than this, we need a
  different view of the problem, as well as a different method.
\end{slide}

\begin{slide}{A model}
  In sciences (of all sorts), a {\em model\/} is a way of looking at the world
  which:\pause{}
  
  \begin{itemize}
    \item {\em Minimizes\/} the impact of factors we {\em don't\/} care about\pause{}
    \item Stays {\em true to the reality\/} of factors we {\em do\/} care
      about\pause{}
    \item {\em Explains\/} why phenomena occur like they do.\pause{}
  \end{itemize}

  \medskip

  Examples of models include:\pause{}

  \begin{itemize}
    \item The Standard Model\pause{}
    \item The orbital model\pause{}
    \item Statistical models\pause{}
  \end{itemize}

  Models allow us to {\em analyze\/} and {\em understand\/} their subject matter
  without having to `manually verify' everything.
\end{slide}

\begin{slide}[toc=]{A model {\em of a computer\/}}

  Because algorithms ultimately run on computers, our model must be of a
  computer.\pause{} 
  
  \medskip

  There are {\em many\/} choices of model, depending on what kind of computer we
  want to study, as well as what aspects of it interest us.\pause{}

  \medskip

  The most traditional (and foundational) model for algorithm analysis is the
  {\em random access model\/} (RAM).\pause{} This closely represents a computer at the
  time when algorithm analysis first became a topic in its own right (around
  1950).

\end{slide}

\begin{slide}[toc=]{The random access model}

  In RAM, we have access to:\pause{}

  \begin{itemize}
    \item A single, sequential {\em processing unit\/} (PU)\pause{} 
    \item {\em Addressable memory}, divided into words of $w$ bits\pause{}
  \end{itemize}

  A {\em primitive instruction\/} is any of the following:\pause{}

  \begin{itemize}
    \item Arithmetic ($+, -, \cdot, \div$) on $w$-bit integers\pause{}
    \item Comparison ($<, >, \leq, \geq, =, \neq$) of two $w$-bit
      integers or flags\pause{}
    \item Allocation of any number of consecutively-addressed words\pause{}
    \item Given an address, a one-word read or write there\pause{}
    \item Conditional or unconditional branch\pause{}
    \item A procedure call\pause{}
    \item A return of a value\pause{}
  \end{itemize}

  Any primitive instruction requires one {\em time unit\/} to execute.
\end{slide}

\begin{slide}{Time and space complexity}
  Let $A$ be an algorithm, and $n$ be the size of the largest input to
  $A$.\pause{} 
  
  \medskip
  
  We define the {\em time complexity of $A$ for inputs of size
  $n$\/} (written $T_{A}(n)$) as the number of primitive instructions that the PU
  must execute to produce correct output for $A$ from any inputs of largest size 
  $n$.\pause{}

  \medskip

  We define the {\em space complexity of $A$ for inputs of size $n$\/} (written
  $S_{A}(n)$) as the number of words of memory that we must allocate to produce 
  correct output for $A$ from any inputs of largest size $n$.\pause{}

  \medskip

  If there are multiple possible values for $T_{A}(n), S_{A}(n)$ for a
  particular $n$, we take the {\em highest\/} possible value.\pause{} Thus, our
  analysis is {\em worst-case}.\pause{}

\end{slide}

\begin{slide}{An example algorithm}

  Problem: {\em Given a non-empty array $\mathsf{arr}$ of one-word integers,
  find the largest integer in $\mathsf{arr}$}.\pause{}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}\pause{}
  
  \medskip

  $T_{\mathsf{Max}}(n) = $ \pause{} $4 + 6(n - 1) + 1 = 6n - 1$\pause{}

  \medskip

  $S_{\mathsf{Max}}(n) = $ \pause{} $2$

\end{slide}

\section{Going asymptotic}

\begin{slide}{Asymptotic analysis}
  
  Ultimately, we don't actually care about what $T(n), S(n)$ {\em are}.\pause{}
  What really matters is {\em how they behave as their input sizes
  grow}.\pause{} Our current method focuses too much on the former, and not
  enough on the latter.

  \medskip 

  Thus, we make the following assumptions:\pause{}
  
  \begin{itemize}
    \item Input sizes can grow arbitrarily large\pause{}
    \item Constant additions or factors are irrelevant\pause{}
    \item Out of multiple $n$-terms, only the {\em largest\/} matters\pause{}
    \item We will talk about rate of growth, {\em not\/} value\pause{}
  \end{itemize}

  \medskip

  We call this kind of analysis {\em asymptotic}.\pause{} This is because the 
  input can grow as big as we like, and we're only interested in how the 
  running time (or space) changes with the growth of the input.
\end{slide}

\begin{slide}{Reviewing the example}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}
  
  \medskip

  $T_{\mathsf{Max}}(n) = 6n - 1$

  \medskip

  $S_{\mathsf{Max}}(n) = 2$

\end{slide}

\begin{slide}[toc=]{Reviewing the example}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}
  
  \medskip

  $T_{\mathsf{Max}}(n) =$ \redsout{$6$}$n$ \redsout{$- 1$}

  \medskip

  $S_{\mathsf{Max}}(n) = 2$

\end{slide}

\begin{slide}[toc=]{Reviewing the example}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}
  
  \medskip

  $T_{\mathsf{Max}}(n) =$ \redsout{$6$}$n$ \redsout{$- 1$}

  \medskip

  $S_{\mathsf{Max}}(n) =$ \redsout{$2$}

\end{slide}

\begin{slide}[toc=]{Reviewing the example}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}
  
  \medskip

  $T_{\mathsf{Max}}(n) =$ \redsout{$6$}$n$ \redsout{$- 1$} \hspace{1cm} \textcolor{red}{WRONG!}

  \medskip

  $S_{\mathsf{Max}}(n) =$ \redsout{$2$} \hspace{1.8cm} \textcolor{red}{WRONG!}

\end{slide}

\begin{slide}[toc=]{Reviewing the example}

  \begin{algorithmic}
    \Function{$\mathsf{Max}$}{$\mathsf{arr}$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[1]$
    \For{$\mathsf{i} \in 2, 3, \ldots$
    \Call{$\mathsf{,length}$}{$\mathsf{arr}$}}
    \If{$\mathsf{x} < \mathsf{arr}[\mathsf{i}]$}
    \State{}$\mathsf{x} \gets \mathsf{arr}[\mathsf{i}]$
    \EndIf{}
    \EndFor{}
    \State{}\Return{}$\mathsf{x}$
    \EndFunction{}
  \end{algorithmic}
  
  \medskip

  $T_{\mathsf{Max}}(n) \text{ \textcolor{red}{is} } \textcolor{red}{O(n)}$

  \medskip

  $S_{\mathsf{Max}}(n) \text{ \textcolor{red}{is} }
  \textcolor{red}{O(1)}$\pause{}
  
  \medskip

  We also say ``the time complexity of $\mathsf{Max}$ is $O(n)$'', or even
  ``$\mathsf{Max}$ is $O(n)$''.\pause{} The second one is a bit unclear, so I'd
  avoid it.
\end{slide}

\begin{slide}{Benefits of asymptotic complexity}
  \vspace{1cm}
  \begin{itemize}
    \item {\em Describes\/} performance on the basis of how our time and space
      requirements will grow relative the size of the problem, not pegged to a
      particular machine (or even model!)\pause{}
    \item {\em Explains\/} performance by showing us what causes the growth to
      be as bad (or good) as it is in the algorithm itself\pause{}
    \item Eliminates `noise' constants, focusing our attention where it really
      counts\pause{}
    \item Separates algorithms into well-defined groupings\pause{}
    \item Can be determined (and verified) very quickly\pause{}
    \end{itemize}

    \medskip

    It's definitely not perfect though --- but that's material for another talk.
\end{slide}

\section{Questions}

\end{document}