\documentclass[12pt]{article}

\usepackage{fullpage,amssymb}
\usepackage{enumitem}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools,algorithm,algorithmicx,algpseudocode}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 240 Assignment 4},%
pdfsubject={University of Waterloo, CS 240, Spring 2023},%
pdfauthor={MP}]{hyperref}


\newlength{\nodeLength}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}

\newcommand{\alg}[1]{\ensuremath\mbox{\it #1}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\newcounter{algorithmeligne}
\newcommand{\instr}[1]{%\underline
                        {\bf #1}}
\newcommand{\nomproc}[1]{{\rm\bf #1}}
\newenvironment{algorithme}
        {
        \setcounter{algorithmeligne}{0}

        \newcommand{\lign}{
                \stepcounter{algorithmeligne}
                {\footnotesize \arabic{algorithmeligne}.}\>
                }
        \begin{center}
        \begin{tabular}{|c|}
        \hline
        \begin{minipage}{1cm}
        \small
        \,
        \ \ \\[-11mm]
        \begin{tabbing}
\hskip1cm\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\\\kill
        }
        {
        \end{tabbing}
        \ \ \\[-8mm]
        \end{minipage}
        \\\hline
        \end{tabular}
        \end{center}
        }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Spring 2024}\\
\vspace{2mm}
{\Large\bf Assignment 4}\\
\vspace{3mm}
\textbf{Due Date: Tuesday July 9, 5pm}
\end{center}
Please read the following link for guidelines on submission:
\begin{center}
\url{https://student.cs.uwaterloo.ca/~cs240/s24/assignments.phtml#guidelines}  
\end{center}
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a4q1.pdf, a4q2.pdf, \dots 
It is a good idea to submit questions as you go so you aren't trying to create several PDF files at the last minute. \\
~\\
\textbf{Late Policy:} Assignments are due at 5:00pm, with the grace period until 11:59pm.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Skip lists [3+3 marks]}

Suppose you have a skip list with only three levels. The lower one has
$n+2$ entries $-\infty < a_0 < \cdots < a_{n-1} < +\infty$. The middle one
has $k+2$ entries, where $k$ is an integer that divides
$n$ (so that $n = km$ for some integer $m$); we assume that (with
the exceptions of $\pm \infty$), these entries are evenly spread out,
so they correspond to $-\infty, a_0,
a_m,a_{2m},\dots,a_{(k-1)m},+\infty$. The top level holds $-
\infty,+\infty$. 
\begin{enumerate}
\item What is the worst time for a query? Give a $\Theta(\ )$ expression
  involving $k$ and $n$, and justify your answer.
\item Given $n$, how to choose $k$ so as to minimize the $\Theta(\ )$
  bound you just obtained, and what does the worst case become in that
  case?  Give a $\Theta(\ )$ expression in terms of $n$, and justify
  your answer. You can assume $n$ is a square.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Analysis of self-organizing search [4+4+1+4+4 marks]}

In this problem, we analyse the move-to-front strategy for linear
search. Suppose we have a linked list with keys $x_1,\dots,x_n$, and
that the probability of accessing $x_i$ is $p_i$; it will be handy
later on to assume that $p_i > 0$ for all $i$.

We consider the move-to-front heuristic. As input, we suppose we are
given a linked list with keys $x_1,\dots,x_n$, but we do not know in
which order they are.

\begin{enumerate}
\item We do not know the order at the beginning, so let us call $X^{(0)}_{i,j}$ 
  the probability that initially $x_i$ is before $x_j$. Show that after 
  one query, the probability that $x_i$ is before $x_j$ is 
  $$X^{(1)}_{i,j} = p_i + (1-p_i - p_j) X^{(0)}_{i,j}$$ and the probability
  that $x_j$ is before $x_i$ is $1-X^{(1)}_{i,j}$.  
\item Show by induction that after $N$ queries, these probabilities 
are 
$$X^{(N)}_{i,j} = p_i (1 + (1-p_i-p_j) + (1-p_i-p_j)^2 + \cdots + (1-p_i-p_j)^{N-1})
  + (1-p_i-p_j)^N X^{(0)}_{i,j}$$
and $1-X^{(N)}_{i,j}$.
\item  Show that the limit probabilities, for $N \to \infty$, are 
  $$ \frac {p_i}{p_i +p_j} \quad \mathrm{and}\quad \frac {p_j}{p_i +p_j}.$$
  You can use the fact that for $0 \le r < 1$, $1 + r + r^2 + r^3 + \cdots = \frac 1{1-r}.$
  In the rest of the problem, we will assume that $N$ is very large, and work with the limit probabilities.
\item  Show that for $N \to \infty$ the expected position of $x_i$ in the list
is
  $$1 + \sum_{j \ne i} \frac {p_j}{p_i +p_j}.$$
Hint: rewrite the number of $x_j$'s before $x_i$ as a sum involving 
indicator variables. Note: we index positions starting from 1, just as we did
in the move-to-front lecture.
\item What is the expected number $C_{\rm MTF}$ of links visited in a search
  using this heuristic?  (do not try to simplify the
  expression). Compute this value for the frequencies of the example
  seen in class:

\begin{center}
\begin{tabular}{r||c|c|c|c|c}
key & A & B & C & D & E \\
\hline
frequency  of access & 2 & 8 & 1 & 10 & 5  \\
\hline
access-probability & $\frac{2}{26}$ & $\frac{8}{26}$ & $\frac{1}{26}$ & $\frac{10}{26}$ & $\frac{5}{26}$
\end{tabular}
\end{center}
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Interpolation search [4+4 marks]}

\begin{enumerate}
\item Suppose that we use interpolation search in an array with
  entries $A[i] = \alpha i$ for $i=0,\dots,n-1$, $\alpha$ positive
  constant. What is the worst-case runtime for search? Give (and
  justify) a $\Theta$ bound.
\item Suppose that we use interpolation search in an array with
  entries $A[i] = \sqrt{i}$, for $i=0,\dots,n-1$, and that we search
  for $k=1$. What is the runtime? Give (and justify) a big-O bound.
  You can use any result seen in class without reproving them.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Tries [3+3 marks]}

\begin{enumerate}
\item For $n \ge 1$, find the height of the trie that stores the
  binary representation of all integers in $\{0,\dots,2^n-1\}$
  (without unnecessary leading zeros), that is, $0\$,1\$,10\$,\dots$.
\item What is the height of the compressed trie storing these words?
\end{enumerate}
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Hashing [2+4 marks]}

\begin{enumerate}
\item Consider a hash table dictionary with universe $U=\{0, 1, 2,
  \dots , 24\}$ and size $M =5$. If items with keys $k = 21, 3, 16, 1$
  are inserted in that order, draw the resulting hash table if we
  resolve collisions using:
\begin{itemize}
\item Linear probing with $h(k) = (k+1) \mod 5$
\item Cuckoo hashing with $h_1(k) = k \mod 5$ and $h_2(k) =\lfloor k/5
  \rfloor$ (use two arrays of size $5$)
\end{itemize}
\item Let $S$ be a set of $n$ keys mapped to a hash table also of size
  $n$ using chaining. We make the uniform hashing assumption,
  and we call $c_n$ the expected number of empty slots. Prove that
  $c_n =n/e + o(n)$, where $e$ is the basis of the natural logarithm.

  You can use the fact that $\lim_{n \to \infty} (1-1/n)^n = 1/e$.
  Hint: use indicator variables $I_0,\dots,I_{n-1}$, that take values
  $0$ or $1$, depending on whether the corresponding entry in the
  table is empty or not; then, find the expected value of each $I_i$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{One-sided range search in a heap [5 marks]}

Heaps are suitable for {\em one-sided range queries}.  Specifically,
assume you are given a max-heap $H$ and an integer $x$, and you are
asked to return all keys in $H$ that fall in the range $[x,\infty)$,
  i.e., all keys that are at least $x$.

Give an algorithm that answers such a one-sided range query in time
that depends only on the number $k$ of keys in the output.  Describe
your algorithm, justify why it works, and analyze the runtime.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
