\documentclass[12pt]{article}
\usepackage{fullpage,url,amssymb,epsfig,color,xspace,tikz,amsmath,tkz-graph}
\usetikzlibrary{shapes,positioning}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\begin{document}
\begin{center} {\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 - Fall 2025}\\
\vspace{2mm}
{\Large\bf Assignment 3}\\
\vspace{3mm}
\textbf{Due Date: Tuesday, October 28, at 5pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} 

\noindent
Please follow the guidelines for submission on the course webpage.\\

\noindent
\textbf{Each question must be submitted individually to Crowdmark.} 
Submit early and often.\\

\noindent
\textbf{Grace period:} submissions made before 7:59PM on October 28 will be accepted without penalty. Your last submission will be graded. Please note that submissions made after 7:59PM {\bf will not be graded} and may only be reviewed for feedback. \\  

\noindent
There are 64 possible marks available.  The assignment will be
marked out of 60.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{AVL Tree Operations [2+5+5=12 marks]}
As discussed in class, it is possible to implement AVL trees such that
the nodes store only the balance factor $\{-1,0,1\}$ at each node
instead of the height of the subtree rooted at the node.

\begin{figure}[h]
\begin{center}\begin{tikzpicture}[%
  level distance=45 pt,
  every node/.style={circle split,draw},
  level 1/.style={sibling distance=200 pt},
  level 2/.style={sibling distance=100 pt},
  level 3/.style={sibling distance=60 pt}%
]
  \node {55}
    child {node {46}
      child {node {13}
        child {node {7}}
        child {node {42}
          child {node {17}}
          child {node {45}}
        }
      }
      child {node {49}
        child {edge from parent[draw=none]}
        child {node {51}}
      }
    }
    child {node {82}
      child {node {59}}
      child {node {92}
        child {node {89}}
        child {edge from parent[draw=none]}
      }
    }
  ;
\end{tikzpicture}\end{center}
\caption{Binary tree $T$ of problem 1 \label{tree}}
\end{figure}
\begin{itemize}
\part{a} Show that the tree $T$ in Figure~\ref{tree}
is an AVL tree by writing in the balance factor in the lower half of each node.
\part{b}  Show the process of inserting a KVP with key 29 into the tree
$T$ in Figure~\ref{tree}..
  Specifically, draw the tree, with balance factors, after each call to
 {\sf restructure}.
\part{c}
   Show the process of deleting key 49 from the \emph{original} tree $T$
in Figure~\ref{tree}. 
  Specifically, draw the tree, with balance factors, after each call to {\sf
 restructure}.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{AVL Trees [4+4=8]}
Consider the binary tree $T$ in Figure~\ref{bintree}.
\begin{enumerate}
\part{a} Draw the tree that results by calling {\sf restructure}.
Note that the balance factors are shown in the lower part of the nodes.
\part{b} Draw the balance factors in the new tree.
\end{enumerate}
\begin{figure}[h]
\centering
\begin{tikzpicture}[
    level distance=1.5cm,
    every node/.style={circle split,draw},
    level 1/.style={sibling distance=5cm},
    level 2/.style={sibling distance=15 mm}
]
\node{{\sf b}\nodepart{lower}$+2$} [child anchor=north]
   child {node {\sf a\nodepart{lower}$0$}
       child {node [isosceles triangle, shape border rotate=90,anchor=apex] {\sf A}}
       child {node [isosceles triangle, shape border rotate=90,anchor=apex] {\sf B}}}
   child {node {\sf d\nodepart{lower}$-1$}
       child {node {\sf c\nodepart{lower}$0$}
          child {node [isosceles triangle, shape border rotate=90,anchor=apex] {\sf C}}
          child {node [isosceles triangle, shape border rotate=90,anchor=apex] {\sf D}}}
      child {node [isosceles triangle, shape border rotate=90,anchor=apex] {\sf E}}}
   ;
\end{tikzpicture}
\caption{Binary tree $T$ of problem 2. \label{bintree}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Height of an AVL Tree [6 marks]}
Describe an algorithm for computing the height of a given AVL tree
in $O(\log n)$ time on an AVL tree of size $n$.  In the pseudocode, use
the following terminology:
{\sf T.left}, {\sf T.right}, and {\sf T.parent} indicate the left
child, right child, and parent of a node $T$ and {\sf T.balance}
indicates its {\it balance factor} (-1, 0, or 1).  For example if
$T$ is the root we have {\sf T.parent=nil} and if $T$ is a leaf we
have {\sf T.left} and {\sf T.right} equal to {\sf nil}.  The input
is the root of the AVL tree.  Justify correctness of the algorithm
and provide a brief justification of the runtime.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Skip Lists [6+6=12 marks]}
\begin{enumerate}
\part{a} Starting with an empty skip list, insert the seven keys
      $67, 28, 64, 66, 60, 81, 49$.
      Use the following coin
      tosses to determine the  heights of towers (note, not every
      toss is necessarily used):
     $$T,T,H,H,T,H,T,H,H,T,H,H,T,T,H,T,H,H,T,T,H,H,H,T,\ldots$$
Note: Should you desire to use LaTex to draw the skip list,
Figure~\ref{fig:skip} gives an example of how to draw a skip list
using the \texttt{tikz} package.

\begin{figure}
\begin{tikzpicture}
\SetGraphUnit{1.5}
\SetVertexNormal[Shape  = rectangle,MinSize=.8 cm]
%%%%%%%%%%%%%%%%% vertices %%%%%%%%%%%%%%%%%%% 
%  name of node x;y  x row y column

\Vertex[L=$-\infty$] {0;0}

\foreach \num [count=\n from 0] in  {1,2,3}
 {\NO[L=$-\infty$](0;\n){0;\num}}        
% No = north (initial node) {new node}  L=label 
\foreach \num/\label [count=\n from 0] in  
    {1/11,2/15,3/17,4/28,5/31,6/55,7/56,8/61,9/+\infty}
      {\EA[L=$\label$](\n;0){\num;0}} 
\foreach \num [count=\n from 0] in  {1,2,3}{%
     \NO[L=$+\infty$](9;\n){9;\num}}  

\foreach \num [count=\n from 0] in  {1,2,3} {%
    \NO[L=$31$](5;\n){5;\num}}   

\foreach \no/\label  in  {1/11,2/15,6/55,7/56} {%
    \NO[L=$\label$](\no;0){\no;1} } 

%%%%%%%%%%%%%%%%% edges %%%%%%%%%%%%%%%%%%%%%%%
 \foreach \num [count=\n from 1] in  {0,...,8}  {\Edge(\num;0)(\n;0)}

 \foreach \num [count=\n from 1] in  {0,...,2}  
 {\Edge(0;\num)(0;\n)  \Edge(5;\num)(5;\n)  \Edge(9;\num)(9;\n)}

\foreach \num  in  {1,2,6,7} {\Edge(\num;0)(\num;1)}   

\foreach \num [remember=\num as \lastnum (initially 0)] in  {5,9}  
 {\Edge(\lastnum;3)(\num;3) }  

\foreach \num [remember=\num as \lastnum (initially 0)] in  {5,9}  
 {\Edge(\lastnum;2)(\num;2)} 

\foreach \num [remember=\num as \lastnum (initially 0)] in  {1,2,5,6,7,9}  
 {\Edge(\lastnum;1)(\num;1)}     
\end{tikzpicture} 
\caption{\label{fig:skip} 
Example of skip list drawn using the \texttt{tikz} packge.}
\end{figure}
\part{b} The worst case time for searching in a singly linked list
      is $\Theta(n)$.   Now consider a variation of  a skip list which
      has fixed height $h=3$ even though $n$ can become arbitrarily large.
      Level $S_0$ contains the keys $-\infty,k_1,k_2,\ldots,k_n,\infty$.
      Level $S_3$ contains only $-\infty$ and $\infty$.
      Describe subsets of keys that should be included in levels $S_1$
      and $S_2$ so that searching in the skip list has worst case cost
      $\Theta(n^{1/3})$.  Provide justification for the runtime of your
      skip list.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tug of War [6+7+7=20 marks]}
A tug of war is a contest in which two teams of players pull on a rope
in opposite directions. The team with the greater combined strength
wins. (We assume that strengths are perfectly
additive, and that there is no element of chance.)

For this problem, you are given $n$ players, at least one of whom is
\emph{strong} and at least one of whom is \emph{weak}. All strong players have
exactly the same strength, and all weak players similarly have exactly
the same strength. All players are either weak or strong. The task at hand is to determine which players are
strong and which are weak. Your tool to determine this is to assign
players to teams and have contests. The outcome of a single contest can
either be a tie, one team winning, or the other team winning.
\begin{enumerate}
  \part{a} Using the decision tree approach, derive a precise expression
  (not big-Omega) of the lower bound for the number of contests
  required in the worst case to determine which players are strong
  and which are weak.

  \part{b} Describe an algorithm called \emph{find-strong}
  to determine the strong players
  when $n=4$. Use the names $P_1, P_2, P_3, P_4$ for the four
  players, and the function
  $$contest\Big(\{first\_team\},\{second\_team\}\Big),$$
  which returns either ``first wins'', ``second wins'', or ``tie''.
  Your function should return a set or list of the strong players.

  Give an exact worst-case analysis of the number of contests required in
  your algorithm.
  For full marks, this should match exactly the lower bound from Part
  (a) when $n=4$.

  \part{c} Describe an algorithm to determine the
  strong and weak players, for any $n$. Use the names $P_1,P_2,\ldots,P_n$
  and the \emph{contest} subroutine from Part (b).
  Show that your algorithm is
  asymptotically optimal, meaning that the big-$O$ cost should match the
  lower bound from Part (a).
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tries [2+2+2=6 marks]} 
In this question, when drawing tries, follow the
convention that \$ is always to the left of 0, and 0 is always to
the left of 1.
\begin{enumerate}
\part{a}
Draw the standard trie on the following four strings (include edge
labels for clarity): 00001\$, 0010\$, 0011\$, 001\$.
\part{b}
Draw the compressed trie on the following four strings:
00001\$, 0010\$, 0011\$, 001\$.
\part{c} Draw the result of inserting 011\$ into your answer to part (b).

\end{enumerate}
\end{document}
