\documentclass[12pt]{article}

\setlength{\textwidth}{6.5in}  %6.25in or 6.5in
\setlength{\textheight}{9.5in}
\setlength{\topmargin}{-.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
% \setlength{\footheight}{.5in}
% \setlength{\footskip}{.5in}
\setlength{\oddsidemargin}{.1in} %.2in or 0in
\setlength{\evensidemargin}{.1in}
\setlength{\parindent}{0.3in}   %.5in
\setlength{\parskip}{0in}       %.1 in or .2 in or 0in
\setlength{\partopsep}{2ex}
\setlength{\topsep}{0ex}
\setlength{\itemsep}{-2ex}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hfuzz=3pt
\vfuzz=3pt

\begin{document}
\sloppy

\noindent
{\Large\bf
\begin{tabular*}{\textwidth}
{@{}l@{\extracolsep{\fill}}c@{\extracolsep{\fill}}r@{}}
CSE250, Spr'22 & Final Exam (alt.) & May 19, 2022
\end{tabular*}
}


\bigskip
\noindent
Open book, open notes, closed neighbors, 170 minutes.
Do {\sc All Six} questions in the exam books provided.
Please {\em show all your work\/}---this may help for partial credit.
The exam totals 200 pts., subdivided (48,36,30,18,36,32)
and further as shown.

\bigskip
\bigskip
\noindent
{\bf (1) (9+9+9+9+12 = 48 pts.)}

Let $h$ be the hash function on strings that adds up number values of letters
$a = 1$, $b = 2$, $c = 3$ etc., and let binary search trees compare
strings in alphabetical order with the earlier (lesser) string on the left.
(Unlike as on homeworks, all letters are used for this $h$.)

Show the process of inserting the strings
{\tt add, be, fad, bag, ace, ach, ah} in that order into the following
data structures.  Show the hash tables after {\tt ace},
and then after {\tt ah}---if you can!
One picture of the BST is enough, while the AVL tree should be shown
after {\em each\/} step, indicating rotations that are made.
\begin{itemize}
\item[(a)]
A size-$8$ hash table with chaining,
with new elements going at end-of-buckets.
\item[(b)]
A size-$8$ open-address hash table,
using linear probing: $h(k) + i$ for the $i$-th try.
\item[(c)]
A size-$8$ open-address hash table, using the
quadratic probe function $h(k) + i^2$.
(Or, if you wish, you can use the text's $h(k) + 2i + 3i^2$.)
\item[(d)]
A simple binary search tree.
\item[(e)]
An AVL tree---again you must show every step, and in
some cases you can vary from the text's algorithm if you
make clear that your ``moves'' are legal.  Does the final
insertion of {\tt ah} force a rotation?
\end{itemize}



\bigskip
\bigskip
\noindent
{\bf (2) (6 $\times$ 6 $=$ 36 pts.)}

{\em Short answer questions\/}: two sentences or formulas at most.
\begin{itemize}
\item[(a)]
Suppose an AVL tree has a node $u$ that has only one child, call
it $v$.  Is $v$ allowed to have a child without the tree having to rotate?
\item[(b)]
Suppose a heap has a node $u$ that has only one child, call it $v$.
How many children is $v$ allowed to have?
\item[(c)]
Show using limits (and/or L'H\^opital's Rule if you know it)
that a running time of $n\log n$ is
asymptotically faster than (i.e., little-oh of) a running time
of $n^2/\log n$.
\item[(d)]
For what value of $n$ and higher will a program with running time
$n\log n$ actually start to out-perform a program with running time
$n^2/\log n$?  Here logs are to base 2.
\item[(e)]
Suppose you create a simple binary search tree of $n$ elements by
first making the $n$ elements into a heap,
and then popping them one by one to insert into the tree in that order.
Does that guarantee that the tree will be balanced?
Explain why or why not.
\item[(f)]
Why is it impossible for an implementation of a stack using an
{\tt Array} or {\tt ArrayBuffer}
to guarantee that every individual push operation will run in $O(1)$ time?
\end{itemize}



\bigskip
\bigskip
\noindent
{\bf (3) (10 $\times$ 3 $=$ 30 pts.)}

Let $ac(n)$ and $wc(n)$ respectively stand for
the average-case time and the worst-case time of an
algorithm running on instances of size $n$.
(The former has the same meaning as ``usual time'' on Prelim II; the
separate concept of {\em amortized time\/} for a repeatable 
operation is not involved here.)
For each of the following algorithms, say whether it
\begin{itemize}
\item[(A)]
should only be run when $n$ is small; 
\item[(B)]
runs well for ``most'' cases, but has poor performance in some
cases---in particular has
$ac(n) = o(wc(n))$; or
\item[(C)]
runs well for all cases---formally, has $wc(n) = \Theta(ac(n))$,
and $wc(n)$ is ``{\em within an $O(\log n)$ factor of the best you could
possibly hope for\/}.''
\end{itemize}

\noindent
Standard implementations of the algorithms and data structures
they act on, such as we have seen or
used in this course, are assumed.  The five sorting algorithms
all work on arrays of size $n$.  The five cases of
{\tt insert} work one element at a time---i.e., they don't
see all $n$ elements ``in advance.''  The algorithms are:
%
\begin{enumerate}
\item
{\tt MergeSort}.
\item
{\tt while} the array is nonempty, find and remove the least element.
\item
{\tt HeapSort}.
\item
{\tt QuickSort}, implemented by choosing the leftmost element in
a sub-array as the ``pivot'' in every recursive step.
\item
``{\tt ValliSort},'' implemented by calling {\tt valli.insert(item)}
on each of the $n$ items.
\item
{\tt insert} $n$ elements into an unsorted 
(singly) linked list that is behaving like a set.
\item
{\tt insert} $n$ elements
into an unsorted (singly) linked list that is
behaving like a ``bag'' (a.k.a.\ multiset).
\item
{\tt insert} 
$n$ elements into a hash table with chaining.
\item
{\tt insert} $n$ elements into a ``simple'' binary search tree.
\item
{\tt insert} $n$ elements into an AVL tree.
\end{enumerate}

\bigskip
\bigskip
\noindent
{\bf (4) (18 pts.\ total)}

\noindent
We would love to have a data structure that:
\begin{itemize}
\item[(a)]
guarantees that any sequence of $n$ elements can be inserted one-at-a-time
in $O(n\log n)$ steps,
\item[(b)]
enables any element to be searched for in $O(\log n)$ time, and
\item[(c)]
allows iteration through all its elements in sorted order in
$O(n)$ time with a very small principal constant.
\end{itemize}
%
Here ``guarantees'' means ``\dots in the worst case.''
The size of the (unspecified) principal constant in (a) and (b) is
considered {\em not\/} of primary importance, not as important as the
constant in (c).  The constant in (c) should be close to the time
taken to follow one pointer link or advance one place in an array
(say, within a factor of 2, but not 3).

Consider {\tt BALBOA}, a {\tt Hash Table} with chaining,
and {\tt AVL Trees}.  It is OK to state features for the
first two even if you didn't code them---e.g.\ for {\tt BALBOA}:
refresh with $r = \sqrt{n}$ every time the input size doubles.
For each one, say
which of (a), (b), and (c) it satisfies, and which it doesn't.
You must {\em justify\/} all your negative answers with a reason or
an example of a case where it fails.  (Brief justifications for
positive answers aren't required but are a good idea anyway.  Note that
some answers repeat problem (3), and are included here just for
completeness.)


\bigskip
\bigskip
\bigskip
\noindent
{\bf (5) (12 + 24 = 36 pts.)}

Suppose you are interfacing clients to a generic container class
{\tt Container} that uses the ``ISR'' interface,
in particular with a {\tt find} method that returns a valid iterator
if a stored item with the same key is found, and otherwise returns the
{\tt end} iterator. 

\begin{itemize}
\item[(a)]
First suppose the client programs want to use a non-member function
%
\begin{verbatim}
def retrieve[A](cont: Cardbox[A], dummyItem: A): A
\end{verbatim}
%
with the idea that the given {\tt dummyItem} can be mostly blank except
for the key (similar to what was done on Assignment 6).
If a stored item with the same key
is found, we return it, else we return
{\tt dummyItem} is left as it is.

Write a body for {\tt retrieve}, using only {\tt find} and other features of
the ISR interface.  Also answer: in the successful case, are you returning
a fresh copy of the item?

\item[(b)]
Now suppose there might be multiple items with the same key, all having a
different integer value field {\tt value}.  Write code to find the 
item with the same key as {\tt dummyItem.key} that maximizes {\tt value}.
You may assume that {\tt find} returns an iterator to the first such
item and that the others are next in the sequence.
If {\tt find} runs in $O(\log n)$ time and there are always at most
$\log n$ items with the same key, what is the overall running time of
your procedure?  

\end{itemize}


\bigskip
\bigskip
\centerline{\em The last problem is overleaf.}

\newpage
\noindent
{\bf (6) (6 + 12 + 6 + 8 = 32 pts.)}

Suppose you have two heaps {\tt h1} and {\tt h2}, each with $n$ elements
heaped according to the same comparison function, with the maximum
element on top.
Given any number $k \leq 2n$, you want to generate a list of the
top-$k$ elements between the two heaps.  

\begin{itemize}
\item[(a)]
What is the asymptotic running time if you pop off $n$ elements
from one heap, insert them one-by-one into the other heap, and
pop $k$ elements from the latter?
\item[(b)]
Find a smarter way, one that works in $o(n)$ time.  State your
method and give its running time, proving that the time is $o(n)$.
You may use any other data structures that you wish.
\item[(c)]
If you have an array with $2m$ elements in any order, and you
want to find the top $m$ elements, does it matter to the asymptotic
running time if you make a heap and pop $m$ times, versus sorting
the entire array?  
\item[(d)]
In (c), what if the array instead comes with the
first $m$ elements initially sorted among themselves, and the
second $m$ elements ditto?
Harking back to (b), does an $O(m)$ runtime here matter to the
entire asymptotic running time of the task in (b)?
\end{itemize}

\bigskip
\centerline{\sc End of Exam}


\end{document}


% \bigskip
% \bigskip
\newpage
\noindent
{\bf (6) (36 pts.)}

Suppose that the only pieces of
information you have about a templated library
class {\tt\verb+Queue<I>+} and an associated iterator
class {\tt\verb+Queue<I>::iterator+}
are that the former has the public member functions

\begin{verbatim}
void push_back(const I& item);      //add item to rear of queue
I& front();                         //return reference to front item
void pop_front();                   //remove front item
Queue<I>::iterator begin();         //return iterator to front element,
\end{verbatim}

\noindent
---and that the latter has those functions
specified for a {\tt forward\_iterator} in the C++ Standard
Template Library.

\begin{itemize}
\item[(a)]
Write in C++ a function {\tt cut} that takes a queue {\tt qu} and a 
queue-iterator {\tt itr} as arguments, where you may assume that in any
call, {\tt qu} is nonempty and {\tt itr} points to an element of 
{\tt Q}.  The function {\tt cut} should take all elements up to,
but not including, the one pointed to by {\tt itr}, and move them
to the rear of the queue while preserving the sequence.
Simply and visually put, this has the same effect as
cutting a deck of cards so that {\tt *itr} becomes the new top item.

Syntactically, you may not represent {\tt cut} as being a member of the 
{\tt Queue} class---since you have no access to edit it.
Code {\tt cut} either as a non-member template function,
or as a member of a {\tt QueueAdapter} class---if you choose the latter,
sketch the class template header and its pointer {\tt impl} to a {\tt Queue}
as well.  Either way, the return type of {\tt cut} is {\tt void},
and it is OK to pass the iterator by value.  (18 pts.)

\item[(b)]
What is the asymptotic worst-case running time of your 
implementation of {\tt cut} on an $n$-element queue?
Does the average (or ``usual'') running time have the same
``$\Theta$'' order?
(6 pts.)

\item[(c)]
Now suppose you {\em do\/} have authority to modify the
class {\tt Queue} by adding {\tt cut} as a method, and
you know that the implementation uses a doubly-linked list.
How could you improve the running time of {\tt cut}?
Sketch your answer in words and
state the new running time.  (You are not asked to write any code
here, but you should state any assumptions about the private
fields and class invariants of {\tt Queue} and/or its cell and
iterator nested classes that you use.) 
(12 pts.)
\end{itemize}



% \bigskip
% \bigskip
% \noindent
% {\bf (7) (22 pts.)}
% 
% \noindent
% ``All I Want for Christmas'' is a data structure that:
% \begin{itemize}
% \item[(a)]
% guarantees that any sequence of $n$ elements can be inserted one-at-a-time
% in $O(n\log n)$ steps,
% \item[(b)]
% enables any element to be searched for in $O(\log n)$ time, and
% \item[(c)]
% allows iteration through all its elements in sorted order in
% $O(n)$ time with a very small principal constant.
% \end{itemize}
% %
% Here ``guarantees'' means ``\dots in the worst case.''  
% The size of the (unspecified) principal constant in (a) and (b) is
% considered {\em not\/} of primary importance, not as important as the
% constant in (c).  The constant in (c) should be close to the time
% taken to follow one pointer link or advance one place in an array
% (say, within a factor of 2, but not 3).
% 
% Consider {\tt Valli}, any kind of {\tt HashTable}, and {\tt Red-Black Trees}.
% For each one, say 
% which of (a), (b), and (c) it satisfies, and which it doesn't.
% You must {\em justify\/} all your negative answers with a reason or
% an example of a case where it fails.  (Brief justifications for 
% positive answers aren't required but are a good idea anyway.)

% Finally, sketch a way you might attempt to make one of these
% data structures ``do it all.''  Does it work?  Are there any
% other drawbacks that might result?


% \bigskip
% \bigskip
% \bigskip
% (8) {\em True/False\/}: Please write out the word
% ``true'' or ``false'' in full.  You do not need to give
% reasons for your answers, but they may help for partial credit.
% \begin{itemize}
% \item[(a)]
% TBA
% 
% \end{itemize}

\bigskip
\centerline{\sc End of Exam}
\end{document}



(9) {\em Multiple choice questions\/}.  Clearly identify the
{\em unique best answer\/} in your exam booklets.
You need not give reasons for your answers.  $6 \times 3 = 18$ pts.)

\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\item
\begin{itemize}
\item[(a)]
\item[(b)]
\item[(c)]
\item[(d)]
\end{itemize}

\end{enumerate}

\centerline{\sc End of Exam}
\end{document}

