dsa_03_asymptotic2.html

<!doctype html>
<html lang="en">

  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <link href="css/fontawesome-free-5.15.4-web/css/all.css" rel="stylesheet">

    <script src="lib/colorbrewer.v1.min.js" charset="utf-8"></script>
    <script src="lib/colorStringStandalone.js" charset="utf-8"></script>
    <script type="text/javascript" src="lib/jquery-2.2.4.min.js"></script>

    <title>Design & Analysis: Algorithms</title>

    <meta name="description" content="CS4851/6851 GSU class">
    <meta name="author" content="Sergey M Plis">

    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">


    <link rel="stylesheet" href="dist/reset.css">
    <link rel="stylesheet" href="dist/reveal.css">
    <!-- Code syntax highlighting -->
    <link rel="stylesheet" href="plugin/highlight/monokai.css" id="highlight-theme">
    <!-- <link rel="stylesheet" href="lib/css/zenburn.css"> -->
    <link rel="stylesheet" href="css/custom.css">
    <link rel="stylesheet" href="dist/theme/aml.css" id="theme">
    <!-- Printing and PDF exports -->
    <script>
      var link = document.createElement( 'link' );
      link.rel = 'stylesheet';
      link.type = 'text/css';
      link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.scss';
      document.getElementsByTagName( 'head' )[0].appendChild( link );

    </script>
  </head>


  <body>
    <div class="reveal">
      <!-- In between the <div="reveal"> and the <div class="slides">-->
          <!-- <header style="position: absolute; top: 10px; left: 100px; z-index: 500; font-size:100px;background-color: rgba(0,0,0,0); text-align: center !important"></header>  -->
          <!-- In between the <div="reveal"> and the <div class="slides">-->
              <!-- Any section element inside of this container is displayed as a slide -->
              <div class="slides">
		<section>
		  <section>
		    <p>
		      <h2>Design & Analysis: Algorithms</h2>
                      <h3>03: Asymptotic Analysis & Recurrences</h3>
		    <p>
		  </section>
	          <section>
		    <h3>Outline of the lecture</h3>
                    <ul>
		      <li class="fragment roll-in"> Asymptotic Analysis
                      <li class="fragment roll-in"> Recurrence Relations
		    </ul>
                  </section>
                </section>

		<section>
		  <section>
                    <h1>Asymptotic analysis</h1>
		  </section>

                  <section>
                    <h2><i class="fa fa-question-circle" aria-hidden="true"></i></h2>
                    <blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 38px; width: 100%;" class="fragment" data-fragment-index="0">
                      Design an algorithm to return the largest sum of contiguous integers in an array of ints
                    </blockquote>
                    <blockquote shade style="width:100%;" class="fragment" data-fragment-index="1">
                      Example: if the input is $(-10, 2,3,-2,0,5,-15)$, the largest sum is $8$, which we get from $(2,3,-2,0,5)$
                    </blockquote>
                  </section>
                  <section>
                    <h2>A Naive Algorithm</h2>
                    <pre class="python"><code data-line-numbers data-trim data-noescape>
def max_seq1(sequence):
    n = len(sequence)
    max_sum = -100000
    for i in range(n):
        for j in range(i, n):
            sum = 0
            for k in range(i, j + 1):
                sum += sequence[k]
                if sum > max_sum:
                    max_sum = sum
    return max_sum
                    </code></pre>
                  </section>
                  <section>
                    <h2>Analysis</h2>
                    <ul style="font-size:32px;">
                      <li class="fragment roll-in"> Need to count the total number of operations of <code>max_seq1</code>
                      <li class="fragment roll-in"> Might as well assume time to do the inner loop is 1 (since it's a constant and therefore $O(1))$
                      <li class="fragment roll-in"> Let $f(n)$ be the runtime of an array of size $n$
                        <row>
                          <col50>
                            <div style="font-size:22px;">
                              \begin{align}
                              f(n) & \fragment{4}{ = \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j 1}\\
                              & \fragment{5}{ = \sum_{i=1}^n \sum_{j=i}^n (j - i + 1)}\\
                              & \fragment{6}{ = \sum_{i=1}^n \sum_{j=1}^{n-i+1} j }\\
                              & \fragment{7}{ = \sum_{i=1}^n (n-i+1)(n-i+2)/2}\\
                              \end{align}
                            </div>
                          </col50>
                          <col50>
                            <pre class="python"><code data-line-numbers data-trim data-noescape>
def max_seq1(sequence):
    n = len(sequence)
    max_sum = -100000
    for i in range(n):
        for j in range(i, n):
            sum = 0
            for k in range(i, j + 1):
                sum += sequence[k]
                if sum > max_sum:
                    max_sum = sum
    return max_sum
                            </code></pre>
                          </col50>
                        </row>
                    </ul>
                  </section>
                  <section>
                    <h2>Analysis cont.</h2>
                    <row style="font-size:26px;">
                      <col50>
                        \begin{align}
                        f(n) & = \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j 1\\
                        & = \sum_{i=1}^n \sum_{j=i}^n (j - i + 1)\\
                        & = \sum_{i=1}^n \sum_{j=1}^{n-i+1} j \\
                        & = \sum_{i=1}^n (n-i+1)(n-i+2)/2\\
                        \end{align}
                      </col50>
                      <col50>
                        \begin{align}
                        f(n) & \fragment{1}{ = \sum_{i=1}^n (i/2)(i+1)}\\
                        &\fragment{2}{ = \frac{1}{2} \sum_{i=1}^n (i^2 + i)}\\
                        &\fragment{3}{ = \frac{1}{2} (\sum_{i=1}^n i^2 + \sum_{i=1}^n i )}\\
                        & \fragment{4}{ = \frac{1}{2} (O(n^3) + O(n^2))}\\
                        &\fragment{4}{ = O(n^3)}\\
                        \end{align}
                      </col50>
                    </row>
                  </section>

                  <section>
                    <h2>Can we do better?</h2>
                  </section>

                  <section>
                    <h2>A Better Algorithm</h2>
                    <pre class="python"><code data-line-numbers data-trim data-noescape>
def max_seq2(sequence):
    n = len(sequence)
    max_sum = 0
    for i in range(n):
        sum = 0
        for j in range(i, n):
            sum += sequence[j]
            if sum > max_sum:
                max_sum = sum
                # store (i,j) if desired
    return max_sum
                    </code></pre>
                  </section>

                  <section>
                    <h2>Analysis</h2>
                    <ul style="font-size:32px;">
                      <li> Let $f(n)$ be the number of operations this algorithm performs on an array of size $n$.
                    </ul>
                    <row>
                      <col50>
                        <div style="font-size:22px;">
                          \begin{align}
                          f(n) & \fragment{1}{ = \sum_{i=1}^n \sum_{j=i}^n 1}\\
                          & \fragment{2}{ = \sum_{i=1}^n (n - i + 1)}\\
                          & \fragment{3}{ = \sum_{i=1}^n i }\\
                          & \fragment{4}{ = (n+1)n/2}\\
                          & \fragment{5}{ = O(n^2)}\\
                          \end{align}
                        </div>
                      </col50>
                      <col50>
                        <pre class="python" style="font-size:12pt;"><code data-line-numbers data-trim data-noescape>
def max_seq2(sequence):
    n = len(sequence)
    max_sum = 0
    for i in range(n):
        sum = 0
        for j in range(i, n):
            sum += sequence[j]
            if sum > max_sum:
                max_sum = sum
                # store (i,j) if desired
    return max_sum
                        </code></pre>
                      </col50>
                    </row>
                  </section>
                  <section>
                    <h2> Challenge </h2>
                    <ul>
		      <li class="fragment roll-in"> <code>max_seq2</code> is much better than <code>max_seq1</code> <br>$O(n^2)$ vs $O(n^3)$
                      <li class="fragment roll-in"> But it’s still not great, can you do better?

                  </section>
                  <section>
                    <h2>Beyond Big-O</h2>
                    <ul>
                      <li class="fragment roll-in"> Both <code>max_seq1</code> and <code>max_seq2</code> have same best case and worst
case behavior
<li class="fragment roll-in"> We can say more about them than big-$O$ time
<li class="fragment roll-in"> I.e. We can say that each has run time approx “$=$” to
some amount; We can also say that <code>max_seq2</code> is approx “$<$”
<code>max_seq1</code>;
<li class="fragment roll-in"> $O$ is an asymptotic analogue to “$≤$”, but we’d also like analogues to $<$, $=$, $≥$ and $>$.
                    </ul>
                  </section>
                  <section>
                    <h2>Relatives of big-O</h2>
                    <ul style="font-size:26pt;">
                      <li class="fragment roll-in"> $O$ "$\leq$" This algorithm is $O(n^2)$ (i.e. worst case is $\Theta(n^2)$)
                      <li class="fragment roll-in"> $\Theta$ "$=$"This algorithm is $\Theta(n)$ (best and worst case are $\Theta(n)$)
                      <li class="fragment roll-in"> $\Omega$ "$\geq$" Any comparison-based algorithm for sorting is $\Omega(n \log n)$
                      <li class="fragment roll-in"> $o$ "<" Can you write an algorithm for sorting that is $o(n^2)$?
                      <li class="fragment roll-in"> $\omega$ ">" This algorithm is not linear, it can take time $\omega(n)$

                    </ul>
                  </section>
                  <section>
                    <h2>Formal Definitions: $O$, $\Theta$, $\Omega$</h2>
                    <ul style="font-size:28pt;">
                      <li class="fragment roll-in"> $O(g(n)) = \{f(n) :$ there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0\}$
<li class="fragment roll-in"> $\Theta(g(n)) = \{f(n) :$ there exist positive constants $c_1$, $c_2$, and $n_0$
such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$
<li class="fragment roll-in"> $\Omega(g(n)) = \{f(n):$ there exist positive constants $c$ and $n_0$
such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0\}$

                    </ul>
                  </section>
                  <section>
                    <h2>Formal Definitions: $o$, $\omega$</h2>
                    <ul style="font-size:28pt;">
<li class="fragment roll-in"> $o(g(n)) = \{f(n):$ for any positive constant $c > 0$ there exists
$n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n \geq n_0\}$
<li class="fragment roll-in"> $\omega(g(n)) = \{f(n):$ for any positive constant $c > 0$ there exists
$n_0 > 0$ such that $0 \leq cg(n) < f(n)$ for all $n \geq n_0\}$
                    </ul>
                  </section>
                  <section>
                    <h2>Rule of Thumb</h2>
                    <ul style="font-size:28pt;">
                    <li class="fragment roll-in"> Let $f(n)$, $g(n)$ be two functions of $n$
<li class="fragment roll-in"> Let $f_1(n)$, be the fastest growing term of $f(n)$, stripped of
its coefficient.
<li class="fragment roll-in"> Let $g_1(n)$, be the fastest growing term of $g(n)$, stripped of
  its coefficient.<br>
  Then we can say:
  <li class="fragment roll-in"> If $f_1(n) \leq g_1(n)$ then $f(n) = O(g(n))$
<li class="fragment roll-in"> If $f_1(n) \geq g_1(n)$ then $f(n) = \Omega(g(n))$
<li class="fragment roll-in"> If $f_1(n) = g_1(n)$ then $f(n) = \Theta(g(n))$
<li class="fragment roll-in"> If $f_1(n) < g_1(n)$ then $f(n) = o(g(n))$
<li class="fragment roll-in"> If $f_1(n) > g_1(n)$ then $f(n) = \omega(g(n))$
                    </ul>
                  </section>
                  <section>
                    <h2>Useful Facts</h2>
                    <div style="text-align:left;">
                    Consider some functions
                    $f(n)$ and $g(n)$ that are asymptotically
                    nonnegative<br>
                    The following are all true statements:
                    </div>
                    <ul style="font-size:28pt;">
                      <li class="fragment roll-in"> $f(n)$ is $o(g(n))$ if $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = 0$
                      <li class="fragment roll-in"> $f(n)$ is $\omega(g(n))$ if $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \infty$
                      <li class="fragment roll-in">  Note, $f(n)$ is $\omega(g(n))$ $\iff$ $g(n)$ is $o(f(n))$
                    </ul>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: -180px; margin-top: -70px">
                      <img src="figures/Lhopital.png" alt="L'Hopital" style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); margin-bottom: -5%" width="160px" >
                      <div style="font-size:10pt;">L'Hopital</div>
                    </div>
                    <div id="header-left" style="margin-left: -180px; margin-top: -70px">
                      <img src="figures/Johann_Bernoulli.jpeg" alt="Bernoulli" style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); margin-bottom: -5%" width="160px" >
                      <div style="font-size:10pt;">Johann Bernoulli</div>
                    </div>
                    <h2>L'Hopital's Rule</h2>
                    <ul style="list-style-type: none;">
                    <li class="fragment roll-in"> Let $f(n)$ and
             $g(n)$ be differentiable functions that both go to
                      infinity. Then by L'Hopital:
                      <blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width:100%; text-align:center;">
                        $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \lim_{n\rightarrow\infty}\frac{f'(n)}{g'(n)}$
                      </blockquote>
                    <li class="fragment roll-in"> The general L'Hopital's Rule:
                      <blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width:100%; text-align:center;">
                        $\lim_{n\rightarrow c}\frac{f(n)}{g(n)} = \lim_{n\rightarrow c}\frac{f'(n)}{g'(n)}$
                      </blockquote>
                    </ul>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: -180px; margin-top: -70px">
                      <img src="figures/Lhopital.png" alt="L'Hopital" style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); margin-bottom: -5%" width="160px" >
                      <div style="font-size:10pt;">L'Hopital</div>
                    </div>
                    <div id="header-left" style="margin-left: -180px; margin-top: -70px">
                      <img src="figures/Johann_Bernoulli.jpeg" alt="Bernoulli" style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); margin-bottom: -5%" width="160px" >
                      <div style="font-size:10pt;">Johann Bernoulli</div>
                    </div>
                    <h2>L'Hopital's Rule: an aside</h2>
                      <blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width:100%; text-align:left;">
I recognize I owe much to Messrs. Bernoulli’s insights, above all to the young (John), currently a professor in Groningue. I did unceremoniously use their discoveries, as well as those of Mr. Leibniz. For this reason I consent that they claim as much credit as they please, and will content myself with what they will agree to leave me
                      </blockquote>
                      <div class='slide-footer' style="text-align: left;">
                        <a href="https://lhospitalsrule.weebly.com/history.html">https://lhospitalsrule.weebly.com/history.html</a>
                        </div>
                  </section>
                  <section>
                    <h2>More Examples</h2>
                    The following are all true statements:<br>
                    <ul style="list-style-type: none;">
                      <li class="fragment roll-in"> $\sum_{i=1}^n i^2$ is $O(n^3)$, $\Omega(n^3)$, and $\Theta(n^3)$
                      <li class="fragment roll-in"> $\log n$ is $o(\sqrt{n})$
                      <li class="fragment roll-in"> $\log n$ is $o(\log^2n)$
                      <li class="fragment roll-in"> $10,000n^2+25n$ is $\Theta(n^2)$
                    </ul>
                  </section>
                  <section>
                    <h2>True or False (justify your answer) <i class="far fa-comments"></i></h2>
                    <ol>
                      <li class="fragment roll-in"> $n^3+4$ is $\omega(n^2)$
                      <li class="fragment roll-in"> $n \log n^3$ is $\Theta(n\log n)$
                      <li class="fragment roll-in"> $\log^3 5n^2$ is $\Theta(\log n)$
                      <li class="fragment roll-in"> $10^{-10}n^2 + n$ is $\Theta(n)$
                      <li class="fragment roll-in"> $n\log n$ is $\Omega(n)$
                      <li class="fragment roll-in"> $n^3 + 4$ is $o(n^4)$
                    </ol>
                  </section>
                  <section>
                    <h2>Proofs</h2>
                    <ul>
                      <li class="fragment roll-in"> To prove an
asymptotic relationship between two functions $f(n)$ and $g(n)$ takes
more effort
                      <li class="fragment roll-in"> To do this, we
need to start with the formal definition of the relationship we are
trying to establish
                      <li class="fragment roll-in"> In particular, we
will need to show that there exist constants which satisfy the
appropriate definitions
                    </ul>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: -180px; margin-top: -10px">
                      <h3>Example 1</h3>
                    </div>

                    <div style="text-align:left;">
                      Let $f(n) = 10\log^2 n + \log n$, $g(n) = \log^2 n$. Let’s show that $f(n) = \Theta(g(n))$.
                    </div>
                    <ul>
                      <li class="fragment  roll-in"> We  want positive
constants $c_1$, $c_2$  and $n_0$ such that $0 \leq  c_1g(n) \leq f(n)
\leq c_2g(n)$ for all $n \geq n_0$
                      <li class="fragment roll-in"> In other words, we
                      want $c_1$, $c_2$ and $n_0$ such that:
                        <blockquote style="width:100%;text-align:center;">
                          $0 \leq c_1 \log^2 n \leq 10 \log^2 n + \log n \leq c_2 \log^2 n$
                        </blockquote>
                      <li class="fragment roll-in"> Dividing by $\log^2 n$, we get:
                        <blockquote style="width:100%;text-align:center;">
                          $0 \leq c_1 \leq 10 + 1/\log n \leq c_2$
                        </blockquote>
                      <li class="fragment roll-in"> If we choose $c_1
= 1$, $c_2 = 11$ and $n_0 = 2$, then the above inequality will hold
for all $n \geq n_0$

                    </ul>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: -180px; margin-top: -10px">
                      <h3>Example 2</h3>
                    </div>

                    <div style="text-align:left;font-size:28pt;">
                      Let $f(n) = \log^a n$, $g(n) = n^b$ for any constants $a$ and $b > 0$. Let’s show that $f(n) = o(g(n))$.
                    </div>
                    <ul style="font-size:28pt;">
                      <li class="fragment roll-in"> For any positive constant $c$, we want to show $\exists n_0 > 0$
such that $0 \leq f(n) < cg(n)$ for all $n \geq n_0$.
<li class="fragment roll-in"> In other words, we want to show that $\exists n_0 > 0$ such
                          that
                          <blockquote style="width:100%;text-align:center;">
                            $0 \leq log^a n < cn^b$
                          </blockquote>
                          <li class="fragment roll-in"> Dividing by $n^b$, we get:
                          <blockquote style="width:100%;text-align:center;">
                            $0 \leq \frac{log^a n}{n^b} \leq c$
                          </blockquote>
                          <li class="fragment roll-in"> We know that $\lim_{n\rightarrow \infty} \frac{\log^a n}{n^b} = 0$ (by L’Hopital) so for any
constant $c$, there must be a $n_0$ such that the above inequality is satisfied for all $n \geq n_0$.
                    </ul>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: -180px; margin-top: -10px">
                      <h3>Example 3</h3>
                    </div>

                    <div style="text-align:left;font-size:28pt;">
                      Let $f(n)$ be asymptotically positive and let $g(n) = 10f(n)$. Let’s show that $f(n) = \Theta(g(n))$.
                    </div>
                    <ul style="font-size:28pt;">
                      <li class="fragment roll-in"> We must show that
                        there are positive constants $c_1$, $c_2$ and
                        $n_0$ such that:
                        <blockquote style="width:100%;text-align:center;">
                          $c_1 10f(n) \leq f(n) \leq c_210f(n)$
                        </blockquote>
                      <li class="fragment roll-in"> Dividing through by $f(n)$, we have
                        <blockquote style="width:100%;text-align:center;">
                          $c_110 ≤ 1 ≤ c_210$
                        </blockquote>
                      <li class="fragment roll-in"> If we choose $c_1 = c_2 = 1/10$ and $n_0 = 1$, then the above
inequality is satisfied for all $n \geq n_0$
                    </ul>
                  </section>
                  <section>
                    <h2>Exercise <i class="fas fa-pen-square"></i></h2>
                    <div style="text-align:left;">
                    Let $f(n)$ be an asympotitically positive function and let $g(n) = f(n) \log n$. Show that $f(n) = o(g(n))$
                    </div>
                    <ul>
<li class="fragment roll-in"> Write down exactly what needs to be shown to prove that
$f (n) = o(g(n))$
<li class="fragment roll-in"> Now solve for $n_0$ as a function of $c$ in the above statement
                    </ul>
                  </section>
                  <section>
                    <h2><i class="far fa-comments"></i> Let's discuss your solutions <i class="far fa-comments"></i></h2>
                  </section>

                  <section>
                    <h2> Solution (1/2) </h2>
                    <div style="text-align:left;">
                      Let $f(n)$ be an asympotitically positive function and let $g(n) = f(n) \log n$. Show that $f(n) = o(g(n))$
                    </div>
                    <ul style="font-size:28pt;">
                      <li class="fragment roll-in"> For any positive
                      constant $c$, we want to show there is a $n_0 >
                      0$ such that $0 \leq f(n) < cg(n)$ for all $n
                      \geq n_0$.

                                                  <li class="fragment
                      roll-in"> In other words, we want to show that
                      $\exists n_0 > 0$ such that
          <blockquote style="width:100%;text-align:center;">
            $0 \leq f(n) < cf(n)\log n$
          </blockquote>
          <li class="fragment roll-in"> Dividing by $f(n)\log n$, we get: $0 \leq \frac{1}{\log n} < c$
          <li class="fragment roll-in"> We know that $\lim_{n\rightarrow \infty} \frac{1}{\log n} = 0$. Thus for any constant $c$, there must be a $n_0$ such that the above inequality is satisfied for all $n>n_0$
                    </ul>
                  </section>
                  <section>
                    <h2> Solution (2/2) </h2>
                    <div style="text-align:left;font-size:20pt;">
                      Let $f(n)$ be an asympotitically positive function and let $g(n) = f(n) \log n$. Show that $f(n) = o(g(n))$
                    </div>
                    <ul style="font-size:20pt;">
                      <li class="fragment roll-in"> For any positive
                      constant $c$, we want to show there is a $n_0 >
                      0$ such that $0 \leq f(n) < cg(n)$ for all $n
                      \geq n_0$.

                                                  <li class="fragment roll-in"> In other words, we want to show that
                      $\exists n_0 > 0$ such that
          <blockquote style="width:100%;text-align:center;">
            $0 \leq f(n) < cf(n)\log n$
          </blockquote>
                <li class="fragment roll-in"> Dividing by $f(n)\log n$, we get:
                  \begin{align}
                  \frac{1}{\log n} & < c\\
                                       1 & < \log n^c                    \\
                                             2^\frac{1}{c} & < n\\
                                            \end{align}
          <li class="fragment roll-in"> <alert>  $\forall c$ when $n_0 > 2^\frac{1}{c}$, $\forall n> n_0$, $f(n) < cg(n)$
              </alert>

                    </ul>
                  </section>

                  <section>
                    <h2>Asymptotic Analysis: take away</h2>
                    <ul>
                      <li class="fragment roll-in"> In studying
                        behavior of algorithms, we’ll be more
                        concerned with rate of growth than with
                        constants
                      <li class="fragment roll-in"> $O$, $\Theta$,
                      $\Omega$, $o$, $\omega$ give us a way to talk
                      about rates of growth
                      <li class="fragment roll-in"> Asymptotic
                      analysis is an extremely useful way to compare
                      run times of algorithms
                      <li class="fragment roll-in"> However, empirical
                      analysis is also important (homework may contain questions for this)
                    </ul>
                  </section>


                  <section>
                    <h2>Assigned reading</h2>
                    <row>
                      <col60>
                        <img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1);" width="80%"
                             src="figures/cormen_algs.jpeg" alt="Cormen Algs">
                      </col60>
                      <col40>
                        Complete Chapter 3: Growth of Functions<br>
                        if not already completed
                      </col40>
                    </row>
                  </section>
		</section>

                <section>
                  <section>
                    <h1>Recurrence Relations</h1>
                  </section>
                  <section>
                    <div id="header-right" style="margin-right: 100px; margin-top: -220px; width:720px;">
                    <pre class="python" style="font-size:12pt;"><code data-trim data-noescape data-line-numbers>
def binary_search(sequence, start, end, key):
    if end <= start:
        return False
    middle = (end + start) // 2
    if sequence[middle] == key:
        return True
    elif sequence[middle] > key:
        return binary_search(sequence, start, middle - 1, key)
    else:
        return binary_search(sequence, middle + 1, end, key)
                    </code></pre>
                    </div>
                    <h2></h2>
                    <ul>
<li class="fragment roll-in"> Getting the run times of recursive algorithms can be challenging
<li class="fragment roll-in"> Recall our algorithm for binary search
<li class="fragment roll-in"> Let $T(n)$ be the run time of this algorithm on an array of size $n$
<li class="fragment roll-in"> Then we can write $T(1) = 1, T(n) = T(n/2) + 1$
                    </ul>
                  </section>
                  <section>
                    <h2>What?</h2>
                    <ul>
<li class="fragment roll-in"> $T(n)$ is a function giving the run time of Binary Search on
an array of size $n$
<li class="fragment roll-in"> $T(n) = T(n/2) + 1$ is a an example of a recurrence relation
<li class="fragment roll-in"> A Recurrence Relation is any equation for a function $T(n)$,
where $T(n)$ appears on both the left and right sides of the
equation.
<li class="fragment roll-in"> We always want to “solve” these recurrence relation by getting an equation for $T(n)$, where $T$ appears on just the left
side of the equation

                    </ul>
                  </section>
                  <section>
                    <h2>Use of Recurrences</h2>
                    <ul>
<li class="fragment roll-in"> We can use recurrence relations to analyze many properties
of recursive algorithms e.g. run time, value returned, etc.
<li class="fragment roll-in"> To do this we need to:
  <ol>
    <li>write down the correct recurrence
      relation
    <li>solve the recurrence relation
  </ol>
<li class="fragment roll-in"> Step 1 is usually easier than step 2
                    </ul>
                  </section>
                  <section>
                    <h2>A side note</h2>
                    <ul>
                      <li class="fragment roll-in"> The running time of an algorithm on a constant size input is
                        always $\Theta(1)$
                      <li class="fragment roll-in"> Thus for convenience, we frequently omit statements of the
boundary conditions and just assume $T(n)$ is constant when
$n$ is a constant.
<li class="fragment roll-in"> Example: Instead of saying “If $n = 1$, $T(n) = \Theta(1)$, and if
$T(n) = 2T(n/2) + \Theta(n)$”, we just say “$T(n) = 2T(n/2) +
\Theta(n)$”

                    </ul>
                  </section>
                  <section>
                    <h2><code>alg1</code></h2>
                    <pre class="python"><code data-trim data-noescape data-line-numbers>
def alg1(n):
    if n < 1:
        return 1
    else:
        return alg1(n//2) + alg1(n//2) + n
           </code></pre>
                    <ul>
<li class="fragment roll-in"> Let $T(n)$ be the run time of <code>alg1</code> on input $n$
<li class="fragment roll-in"> Then we can write $T(n) = 2T(n/2) + 1$
<li class="fragment roll-in"> Let $f(n)$ be the value returned by <code>alg1</code> on input $n$
<li class="fragment roll-in"> Then we can write $f(n) = 2f(n/2) + n$ and $f(1) = 1$
                    </ul>
                  </section>
                  <section>
                    <h2>What now?</h2>
                    <ul>
                      <li class="fragment roll-in"> To get the “real”
run time or value returned, we need to solve the recurrence relation
                      <li class="fragment roll-in"> This means that no
                      function appear on the right hand side
                      <li class="fragment roll-in"> We will review
                        several techniques for solving recurrences including:
                        <ul>
                          <li>the substitution method,
                          <li>recursion trees,
                          <li>the Master method, and
                          <li>annihilators
                        </ul>
                    </ul>
                  </section>
                </section>
                <section>
                  <h2>See you</h2>
                  Monday January 23rd
                </section>

              </div>

            </div>

            <script src="dist/reveal.js"></script>

            <!-- <link rel="stylesheet" href="lib/css/monokai.css"> -->
            <script src="plugin/highlight/highlight.js"></script>
            <script src="plugin/math/math.js"></script>
            <script src="plugin/chalkboard/plugin.js"></script>
            <script src="plugin/notes/notes.js"></script>
            <script src="plugin/zoom/zoom.js"></script>
            <script src="plugin/menu/menu.js"></script>
            <script>
              // Full list of configuration options available at:
              // https://github.com/hakimel/reveal.js#configuration
              let notes = document.querySelectorAll('aside.notes');
              notes.forEach(n => {
	      let html = n.innerHTML;
	      html = html.trim().replace(/\n/g, '<br/>');
	      n.innerHTML = html;
              });
              Reveal.initialize({
                  // history: true,
                  hash: true,
                  margin: 0.01,
                  minScale: 0.01,
                  maxScale: 1.23,
                  menu: {
                      themes: true,
                      openSlideNumber: true,
                      openButton: false,
                  },
                  customcontrols: {
                      slideNumberCSS : 'position: fixed; display: block; right: 90px; top: auto; left: auto; width: 50px; bottom: 30px; z-index: 31; font-family: Helvetica, sans-serif; font-size:  12px; line-height: 1; padding: 5px; text-align: center; border-radius: 10px; background-color: rgba(128,128,128,.5)',
                      controls: [
                          { icon: '<i class="fa fa-caret-left"></i>',
                            css: 'position: fixed; right: 60px; bottom: 30px; z-index: 30; font-size: 24px;',
                            action: 'Reveal.prev(); return false;'
                          },
                          { icon: '<i class="fa fa-caret-right"></i>',
                            css: 'position: fixed; right: 30px; bottom: 30px; z-index: 30; font-size: 24px;',
                            action: 'Reveal.next(); return false;'
                          }
                      ]
                  },
                  chalkboard: {
                      boardmarkerWidth: 1,
                      chalkWidth: 2,
                      chalkEffect: 1,
                      slideWidth: Reveal.width,
                      slideHeight: Reveal.height,
                      toggleNotesButton: false,
                      toggleChalkboardButton: false,
                      //src: "chalkboards/chalkboard_em2.json",
                      readOnly: false,
                      theme: "blackboard",
                      eraser: { src: "plugin/chalkboard/img/sponge.png", radius: 30},
                  },

                  math: {
                      mathjax: 'https://cdn.jsdelivr.net/gh/mathjax/mathjax@2.7.8/MathJax.js',
                      config: 'TeX-AMS_SVG-full',
                      // pass other options into `MathJax.Hub.Config()`
                      TeX: {
                          Macros: {
        	              RR: '\\mathbb{R}',
        	              PP: '\\mathbb{P}',
        	              EE: '\\mathbb{E}',
        	              NN: '\\mathbb{N}',
        	              vth: '\\vec{\\theta}',
                              loss: '{\\cal l}',
                              hclass: '{\\cal H}',
                              CD: '{\\cal D}',
                              def: '\\stackrel{\\text{def}}{=}',
                              pag: ['\\text{pa}_{{\cal G}^{#1}}(#2)}', 2],
                              vec: ['\\boldsymbol{\\mathbf #1}', 1],
        	              set: [ '\\left\\{#1 \\; : \\; #2\\right\\}', 2 ],
                              bm: ['\\boldsymbol{\\mathbf #1}', 1],
                              argmin: ['\\operatorname\{arg\\,min\\,\}'],
                              argmax: ['\\operatorname\{arg\\,max\\,\}'],
                              prob: ["\\mbox{#1$\\left(#2\\right)$}", 2],
                          },
                          loader: {load: ['[tex]/color']},
                          extensions: ["color.js"],
                          tex: {packages: {'[+]': ['color']}},
                          svg: {
                              fontCache: 'global'
                          }
                      }
                  },

                  plugins: [ RevealMath, RevealChalkboard, RevealHighlight, RevealNotes, RevealZoom, RevealMenu ],

              });

              Reveal.configure({ fragments: true }); // set false when developing to see everything at once
              Reveal.configure({ slideNumber: true });
              //Reveal.configure({ history: true });
              Reveal.configure({ slideNumber: 'c / t' });
              Reveal.addEventListener( 'darkside', function() {
                  document.getElementById('theme').setAttribute('href','dist/theme/aml_dark.css');
              }, false );
              Reveal.addEventListener( 'brightside', function() {
                  document.getElementById('theme').setAttribute('href','dist/theme/aml.css');
              }, false );

            </script>

            <style type="text/css">
              /* 1. Style header/footer <div> so they are positioned as desired. */
              #header-left {
                  position: absolute;
                  top: 0%;
                  left: 0%;
              }
              #header-right {
                  position: absolute;
                  top: 0%;
                  right: 0%;
              }
              #footer-left {
                  position: absolute;
                  bottom: 0%;
                  left: 0%;
              }
            </style>

            <!-- // 2. Create hidden header/footer -->
            <div id="hidden" style="background; display:none;">
              <div id="header">
                <div id="header-left"><h4>CS4520</h4></div>
                <div id="header-right"><h4>Algorithms</h4></div>
                <div id="footer-left">
                  <img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1);" width="100"
                       src="figures/flowchart.png" alt="robot learning">
                </div>
              </div>
            </div>


            <script type="text/javascript">
              // 3. On Reveal.js ready event, copy header/footer <div> into each `.slide-background` <div>
              var header = $('#header').html();
              if ( window.location.search.match( /print-pdf/gi ) ) {
                  Reveal.addEventListener( 'ready', function( event ) {
                      $('.slide-background').append(header);
                  });
              }
              else {
                  $('div.reveal').append(header);
              }
            </script>

  </body>
</html>