\documentclass[12pt]{article} 


%%%%%%% a few packages
\usepackage{fullpage}
\usepackage[ruled,vlined,linesnumbered,titlenumbered]{algorithm2e}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\SetKw{KwBreak}{break}
\usepackage{color}
\usepackage{hyperref} % for the URL
\usepackage{verbatim} % for comments, for version control
\usepackage{ifthen} % for version control
\usepackage{todonotes} 
\usepackage{amsmath} 
\def\calI{\ensuremath{\mathcal{I}}}
\def\part#1{\item[\bf #1)]}
\usepackage{tikz}
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240E, Spring 2025}\\
\vspace{3mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, June 3, 2025 at 5pm}, with grace period until 7:59pm.
\end{center}

\medskip

Remark: For all questions on this assignment you {\bf cannot compute
logarithms or exponentiations in constant time}.    If you need these,
then your algorithm must compute them from scratch, and the time to do
so must be counted when analyzing run-time.

\def\alg#1{\text{\it #1}}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\subsection{[20 marks]}

Consider the following realization (called {\em buckets of sorted arrays})
    of ADT Dictionary.  We have an array $B[0\dots N{-}1]$ for some $N\geq 0$.
    Entry $B[j]$ is either NULL, or it stores a reference to an  array of size exactly $2^j$,
    with items in sorted order.    The following is an example.

\begin{center}
\begin{tikzpicture}[scale=0.8,line width=1pt,
                    start chain=going below,node distance=-1pt,
                    every node/.style={draw,minimum width=5mm,minimum height=5mm},
                    chainnode/.style={draw,minimum width=1.3cm,minimum height=8mm},
                    every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
                    label distance=0mm]
%%%%%%%%% 0 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:0},label={above:$B$}] (zero) {$\bullet$};
%\node[draw=none,above=1pt of zero] {$B$};
    \node[right=1cm of zero,rectangle] {45} edge[<-] (zero.center);
%%%%%%%%% 1 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:1}] (one) {$\bullet$};
    \node[right=1cm of one,rectangle, rectangle split,rectangle split parts=2,rectangle split horizontal] {13 \nodepart{second} 60} edge[<-] (one.center);
%%%%%%%%% 2 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:2}] (two) {\scriptsize NULL};
%%%%%%%%% 3 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:3}] (three) {$\bullet$};
    \node[right=1cm of three,rectangle, rectangle split,rectangle split parts=8,rectangle split horizontal] {10 \nodepart{second} 17 \nodepart{third} 24 \nodepart{four} 31 \nodepart{five} 42 \nodepart{six} 49 \nodepart{seven} 55 \nodepart{eight} 56 } edge[<-] (three.center);
%%%%%%%%% 4 %%%%%%%%%%%%%
  \node[on chain,chainnode, label={left:4}] (four) {\scriptsize NULL};
%%%%%%%%% 5 %%%%%%%%%%%%%
    \node[on chain,chainnode, label={left:5}] (five) {\scriptsize NULL};
\node[left=2cm of zero,label={above:$n$}] {11};
\node[left=2cm of two,label={above:$N$}] {6};
\end{tikzpicture}
\end{center}

    \begin{enumerate}
    \part{a} Design an algorithm that does \alg{search}($k$) in buckets of sorted arrays in $O(\log^2 n)$ time.
        You may assume that you know $n$ and $N$, but $N$ could be arbitrarily large relative to $n$.
	You need not argue correctness, but explain your idea in detail.  
        
    \part{b} Insert key 40 into the example and show the resulting $B$.
        There are multiple possible answers; show
        the one that moves as few items as possible into a different bucket.

    \part{c} Design an algorithm to do \alg{insert}($k,v$)
	in such a way that as few items as possible are moved.  
	Your algorithm must have worst-case run-time $O(1+s)$,
	where $s$ is the number of items that were moved.
	You need not argue correctness.  
    You may assume that $N$ is sufficiently big so that the new item will fit.

    \part{d} 
        Define $\Phi := \sum_{j=0}^N \sum_{x\in B[j]} (N-j)$.    Briefly verify
    that this is a potential function, and then show that with this
        potential function (and a suitable choice of time units), the amortized time of \alg{insert} is $O(\log n)$.
    For this part you may assume that $N\in O(\log n)$.

    \end{enumerate}

\subsection{[20 marks]}

Let $T(w)$ be the number of times that we print a `*' when calling Algorithm~\ref{alg:silly-algo} with a bitstring $w$ of
length $n$.     Now let $T^{\rm best}(n)$, $T^{\rm worst}(n)$, and $T^{\rm avg}(n)$ be
the best, worst, and average of this (over all bitstrings of length $n$).

\bigskip
\hspace*{-5mm}
\begin{minipage}[t]{0.43\linewidth}
\begin{itemize}
\part{a} Prove an $O$-bound on $T^{\rm best}(n)$.
\part{b} Prove an $\Omega$-bound on $T^{\rm worst}(n)$.
\part{c} Show that $T^{\rm avg}(n)\in O(T^{\rm best}(n))$.
\end{itemize}
\end{minipage}
\hspace*{\fill}%
\begin{minipage}[t]{0.55\linewidth}
\vspace*{-5mm}
\begin{algorithm}[H]
\caption{$\alg{silly-algo}(w,n)$}
\label{alg:silly-algo}
\Input{bitstring $w$ of length $n$}
$i\gets 0$, \lWhile{$w[i]==0$}{$i\gets i+1$}
\tcp{\small$\!w[i]$ is leftmost non-zero, possibly $\$\!\!$}
\lFor*{$k=1$ to $(i{+}1)^2$}{ print ``*'' }
\end{algorithm}
\end{minipage}

	Hint: If you find part (c) difficult, then for partial credit
	state a summation-formula for $T^{\rm avg}(n)$, simplify it
	as much as possible, and give as tight an upper bound for it
	as you can manage. 
	You may use without proof that $x\geq 4\log x$ for $x\geq 16$.
	The course-notes have bounds for some summations that you 
	may use without proof (but state the page-number).

\subsection{[20 marks]}

Consider a version of binomial heaps that has the same structure
and order properties, but the following implementation of the operations
for a binomial heap $P$:
        \begin{itemize}
        \item {\it $P$.merge}($P'$):  Append the list of $P'$ to the one of $P$.  
		This takes $O(1)$ time.
        \item {\it $P$.insert}($x$):  Create a single-node binomial heap $P'$ that
		stores $x$ and then call {\it $P$.merge}($P'$).
                This takes $O(1)$ time.
        \item {\it $P$.deleteMax}: First, make $P$ proper with the same routine
		as in class.  Then perform {\it deleteMax} as in class, i.e.,
		find the maximum among the roots (in the list $L$ of flagged 
		trees),
		remove the tree $T$ that contains the maximum $x_0$ from $L$, 
		split $T\setminus \{x_0\}$ into flagged trees, let $P'$ be the
		binomial heap with these flagged trees and 
		call {\it $P$.merge}($P'$).   
		This takes $O(|L|+\log n)$ time, where $n$ is the number
		of items and $|L|$ is the length of the list at the beginning 
		of the operation.
        \end{itemize}

\smallskip
        \begin{enumerate}
        \part{a} Show that {\it deleteMax} has worst-case run-time in $\Theta(n)$.

        \part{b} Argue that with this implementation, the {\em amortized} run-time
                is in $O(1)$ for insert and in $O(\log n)$ for deleteMax.
		Using a potential function is recommended; coming up with
		a suitable one is part of the assignment.

		(You do not need to analyze the amortized run-time of {\it merge}
		as a stand-alone operation, though of course you do need to analyze
		its effects if it is called within {\em insert} or {\em deleteMax}.)
        \end{enumerate}

\subsection{[20 marks]}

Professor Clever was teaching lower bounds for 
comparison-based sorting the other day, and at the end of the lecture
she had a brilliant idea. It is true that every comparison-based
sorting algorithm requires $\Omega(n\log n)$ operations to sort an
array of numbers, but perhaps we could do better if we were satisfied with only ``almost'' sorted arrays?

An \emph{almost-sorted array} is an array from which we can obtain
a sorted array by moving every element in the array by at most
$10$ positions. An \emph{almost-sorting algorithm}
takes an array of $n$ numbers as the input and reorders the elements
in the array so that the array is almost-sorted.

Show that Professor Clever is wrong: even if we only
require almost-sorted arrays as the output, every comparison-based
almost-sorting algorithm still requires $\Omega(n\log n)$ comparisons.
    
\subsection{[20 marks]}

\begin{enumerate}
\part{a} 
Assume that you are given a non-empty singly-linked list $L$ that contains $n$ key-value pairs
in sorted order.   Design an algorithm to build a binary search tree that contains
exactly the items of $L$ and that is \emph{perfectly size-balanced}, i.e., 
for every vertex $z$ we have $|\alg{size}(z.\alg{left})-\alg{size}(z.\alg{right})|\leq 1$.
The run-time must be $O(n)$ and the algorithm should use $O(\log n)$ auxiliary
space (i.e., space other than the input-list $L$ and the output-tree $T$ that you are building).

\part{b} Prof.~Quirky thinks that he can do the above with a 
comparison-based algorithm even if list $L$ is in unsorted
order.  Show that this is not possible.

\end{enumerate}

\end{document}
