\documentclass{assignment-263}


\anum{1}
\course{CSC263}
\duedate{Jan 27, 2020}
\filename{ps1.pdf, ps1.tex, pretend\_sorted\_array.py }

\begin{document}

\think

\textbf{Please see the course information sheet for the late submission
  policy.}

\begin{enumerate}
\item \textbf{[10 points]}
  Recall this code from lecture.

\begin{python}
Search42(L):
  z = L.head
  while z != None and z.key != 42:
     z = z.next
  return z
\end{python}

Suppose that the input list L has $n$ ($\ge 25$) elements (excluding the
\texttt{None} element). The list is constructed randomly as follows:


The first number in the list is picked uniformly randomly from the set
of all even numbers between $2$ and $2n$ (both inclusive), i.e.,
$\{2, 4, 6, 8, 10, \ldots, 2n\},$ the second number in the list is picked uniformly randomly
from the set of all even numbers between $4$ and $2n$ inclusive,
i.e. $\{4, 6, 8, 10, \ldots, 2n\},$ etc. Generally, the $k^{\textrm{th}}$ element
in the list is picked uniformly randomly from $\{2k, 2(k+1), \ldots, 2n\}.$
All choices are made independently of each other.

Let us analyze the number of times line 3 is executed. Answer the
following questions in \textbf{exact form} and \textbf{not} in
asymptotic notation. Show your work!
\begin{enumerate}
\item (2 points) What is the \textbf{smallest number of times} line 3
  is executed? What is the probability that line 3 is executed the
  smallest possible number of times? Justify your answer carefully:
  show your work and explain your calculation.
\item (3 points) What is the \textbf{largest number of times} line 3
  is executed? What is the probability that line 3 is executed the
  largest possible number of times? Justify your answer carefully:
  show your work and explain your calculation.
\item (4 points) What is the \textbf{expected number of times} line 3
  is executed? Justify your answer carefully: show your work and
  explain your calculation.
\item (1 point) For what value of $n$ is the expected number of times
  line 3 is executed between 13 and 17 (both inclusive)? You are
  allowed to use math tools such as a calculator or WolframAlpha to
  obtain your answer.
\end{enumerate}



\item[2.] \textbf{(total 10 points)} Consider the following code for checking if the input array
  \verb|A| is a max-heap:
  
\begin{python}
  // Assume arrays are zero-indexed
  // and A.size() returns number of elements in A
CheckMaxHeap(A):
  for i from 0 to floor(A.size()/2)-1:
    if CheckMaxHeapHelper(A, i) == False
      return False
  return True

CheckMaxHeapHelper(A, i):
  if 2i+1 < A.size():
    if A[2i+1] > A[i]:
      return False
  if 2i+2 < A.size():
    if A[2i+2] > A[i]:
      return False
  return True
\end{python}

  \begin{enumerate}
  \item (2 points total) Consider an array \verb|A| with three elements
    (suppose \verb|A| is 0-indexed). Suppose the elements of \verb|A|
    are filled with a random permutation of \verb|{1, 2, 3}|.
    \begin{enumerate}
    % \item For \verb|A| to be a max-heap, what is \verb|A[0]|? Briefly
      % explain your answer.
    \item (1 point) What is the probability that \verb|A| is a max-heap? Briefly
      explain your answer.
    \item (1 point) If we run \verb|CheckMaxHeap(A)|, what is the expected
      number of times \verb|CheckMaxHeapHelper| is called? Justify
      your answer carefully: show your work and explain your
      calculation.
    \end{enumerate}
  \item (8 points) Now consider an array \verb|A| with five
    elements (suppose \verb|A| is 0-indexed). Suppose the elements of
    \verb|A| are filled with a random permutation of
    \verb|{1, 2, 3, 4, 5}|.
    \begin{enumerate}
    \item (2 points) What is the probability that
      \verb|CheckMaxHeapHelper(A, 0)| 
      returns \verb|True|? Justify
      your answer carefully: show your work and explain your
      calculation.
    \item (4 points) What is the probability that
      \verb|CheckMaxHeap(A)| 
      returns \verb|True|? Justify
      your answer carefully: show your work and explain your
      calculation. Enumeration is not a justification.

    \item (2 points) If we run \verb|CheckMaxHeap(A)|, what is the expected
      number of times \verb|CheckMaxHeapHelper| is called? Justify
      your answer carefully: show your work and explain your
      calculation.
    \end{enumerate}
  \end{enumerate}
\end{enumerate}


\program

\begin{enumerate}
\item[3.] \textbf{(12 points)}
  Consider the following \emph{slow} data structure that maintains a
sorted array along with a \emph{pointer} index, and permits the
following commands as follows:
  \begin{itemize}
  \item The \verb|initialize| command is a string of the form
    \verb|initialize x1 x2 ... xk|, where \verb|x1|, \verb|x2|,
    ... \verb|xk| are integers (not necessarily in a sorted
    order). This command means that the array must be initialized with
    the collection $\{ \verb|x1|, \verb|x2|, \ldots, \verb|xk|\}$ in
    \textbf{sorted order}. Note that the command \verb|initialize| are
    all separated by a single space.  There will be exactly one
    \verb|initialize| command that will appears as the first command
    in the list of commands.

    At initialization, consider that the \emph{pointer} is at the
    location of the entry $\verb|x1|$ in the sorted array.


    e.g.  \verb|initialize 15 4 7 12| would initialize the sorted
    array as \verb|A = [4, 7, 12, 15]|, and will initialize the
    \emph{pointer} index to 3 since \verb|A[3] = 15| (assume that the
    array is o-indexed).
    
  \item An \verb|insert| command is a string of the form
    \verb|insert x|, where \verb|x| is an integer. (Note the space
    between \verb|insert| and \verb|x|.) This command adds \verb|x| to
    the array while maintaining a sorted order.

    e.g. executing \verb|insert 8| on the above example implies that
    we must update our array to be \verb|A = [4, 7, 8, 12, 15]|. The
    \emph{pointer} remains as 3, and is \emph{not updated}.
  
  \item \verb|move_pointer_left| command moves the pointer left. If
    the pointer is already at the first element in the array, the
    pointer stays at the first element.

    e.g. after executing \verb|move_pointer_left| on the above
    example, the pointer would be updated to 2.
  
  \item Similarly, \verb|move_pointer_right| command moves the pointer
    right. If the pointer is already at the last non-empty location in
    the array, the pointer stays at its location.

    e.g. after executing \verb|move_pointer_right| on the above
    example, the pointer would be updated to 3.
    
  \item \emph{Output:} At the end of executing each command, the data
    structure prints the element at the current location of the
    pointer.

    e.g. After executing the commands in the above examples in order,
    the outputs would be \verb|15 12 8 12|.
  \end{itemize}


  Note that the above data structure is \emph{slow}.
  
  In this question, you will implement a new ADT that we shall call
  \textbf{PretendSortedArray}.  Our ADT emulates the behavior of  the
  above data structure but in a \textbf{much faster way}. 

  
  The function \verb|pretend_sorted_array| takes a list of commands
  described above that operate on the current collection of data. Your
  task is to process the commands in order and return the list of
  outputs. There are four kinds of commands: \verb|initialize|
  commands, \verb|insert| commands, \verb|move_pointer_left| commands
  and \verb|move_pointer_right| commands.


  Your goal is to implement
  \begin{itemize}
  \item the \verb|initialize| command in worst-case $O(n)$ time, where $n$ is the
    number of elements in the initial collection,
  \item and the \verb|insert|, \verb|move_pointer_left|, and
    \verb|move_pointer_right| commands each in worst-case $O(\log n)$ time, where
    $n$ is the number of elements currently in the collection.
  \end{itemize}

  The list returned by \verb|pretend_sorted_array| consists of the
  results, in order, from each of the commands in the list.  For
  example, here is a sample call of \verb|pretend_sorted_array|:

\begin{verbatim}
pretend_sorted_array(
  [ 'initialize 4 15 7 12',
    'move_pointer_left',
    'move_pointer_right',
    'insert 8',
    'insert 6',
    'move_pointer_right',
    'move_pointer_right', 
    'move_pointer_right',
  ])
\end{verbatim}

  This corresponds to the following states of the sorted array and
  pointer:
  \begin{itemize}
  \item We initialize the array with the sorted collection of number,
    and initialize the pointer to the location of 4 in the array.
    
    \verb|A = [4, 7, 12, 15]| and \verb|pointer = 0|. Outputs \verb|4|
  \item We try to move the pointer left. Since it's already at the
    first location, we don't update it.

    \verb|A = [4, 7, 12, 15]| and \verb|pointer = 0|. Outputs \verb|4|
  \item We move the pointer to the right.

    \verb|A = [4, 7, 12, 15]| and \verb|pointer = 1|. Outputs \verb|7|
  \item We insert 8 into the sorted array.

    \verb|A = [4, 7, 8, 12, 15]| and \verb|pointer = 1|.
    Outputs
    \verb|7|
  \item We insert 6 into the sorted array.

    \verb|A = [4, 6, 7, 8, 12, 15]| and \verb|pointer = 1|. Outputs \verb|6|
  \item We move the pointer right.

    \verb|A = [4, 6, 7, 8, 12, 15]| and \verb|pointer = 2|. Outputs \verb|7|
  \item We move the pointer right.

    \verb|A = [4, 6, 7, 8, 12, 15]| and \verb|pointer = 3|. Outputs \verb|8|
  \item We move the pointer right.

    \verb|A = [4, 6, 7, 8, 12, 15]| and \verb|pointer = 4|. Outputs \verb|12|
  \end{itemize}

  
  \verb|pretend_sorted_array| returns
  \verb|[4, 4, 7, 7, 6, 7, 8, 12]|.
   
  Requirements:
  \begin{itemize}
  \item Your code must be written in Python 3, and the filename must
    be \verb|pretend_sorted_array.py|.
  \item We will grade only the \verb|pretend_sorted_array| function;
    please do not change its signature in the starter code. include as
    many helper functions as you wish.
  \end{itemize}
   
  \textbf{Write-up}: in your \verb|ps1.pdf/ps1.tex| files, briefly and
  informally argue why your code is correct, and has the desired
  runtime.
  
\end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
