\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{Makeup Exam}
\date{October 7, 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, tol)} where \pyth{L}
is assumed to be a Python list containing floating point numbers, and
\pyth{tol} is assumed to be a single floating point number.
\begin{python}
def my_function(L, tol):
    for j in range(len(L)):
        for k in range(j+1, len(L)):
            if abs(L[j] - L[k]) <= tol:
                return True
    return False
\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 Give an asymptotically faster equivalent implementation of
\pyth{my_function}.
\end{enumerate}
\hfill (5+5+5)
%\newpage



\item You are given that the \emph{pre-order} traversal of a binary
tree yields the sequence A--B--D--E--C--F, while the \emph{in-order}
traversal of the same tree yields the sequence D--B--E--A--F--C.

\begin{enumerate}
\item Reconstruct the binary tree given this information.
\item State the \emph{post-order} traversal sequence of the same tree.
\item Can you always reconstruct a binary tree if you know the
pre-order and the in-order traversal sequence?  Explain why or give a
counter example.
\end{enumerate}
\hfill (5+5+5)
%\newpage
\item Insert the following sequence of elements into an initially
empty AVL tree.  Indicate all subtree heights 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.)
\[
  10, 5, 2, 7, 6, 8, 9
\]
\hfill (10)
%\newpage


\item State one distinct advantage that would favor each of the
following sorting algorithms for a specific use case.
\begin{enumerate}
\item Insertion sort
\item Quick sort
\item Merge sort
\item Heap sort
\item Splay sort
\end{enumerate}
\hfill (5)
%\newpage

\item Consider the following weighted graph.
\begin{center}
\begin{tikzpicture}[>=stealth',
                    node distance=3cm and 3cm,
                    on grid,
                    initial/.style={}]
  \node[state] (s)                    {$s$};
  \node[state] (t) [right=of s]       {$t$};
  \node[state] (u) [above right=of t] {$u$};
  \node[state] (v) [below right=of t] {$v$};
  \node[state] (w) [below right=of u] {$w$};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (s) edge [mystyle] node[above right] {3} (t)
      (s) edge [mystyle] node[above left] {6} (u)
      (s) edge [mystyle] node[below] {2} (v)
      (t) edge [mystyle] node[pos=0.75,above right] {5} (w)
      (t) edge [mystyle] node[below right] {5} (u)
      (t) edge [mystyle] node {4} (v)
      (u) edge [mystyle] node[pos=0.25] {4} (v)
      (u) edge [mystyle] node[above right] {1} (w)
      (v) edge [mystyle] node[below right] {6} (w);
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item  Draw the minimum spanning tree that results from running the
Prim--Jarn{\'\i}k algorithm on this graph, starting at vertex
$s$. List the order in which edges are added to the tree.
\item Draw the minimum spanning tree that  results from running Kruskal’s algorithm on this graph. List the order in which edges are added to the tree.
\end{enumerate}
\hfill (5+5)
%\newpage
\item
\begin{enumerate}
\item State Dijkstra's algorithm for computing the shortest path in a
weighted graph $G$ with vertex set $V$, edge set $E$, and non-negative
weights $w$ from a starting vertex $s \in V$ to each vertex $v \in V$
using Python or pseudo-code.  You may assume that you have access to
an implementation of the Adaptable Priority Queue ADT.

\item Adaptable priority queues are often implemented using the heap
data structure.  State the asymptotic running times for each of the
core methods of the Adaptable Priority Queue ADT.  Give a brief
justification in each case.

\item For Dijkstra's algorithm, there are situations where a simpler
implementation of the Adaptable Priority Queue ADT is actually
asymptotically faster.  Explain!
\end{enumerate}
\hfill (5+5+5)
% \newpage
% (Scratch paper)
% \newpage
% (Scratch paper)

\end{enumerate}
\end{document}
