\documentclass[12pt,a4paper]{article}

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

\begin{document}

\title{Algorithms and Data Structures}
\author{Mock Exam}
\date{July 12, 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^2+n^4, n^2 \, \log n, n^2, (\log n)^2, n^3, (\log n)^3
\]
\item An algorithm executes an $O(\log n)$-time computation for each
entry of an $n$-element sequence.  Give a Big-Oh upper bound and a
Big-Omega lower bound on its running time.

\item Give the best possible Big-Oh upper bound for the running time
of the following Python function which takes as input two Python lists
\pyth{A} and \pyth{B} with respective lengths $n$ and $m$.

\begin{python}
def mystery_function (A,B):
    i = 0
    j = 0
    while i<len(A) and j<len(B):
        if A[i]==B[j]:
            return True
        elif A[i]<B[j]:
            i += 1
        else:
            j += 1
    return False
\end{python}

\item What is \pyth{mystery_function} good for?  State, if necessary,
conditions on the input arrays \pyth{A} and \pyth{B} that make
\pyth{mystery_function} perform useful work.
    
\end{enumerate}
\hfill(5+5+5+5)
%\newpage

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

\begin{enumerate}
\item One can implement a \emph{stack} based on a \emph{linked list}
such that each push or pop operation completes in $O(1)$-time.

\item One can implement a \emph{stack} based on a \emph{dynamic array} 
such that each push or pop operation completes in $O(1)$-time.

\item It is possible to append a \emph{linked list} to another in
$O(1)$-time.

\item \emph{Heap-sort} is always faster then \emph{insertion-sort}.

\item \emph{Heap-sort} is faster than \emph{insertion-sort} when the
input is a list containing $n$ copies of the same number.


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


\item
\begin{enumerate}
\item The nodes of a complete binary tree have keys that represent
their position in a breadth-first traversal of the tree.  Argue that
this tree is a heap.

\item Give a pseudo-code (or Python) representation of the
breadth-first traversal of a tree with an auxiliary queue.

\item Argue that the run-time of this algorithm is $O(n)$, where $n$
is the number of nodes in the tree.

\item Alternatively, you can process the nodes of this tree
breadth-first by repeatedly calling the \pyth{remove_min} method of
the heap.  Does this algorithm also run in $O(n)$ time?  Explain!

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


\item Attached is an excerpt of a code listing for a buggy
implementation of a priority queue with a binary heap.
\begin{enumerate}
\item Draw an example of a heap with exactly $5$ nodes so that a call
to \pyth{remove_min} produces an invalid heap.

\item Identify the part of the code that is buggy.  Explain!

\emph{Hint:} The functions \pyth{_parent} to
\pyth{_has_right} which implement the index arithmetic are
correct, you do not need to look there.

\item Fix the bug.

\item Rewrite the function \pyth{_upheap} to use a loop instead of
recursion. 

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

\begin{python}
class HeapPriorityQueue(PriorityQueueBase):

  def _parent(self, j):
    return (j-1) // 2

  def _left(self, j):
    return 2*j + 1
  
  def _right(self, j):
    return 2*j + 2

  def _has_left(self, j):
    return self._left(j) < len(self._data)
  
  def _has_right(self, j):
    return self._right(j) < len(self._data)
  
  def _swap(self, i, j):
    """Swap the elements at indices i and j of array."""
    self._data[i], self._data[j] = self._data[j], self._data[i]

  def _upheap(self, j):
    parent = self._parent(j)
    if j > 0 and self._data[j] < self._data[parent]:
      self._swap(j, parent)
      self._upheap(parent)
  
  def _downheap(self, j):
    if self._has_left(j):
      left = self._left(j)
      small_child = left
      if self._has_right(j):
        right = self._right(j)
        if self._data[right] < self._data[left]:
          small_child = right
      self._swap(j, small_child)
      self._downheap(small_child)

  def __init__(self):
    """Create a new empty Priority Queue."""
    self._data = []

  def __len__(self):
    """Return the number of items in the priority queue."""
    return len(self._data)

  def add(self, key, value):
    """Add a key-value pair to the priority queue."""
    self._data.append(self._Item(key, value))
    self._upheap(len(self._data) - 1)
  
  def min(self):
    """Return but do not remove (k,v) tuple with minimum key.

    Raise Empty exception if empty.
    """
    if self.is_empty():
      raise Empty('Priority queue is empty.')
    item = self._data[0]
    return (item._key, item._value)

  def remove_min(self):
    """Remove and return (k,v) tuple with minimum key.

    Raise Empty exception if empty.
    """
    if self.is_empty():
      raise Empty('Priority queue is empty.')
    self._swap(0, len(self._data) - 1)
    item = self._data.pop()
    self._downheap(0)
    return (item._key, item._value)
\end{python}
%\newpage

\item Write an algorithm \pyth{min_list}, in pseudo-code or in
Python, that returns a list with the values of all nodes of a heap
whose key is identical to the minimal key.
\hfill(10)
%\newpage\mbox{}\newpage

\end{enumerate}


\end{document}