docs/notes/algorithms.html

<!doctype html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">

  <title>Algorithms</title>

  <link rel="stylesheet" href="css/reset.css">
  <link rel="stylesheet" href="css/reveal.css">
  <link id="theme" rel="stylesheet" href="css/theme/black.css">
  <link rel="stylesheet" href="css/style.css">
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.5.0/css/font-awesome.min.css">

  <!-- Theme used for syntax highlighting of code -->
  <link rel="stylesheet" href="lib/css/monokai.css">
  <script src="js/diagrams.js"></script>

  <!-- 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.css';
    document.getElementsByTagName('head')[0].appendChild(link);
  </script>
</head>

<body>
  <div class="reveal">
    <div class="slides">
      <section class="center">
        <h1>Algorithms</h1>
      </section>
      <section>
        <section>
          <h2>Motivation</h2>
          <h5>Why we need algorithms, and what they are.</h5>
        </section>
        <section>
          <h3>Algorithms: Why</h3>
          <p>Once we solve a given problem, how can we tell people about our solution?</p>
          <p class="fragment">
            Consider baking; you transmit recipes, detailing how much of ingredient $x$ at what time.
          </p>
          <p class="fragment">
            Consider assembling furniture; you send blueprints for each step, including where screw $y$ goes and
            when it should be installed.
          </p>
          <p class="fragment">
            Similarly to these scenarios, when we solve a computational problem, we want to transmit the solution to
            others who may make use of it. In computer science, our recipes for success are called <em>algorithms</em>
          </p>
        </section>
        <section>
          <h3>Algorithms: How</h3>
          <p>
            To convey algorithms to others, we use <em>pseudocode</em>, which is intended to be read by humans, not
            executed by computers.
          </p>
          <p class="fragment">
            In this class, most pseudocode will bear a striking resemblance to Python, a simple,
            high-level, interpreted language
          </p>
          <p class="fragment">
            <pre class="fragment"><code class="python" data-trim="">
              def algorithm(x: type, y: type) -> output:
                step 1
                step 2
                step 3
            </code></pre>
          </p>
        </section>
        <section>
          <h3>Algorithms: Implementing</h3>
          <p>We implement algorithms as functions.</p>
        </section>
        <section>
          <h3>Conclusions</h3>
          <p>In this class we will study the creation, implementation, and analysis of algorithms extensively.</p>
          <p class="fragment">
            Some questions we will answer:
            <ul>
              <li class="fragment">How fast can we sort things?</li>
              <li class="fragment">How fast can we search for substrings in a given text?</li>
              <li class="fragment">How fast can we determine if an element is present in a given collection?</li>
            </ul>
          </p>
        </section>
      </section>
      <section>
        <section class="center">
          <h2>Searching</h2>
          <h5>How to find things</h5>
        </section>
        <section>
          <h3>Searching: Unordered Arrays of Integers</h3>
          <p class="fragment">Problem: Given an unordered array of elements, how can you tell if $x \in A$</p>
          <p class="fragment">Solution: Traverse the entirety of the array, and check each element.</p>
        </section>
        <section>
          <h3>Searching: Ordered Arrays of Integers</h3>
          <p class="fragment">Problem: Assume $A$ is now sorted, create an algorithm to tell if $x \in A'$</p>
          <p class="fragment">
            <pre>
            <code class="python" data-trim>
              def binary_search(x: int, A: List[int]) -> bool:
                if A == []: 
                  return False
                elif A[len(A) // 2] == x: 
                  return True
                elif A[len(A) // 2] < x: 
                  return binary_search(x, A[len(A) // 2:]) 
                else: 
                  return binary_search(x, A[:len(A) // 2]) 
            </code>
          </pre>
          </p>
        </section>
        <section>
          <h3>Comparing our two approaches</h3>
          <p>From our previous two approaches, which do you think is faster? Why?</p>
          <p class="fragment">Linear search has to look at all $n$ elements.</p>
          <p class="fragment">Binary search cuts the search space in half at each call</p>
          <p class="fragment">How many elements must ordered search examine?</p>
          <p class="fragment">$\log_2 n$</p>
          <p class="fragment">
            <strong>Which would you prefer? $n$ or $\log_2 n$</strong>
          </p>
        </section>
      </section>
      <section>
        <section>
          <h2>Algorithm Analysis</h2>
          <h5>How to prove one algorithm is faster than another</h5>
        </section>
        <section>
          <h3>Motivation</h3>
          <p>We need some way to decide which algorithms are better than others</p>
          <p class="fragment">What are some ways we can <em>measure runtimes?</em></p>
          <ul>
            <li class="fragment">Empirically</li>
            <li class="fragment">Analytically</li>
          </ul>
          <aside class="notes">
            empirically is like using a stopwatch
            analytically is analyzing mathematical operations to create a function of runtime over all inputs.
          </aside>
        </section>
        <section>
          <h3>Empirical Analysis</h3>
          <p>The stopwatch approach</p>
          <p class="fragment">Vary your inputs, timing each execution, then plot the results.</p>
          <p class="fragment column">
            Pros:
            <ul>
              <li class="fragment">Easy</li>
              <li class="fragment">Quick</li>
              <li class="fragment">Good for comparing similar algorithms</li>
            </ul>
          </p>
          <p class="fragment column">
            Cons:
            <ul>
              <li class="fragment">Hardware dependant</li>
              <li class="fragment">Doesn't Generalize</li>
              <li class="fragment">Have to implement the algorithm</li>
              <li class="fragment">Can take months to exhaustively time</li>
              <li class="fragment">Need input data</li>
            </ul>
          </p>
        </section>
        <section>
          <h3>Asymptotic Analysis</h3>
          <p>Framing runtime as a function of an algorithms' inputs</p>
          <p class="fragment">How? <span class="fragment">Counting basic operations</span></p>
          <pre class="fragment"><code class="python" data-trim>
            def search(A: List[int], key: int) -> bool:
              for element in A:
                if element == key:
                  return True
              return False
          </code></pre>
          <p class="fragment">For each of the $n$ elements, search performs 1 operation, so $T(n) = n$</p>
        </section>
        <section>
          <h3>Asymptotic Analysis: Bounds</h3>
          <p>There are two primary ways to describe an algorithms asymptotic performance</p>
          <p class="fragment">
            <ul>
              <li>Upper Bound: the algorithm can do no <strong>worse</strong> than this</li>
              <li>Lower Bound: the algorithm can do no <strong>better</strong> than this</li>
            </ul>
          </p>
        </section>
        <section>
          <h3>Big-Oh, Omega, and Theta</h3>
          <ul>
            <li class="fragment">
              $O(?)$
              <ul>
                <li>Pronounced "Big-Oh"</li>
                <li>Represents the upper bound</li>
                <li>May not always be <em>tight</em></li>
              </ul>
            </li>
            <li class="fragment">
              $\Omega(?)$
              <ul>
                <li>Pronounced "Big-Omega"</li>
                <li>Represents the lower bound</li>
                <li>May not always be <em>tight</em></li>
              </ul>
            </li>
            <li class="fragment">
              $\Theta(?)$
              <ul>
                <li>Pronounced "Big-Theta"</li>
                <li>Used when $O(T(n)) == \Omega(T(n))$ for a given algorithm</li>
                <li>Is the strongest promise, since the upper and lower bounds must be equal</li>
              </ul>
            </li>
          </ul>
        </section>
        <section>
          <h3>$O(?)$, $\Omega(?)$, $\Theta(?)$</h3>
          <pre><code class="python" data-trim>
            def f1(A: List[int], sum: int) -> bool:
              for x in A:
                for y in A:
                  if x + y == sum:
                    return True
              return False
          </code></pre>
          <p class="fragment">$O(n^2), \Omega(1)$</p>
        </section>
        <section>
          <h3>$O(?)$, $\Omega(?)$, $\Theta(?)$</h3>
          <pre><code class="python" data-trim>
            def f2(x: int) -> int:
              product = 1
              for i in range(1, x):
                product *= i
              return product
          </code></pre>
          <p class="fragment">$O(n), \Omega(n), \Theta(n)$</p>
        </section>
        <section>
          <h3>Visual Growth</h3>
          <canvas id="visualGrowth"></canvas>
        </section>
        <section>
          <h3>Dominant Terms</h3>
          <p>
            Asymptotic analysis can be thought of as a limit problem.

            $$O(kn^2) \rightarrow \lim_{n \rightarrow \infty} O(kn^2) = O(n^2)$$

            As $n \rightarrow \infty$, we know that $k$ becomes irrelevant
          </p>
          <p class="fragment">Thus we will normally discuss "classes" of algorithms</p>
        </section>
        <section>
          <h3>Ordering Algorithms by Speed</h3>
          <table>
            <thead>
              <th>Nodation</th>
              <th>Name</th>
            </thead>
            <tbody>
              <tr>
                <td>$O(1)$</td>
                <td>Constant Time</td>
              </tr>
              <tr>
                <td>$O(\log n)$</td>
                <td>Logarithmic</td>
              </tr>
              <tr>
                <td>$O(n)$</td>
                <td>Linear</td>
              </tr>
              <tr>
                <td>$O(n \cdot \log n)$</td>
                <td>Linearithmic</td>
              </tr>
              <tr>
                <td>$O(n^c)$</td>
                <td>Polynomial</td>
              </tr>
              <tr>
                <td>$O(c^n)$</td>
                <td>Exponential</td>
              </tr>
              <tr>
                <td>$O(n!)$</td>
                <td>Factorial</td>
              </tr>
            </tbody>
          </table>
        </section>
      </section>
      <section>
        <section>
          <h2>Recursion</h2>
          <h5>How we can analyze the runtime of recursive programs</h5>
        </section>
        <section>
          <h3>Recursive Problem Solving</h3>
          <p>Breaking down a large problem into a smaller one.</p>
          <pre><code class="python" data-trim>
            def sum(A: List[int]) -> int:
              sum = 0
              for element in A:
                sum += element
              return sum

            def sum(A: List[int]) -> int:
              if A == []: return 0
              else: return A[0] + sum(A[1:])
          </code></pre>
          <p class="fragment">Base Case; Recursive Call</p>
        </section>
        <section>
          <h3>Select the best base case</h3>
          <pre><code class="python" data-trim>
            def sum(A: List[int]) -> int:
              if len(A) == 2: return A[0] + A[1]
              else: return A[0] + sum(A[1:])

            def sum(A: List[int]) -> int:
              if len(A) == 1: return A[0]
              else: return A[0] + sum(A[1:])
            
            def sum(A: List[int]) -> int:
              if len(A) == 0: return A[0]
              else: return A[0] + sum(A[1:])
          </code></pre>
        </section>
        <section>
          <h3>Recursive Definitions</h3>
          <pre><code class="python" data-trim>
            def factorial(n: int) -> int:
              if n <= 1: return 1
              else: return n * fact(n - 1)
          </code></pre>
          <p>Factorial of n = $$n! = (n - 1)! \cdot n, \forall n > 1; 1! = 0! = 1$$</p>
        </section>
        <section>
          <h3>Recurrence Relations</h3>
          <p>Factorial of n = $$T(n) = T(n - 1) + 1; T(0) = T(1) = 1$$</p>
          <p class="fragment">Again, we specify the base case, by saying the time to compute $n = 0$ or $n = 1$ takes 1
            operation.</p>
        </section>
        <section>
          <h3>Unrolling a Recurrence Relation</h3>
          <p>
            $$
            \begin{align}
            T(n) &= T(n - 1) + 1; T(0) = T(1) = 1 \\
            T(n - 1) &= T(n - 2) + 1 \\
            T(n) &= (T(n - 2) + 1) + 1 \\
            T(n - 2) &= T(n - 3) + 1 \\
            T(n) &= ((T(n - 3) + 1) + 1) + 1 \Rightarrow T(n - 3) + 3 \\
            &= T(n - k) + k \textit{ (Substitute k)} \\
            n - k &= 0 \textit{ (Solve the base case)} \\
            n &= k \\
            T(n) &= T(n - n) + n \Rightarrow n \Rightarrow O(n)
            \end{align}
            $$
          </p>
        </section>
        <section>
          <h3>Unrolling a Recurrence Relation: 2</h3>
          <p>
            $$
            \begin{align}
            T(n) &= n + T(n - 1) \\
            &= n + (n - 1 + T(n - 2)) \\
            &= n + (n - 1 + (n - 2 + T(n - 3))) \\
            &= n + (n - 1 + (n - 2 + (n - 3 + T(n - 4)))) \\
            &= n + (n - 1 + (n - 2 + (n - 3 + (n - 4 + (... + 1)))) \\
            &= \sum_{i = 1}^n i \Rightarrow \frac{n(n + 1)}{2}
            \end{align}
            $$
          </p>
        </section>
        <section>
          <h3>Unrolling a Recurrence Relation: 3</h3>
          <p>
            \begin{align}
            T(n) &= 2T(n - 1) + 3; T(1) = 1 \\
            &= 2(2T(n - 2) + 3) + 3 \\
            &= 2(2(2T(n - 3) + 3) + 3) + 3 \\
            &= 2(2^2 T(n - 3) + 2 \cdot 3 + 3) + 3 \\
            &= 2^3 T(n - 3) + 2^2 \cdot 3 + 2 \cdot 3 + 3 \\
            &= 2^k T(n - k) + \sum_{i = 0}^{k - 1} 2^i \cdot 3 \\
            T(n) &= 2^{n - 1} + \sum_{i = 0}^{n - 2} 2^i \cdot 3 \\
            T(n) &= 2^{n - 1} + 3 (2^{n - 1} - 1) = O(2^n)
            \end{align}
          </p>
        </section>
        <section>
          <h3>Summation Identities</h3>
        </section>
      </section>
    </div>
  </div>
  <script src="js/reveal.js">
  </script>
  <script>
    Reveal.initialize({
      dependencies: [{
          src: 'plugin/markdown/marked.js'
        },
        {
          src: 'plugin/markdown/markdown.js'
        },
        {
          src: 'plugin/notes/notes.js',
          async: true
        },
        {
          src: 'plugin/highlight/highlight.js',
          async: true
        },
        {
          src: 'plugin/math/math.js',
          async: true
        },
        {
          src: 'plugin/menu/menu.js',
          async: true
        },
        {
          src: 'plugin/chalkboard/chalkboard.js',
          async: true
        }
      ],
      hash: true,
      center: false,
      fragmentInURL: true,
      keyboard: {
        // toggle notes canvas when 'c' is pressed
        67: function () {
          RevealChalkboard.toggleNotesCanvas()
        },
        // toggle chalkboard when 'b' is pressed
        66: function () {
          RevealChalkboard.toggleChalkboard()
        },
        // clear chalkboard when 'DEL' is pressed
        46: function () {
          RevealChalkboard.clear()
        },
        // reset chalkboard data on current slide when 'BACKSPACE' is pressed
        8: function () {
          RevealChalkboard.reset()
        },
        // download recorded chalkboard drawing when 'd' is pressed
        68: function () {
          RevealChalkboard.download()
        },
      },
      chalkboard: {
        toggleChalkboardButton: {
          left: "80px"
        },
        toggleNotesButton: {
          left: "130px"
        },
        color: ['rgba(255, 255, 255, 1)', 'rgba(255, 255, 255, 1)']
      },
      menu: {
        titleSelector: 'h2',
        hideMissingTitles: true,
      }
    });
  </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/Chart.js/2.8.0/Chart.bundle.min.js"
    integrity="sha256-xKeoJ50pzbUGkpQxDYHD7o7hxe0LaOGeguUidbq6vis=" crossorigin="anonymous"></script>
  <script>
    var range = [...Array(10).keys()];
    var ctx = document.getElementById("visualGrowth");
    var chart = new Chart(ctx, {
      type: 'line',
      data: {
        labels: range,
        datasets: [{
            data: range.map(x => 5 * x),
            label: "x",
            backgroundColor: "#ffffff",
            borderColor: "#ffffff",
            fill: false,
          },
          {
            data: range.map(x => x ** 2),
            label: "x^2",
            backgroundColor: "#ffffff",
            borderColor: "#ffffff",
            fill: false,
          }
        ]
      },
      options: {
        scales: {
          xAxes: [{
            // type: 'linear',
            // ticks: {
            //   // stepSize: 10,
            // }
          }]
        }
      }
    });
  </script>
</body>

</html>