\documentclass[12pt,a4paper]{article}

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

\begin{document}

\title{Algorithms and Data Structures}
\author{Final Exam}
\date{August 8, 2022}
\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}

% \newpage
\begin{enumerate}

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

\item Give a sharp Big-Oh upper bound and a sharp Big-Omega lower
bound for the running time of the following Python function which
takes as input a Python list \pyth{S} of length $n$.

\begin{python}
def mystery_function (S):
    for j in range(len(S)):
        for k in range(j+1, len(S)):
            if S[j] == S[k]:
                return False
    return True
\end{python}

\item What is \pyth{mystery_function} good for?

\item Can you suggest a different implementation of
\pyth{mystery_function} which has a running time of $O(n \log n)$?

\emph{Note:} No need to write Python code -- a high-level description
in words suffices.  Be sure to justify that your suggestion achieves
the claimed running time.
    
\end{enumerate}
\hfill(5+5+5+5)


\item True or false?  Explain your answer in 1--2 sentences.

\begin{enumerate}

\item A pre-order traversal of a tree with $n$ nodes runs in $O(n)$
time.

\item Accessing the next element in a pre-order traversal of a tree
can always be done in $O(1)$ time.

\item Accessing the next element in a breadth-first traversal of a
binary tree can always be done in $O(1)$ time.

\item Inserting an element into a hash table can always be done in
$O(1)$-time.

\item There are binary search trees where a search can take
$\Omega(n)$ time.

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



\item
\begin{enumerate}

\item Draw the resulting binary search tree when you remove the root
node $51$ from the following tree.
\begin{center}
 \begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  level/.style = {sibling distance = 30mm/#1}
  ]
  \node {51}
  child {node {12} 
        child {node {1}}
        child {node {43}
               child {node {36}}
               child {edge from parent[draw = none]}
              }
        }
  child {node {87}
         child {node {52}
                child {edge from parent[draw = none]}
                child {node {83}}
               }
         child {node{90}}
        };
\end{tikzpicture}   
\end{center}

\item Draw an example of an AVL-tree where the removal of an element
triggers more than one rotation.

\item Suppose you have an implementation of an AVL-tree.  Argue that
you can use it to sort a list in $O(n \log n)$ time.


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




\item Let \pyth{G} be an undirected graph without weights.  The graph
distance between vertices \pyth{u} and \pyth{v} is then defined as the
length of the shortest path between \pyth{u} and \pyth{v}.  The
following function computes the graph distance, where
\pyth{LinkedQueue} is an implementation of the standard queue data
type, and \pyth{neighboring_vertices(w)} is an iterator over all
vertices connected to \pyth{w} by an edge.

\begin{python}
def distance(G, u, v):
    Q = LinkedQueue()          
    Q.enqueue((u,0))   
    while not Q.is_empty():
        w, d = Q.dequeue()
        if w == v:
            return d
        for s in G.neighboring_vertices(w):
            Q.enqueue((s, d+1))        
\end{python}

\begin{enumerate}
\item How does this algorithm work?  (You may argue by analogy with
one of the tree traversal algorithms.)

\item In certain cases, this algorithm may fail spectacularly.  Why
and when?

\item What is the running time, in Big-Oh notation, of this algorithm
if every vertex has an edge to $5$ others?  And if the graph is
complete, i.e., every vertex has an edge to every other vertex?

\item Give a modification of the algorithm that reduces the running
time to $O(n+m)$, where $n$ is the number of vertices and $m$ is the
number of edges in the graph.  (You may state the modification in
precise language -- no need to write Python code.)  Give a brief
reasoning why your modification respects the required running time
bound. 

\item Does your modification avoid the problem from part (b)?  Why or
why not?

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


\item Write an algorithm \pyth{search}, in pseudo-code or in
Python, which returns the position of an element with key \pyth{k} in
a binary search tree \pyth{T} if the element is found, and returns
\pyth{None} otherwise.

\hfill(10)


\end{enumerate}


\end{document}