GettingStarted.html

<!DOCTYPE html>
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
    <head>
        <meta name="viewport"
              content="width=device-width, initial-scale=1">
        <meta charset="UTF-8">
        <link href="style.css" rel="stylesheet" type="text/css"/>
        <title>
            Design and Analysis of Algorithms: Getting Started
        </title>
    </head>

    <body>
    <header id="header">
        <a id="logo" href="index.html">
            <img src="graphics/Julia.png" alt="">
            <span class="brand-text">Design &amp; Analysis of Algorithms</span>
        </a>
        <nav id="user-tools">
            <a href="index.html">Home</a>
            <a href="about.html">About</a>
            <a href="feedback.html">Feedback</a>
        </nav>
    </header>
        <h1>
            Design and Analysis of Algorithms: Getting Started
        </h1>

            <details>
                <summary class="sum1">
                2.1 Insertion Sort
                </summary>

                <details>
                    <summary class="sum2">
                    How Insertion Sort Works
                    </summary>

                    <ul>
                        <li>
                            <b>Input</b>:
                            A sequence of <i>n</i> numbers 
                            &lang;
                            <i>a</i><sub>1</sub>,
                            <i>a</i><sub>2</sub>, . . .
                            <i>a</i><sub><i>n</i></sub>
                            &rang;
                        </li>
                        <li>
                            <b>Output</b>: A permutation (reordering)
                            &lang;
                            <i>a</i>'<sub>1</sub>,
                            <i>a</i>'<sub>2</sub>, . . .
                            <i>a</i>'<sub><i>n</i></sub>
                            &rang;
                            such that
                            <i>a</i>'<sub>1</sub> &le;
                            <i>a</i>'<sub>2</sub> &le; . . .
                            &le; <i>a</i>'<sub><i>n</i></sub>.
                        </li>
                    </ul>

                    <p>
                        Insertion sort animation:
                    </p>

                      <canvas id="canvas" width="800" height="200"
                          style="border:1px solid #000000"></canvas>
                      <script src="Algocynfas/fabric.js"></script>
                      <script src="Algocynfas/common_primitives.js">
                      </script>
                      <script src="Algocynfas/list_primitives.js"></script>
                      <script src="Algocynfas/insertion_sort.js"></script>
                      <script>
                          var canvas = new fabric.Canvas('canvas');
                          var list_to_sort = [10, 1, 56, 34,
                                                97, 88, 23, 12, 5];
                          sort(list_to_sort)
                          async function sort(list_to_sort) {
                              await window.insertionSort(list_to_sort);
                          }
                      </script>

                    <p>
                    <br />
                        <b>Pseudo-code</b>:
                        We employ this instead of "real"
                        code. It keeps the "code" language independent,
                        and allows us to express ideas in the simplest way
                        possible.
                    </p>

                </details>

                <details>
                    <summary class="sum2">
                    Loop Invariants
                    </summary>
    
                    <p>
                    A key idea in proving correctness. We must show
                    the algorithm is correct at:
                    </p>

                    <ol>
                        <li>
                            <b>Initialization</b>: The invariant is true 
                            before the loop starts.
                        </li>
                        <li>
                            <b>Maintenance</b>: The invariant is true
                            at the "top" of the loop each time through.
                        </li>
                        <li>
                            <b>Termination</b>: The invariant is true
                            when the loop terminates.
                        </li>
                    </ol>

                </details>

            </details>

        <details>
            <summary class="sum1">
                2.2 Analyzing algorithms
            </summary>

              <details>
                  <summary class="sum2">
                  Running time
                  </summary>
              
                  <p>
                      We surely do not want to talk about actual time
                      in nanoseconds, as that depends on too
                      many external things: what other
                      processes are running, details of the
                      hardware, compiler switches, etc, etc. 
                      So instead we come up with a very
                      primitive <em>abstract machine</em> (RAM=the
                      Random Access Machine: CPU + directly
                      addressable memory) which we analyze instead
                      of a real computer.  Then primitive
                      operations are memory reads/writes and operations
                      in the CPU, such as address arithmetic,
                      additions, multiplications, divisions,
                      etc. Our idea of "running time" is then
                      simply the number of operations
                      performed when the program runs.
                  </p>
              </details> 
              
              <details>
                  <summary class="sum2">
                  More trouble
                  </summary>
              
                  <p>
                    Even for inputs of a fixed size
                    (say, your favorite program
                    sorting 10 numbers), different specific
                    inputs will produce different performance.
                    For example, a clever algorithm may
                    notice that the input is already sorted
                    and not try sorting it again. So, we
                    distinguish between best- and worst-case
                    performance (minimum and maximum number
                    of operations performed by the algorithm,
                    over all possible legal inputs of a given size).
                    (There is also the concept of
                    "average-case," but it is tricky,
                    as it requires a definition of what average
                    means: technically, you need to specify
                    a <i>distribution</i> of the inputs.
                    We will mostly stay away from average-case
                    analysis and focus on the worst case;
                    we will occasionally look at the best case too.)
                  </p>
              </details> 
                
              <details>
                  <summary class="sum2">
                  Generalized statement of running time
                  </summary>
              
                    <p>
                      What we really want, is not the running time
                      (as the number of operations,
                      say, in the worst case), for a specific
                      input size, but as a function of the
                      input size, over all sizes. For example,
                      it may be that a given sorting
                      algorithm requires <em>4n<sup>2</sup> + 4n + 24</em>
                      operations to sort <em>n</em> items.
                     </p>
              </details> 
                
              <details>
                  <summary class="sum2">
                  Asymptotic behavior
                  </summary>
              
                    <p>
                    In order to make life easier, we will not
                    be focusing on the exact value of
                    such function, but on its <i>asymptotic</i> behavior.
                    </p>
                    <figure>
                      <img
                      src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Comparison_computational_complexity.svg/250px-Comparison_computational_complexity.svg.png">
                    </figure>
              </details> 
                
              <details>
                  <summary class="sum2">
                  Highest power of n
                  </summary>
              
                    <p>
                    In particular, we want to focus on the
                    highest power of n in any
                    function expressing the run time
                    of an algorithm. That is because, as
                    input size grows, that power will
                    dwarf all others in significance.
                    Consider the contribution of <em>n<sup>2</sup></em>
                    and <em>n</em> in the runtime of the
                    sorting algorithm mentioned above
                    for various values of <em>n</em>:
                    </p>
              
                    <table>
                        <tr>
                            <th>
                                n
                            </th>
                            <th>
                                n<sup>2</sup>
                            </th>
                        </tr>
                        <tr>
                            <td>10</td>
                            <td>100</td>
                        </tr>
                        <tr>
                            <td>100</td>
                            <td>10,000</td>
                        </tr>
                        <tr>
                            <td>1000</td>
                            <td>1,000,000</td>
                        </tr>
                        <tr>
                            <td>10,000</td>
                            <td>100,000,000</td>
                        </tr>
                        <tr>
                            <td>100,000</td>
                            <td>10,000,000,000</td>
                        </tr>
                    </table>
              
                    <p>
                    Now consider that Amazon is processing
                    tens of millions of transactions
                    per day: of what significance is the
                    <em>n</em> factor in the performance
                    of their servers, if they are using an algorithm with an
                    <em>n<sup>2</sup></em> factor involved to sort them?
                    </p>
                </details> 

    <details>
        <summary class="sum2">
            Quiz
        </summary>
        <ol>
            <li>
                In a theoretical analysis of algorithms, we want to discuss running time in nanoseconds.
            </li>
            <ol type="a" class="nested">
                <li>
                <input type="radio" name="q1" value="a">
                False
                </li>
                <li>
                <input type="radio" name="q1" value="b">
                True
                </li>
            </ol>
            <li>
                We will generally consider:
            </li>
            <ol type="a" class="nested">
                <li>
                <input type="radio" name="q2" value="a">
                best-case running time
                </li>
                <li>
                <input type="radio" name="q2" value="b">
                worst-case running time
                </li>
                <li>
                <input type="radio" name="q2" value="c">
                memory usage
                </li>
                <li>
                <input type="radio" name="q2" value="d">
                average-case running time
                </li>
            </ol>
            <li>
                We will mostly concern ourselves with an algorithm's behavior
            </li>
            <ol type="a" class="nested">
                <li>
                <input type="radio" name="q3" value="a">
                for small inputs
                </li>
                <li>
                <input type="radio" name="q3" value="b">
                egregiously
                </li>
                <li>
                <input type="radio" name="q3" value="c">
                asymptotically
                </li>
                <li>
                <input type="radio" name="q3" value="d">
                exponentially
                </li>
            </ol>
            <li>
                In analyzing an algorithm in terms of <i>n</i>, the number of inputs, we would like to focus on:
            </li>
            <ol type="a" class="nested">
                <li>
                <input type="radio" name="q4" value="a">
                the lowest power of <i>n</i>
                </li>
                <li>
                <input type="radio" name="q4" value="b">
                the highest power of <i>n</i>
                </li>
                <li>
                <input type="radio" name="q4" value="c">
                the logarithm of <i>n</i>
                </li>
                <li>
                <input type="radio" name="q4" value="d">
                all of the above
                </li>
            </ol>
        </ol>
        <details>
            <summary class="sum3">
                Answers
            </summary>
            <p>
                1. a; 2. b; 3. c; 4. b; 
            </p>
        </details>
    </details>

            </details> 

            <details>
                <summary class="sum1">
                Running code in your browser
                </summary>

                <p>
                We will try to provide you with many opportunities to try
                out these algorithms as possible.
                Here is Python code for a swap routine, which our textbook
                uses periodically:
                </p>
        <pre>
        
        l = [1, 2, 3]
        
        def swap(l, i, j): 
            temp = l[i]
            l[i] = l[j]
            l[j] = temp
        
        </pre>

                <p>
                    Paste that code into the Python console below:
                </p>
 
        <div class="python-console">
            <iframe style="width: 640px; height: 480px;"
                    name="embedded_python_anywhere"
                    src="https://www.pythonanywhere.com/embedded3/" scrolling="yes">
            </iframe>
            <figcaption>
                Python console
            </figcaption>
        </div>


                <p>
                    Hit return. Then type 'swap(l, 0, 2)' and hit return.
                    <br />
                    Then type 'l'.
                    <br />
                    <br />
                    You should see '[3, 2, 1]': you swapped element 0 and
                    2!
                </p>

                <p>
                    Now type in the following:
                </p>

    <pre>
        def bubble_sort(l):
            for i in range(0, len(l) - 1):
                for j in range(len(l) - 1, i, -1):
                    if l[j] &lt; l[j - 1]:
                        print("Swapping " + str(l[j]) + " and "
                                + str(l[j - 1]))
                        swap(l, j, j - 1)
            return l
    </pre>

            </details>

            <details>
                <summary class="sum1">
                Source Code
                </summary>
                <p>
            
<a href="https://github.com/gcallah/algorithms/tree/master/Java/GettingStarted">Java</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Ruby/GettingStarted">Ruby</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Go/GettingStarted">Go</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/C++/GettingStarted">C++</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Python/GettingStarted">Python</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Clojure/GettingStarted">Clojure</a><br>
                </p>
            </details>

            <details>
                <summary class="sum1">
                For Further Study
                </summary>
                <ul>
                </ul>
            </details>
            
            <details>
                <summary class="sum1">
                Homework
                </summary>
            </details>
    </body>
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-97026578-2', 'auto');
        ga('send', 'pageview');
    </script>
</html>