\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx,colortbl}
\usepackage{pythonhighlight,enumitem}
\usepackage{tikz}

\begin{document}

\title{Algorithms and Data Structures}
\author{Makeup Exam}
\date{October 9, 2024}
\maketitle

% %\vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}\
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}
% \vspace*{\fill}
% \begin{center}

% \includegraphics[width=0.45\textwidth,trim={230 530 150 130},clip]{avl-tree-figure.pdf}
% \includegraphics[width=0.45\textwidth,trim={230 350 150 310},clip]{avl-tree-figure.pdf}

% \includegraphics[width=0.45\textwidth,trim={220 200 150 500},clip]{avl-tree-figure.pdf}

% (a) before insertion, (b) after insertion, (c) rebalanced
% \end{center}

% \newpage

\begin{enumerate}

\item
\begin{enumerate}
\item Order the following functions by their asymptotic growth rate:
\[
  n, n+n^2+n^3, 2^{(n^2)}, (2^n)^2, 2^{2 \log n}, 2^{4 \log n}
\]
\emph{Note: $\log n$ denotes the base-$2$ logarithm!}

\item Al and Bob are arguing about their algorithms. Al claims his
$O(n \log n)$-time method is always faster than Bob's $O(n^2)$-time
method. To settle the issue, they perform a set of experiments. To
Al's dismay, they find that if $n < 100$, the $O(n^2)$-time algorithm
runs faster, and only when $n \geq 100$ is the $O(n \log n)$-time one
better. Explain how this is possible.
\end{enumerate}

\hfill (5+5)


\item Consider the following algorithm, which takes as input a list
\texttt{L} containing integer entries:
\begin{python}
def f(L):
    n = len(L)
    for i in range(n):
        for j in range (i):
            for k in range(n):
                if abs(L[i]-L[j]) == L[k]:
                   return True
    return False
\end{python}
\begin{enumerate}
\item Describe what this algorithm does and state its asymptotic
running time in the best case and in the worst case.
\item Describe an alternative algorithm for the same problem that uses
hashing and completes in $O(n^2)$ time.  You may assume that inserting
a key into the hash table or searching for a key always completes in
$O(1)$ time
\end{enumerate}
\hfill (5+5)



\item Are the following statements true or false?  Explain your
answer in 1--2 sentences.

\begin{enumerate}

\item There exists a sort algorithm that can sort a list of length $n$
in $O(n)$ best case.

\item There exists a sort algorithm that can sort a list of length $n$
in $O(n)$ worst case.

\item Searching for an element in a splay tree with $n$ elements
always completes in $O(\log n)$ time.

\item Searching for the same element in a splay tree with $n$ elements
$n$ times in direct succession takes $O(n)$ time.

\item When implementing Dijkstra's algorithm to find the shortest path
between vertices in a connected graph, we should always use a
heap-based adaptable priority queue to get optimal performance.

\end{enumerate}
\hfill(2+2+2+2+2)

\item Give the pre-order, in-order, and post-order traversals of the
following binary tree:
\begin{center}
 \begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  level/.style = {sibling distance = 70mm/#1}
  ]
  \node {A}
  child {node {B}}
  child {node {C}
         child {node{D}}
         child {node{E}
                child {node {F}}
                child {node {G}
                       child {node {H}}
                       child {node {I}}}}};
\end{tikzpicture}   
\end{center}
\hfill(5)


\item Insert the keys 7, 3, 6, 9, 4, 5 into an initially empty max-heap.
Show the max-heap at each step of insertion.
\hfill(5)

\item Insert the keys 3, 4, 5, 6, 9, 7 into an initially empty AVL tree
tree.  Show the AVL tree at each step of insertion.

(You may consult the attached AVL tree ``cheat sheet''.)
\hfill(5)

\item Give a precise and complete description of Kruskal's algorithm
for computing the minimum spanning tree of a graph.
\hfill(5)

%\mbox{(Solution ctd.\ or scratch.)}\newpage

\end{enumerate}


\end{document}