\documentclass[12pt,a4paper]{article}

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

\begin{document}

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

% \newpage
\begin{enumerate}

\item
\begin{enumerate}
\item Simplify the following Big-Oh resp.\ Big-Omega expressions as
much as possible:
\begin{enumerate}[label={\upshape(\roman*)}]
\item $O(\log n) + O(n \log n) + O((\log n)^4)$
\item $\Omega(\log n) + \Omega(\log \log n) + \Omega(\log\log\log n)$
\item $O(1+2n+3n^2+4n^3)$
\item $\displaystyle O\biggl(\sum_{i=1}^n i^2 \biggr)$
\item $O(n)+\Omega(n)$
\end{enumerate}

\item What is the running time of the following code as a function of
$n$?  Give a Big-Oh upper bound and a Big-Omega lower bound.
\begin{python}
def idle(n):
    r = 0
    i = n
    while i>0:
        r += i
        i = i//2
    return r
\end{python}
\end{enumerate}
\hfill (10+5)

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

\begin{enumerate}

\item Python lists (i.e., dynamic arrays) can be used to efficiently
implement a stack, using \texttt{L.append(e)} and \texttt{L.pop()} for
push and pop, respectively.

\item Python lists (i.e., dynamic arrays) can be used to efficiently
implement a queue, using \texttt{L.append(e)} and \texttt{L.pop(0)} for
enqueue and dequeue, respectively.

\item A heap can be searched more efficiently than an unsorted array.

\item A heap can be searched more efficiently than a sorted array.

\item Breadth-first traversal of a binary tree takes worst-case $O(1)$
time for each node.
\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 = 30mm/#1}
  ]
  \node {A}
  child {node {I} 
        child {node {B}}
        child {node {H}
               child {node {G}}
               child {edge from parent[draw = none]}
              }
        }
  child {node {C}
         child {node {E}
                child {edge from parent[draw = none]}
                child {node {F}}
               }
         child {node{D}}
        };
\end{tikzpicture}   
\end{center}
\hfill(5)


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

\item Insert the keys 4, 9, 3, 7, 5, 6 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 A function takes as input a list of integers \texttt{L} of
length $n$ and an integer value \texttt{total}.  It returns a tuple of
elements from the list with sum \texttt{total}, if possible, and
\texttt{None} otherwise.  Describe an algorithm that can do this in
$O(n \log n)$ time.  \hfill(5)

\item In the following, $G$ is a graph in a ``map of maps''
representation.  An example is the following:
\begin{python}
G = {'A' : {'B', 'E', 'D'},
     'B' : {},
     'C' : {'B', 'E', 'F'},
     'D' : {'B'},
     'E' : {'D'},
     'F' : {'A', 'D', 'E'}}
\end{python}
\begin{enumerate}
\item Draw a representation of this graph in the plane.
\item What does the following function do if it is executed on a graph
\texttt{G} above?
\begin{python}
def mystery_function(p):
    for n in G[p]:
        if n not in v:
            v[n] = p
            mystery_function(n)
              
v = {}
v['A'] = None
mystery_function('A')
\end{python}
\item What data structure is encoded in \texttt{v} if this code is run
on a general graph \texttt{G}?
\item If \texttt{n=len(G)}, what is the running time of this
algorithm?  Give a Big-Oh upper bound and a Big-Omega lower bound.
Justify your answer using your knowledge about the running time of the
native Python dictionary operations.

\item Sketch, using Python or Python-like pseudocode, a
``breadth-first search'' (BFS) traversal of a graph of this type.
\end{enumerate}
\hfill(2+3+2+3+5)

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

\end{enumerate}


\end{document}