API tools faq
paste
Advertisement
cookchar

Algorithm Dictionary [Q2-17]

cookchar
Aug 26th, 2017
233
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Latex 32.02 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[12pt]{article}
  2. \usepackage[letterpaper,total={6.5in,9in}]{geometry}
  3. \usepackage{amsmath}
  4. \usepackage{amsfonts}
  5. \usepackage{tikz}
  6. \usepackage{ragged2e}
  7. \usepackage{listings}
  8. \usepackage{setspace}
  9. \usepackage{color}
  10. \usepackage{multicol}
  11. \usepackage{array}
  12. \renewcommand{\familydefault}{\ttdefault}
  13. \begin{document}
  14.     \sloppy
  15.     \begin{center}
  16.         \huge
  17.         \underline{Algorithms Dictionary}
  18.  
  19.         \large
  20.         Charlie Cook -- Algorithms \& Data Structures -- 5/7/17
  21.  
  22.         \small
  23.         Last Updated 5/9/17 -- 30 Pages -- 177 KB
  24.     \end{center}
  25.  
  26.     \begin{center}
  27.         \LARGE
  28.         \underline{Trees \& Sorting}
  29.     \end{center}
  30.  
  31.     \begin{justify}
  32.         \large
  33.         \underline{Binary Search Tree}
  34.  
  35.         \normalsize
  36.         A B.S.T. is a data structure in which each element has one parent and (at most) two children; The lefthand children are always less than their parents and the righthand children are always greater than their parents. Only the location of the root/topmost element is needed to access the entire tree.
  37.  
  38.         Starting from the root, go down all the lefthand children until there are no more. The lowest lefthand child is the smallest element in the tree. From there, go back to the lowest element’s parent, then to the righthand child of said parent if it exists. Repeat until you arrive back at the root. From there, go to the first righthand child and go down it’s lefthand children until there are no more. Mirror the process described for the lefthand side of the tree, working your way down instead of up this time.
  39.  
  40.         More simply, this can be visualized as walking around the tree in a counterclockwise rotation, starting at the root. Consider elements visited only when you are below them. In the below example, when you start at 10, you are above it. You can’t be below 10 (map-wise) until you go beneath 1, 5, and 7.
  41.  
  42.         \large
  43.         \underline{Ex.}
  44.     \end{justify}
  45.     \begin{center}
  46.         \begin{tikzpicture}
  47.             \draw [very thick] (0,0) circle (0.5);
  48.             \draw [very thick] (-1,-2) circle (0.5);
  49.             \draw [very thick] (1,-2) circle (0.5);
  50.             \draw [very thick] (-2,-4) circle (0.5);
  51.             \draw [very thick] (-0.75,-4) circle (0.5);
  52.             \draw [very thick] (0.75,-4) circle (0.5);
  53.             \draw [very thick] (2,-4) circle (0.5);
  54.             \draw [very thick, ->] (-0.5,0) -- (-1,-1.5);
  55.             \draw [very thick, ->] (0.5,0) -- (1,-1.5);
  56.             \draw [very thick, ->] (-1.5,-2) -- (-2,-3.5);
  57.             \draw [very thick, ->] (-0.5,-2) -- (-0.75,-3.5);
  58.             \draw [very thick, ->] (1.5,-2) -- (2,-3.5);
  59.             \draw [very thick, ->] (0.5,-2) -- (0.75,-3.5);
  60.             \node at (0,0) {10};
  61.             \node at (-1,-2) {5};
  62.             \node at (1,-2) {13};
  63.             \node at (-2,-4) {1};
  64.             \node at (-0.75,-4) {7};
  65.             \node at (0.75,-4) {11};
  66.             \node at (2,-4) {15};
  67.             \node at (-1.5,0) {Root $\rightarrow$};
  68.             \node [left] at (-2.5,-4) {Lowest Element $\rightarrow$};
  69.             \node [right] at (2.5,-4) {$\leftarrow$ Highest Element};
  70.         \end{tikzpicture}
  71.     \end{center}
  72.     \begin{justify}
  73.         \large
  74.         \underline{Code}
  75.  
  76.         \small
  77.         \lstinputlisting[language=C, showstringspaces=false, firstline=5, lastline=163, breaklines=true, tabsize=2]{cc_BST.c}
  78.     \end{justify}
  79.     \pagebreak
  80.     \begin{justify}
  81.         \footnotesize
  82.         \underline{Note: For the following five algorithms, this is the definition of the swap function:}
  83.         \lstinputlisting[language=C, showstringspaces=false, firstline=48, lastline=52, breaklines=true, tabsize=2]{sorting.c}
  84.  
  85.         \large
  86.         \underline{Bubble Sort}
  87.  
  88.         \normalsize
  89.         Bubble Sort passes through an array as many times as there are elements in the array. In each pass, it checks every element against the one after it; If the after element is less than the current element, the elements are swapped. Once the last pass is complete, the array is sorted.
  90.  
  91.         Bubble Sort can be optimized to have less passes than the number of elements by adding a check; If no swaps have occurred in a pass, the array is sorted.
  92.  
  93.         \large
  94.         \underline{Ex.}
  95.  
  96.         \small
  97.         \begin{lstlisting}[tabsize=4]
  98.         array (no passes):  4, 2, 1, 3      [SWAPS: 0]
  99.         array (1 pass):     2, 1, 3, 4      [SWAPS: 3]
  100.         array (2 passes):   1, 2, 3, 4      [SWAPS: 4]
  101.         (The 3rd pass does not have any swaps. The list is sorted.)
  102.  
  103.         (3 passes and 4 swaps were needed.)
  104.         \end{lstlisting}
  105.  
  106.         \large
  107.         \underline{Code}
  108.  
  109.         \small
  110.         \lstinputlisting[language=C, showstringspaces=false, firstline=167, lastline=189, breaklines=true, tabsize=2]{sorting.c}
  111.     \end{justify}
  112.     \pagebreak
  113.     \begin{justify}
  114.         \large
  115.         \underline{Insertion Sort}
  116.  
  117.         \normalsize
  118.         Insertion Sort passes through an array once, starting from the second element. Each element is inserted into its proper position. This can be done by swapping the current element and its prior element while the prior element is greater than the current element. Once the pass is done, the array is sorted.
  119.  
  120.         \large
  121.         \underline{Ex.}
  122.  
  123.         \small
  124.         \begin{lstlisting}[tabsize=4]
  125.         array (no inserts): 4, 2, 1, 3
  126.         array (1 insert):   2, 4, 1, 3
  127.         array (2 inserts):  1, 2, 4, 3
  128.         array (3 inserts):  1, 2, 3, 4      [SORTED]
  129.  
  130.         (1 pass and 3 swaps were needed.)
  131.         \end{lstlisting}
  132.        
  133.         \large
  134.         \underline{Code}
  135.  
  136.         \small
  137.         \lstinputlisting[language=C, showstringspaces=false, firstline=191, lastline=207, breaklines=true, tabsize=2]{sorting.c}
  138.     \end{justify}
  139.     \pagebreak
  140.     \begin{justify}
  141.         \large
  142.         \underline{Selection Sort}
  143.  
  144.         \normalsize
  145.         Selection Sort passes through an array once, starting from the second element. The minimum element of all elements beyond (and including) the current element is selected and moved down the array until it is at the top of the sorted partition. The moving down is accomplished by swapping the minimum element with elements before it until it is in the sorted partition, or the element before it is smaller than the minimum. Once the pass is done, the array is sorted.
  146.  
  147.         \large
  148.         \underline{Ex.}
  149.        
  150.         \small
  151.         \begin{lstlisting}[tabsize=4]
  152.         array (no selects): 4, 2, 1, 3
  153.         array (1 select):   1, 4, 2, 3
  154.         array (2 selects):  1, 2, 4, 3
  155.         array (3 selects):  1, 2, 3, 4      [SORTED]
  156.  
  157.         (1 pass and 3 swaps were needed.)
  158.         \end{lstlisting}
  159.        
  160.         \large
  161.         \underline{Code}
  162.  
  163.         \small
  164.         \lstinputlisting[language=C, showstringspaces=false, firstline=224, lastline=251, breaklines=true, tabsize=2]{sorting.c}
  165.     \end{justify}
  166.     \pagebreak
  167.     \begin{justify}
  168.         \large
  169.         \underline{Merge Sort}
  170.  
  171.         \normalsize
  172.         Merge Sort subdivides an array recursively until each partition is a single element. It then merges the one element arrays back together in order, yielding a sorted array at the end.
  173.  
  174.         \large
  175.         \underline{Ex.}
  176.        
  177.         \small
  178.         \begin{lstlisting}[tabsize=4]
  179.         array:  4, 2, 1, 3
  180.  
  181.         part. 1:    4, 2
  182.         subparts:   [4], [2]
  183.         merged: 2, 4
  184.  
  185.         part. 2:    1, 3
  186.         subparts:   [1], [3]
  187.         merged: 1, 3
  188.    
  189.         merged: 1, 2, 3, 4
  190.         \end{lstlisting}
  191.        
  192.         \large
  193.         \underline{Code}
  194.  
  195.         \small
  196.         \lstinputlisting[language=C, showstringspaces=false, firstline=253, lastline=301, breaklines=true, tabsize=2]{sorting.c}
  197.     \end{justify}
  198.     \pagebreak
  199.     \begin{justify}
  200.         \large
  201.         \underline{Heap Sort}
  202.  
  203.         \normalsize
  204.         Heap Sort takes the elements in an array and moves them into a heap, a tree structure where each element has at most two children. The root of the tree is the maximum element from the array, and each child is smaller than its parent. Elements in the heap can be swapped easily to keep the tree in heap form, and the maximum is always on top. To sort, simply take the root out and put it at the end of the sorted array, then reorder the heap. The heap will shrink until only one element remains.
  205.  
  206.         \large
  207.         \underline{Ex.}
  208.        
  209.         \normalsize
  210.         \begin{lstlisting}[tabsize=4]
  211.         array (pre-heap):   4, 2, 1, 3
  212.         heap (0 removals):    4     sorted array:
  213.                              /\
  214.                             3 1
  215.                             /
  216.                             2
  217.         heap (1 removal):     3     sorted array: 4
  218.                              /\
  219.                             2 1
  220.         heap (2 removals):   2      sorted array: 3, 4
  221.                              \
  222.                              1
  223.         heap (3 removals):  1       sorted array: 2, 3, 4
  224.         sorted array (post-heap):   1, 2, 3, 4
  225.  
  226.         (1 heapify, 3 reorders, and 4 removals were needed.)
  227.         \end{lstlisting}
  228.        
  229.         \large
  230.         \underline{Code}
  231.  
  232.         \small
  233.         \lstinputlisting[language=C, showstringspaces=false, firstline=342, lastline=387, breaklines=true, tabsize=2]{sorting.c}
  234.     \end{justify}
  235.     \pagebreak
  236.  
  237.     \begin{center}
  238.         \LARGE
  239.         \underline{Time Complexity}
  240.     \end{center}
  241.  
  242.     \begin{justify}
  243.         Time Complexity is a way to classify and rank algorithms. As the name implies, the runtime of an algorithm is what is used in ranking. An algorithm's runtime can be represented as some function of the size of the input data, commonly designated as $n$. For sorting algorithms, $n$ is the number of elements in the array that needs sorting.
  244.  
  245.         To simplify the expressions, Big-O Notation is used, which drops out the lower order terms and leading coefficient in favor of focusing on the leading term. Below is a table of time complexity classes and algorithms associated with those classes.
  246.     \end{justify}
  247.  
  248.     \begin{center}
  249.         \begin{tabular}{|| m{1.125in} | m{0.875in} | m{4in} ||}
  250.             \hline
  251.             Time Type & Big-O Type & Algorithm(s) \\
  252.             \hline
  253.             \hline
  254.             Constant & $O(1)$ & Swapping Two Array Elements \\
  255.             \hline
  256.             Logarithmic & $O(\log{(n)})$ & Binary Search \\
  257.             \hline
  258.             Linear & $O(n)$ & Printing an Array, Finding Array Extrema \\
  259.             \hline
  260.             Linearithmic & $O(n \log{(n)})$ & Merge \& Heap Sort \\
  261.             \hline
  262.             Quadratic & $O(n^2)$ & Bubble, Insertion, \& Selection Sort \\
  263.             \hline
  264.             Factorial & $O(n!)$ & Bogo Sort (See the next page)\\
  265.             \hline
  266.         \end{tabular}
  267.         \\~\\
  268.         \large
  269.         \underline{Time Complexity Table}
  270.     \end{center}
  271.     \pagebreak
  272.  
  273.     \begin{center}
  274.         \LARGE
  275.         \underline{The Traveling Salesman Problem}
  276.     \end{center}
  277.  
  278.     \begin{justify}
  279.         The Traveling Salesman Problem is an open NP-Hard problem in Computer Science. It simply states:
  280.         \\~\\
  281.         \textsf{Given a list of cities and the distances between them, what is the shortest route that will let you visit all cities and return to the city you start from?}
  282.         \\~\\
  283.         An alternate version of it, designated the T.S.P. Decision Version, also exists, which states:
  284.         \\~\\
  285.         \textsf{Given a limit to the distance of a route, does a viable route exist that will satisfy T.S.P. and be under the limit?}
  286.         \\~\\
  287.         If we reference the graph below, say we want to start from Fitchburg (node 3) and visit all of the eight cities in the New England area that are shown. If we consider the normal version of T.S.P., the first thing we might try is to list out all routes that visit all cities and end up back in Fitchburg. This might take a while, and if we also wanted to visit some small towns as well, say we add 20 of them to the graph, the number of routes will grow worse than exponentially.
  288.  
  289.         In fact, attempting this method of brute-forcing T.S.P. has a time complexity of $O(n!)$, where $n$ is the number of cities. Bogo Sort also has this time complexity. For those unaware, Bogo Sort involves randomly shuffling a list, checking if its sorted, and repeating until the list is sorted. Clearly, brute-force will not be efficient for this problem, hence it's classification as NP-Hard.
  290.     \end{justify}
  291.  
  292.     \begin{center}
  293.         \begin{tikzpicture}
  294.             \draw [very thick] (-4,6) circle (0.5);
  295.             \draw [very thick] (-2,4.5) circle (0.5);
  296.             \draw [very thick] (4,4.5) circle (0.5);
  297.             \draw [very thick] (2,3) circle (0.5);
  298.             \draw [very thick] (-4,1.5) circle (0.5);
  299.             \draw [very thick] (0,1.5) circle (0.5);
  300.             \draw [very thick] (4,1.5) circle (0.5);
  301.             \draw [very thick] (-4,0) circle (0.5);
  302.             \draw [very thick] (2,0) circle (0.5);
  303.             \normalsize
  304.             \node at (-4,6) {0};
  305.             \node at (-2,4.5) {1};
  306.             \node at (4,4.5) {2};
  307.             \node at (2,3) {3};
  308.             \node at (-4,1.5) {4};
  309.             \node at (0,1.5) {5};
  310.             \node at (4,1.5) {6};
  311.             \node at (-4,0) {7};
  312.             \node at (2,0) {8};
  313.             \footnotesize
  314.             \node [above right] at (-3.5,6) {Burlington};
  315.             \node [above right] at (-1.5,4.5) {Montpelier};
  316.             \node [above right] at (4.5,4.5) {Manchester};
  317.             \node [above] at (2,3.5) {Fitchburg};
  318.             \node [below right] at (-3.5,1.5) {Springfield};
  319.             \node [below right] at (0.5,1.5) {Worcester};
  320.             \node [right] at (4.5,1.5) {Boston};
  321.             \node [below right] at (-3.5,0) {Hartford};
  322.             \node [below right] at (2.5,0) {Providence};
  323.  
  324.             \draw [very thick, <->] (-3.5,6) -- (-2,5);
  325.             \draw [very thick, <->] (-2,4) -- (-4,2);
  326.             \draw [very thick, <->] (-1.5,4.5) -- (3.5,4.5);
  327.             \draw [very thick, <->] (-1.5,4.5) -- (1.5,3);
  328.             \draw [very thick, <->] (3.5,4.5) -- (2.5,3);
  329.             \draw [very thick, <->] (4,4) -- (4,2);
  330.             \draw [very thick, <->] (2.5,3) -- (4,2);
  331.             \draw [very thick, <->] (1.5,3) -- (0,2);
  332.             \draw [very thick, <->] (1.5,3) -- (-3.5,1.5);
  333.             \draw [very thick, <->] (-3.5,1.5) -- (-0.5,1.5);
  334.             \draw [very thick, <->] (0.5,1.5) -- (3.5,1.5);
  335.             \draw [very thick, <->] (-4,1) -- (-4,0.5);
  336.             \draw [very thick, <->] (0,1) -- (-3.5,0);
  337.             \draw [very thick, <->] (0,1) -- (1.5,0);
  338.             \draw [very thick, <->] (-3.5,0) -- (1.5,0);
  339.             \draw [very thick, <->] (2.5,0) -- (4,1);
  340.             \normalsize
  341.             \node [above] at (-2.5,5.5) {$39$};
  342.             \node [above] at (1,4.5) {$130$};
  343.             \node [right] at (4,3) {$53$};
  344.             \node [right] at (0,4) {$153$};
  345.             \node [above left] at (-3,3) {$173$};
  346.             \node at (-1,2.5) {$69$};
  347.             \node [above] at (1,2) {$28$};
  348.             \node [above] at (3,2) {$47$};
  349.             \node [below right] at (3,4) {$42$};
  350.             \node [above] at (-1,1.5) {$52$};
  351.             \node [above] at (2,1.5) {$48$};
  352.             \node [below right] at (-4,1) {$27$};
  353.             \node [below] at (0,0) {$74$};
  354.             \node [above] at (-2,0.5) {$64$};
  355.             \node [above] at (1,0.5) {$40$};
  356.             \node [above] at (3,0.5) {$51$};
  357.             \node [above right] at (0,6) {\underline{Cities in New England}};
  358.         \end{tikzpicture}
  359.     \end{center}
  360.     \pagebreak
  361.  
  362.     \begin{center}
  363.         \LARGE
  364.         \underline{Dijkstra \& Pathfinding}
  365.     \end{center}
  366.  
  367.     \begin{justify}
  368.         Dijkstra's Shortest Path Algorithm is fairly straightforward. First, you need a graph/map, which consists of a group of nodes linked in a certain fashion. The nodes should be numbered starting from 0, and can be represented as a square matrix or two-dimensional array. In this, a row corresponds to the paths that lead out of a node, and a column corresponds to the paths that lead into a node.
  369.  
  370.         To find the shortest path through the graph or from a given node to every other, do the following:
  371.         \begin{enumerate}
  372.             \item Create three arrays as long as the number of nodes in the graph. Name them "distance", "accessed", and "previous"
  373.             \item Initialize the distance and previous arrays to be all -1, except the index corresponding the the origin node. For that node, set its distance to 0 and previous to its index in the matrix
  374.             \item Initialize the accessed array be all 0, except the origin node, which should be 1.
  375.             \item From the origin node, scan through its row in the matrix. If the distance to a new node plus the distance to the origin node is less than the current distance to the new node, or there is a path to the new node and no path to it currently exists (i.e. it has a distance value of -1), update the distance to the new node and its entry in the previous array.
  376.             \item Once the row of the origin node is scanned, select the node that has the smallest distance and is also unaccessed. Move to this node, and set it as accessed.
  377.             \item Repeat steps 4 and 5 until all nodes have been accessed. The final versions of the distance and previous arrays will allow you to extrapolate the shortest paths to any node.
  378.         \end{enumerate}
  379.  
  380.         To read a path to a node, go to its entry in the previous array. Read what node was prior to your target node, and check its prior node. Repeat this until you find a node who is its own prior node, which corresponds to the origin node. Then, start printing the indicies of the nodes from origin to target.
  381.  
  382.         \pagebreak
  383.         \large
  384.         \underline{Ex.}
  385.  
  386.         \begin{center}
  387.             \begin{tikzpicture}
  388.                 \draw [very thick] (-4,6) circle (0.5);
  389.                 \draw [very thick] (-2,4.5) circle (0.5);
  390.                 \draw [very thick] (4,4.5) circle (0.5);
  391.                 \draw [very thick] (2,3) circle (0.5);
  392.                 \draw [very thick] (-4,1.5) circle (0.5);
  393.                 \draw [very thick] (0,1.5) circle (0.5);
  394.                 \draw [very thick] (4,1.5) circle (0.5);
  395.                 \draw [very thick] (-4,0) circle (0.5);
  396.                 \draw [very thick] (2,0) circle (0.5);
  397.                 \normalsize
  398.                 \node at (-4,6) {0};
  399.                 \node at (-2,4.5) {1};
  400.                 \node at (4,4.5) {2};
  401.                 \node at (2,3) {3};
  402.                 \node at (-4,1.5) {4};
  403.                 \node at (0,1.5) {5};
  404.                 \node at (4,1.5) {6};
  405.                 \node at (-4,0) {7};
  406.                 \node at (2,0) {8};
  407.                 \footnotesize
  408.                 \node [above right] at (-3.5,6) {Burlington};
  409.                 \node [above right] at (-1.5,4.5) {Montpelier};
  410.                 \node [above right] at (4.5,4.5) {Manchester};
  411.                 \node [above] at (2,3.5) {Fitchburg};
  412.                 \node [below right] at (-3.5,1.5) {Springfield};
  413.                 \node [below right] at (0.5,1.5) {Worcester};
  414.                 \node [right] at (4.5,1.5) {Boston};
  415.                 \node [below right] at (-3.5,0) {Hartford};
  416.                 \node [below right] at (2.5,0) {Providence};
  417.  
  418.                 \draw [very thick, <->] (-3.5,6) -- (-2,5);
  419.                 \draw [very thick, <->] (-2,4) -- (-4,2);
  420.                 \draw [very thick, <->] (-1.5,4.5) -- (3.5,4.5);
  421.                 \draw [very thick, <->] (-1.5,4.5) -- (1.5,3);
  422.                 \draw [very thick, <->] (3.5,4.5) -- (2.5,3);
  423.                 \draw [very thick, <->] (4,4) -- (4,2);
  424.                 \draw [very thick, <->] (2.5,3) -- (4,2);
  425.                 \draw [very thick, <->] (1.5,3) -- (0,2);
  426.                 \draw [very thick, <->] (1.5,3) -- (-3.5,1.5);
  427.                 \draw [very thick, <->] (-3.5,1.5) -- (-0.5,1.5);
  428.                 \draw [very thick, <->] (0.5,1.5) -- (3.5,1.5);
  429.                 \draw [very thick, <->] (-4,1) -- (-4,0.5);
  430.                 \draw [very thick, <->] (0,1) -- (-3.5,0);
  431.                 \draw [very thick, <->] (0,1) -- (1.5,0);
  432.                 \draw [very thick, <->] (-3.5,0) -- (1.5,0);
  433.                 \draw [very thick, <->] (2.5,0) -- (4,1);
  434.                 \normalsize
  435.                 \node [above] at (-2.5,5.5) {$39$};
  436.                 \node [above] at (1,4.5) {$130$};
  437.                 \node [right] at (4,3) {$53$};
  438.                 \node [right] at (0,4) {$153$};
  439.                 \node [above left] at (-3,3) {$173$};
  440.                 \node at (-1,2.5) {$69$};
  441.                 \node [above] at (1,2) {$28$};
  442.                 \node [above] at (3,2) {$47$};
  443.                 \node [below right] at (3,4) {$42$};
  444.                 \node [above] at (-1,1.5) {$52$};
  445.                 \node [above] at (2,1.5) {$48$};
  446.                 \node [below right] at (-4,1) {$27$};
  447.                 \node [below] at (0,0) {$74$};
  448.                 \node [above] at (-2,0.5) {$64$};
  449.                 \node [above] at (1,0.5) {$40$};
  450.                 \node [above] at (3,0.5) {$51$};
  451.                 \node [above right] at (0,6) {\underline{Cities in New England}};
  452.             \end{tikzpicture}
  453.         \end{center}
  454.  
  455.         \normalsize (NE.txt)
  456.         \small
  457.         \lstinputlisting[tabsize=4]{NE.txt}
  458.  
  459.         \normalsize (NE\_Solved.txt)
  460.         \footnotesize
  461.         \lstinputlisting[tabsize=8]{NE_Solved.txt}
  462.  
  463.         \pagebreak
  464.         \large
  465.         \underline{Code}
  466.  
  467.         \small
  468.         \lstinputlisting[language=C, showstringspaces=false, breaklines=true, tabsize=2]{cc_Dijkstra.c}
  469.     \end{justify}
  470.     \pagebreak
  471.  
  472.     \begin{center}
  473.         \LARGE
  474.         \underline{Theory of Computation}
  475.     \end{center}
  476.  
  477.     \begin{center}
  478.         \begin{tikzpicture}
  479.             \large
  480.             \node [below] at (0,0) {\underline{Simplified Chomsky Hierarchy}};
  481.             \draw [ultra thick] (0,2) circle (2);
  482.             \draw [ultra thick] (0,3) circle (3);
  483.             \draw [ultra thick] (0,4) circle (4);
  484.             \small
  485.             \node [above] at (0,2) {Finite State};
  486.             \node [below] at (0,2) {Automata};
  487.             \node [below] at (0,5) {Push-Down Automata};
  488.             \node [below] at (0,7) {Turing Machines};
  489.         \end{tikzpicture}
  490.     \end{center}
  491.  
  492.     \begin{justify}
  493.         \large
  494.         \underline{Finite State Automata}
  495.  
  496.         \normalsize
  497.         Finite State Automata, found in the center of Chomsky's Hierarchy (pictured above), are the simplest forms of computers. They can be visualized as a graph of nodes, where the start node has a blank arrow leading into it and where the end node is a double-circle. For example, below is a F.S.T. that can generate all strings that have an even number of 0's followed by an odd number of 1's. Please note that arrows marked with a $\lambda$ are null paths, which do not produce anything.
  498.     \end{justify}
  499.  
  500.     \begin{center}
  501.         \begin{tikzpicture}
  502.             \large
  503.             \node at (0,0) {\underline{F.S.A.: $0^n1^m:n$ is even, $m$ is odd}};
  504.             \draw [very thick] (-4,4) circle (0.5);
  505.             \draw [very thick] (-2,4) circle (0.5);
  506.             \draw [very thick] (-3,2) circle (0.5);
  507.             \draw [very thick] (2,4) circle (0.5);
  508.             \draw [very thick] (4,4) circle (0.5);
  509.             \draw [very thick] (3,2) circle (0.5);
  510.             \draw [thick] (4,4) circle (0.75);
  511.             \node at (-4,4) {a};
  512.             \node at (-2,4) {c};
  513.             \node at (-3,2) {b};
  514.             \node at (2,4) {d};
  515.             \node at (4,4) {f};
  516.             \node at (3,2) {e};
  517.             \draw [very thick, ->] (-5,4) -- (-4.5,4);
  518.             \draw [very thick, ->] (-4,3.5) -- (-3.5,2);
  519.             \draw [very thick, ->] (-2.5,2) -- (-2,3.5);
  520.             \draw [very thick, ->] (-1.5,4) -- (1.5,4);
  521.             \draw [very thick, ->] (2.5,4) -- (3.5,4);
  522.             \draw [very thick, ->] (3,2.5) -- (2.5,4);
  523.             \draw [very thick, ->] (2,3.5) -- (2.5,2);
  524.             \draw [very thick, ->] (-2.5,4) -- (-3,2.5);
  525.             \node [above] at (0,4) {$\lambda$};
  526.             \node [left] at (-4,3) {$0$};
  527.             \node [right] at (-2,3) {$0$};
  528.             \node [above] at (-3,3) {$0$};
  529.             \node [below] at (2,3) {$1$};
  530.             \node [above] at (3,3) {$1$};
  531.             \node [above] at (3,4) {$1$};
  532.         \end{tikzpicture}
  533.     \end{center}
  534.     \pagebreak
  535.  
  536.     \begin{justify}
  537.         \large
  538.         \underline{Push-Down Automata}
  539.  
  540.         \normalsize
  541.         Push-Down Automata, which encompass Finite State Automata, implement a stack as a crude form of memory. The concept of a stack is critical to Computer Science, as it can represent recursion and other tricky concepts in an elementary way. A stack can have objects pushed onto it or popped off of it. Only the top element on a stack, the element last pushed on, can be popped off. Though physical implementations of stacks generally have a limit to their size, for our purposes, assume stacks can fit near-infinitely many elements.
  542.  
  543.         One thing that Push-Down Automata can do that Finite State Automata cannot is generate all strings that have an equal number of 0's and 1's. Also, Push-Down Automata can generate all binary palindrome strings. Examples of both of these can be seen below. It should be noted that in order for an automata to finish, its stack must be empty. Also, if a push invovles a letter, that letter must be at the top of the stack in order for a pull of it to be processed. Finally, as with Finite State Automata, $\lambda$ paths do not do anything.
  544.     \end{justify}
  545.  
  546.     \begin{multicols}{2} \begin{center}
  547.         \begin{tikzpicture}
  548.             \large
  549.             \node [below] at (0,-0.5) {\underline{P.D.A.: $0^n1^n : n \in \mathbb{N}$}};
  550.             \draw [very thick] (-2,2) circle (0.5);
  551.             \draw [very thick] (2,2) circle (0.5);
  552.             \draw [thick] (2,2) circle (0.75);
  553.             \draw [very thick, rounded corners, ->] (-2,1.5) -- (-2.25,0.5) -- (-1.75,0.5) -- (-2,1.5);
  554.             \draw [very thick, rounded corners, ->] (2,1.5) -- (2.25,0.5) -- (1.75,0.5) -- (2,1.5);
  555.             \draw [very thick, ->] (-1.5,2) -- (1.5,2);
  556.             \draw [very thick, ->] (-3,2) -- (-2.5,2);
  557.             \node at (-2,2) {a};
  558.             \node at (2,2) {b};
  559.             \node [below] at (-2,0.5) {$0$ / push};
  560.             \node [below] at (2,0.5) {$1$ / pull};
  561.             \node [above] at (0,2) {$\lambda$};
  562.         \end{tikzpicture}
  563.         \begin{tikzpicture}
  564.             \large
  565.             \node [below] at (0,-0.5) {\underline{P.D.A.: Binary Palindromes}};
  566.             \draw [very thick] (-2,2) circle (0.5);
  567.             \draw [very thick] (2,2) circle (0.5);
  568.             \draw [thick] (2,2) circle (0.75);
  569.             \draw [very thick, rounded corners, ->] (-2,1.5) -- (-2.25,0.5) -- (-1.75,0.5) -- (-2,1.5);
  570.             \draw [very thick, rounded corners, ->] (2,1.5) -- (2.25,0.5) -- (1.75,0.5) -- (2,1.5);
  571.             \draw [very thick, rounded corners, ->] (-2,2.5) -- (-2.25,3.5) -- (-1.75,3.5) -- (-2,2.5);
  572.             \draw [very thick, rounded corners, ->] (2,2.5) -- (2.25,3.5) -- (1.75,3.5) -- (2,2.5);
  573.             \draw [very thick, ->] (-1.5,2) -- (1.5,2);
  574.             \draw [very thick, ->] (-3,2) -- (-2.5,2);
  575.             \draw [very thick, rounded corners, ->] (-1.5,2) -- (0,3) -- (1.647,2.354);
  576.             \draw [very thick, rounded corners, ->] (-1.5,2) -- (0,1) -- (1.647,1.647);
  577.             \node at (-2,2) {a};
  578.             \node at (2,2) {b};
  579.             \node [below] at (-2,0.5) {$0$ / push(Z)};
  580.             \node [below] at (2,0.5) {$0$ / pull(Z)};
  581.             \node [above] at (0,2) {$\lambda$};
  582.             \node [above] at (0,3) {1};
  583.             \node [above] at (0,1) {0};
  584.             \node [above] at (-2,3.5) {$1$ / push(O)};
  585.             \node [above] at (2,3.5) {$1$ / pull(O)};
  586.         \end{tikzpicture}
  587.     \end{center} \end{multicols}
  588.     \pagebreak
  589.    
  590.     \begin{justify}
  591.         \large
  592.         \underline{Turing Machines}
  593.  
  594.         \normalsize
  595.         Turing Machines, which encompass the prior two automata types, can compute the answer to any problem for which an algorithm exists. Pioneered and commemorated to Alan Turing, the Father of Computer Science, they function as such:
  596.  
  597.         Using a (reasonably) infitine tape of cells, a Turing Machine is instructed with a set of rules. For each rule, the T.M. reads the current cell it is at on the tape. Based on what is read, the T.M. may change to a new state, and may overwrite the cell. Once a state-change and/or a write occur, the T.M. will then move one cell to the left or to the right. Eventually, a properly designed Turing Machine will enter a halt state, in which it can be in an "accept" substate, or in a "reject" substate.
  598.  
  599.         The concept of the state, coupled with the tape of data and instructions, paved the way for the development of general purpose computers following the Second World War in the mid 20th Century. Unfortunately, due to homophobic sentiments and nosy police officers, Alan Turing was forced into hormone theropy when it was revealed he was gay, a crime under contemporary British law. This, coupled with the resentment Turing now faced in the industry, led him to end his life prematurely, and he would not be pardoned by the government of Britain for nearly five decades afterwards. Back on topic.
  600.  
  601.         Below are instructions for a Turing Machine that will increment a binary number on a tape. Each instruction should be read as:
  602.  
  603.         \begin{center}
  604.             \small
  605.             [Current State], [Data Read]=>[New State], [Data Write], [Move Tape]
  606.         \end{center}
  607.  
  608.         S is the starting state. $\delta$ is the leftmost cell on the tape, and beyond which the machine is barred from going. \_ is a blank cell. Once the "accept" state is entered, the machine halts.
  609.     \end{justify}
  610.  
  611.     \begin{multicols}{3}
  612.         \begin{lstlisting}[tabsize=6, escapeinside={(*}{*)}]
  613. S, (*$\delta$*)=>S, (*$\delta$*), R;
  614. S, 0=>Z, 0, R;
  615. S, 1=>(*$\Omega$*), 1, R;
  616.  
  617.  
  618. (*$\Omega$*), 1=>(*$\Omega$*), 1, R;
  619. (*$\Omega$*), 0=>Z, 0, R;
  620. (*$\Omega$*), _=>F, 0, L;
  621.         \end{lstlisting}
  622.         \begin{lstlisting}[tabsize=6, escapeinside={(*}{*)}]
  623. Z, 0=>Z, 0, R;
  624. Z, 1=>Z, 1, R;
  625. Z, _=>A, _, L;
  626.  
  627.  
  628.  
  629. A, 0=>H, 1, L;
  630. A, 1=>A, 0, L;
  631.         \end{lstlisting}
  632.         \begin{lstlisting}[tabsize=6, escapeinside={(*}{*)}]
  633. H, 0=>H, 0, L;
  634. H, 1=>H, 1, L;
  635. H, (*$\delta$*)=>accept;
  636.  
  637. F, 1=>F, 0, L;
  638. F, (*$\delta$*)=>W, (*$\delta$*), R;
  639.  
  640. W, 0=>H, 1, L;
  641.         \end{lstlisting}
  642.     \end{multicols}
  643.  
  644.     \begin{center}
  645.         \large
  646.         \underline{T.M.: Binary Incrementer with Overflow Accommodation}
  647.     \end{center}
  648.     \pagebreak
  649.  
  650.     \begin{center}
  651.         \LARGE
  652.         \underline{RSA Encryption}
  653.     \end{center}
  654.  
  655.     \begin{center}
  656.         \small
  657.         Note: the traditional Alice and Bob characters will be supplemented by \textcolor{blue}{Amuro Ray} and \textcolor{yellow}{Sayla Mass} from Mobile Suit Gundam.
  658.     \end{center}
  659.  
  660.     \begin{FlushLeft}
  661.         \textcolor{blue}{Amuro} and \textcolor{yellow}{Sayla} wish to talk securely, since they know \textcolor{red}{Char}, \textcolor{yellow}{Sayla}'s over-protective and slightly fascist older brother, is listening to them. First, they each pick two prime numbers (usually large but for this example they will be small) to keep secret.
  662.         \\~\\
  663.         \textcolor{blue}{Amuro}'s primes, $P_A$ and $Q_A$, are $5$ and $29$.
  664.  
  665.         \textcolor{yellow}{Sayla}'s primes, $P_S$ and $Q_S$, are $7$ and $23$.
  666.         \\~\\
  667.         \textcolor{blue}{Amuro} transmits the product of his primes, $N_A = 145 (= 5 * 29)$.
  668.  
  669.         \textcolor{yellow}{Sayla} transmits the product of her primes, $N_S = 161 (= 7 * 23)$.
  670.         \\~\\
  671.         \textcolor{red}{Char} can see both $N_A$ and $N_S$. So too can \textcolor{yellow}{Sayla} and \textcolor{blue}{Amuro}.
  672.         \\~\\
  673.         \textcolor{blue}{Amuro} picks another prime number, $E_A = 13$, and transmits it.
  674.  
  675.         \textcolor{yellow}{Sayla} picks another prime number, $E_S = 17$, and transmits it.
  676.         \\~\\
  677.         \textcolor{red}{Char} can see both $E_A$ and $E_S$. So too can \textcolor{yellow}{Sayla} and \textcolor{blue}{Amuro}. $E_A$ and $E_S$ act as \textcolor{blue}{Amuro} and \textcolor{yellow}{Sayla}'s public/encryption keys. Now \textcolor{blue}{Amuro} and \textcolor{yellow}{Sayla} can send each other encrypted messages.
  678.         \\~\\
  679.         Using ASCII, \textcolor{blue}{Amuro} encrypts his message, $M_A$ = "X", or $88$ in ASCII, using the following formula:
  680.  
  681.         \begin{center}
  682.             ${M_A}^{E_S} \mod N_S = 88^{17} \mod 161 = 44 =$ "," $= C_A$
  683.         \end{center}
  684.  
  685.         $C_A$ is \textcolor{blue}{Amuro}'s ciphertext, which he can transmit. He does.
  686.         \\~\\
  687.         \textcolor{yellow}{Sayla} chooses her message, $M_S = $ "O", or $79$ in ASCII, and uses a similar formula:
  688.  
  689.         \begin{center}
  690.             ${M_S}^{E_A} \mod N_A = 79^{13} \mod 145= 69 =$ "E" $= C_S$
  691.         \end{center}
  692.  
  693.         $C_S$ is \textcolor{yellow}{Sayla}'s ciphertext, which she can transmit. She does.
  694.         \\~\\
  695.         \textcolor{red}{Char} can see \textcolor{blue}{Amuro} and \textcolor{yellow}{Sayla}'s ciphertexts, "," and "E", and is perplexed.
  696.     \end{FlushLeft}
  697.     \pagebreak
  698.     \begin{FlushLeft}
  699.         To decrypt $C_S$, \textcolor{blue}{Amuro} must calculate his private/decryption key, $D_A$. He can do this because of the following congruence:
  700.        
  701.         \begin{center}
  702.         $E_A * D_A \equiv 1 \mod (P_A -1) * (Q_A - 1)$
  703.         \end{center}
  704.  
  705.         This translates to the equation:
  706.  
  707.         \begin{center}
  708.         $E_A * D_A = k * (P_A -1) * (Q_A - 1) + 1$
  709.         \end{center}
  710.  
  711.         Where $k$ is some integer. Solving this equation for $D_A$ shows:
  712.         \begin{align*}
  713.             D_A &= (k * (P_A -1) * (Q_A - 1) + 1) / E_A \\
  714.                 &= (k * (5 -1) * (29 - 1) + 1) / 13 \\
  715.                 &= (k * 4 * 28 + 1) / 13 \\
  716.                 &= (112k + 1) / 13
  717.         \end{align*}
  718.  
  719.         $D_A$ needs to be an integer, and $k = 8$ results in $D_A = 69$.
  720.         \\~\\
  721.         \textcolor{blue}{Amuro} can put $C_S$ through a similar equation now to get $M_S$:
  722.  
  723.         \begin{center}
  724.         ${C_S}^{D_A} \mod N_A = 69^{69} \mod 145 = 79 = M_S = “O”$
  725.         \end{center}
  726.  
  727.         Likewise, \textcolor{yellow}{Sayla} can compute her private key, $D_S$:
  728.         \begin{align*}
  729.             D_S &= (k * (P_S -1) * (Q_S - 1) + 1) / E_S \\
  730.                 &= (k * (7 -1) * (23 - 1) + 1) / 17 \\
  731.                 &= (k * 6 * 22 + 1) / 17 \\
  732.                 &= (132k + 1) / 17
  733.         \end{align*}
  734.  
  735.         $D_S$ needs to be an integer, and $k = 13$ results in $D_S = 101$.
  736.         \\~\\
  737.         Now \textcolor{yellow}{Sayla} can decrypt $C_A$ to get $M_A$:
  738.  
  739.         \begin{center}
  740.         ${C_A}^{D_S} \mod N_S = 44^{101} \mod 161 = 88 = M_A = “X”$
  741.         \end{center}
  742.  
  743.         All the while, \textcolor{red}{Char} is none the wiser to \textcolor{blue}{Amuro} and \textcolor{yellow}{Sayla}'s messages, since \textcolor{red}{Char} doesn't know $P_A$, $Q_A$, $P_S$, or $Q_S$, and this cannot calculate $D_A$ or $D_S$.
  744.     \end{FlushLeft}
  745.     \pagebreak
  746.     \begin{FlushLeft}
  747.         If \textcolor{blue}{Amuro} wishes to send his signature as well, and keep it secret, he first encrypts his signature, $S_A =$ "A", or $65$ in ASCII, with his decryption/private key, $D_A$. Next, he encrypts the resulting message with \textcolor{yellow}{Sayla}'s encryption/public key, $E_S$. The resulting ciphered-signature will be referred to as ${CS}_A$.
  748.         \begin{align*}
  749.             ({S_A}^{D_A} \mod N_A)^{E_S} \mod N_S &= \\
  750.             (65^{69} \mod 145)^{17} \mod 161 &= 156 = {CS}_A = "\pounds"
  751.         \end{align*}
  752.  
  753.         (Note: The symbol for $CS_A$ is from extended ASCII)
  754.         \\~\\
  755.         \textcolor{blue}{Amuro} can now transmit $CS_A$. When \textcolor{yellow}{Sayla} receives it, she knows to decrypt it first with her decryption/private key, $D_S$, then with \textcolor{blue}{Amuro}'s encryption/public key, $E_A$.
  756.         \begin{align*}
  757.             ({{CS}_A}^{D_S} \mod N_S)^{E_A} \mod N_A &= \\
  758.             (156^{101} \mod 161)^{13} \mod 145 &= 65 = S_A = "A"
  759.         \end{align*}
  760.  
  761.         Since \textcolor{yellow}{Sayla} received \textcolor{blue}{Amuro}'s initial "A", his signature, from decrypting the message with \textcolor{blue}{Amuro}'s encryption/public key, $E_A$, she can trust that it must have been encrypted with \textcolor{blue}{Amuro}'s  decryption/private key, $D_A$, which only he has access to.
  762.     \end{FlushLeft}
  763. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!