\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx,tabularray}
\usepackage{pythonhighlight}
\usepackage{tikz}
\usetikzlibrary{arrows,positioning,automata}

\begin{document}

\title{Algorithms and Data Structures}
\author{Final Exam}
\date{August 5, 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{my_function(L)} where \pyth{L} is assumed to
be a Python list:
\begin{python}
def my_function(L):
    for k in range(1, len(L)):
        current = L[k]
        j = k
        while j>0 and L[j-1]>current:
            L[j] = L[j-1]
            j -= 1
        L[j] = current
\end{python}
\begin{enumerate}
\item What is this function doing?
\item What is its worst case asymptotic running time as a function of
\pyth{n=len(L)}? 
\item  What is its best case asymptotic running time?  Describe a list
\pyth{L} for which the best case running time is achieved.
\end{enumerate}
\hfill (5+5+5)


\item Sketch, using Python or Python-like pseudocode, the
implementation of a function that checks whether a graph $G=(V,E)$ has
a cycle.
\hfill (10)
\item Consider the array $[2, 9, 4, 10, 15, 11, 6, 12]$ representing a
binary tree in the standard array-representation.
\begin{enumerate}
\item Draw the corresponding binary tree.  Is it a min-heap?  If not,
restore the min-heap property in a bottom-up pass through the tree.
\item Insert the element $1$ into the min-heap from part (a) and show
all ``bubble-up'' operations required to restore heap order.
\end{enumerate}
\hfill (5+5)
\item Insert the element $16$, then the element $18$ into the
following AVL tree.  Indicate all subtree heights before each
insertion, and show the changes introduced by the insertions and the
subsequent rebalancing step-by-step.  (You may consult the summary of
tree rotations 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 {7}
  child {node {3}
         child {node {1}}
         child {node {6}}}
  child {node {13}
         child {node{9}
                child {node {8}}
                child {node {10}}}
         child {node{17}
                child {node {15}}
                child[missing]{}}};
\end{tikzpicture}   
\end{center}
\hfill (10)
\item We noted in class that we can use the splay tree data structure
to sort an array $L$ of length $n$ as follows: Take an initially empty
splay tree $S$ and move the elements of $L$ one-by-one into $S$.  Then
traverse $S$ in-order, moving the elements back into $L$.  This
algorithm is known as ``splay-sort''.

\begin{enumerate}
\item Prove that  splay-sort takes $O(n \log n)$ time.

\emph{Note:} You can use, without proof, the result from class that
$m$ splay tree operations starting from an initially empty splay tree
take $O(m \log n)$ time, where $n$ is the maximal size of the tree.

\item Prove that splay-sort takes $O(n)$ time when $L$ is already sorted.
\end{enumerate}
\hfill(5+5)


\item Let $G=(V,E)$ be a connected weighted graph with non-negative
weights.  A \emph{shortest-path tree} of $G$ is a tree that contains
all the vertices of $G$ such that the path from its root $s$ to every
vertex $v \in V$ is a shortest path in $G$.
\begin{enumerate}
\item Draw a shortest-path tree for the graph
\begin{center}
\begin{tikzpicture}[>=stealth',
                    node distance=2cm and 3.5cm,
                    on grid,
                    initial/.style={}]
  \node[state] (O)                    {$s$};
  \node[state] (A) [above right=of O] {$a$};
  \node[state] (B) [below right=of O] {$b$};
  \node[state] (C) [right=of A]       {$c$};
  \node[state] (D) [right=of B]       {$d$};
  \node[state] (T) [below right=of C] {$e$};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (O) edge [mystyle] node[above left] {1} (A)
      (O) edge [mystyle] node[below left] {2} (B)
      (B) edge [mystyle] node {1} (A)
      (A) edge [mystyle] node {4} (C)
      (C) edge [mystyle] node[pos=0.25,below right] {3} (B)
      (A) edge [mystyle] node[pos=0.25,below left] {2} (D)
      (B) edge [mystyle] node[below] {1} (D)
      (C) edge [mystyle] node {1} (D)
      (C) edge [mystyle] node[above right] {1} (T)
      (D) edge [mystyle] node[below right] {2} (T);
\end{tikzpicture}
\end{center}
\item Show that a shortest-path tree always exists under the
conditions stated.
\item Give a small example that shows that a shortest-path tree is
not necessarily a minimum spanning tree.
\end{enumerate}
\hfill (5+5+5)
% \newpage
% (Scratch paper)
% \newpage
% (Scratch paper)

\end{enumerate}
\end{document}
