\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 2026},%
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 2026}\\
\vspace{2mm}
{\Large\bf Assignment 4}\\
\vspace{3mm}
\textbf{Due Date: Tuesday July 14, 5pm}
\end{center}
Please read the following link for guidelines on submission:
\begin{center}
\url{https://student.cs.uwaterloo.ca/~cs240/assignments.phtml#guidelines}  
\end{center}
\textbf{Late Policy:} Assignments are due at 5:00pm, with a grace period until 7:59pm.


\subsection{Analysis of search in skip lists [2+1+5+3 marks]}

We work with a skip list with $n$ keys, and we consider the search for
a key $k$. This key, and the keys in the skip list, are fixed
throughout. All the expected values are computed with respect to the
coin tosses we do to build the skip list. For $i\ge 0$,
we call $N_i$ the number of nodes we visit at level $i$ when
searching for $k$ (this is a random variable, it depends on the skip list).

\begin{enumerate}[label=(\alph*)]
\item Using the expected value of the number of nodes at level $i$ seen in
  class, give a simple upper bound on $E[N_i]$ that depends on $i$.
\item Justify the following observation: if we follow a search path backward,
  then whenever we can go up, we must go up.
\item For a level $i \ge 0$, let $1 \le \ell_i \le r_i \le n$ be the
  indices of the towers that we visit at level $i$ during the search.
  Prove that, for a given value of $r_i$, we have 
  \begin{itemize}
  \item $P(\ell_i=r_i)=1/2$
  \item $P(\ell_i=r_i-1)=1/4$
  \item \dots
  \item $P(\ell_i=2)=1/2^{r_i-1}$
  \item $P(\ell_i=1)=1/2^{r_i-1}$
  \end{itemize}
  Deduce that, still for a given $r_i$, $E[r_i-\ell_i+1]\le 2$, and from that
  that $E[N_i] \le 2$.
\item Use the two bounds on $E[N_i]$ to prove that the total number of
  nodes we visit during a search is, in expectation, $O(\log n)$. You
  can assume that $n$ is a power of $2$.
\end{enumerate}

\paragraph{Results you can use}
\begin{itemize}
\item $\sum_{j=0}^{N-1} j/2^j= 2 - (N+1)/2^{N-1}$ 
\item law of total expectation: if $X,Y$ are two random variables, and
  for any $k$ we have $E[X-Y | X=k] \le c$, then $E[X-Y] \le c$.
\end{itemize}


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

\subsection{Analysis of self-organizing search [4+2+1+4+3 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$; you can 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}[label=(\alph*)]
\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?  (you do not have 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
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]}

In this problem, to simplify your calculations, assume that
the index $m$ we use in interpolation search (step 5) is
$$m = \ell + \left \lfloor \frac{k-A[\ell]}{A[r]-A[\ell]}(r-\ell) \right \rfloor.$$
The formula used in class is better suited  for the average case analysis,
the one above works better for this problem.
\begin{enumerate}[label=(\alph*)]
\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  (but don't have to)
  \begin{itemize}
  \item use any result seen in class without reproving them, 
  \item assume that this runtime is an increasing function of $n$,
  \item use a sloppy recurrence,
  \item solve this recurrence only for some special values of $n$.
  \end{itemize}
\end{enumerate}

\noindent {\bf The following exercises are provided for additional
  practice and are not part of the graded portion of the
  assignment. While these questions will not be evaluated, we strongly
  encourage you, and expect you, to work through them to deepen your
  understanding of the material. You are welcome to upload your
  solutions to Crowdmark for your own record-keeping and organization;
  however, no grades or feedback will be provided for these
  submissions. You may also ask questions about these exercises during
  office hours or on Piazza.}

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

\subsection{Skip lists}

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}[label=(\alph*)]
\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{Tries}

\begin{enumerate}[label=(\alph*)]
\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}

\begin{enumerate}[label=(\alph*)]
\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}


\end{document}
