\documentclass[12pt]{article}
\usepackage[letterpaper, margin=1.2in]{geometry}
\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}

\usepackage{amsfonts,amsmath,amssymb,enumerate,enumitem}

% dot product
\usepackage{graphicx}

\makeatletter
\newcommand*\bigcdot{\mathpalette\bigcdot@{.5}}
\newcommand*\bigcdot@[2]{\mathbin{\vcenter{\hbox{\scalebox{#2}{$\m@th#1\bullet$}}}}}
\makeatother

\newcommand{\A}{\mathcal{A}}

% for plots
\usepackage{graphicx}
\graphicspath{ {./images/} }

% for textboxes
\usepackage{mdframed}

% for table
\usepackage{booktabs}

\DeclareMathOperator{\adj}{adj}
\DeclareMathOperator{\STP}{STP}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\mincover}{min-cover}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\vdeg}{deg}
\DeclareMathOperator{\nll}{null}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\range}{range}
\DeclareMathOperator{\proj}{proj}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\si}{si}
\DeclareMathOperator{\cl}{cl}

\DeclareMathOperator{\oc}{oc}

\usepackage{algpseudocode}
\usepackage[ruled, linesnumbered]{algorithm2e}

% absolute value
\usepackage{mathtools}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\DeclarePairedDelimiter\norm{\lVert}{\rVert}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclarePairedDelimiter\paren{\lparen}{\rparen}
\DeclarePairedDelimiter\of{\lparen}{\rparen}
\DeclarePairedDelimiter\br{\lbrack}{\rbrack}
\DeclarePairedDelimiter\ang{\langle}{\rangle}
\DeclarePairedDelimiter\cly{\lbrace}{\rbrace}
\DeclarePairedDelimiter\set{\lbrace}{\rbrace}

\usepackage{fancyvrb}

\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

% set notation
\usepackage{braket}

\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother

% for drawing trees
\usepackage{tikz}   	
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}

\usepackage{adjustbox}
% code
\usepackage{fancyvrb}

\renewcommand{\A}{\mathcal{A}}
\newcommand{\Z}{\mathcal{Z}}
\newcommand{\T}{\mathcal{T}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\odd}{\mathrm{odd}}
\newcommand{\even}{\mathrm{even}}
\renewcommand{\vec}{\mathbf}
\newcommand{\eps}{\epsilon}
\newcommand{\B}{\mathcal{B}}
\renewcommand{\Z}{\mathbb{Z}}

\usepackage{calc}

\setcounter{secnumdepth}{0}

% \usepackage{draftwatermark}
% % \SetWatermarkLightness{0.8}
% \SetWatermarkScale{4}

%%%% a few things that are needed for the data base, but mostly ignored here
\usepackage{ifthen} % for version control
\usepackage{todonotes}

\newenvironment{solution}
{
\begin{mdframed}[linewidth=2pt, linecolor=gray]
\color{blue} \textbf{Solution ideas.}
}
{
\end{mdframed}
}

\usepackage{soul}

\usepackage{multicol}

\begin{document}
\parindent=0pt
\setlength{\parskip}{0.5em}

\begin{mdframed}[linewidth=1pt]
CS240E W25 \hfill \textbf{Tutorial 5} \hfill Feb. 7
\end{mdframed}

\subsubsection{Overview}

\begin{multicols}{2}
\begin{itemize}
\item Skip lists
\item Splay Trees
\item Static Ordering for Biased Searches
\item Counting Trees
\end{itemize}
\end{multicols}

\noindent\rule{\textwidth}{0.5pt}

\subsubsection{Problems}

\textbf{Q1. Static Ordering.}

Let $A$ be an unordered array with $n$ distinct items $k_0, ..., k_{n-1}$. Give
an asymptotically tight ($\Theta$) bound on the expected access cost if you put 
$A$ in the optimal static order for the following probability distributions:

\begin{enumerate}
    \item $p_i = \frac{1}{n}$ for $0 \leq i \leq n-1$
    \item $p_i = \frac{1}{2^{i+1}}$, for $0 \leq i \leq n-2$, $p_{n-1} = 1 - 
    \sum_{i=0}^{n-2}p_i = \frac{1}{2^{n-1}}$
\end{enumerate}

\textbf{Q2. Splay Trees.}

Given the following splay tree $S$, calculate its potential using 
the potential function $$\Phi(i) := \sum_{v \in S}\log n_v^{(i)},$$
where $n_v^{(i)}$ is the number of nodes in the subtree rooted at $v$ after $i$ operations,
including $v$ itself. Insert the key 18. Calculate the new potential. Verify 
that the potential difference is less than $4 \log n - 2R + 2$, 
where $R$ is the number of rotations.

\begin{center}
\begin{tikzpicture}[level distance=32,scale=.7,
  every node/.style={font=\small,circle,draw,inner sep=2pt},
  level 1/.style={sibling distance=70pt},
  level 2/.style={sibling distance=70pt},
  level 3/.style={sibling distance=60pt},
  level 4/.style={sibling distance=30pt},
  every lower node part/.style={blue}]
\node (30) {20}
              child {node {10}
                      child {node {5}}
                      child {node {15}
                              child {node {12}}
                              child {node  {17}
                                      child {node {16}}
                                      child {node {19}}
                              }
                      }
              }
              child {node {25}};

\end{tikzpicture}
\end{center}

\textbf{Q3. Skip Lists.}

Insert the numbers 12, 11, 13, 10, and 20 into an empty skip-list using the sequence of coin flips HHTHTHTTHHHT (i.e., every time we go to do a coin flip we take the first item out of this list). Then delete the keys 13 and 20.

\textbf{Q4. Counting Trees.}

How many binary trees with $n$ nodes are there, as a formula in terms of $n$? Find a recurrence relation.

(There is also a closed-form for this recurrence relation, but deriving it is outside the scope of this course.)

\end{document}

