\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}