From f9832050dd30d8e96dc0ea947645758668adae67 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Tue, 3 Nov 2015 14:27:10 +0100 Subject: Assignment 8 --- assignment8.tex | 196 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+) create mode 100644 assignment8.tex (limited to 'assignment8.tex') diff --git a/assignment8.tex b/assignment8.tex new file mode 100644 index 0000000..ecb8915 --- /dev/null +++ b/assignment8.tex @@ -0,0 +1,196 @@ +\documentclass[10pt,a4paper]{article} + +\usepackage[margin=2cm,top=1cm]{geometry} +\usepackage{multicol} + +\let\assignment8 + +\usepackage{enumitem} +\setenumerate[1]{label=\assignment.\arabic*.} +\setenumerate[2]{label=\textit{\alph*})} + +% textcomp package is not available everywhere, and we only need the Copyright symbol +% taken from http://tex.stackexchange.com/a/1677/23992 +\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}} + +\usepackage{fancyhdr} +\renewcommand{\headrulewidth}{0pt} +\renewcommand{\footrulewidth}{0pt} +\fancyhead{} +\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps} +\pagestyle{fancy} + +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage{amsfonts} +\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} + +\usepackage{array} +\usepackage{caption,subcaption} +\usepackage[hidelinks]{hyperref} +\usepackage{url} + +\usepackage{tikz} +% http://tex.stackexchange.com/a/122257/23992 +\tikzset{every picture/.style={font issue=\footnotesize}, + font issue/.style={execute at begin picture={#1\selectfont}} +} +\tikzstyle{b}=[text=black,circle,draw] +\tikzstyle{r}=[text=red,circle,draw] +\tikzstyle{new}=[text=cyan,circle,draw] + +\parindent0pt + +\title{Algoritmen en Datastructuren - assignment \assignment} +\author{Camil Staps\\\small{s4498062}} + +\begin{document} + +\maketitle +\thispagestyle{fancy} + +\begin{multicols}{2} + +\begin{enumerate} + \item \begin{enumerate} + \item We take the middle of the haystack. If we find the needle there, we can terminate (this is correct). If the middle is higher than the needle, we know that everything in the upper part of the haystack is higher, so we can repeat with the lower half of the haystack. Similarly for the lower and upper half. So, also these two \texttt{return}s are correct. If the length of the haystack is $0$, the needle cannot be in the haystack, so we return $0$ (also this is correct). + + \item Best case: needle is the middle of the haystack. + + Worst case: needle is for example at the very beginning or very end of the haystack; then we need to lower the search part size to $1$ before finding the needle. + + \item $T(n)=\pazocal O(1)$ in the case that \texttt{A[m] == x} or \texttt{l > r}; there is no recursion in these cases and checks and array access takes constant time. In all other cases, we have the recurrence $T(n)=\pazocal O(1) + T(n/2)$, since we half the size of the search part. + + Running time, best case: $\pazocal O(1)$; since checks and array access takes constant time. + + Running time, worst case: $\pazocal O(\ln n)$, since we need to execute the function at most $\log_2n$ times, and the non-recursive part of the function takes $\pazocal O(n)$. + \end{enumerate} + + \item See \autoref{fig:8.2}. + + \begin{figure*} + \centering + \begin{tikzpicture}[level 1/.style={sibling distance=60mm}, + level 2/.style={sibling distance=30mm}, + level 3/.style={sibling distance=15mm}, + level 4/.style={sibling distance=8mm}, + level distance=8mm] + \node[b] {26} + child { node[r] {17} + child { node[b] {14} + child { node[r] {10} + child { node[b] {7} + child { node[r] {3} } + child[missing] {} + } + child { node[b] {12} } + } + child { node[b] {16} + child { node[r] {15} } + child[missing] {} + } + } + child { node[b] {21} + child { node[b] {19} + child[missing] {} + child { node[r] {20} } + } + child { node[b] {23} } + } + } + child { node[b] {41} + child { node[r] {30} + child { node[b] {28} } + child { node[b] {38} + child { node[r] {35} + child[missing] {} + child { node[new] {36} } + } + child { node[r] {39} } + } + } + child { node[b] {47} } + }; + \end{tikzpicture} + \caption{The tree of exercise 8.2, after inserting $36$.} + \label{fig:8.2} + \end{figure*} + + If the inserted node were red, this tree wouldn't be a red-black tree. The property that the children of a red node are black is violated, because $35$ is red, but has a red child: $36$. + + In the inserted node were black, this tree wouldn't be a red-black tree either. The property that all paths from every node to its descendant leaves have the same number of black nodes is violated. For example, the path $38\leadsto39$ has one black node (or zero, depending on how you count), but $38\leadsto36$ two (or one). + + \item The largest possible number: we add red nodes wherever possible: on every second level we only put red nodes. This gives us red levels with node counts $2,8,32,128,\dots$. For black height $k=1$ we have therefore $2$ red nodes, plus the root node, is $3$ internal nodes. For $k=2$ we have $2+8=10$ red nodes, and $1+4=5$ black nodes, in total $15$ internal nodes. This suggests a largest possible number of internal nodes of $2^{2k}-1$. + + The smallest possible number is the number of internal nodes of a tree with black-height $k$ and no red nodes. We then need $1$ node as root node, $2$ on the first level, $4$ on the second level, etc. The $k$\textsuperscript{th} level has no internal nodes. Therefore, we would have at least $2^k-1$ internal nodes in a red-black tree with black-height $k$. + + \item See \autoref{fig:8.4}. + + \begin{figure*} + \centering + \begin{subfigure}[b]{.32\textwidth} + \centering + \begin{tikzpicture} + \node[b] {27} + child { node[r] {19} + child { node[b] {15} + child { node[r] {5} } + child[missing] + } + child { node[b] {20} } + } + child { node[b] {32} + }; + \end{tikzpicture} + \caption{Insertion (32, 27, 20, 15, 19 and 5)} + \label{fig:8.4:insertion} + \end{subfigure} + \begin{subfigure}[b]{.32\textwidth} + \centering + \begin{tikzpicture} + \node[b] {27} + child { node[r] {5} + child { node[b] {15} } + child { node[b] {20} } + } + child { node[b] {32} + }; + \end{tikzpicture} + \caption{Deletion of 19} + \label{fig:8.4:deletion-19} + \end{subfigure} + \begin{subfigure}[b]{.32\textwidth} + \centering + \begin{tikzpicture} + \node[b] {5} + child { node[b] {15} } + child { node[b] {27} + child { node[r] {20} } + child[missing] + }; + \end{tikzpicture} + \caption{Deletion of 32} + \label{fig:8.4:deletion-32} + \end{subfigure} + \caption{Insertion and deletion into an initially empty red-black tree.} + \label{fig:8.4} + \end{figure*} + + \item When going down the tree to find the right position for the to be inserted node, we see all the ancestors that we're going to need. Hence, we may just store them temporarily in a list for the duration of the insertion operation. This storage can be implemented using a simple stack, so the running time will still be $\pazocal O(\ln n)$. + + \item \begin{proof} + Right-rotation does not introduce left neighbours. The right-rotation of a node with a left neighbour will decrease the number of left neighbours in the tree by one. Any tree with $n$ nodes has at most $n-1$ left neighbours (every node can be at most one left neighbour, and the root node cannot be a left neighbour). Therefore, we need at most $n-1$ right-rotations to transform any tree into a tree without left neighbours, that is, with only right neighbours. So, this takes $\pazocal O(n)$. + + Right-rotation has an inverse: $$\text{Left-rotate}(\text{Right-rotate}(T,x), \text{left}(x)) = T.$$ + + Therefore, we may invert the above procedure to build any tree from a right-neighbours-only tree in $\pazocal O(n)$. + + By chaining the inverse procedure and the procedure itself, we may transform any tree into any tree with $\pazocal O(n)+\pazocal O(n)=\pazocal O(n)$ rotations (concretely, at most $2(n-1)$). + \end{proof} + +\end{enumerate} + +\end{multicols} + +\end{document} + -- cgit v1.2.3