\documentclass[12pt,a4paper]{article}

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

\begin{document}

\title{Algorithms and Data Structures}
\author{Final Exam}
\date{July 30, 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.72\textwidth,trim={0 6cm 0 0},clip]{splaytree.pdf}
% \end{center}

% \newpage
\begin{enumerate}

\item
\begin{enumerate}
\item Order the following functions by their asymptotic growth rate:
\[
  n, \exp n, \log n, \exp (n^2), \log (\log n), (\log n)^2
\]


\item An algorithm takes as input an $n$-element sequence of integers.
It iterates through all of its elements, executing an $O(\log n)$-time
computation if the value of the current element is even, resp.\ an $O(n)$-time
computation if the value of the current element is odd.  What are the
best-case and worst-case running times of the algorithm?


\item In the following, \texttt{T} is an instance of a standard binary
tree class.  It contains $n$ nodes.  What does the following code do?
What is its running time as a function of $n$?  Give a Big-Oh upper
bound and a Big-Omega lower bound.
\begin{python}
def do_something(T, p):
    if p is not None:
       do_something(T, T.left(p))
       print(T.element(p))
       do_someting(T, T.right(p))

do_something(T, T.root())
\end{python}
\end{enumerate}
\hfill (5+5+5)

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

\begin{enumerate}

\item A singly linked list can be used to implement a stack such that
``push'' and ``pop'' execute in $O(1)$-time.

\item A singly linked list can be used to implement a queue such that
``enqueue'' and ``dequeue'' execute in $O(1)$-time.

\item An AVL tree can be used to sort a list $O(n \log n)$-time.

\item A heap can be used to sort a list in $O(n \log n)$-time.

\item A skip list can be used to sort a list in $O(n \log n)$-time.

\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 {edge from parent[draw = none]}
         child {node {D}
                child {node {F}}
                child {node {G}}}} 
  child {node {C}
         child {node{E}
                child {node {H}}
                child {node {I}}}
         child {edge from parent[draw = none]}
        };
\end{tikzpicture}   
\end{center}
\hfill(5)


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

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

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

\item  Describe an algorithm that takes an undirected, connected graph
$G=(V,E)$ as input and returns \texttt{True} if the graph is a tree
and \texttt{False} otherwise.  \hfill(5)

\item %From GTG, Exercise C-14.63
Consider the following greedy strategy for finding a shortest path from
vertex \textit{start} to vertex \textit{goal} in a given connected graph.
\begin{enumerate}
\item Initialize path to \textit{start}.
\item Initialize set \textit{visited} to \{\textit{start}\}.
\item If \textit{start}=\textit{goal}, return path and exit. Otherwise, continue.
\item Find the edge (\textit{start}, $v$) of minimum weight such that $v$ is adjacent to
\textit{start} and $v$ is not in \textit{visited}.
\item Add $v$ to path.
\item Add $v$ to \textit{visited}.
\item Set \textit{start} equal to $v$ and go to step (c).
\end{enumerate}
Does this greedy strategy always find a shortest path from \textit{start} to \textit{goal}?
Either explain intuitively why it works, or give a counterexample.
\hfill(5)

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

\end{enumerate}


\end{document}