\documentclass[12pt,a4paper]{article}

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

\begin{document}

\title{Algorithms and Data Structures}
\author{Mock Exam}
\date{July 15, 2025}
\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.65\textwidth,trim={100 210 50 130},clip]{rotations-figure.pdf}
% \end{center}

% \newpage
\begin{enumerate}
\item Consider the function \pyth{f(x,n)} where \pyth{x} is assumed to
be an object of a number type and \pyth{n} is assumed to be a
nonnegative integer.
\begin{python}
def f(x, n):
    if n == 0:
        return 1
    elif n%2 == 0:
        return f(x, n//2) * f(x, n//2)
    else:
        return x*f(x, n-1)
\end{python}
\begin{enumerate}
\item What is this function doing?
\item What is the asymptotic running time of this function?
\item Suggest a simple improvement to this function that guarantees an
asymptotic running time of $O(\log n)$. 
\end{enumerate}
\hfill (5+5+5)


\item Sketch, using Python or Python-like pseudocode, the
implementation of a function that computes the height of a tree.
\hfill (10)

\item
\begin{enumerate}
\item Suppose you have array that is sorted in increasing order.  Is
it a valid array representation of a min-heap?
\item You have a valid array representation of a min-heap.  Then
you reverse the array.  Do you get a valid array representation of a
max-heap?
\end{enumerate}
Justify your answer in each case.
\hfill (5+5)

\item Delete the key $8$ from the following AVL tree.  Indicate all
subtree heights before the deletion, and show the changes introduced
by the deletion and subsequent rebalancing step-by-step.  (You may
consult the summary of tree roations on the front page.)
\begin{center}
 \begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  level/.style = {sibling distance = 70mm/#1},
  level 2/.style = {sibling distance = 4.5cm},
  ]
  \node {8}
  child {node {3}
         child {node {1}}
         child {node {6}
                child {node {4}}
                child[missing]{}}}
  child {node {13}
         child {node{9}
                child[missing]{}
                child {node {10}}}
         child {node{17}
                child {node {15}
                       child {node {14}}
                       child[missing]{}}
                child {node {18}
                       child[missing]{}
                       child {node {20}}}}};
\end{tikzpicture}   
\end{center}
\hfill (10)

\item We noted in class that every implementation of a sorted map can
be turned into a sort algorithm as follows: Given a list $L$ to be
sorted, take an initially empty sorted map $M$ and move the elements
of $L$ one-by-one into the sorted list.  Then traverse $M$ in-order,
moving the elements back into $L$.

For each of the following data structures that can be used to
implement a sorted map, state the asymptotic running time in two
cases: worst case, and $L$ already sorted.
\hfill(10)

\bigskip
\begin{tblr}{colspec = {X[c]X[c]X[c]}, hlines, vlines,
 rows = {15mm}}
\textbf{Implementation}  & \textbf{Worst case} & \textbf{$L$ already sorted} \\
Sorted linked list \\
Reverse sorted linked list \\
Skip list \\
AVL tree \\
Splay tree \\
\end{tblr}

\newpage

\item
\begin{enumerate}
\item Show that every rooted tree has at least one leaf.
\item For a graph $G=(V,E)$, let $v = \lvert V \rvert$ denote the number
of vertices and $e = \lvert E \rvert$ denote the number of edges.
Show that $G$ is a tree if and only if
\[
  v = e+1 \,.
\]
\item How many connected components\footnote{A connected component of
a graph $G$ is a maximal connected subgraph of $G$.} does a
forest\footnote{A graph $G$ is a forest if it contains no cycles.  (So
every connected subgraph of a forest is a tree.)} with $v=20$ vertices
and $e=15$ edges have?
\end{enumerate}
\hfill (5+5+5)


\end{enumerate}
\end{document}
