\documentclass{article}
\usepackage{listings}
\usepackage{syntax}
\usepackage[pdftex]{graphicx}
\usepackage[margin=1.28in]{geometry}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Java,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,    // added this
  tabsize=3
}

\title{CS2001: Foundations of Computation \\ Practical 10: Tree-Structured Sets \\ Practical Report} % Title

\author{130017962} % Author name

\date{\today} % Date for the report

\begin{document}

\maketitle % Insert the title, author and date

\section{Introduction}
The purpose of this practical was to practise implementing the binary search tree (BST) data-type by constructing one as the concrete base for a class that represents a set of integers. The specification requires for a union operation that merges two binary search trees in a time efficient manner, while maintaining BST properties in the output set. My implementation both meets and extends on these requirements and supports two other set operations - intersection and difference.

\section{Design}
\subsection{Binary Search Set}
My Set implementation can be found in \textbf{BinarySearchSet.java}, which holds a reference to a root instance of \textbf{Node.java}. The Node class is used to represent a node in a binary search tree - with references to left and right children, as well as a parent. I decided to reference parents since this allows for easier node removals. BinarySearchSet contains all of the required tree methods: add, remove and contains - all of which are implemented recursively in the Node class. The ``toList()'' method performs an in-order traversal of the search tree, adding each node to an integer ArrayList instance. This method is used to efficiently perform set operations.

\subsection{Union Operation}
The union set operation combines two sets while ignoring duplicates. The most obvious way to do this using BSTs would be to traverse the first tree and add each element to the second tree. However, while trivial, this algorithm has $O(n log(n))$ complexity, since $n$ elements have to be added, with addition being a $O(log(n))$ operation. My improved algorithm flattens each tree into a list ($O(n)$ time complexity) and merges the two sorted lists ($O(n + m)$ time complexity where $n$ and $m$ the lengths of the two lists. A new BST is recursively constructed from the merged list in $O(n)$ time. The total operation has $O(n + m)$ time complexity, which is more scalable than $O(n * log(m))$. Merging occurs in the ``mergeSortedLists'' method, which traverses both lists simultaneously and adds the lowest value between the two lists. This takes advantage of the fact that each list is already sorted.

\subsection{Intersection \& Difference Operations}
In order to extend on the specification requirements, I implemented the ``intersection'' and ``difference'' methods in BinarySearchSet, which return lists that contain elements seen in both lists and elements that are only seen in one of the lists, respectively. Both of these methods behave similarly to union(), with small implementation differences.

\subsection{Testing}
It was important to test my set implementation both to assert its correctness and to measure and and confirm its time complexity. The first was done using JUnit tests enclosed in TestSet.java. These test every feature implemented, such as ``testAdd'' - which tests inserting elements into the Set and ``testUnion'', which tests the union operation.

\subsection{Complexity Analysis}
In order to confirm that my implementation's time complexity matches theoretical values I created ``Analysis.java'', which times set operations using System.currentTimeMillis() and System.nanoTime(), and logs this data to the console. In order to plot the data, I pasted the console output into a file and plotted the results using octave. The first graph shows how the insert operation time varies with the number of elements in the set. It can be seen that this operation has an $O(log(n))$ complexity:

\begin{figure}[ht]

    \centering
    \includegraphics[width=0.95\textwidth]{time.png}
    \caption{\textit{Graph showing the complexity of the insert operation on the set}}
\end{figure}

\noindent The second graph shows the performance of the union, intersection and difference operations as a relationship between computation time and set size. It can clearly be seen that all three operations have an $O(n)$ time complexity. This is an improvement over the $O(n * log(n))$ that can be expected from a more trivial version of each algorithm.

\begin{figure}[ht]

    \centering
    \includegraphics[width=1\textwidth]{operations.png}
    \caption{\textit{Graph showing the run time of the union (blue), intersection (green) and difference (red) methods performed on arrays of increasing size}}
\end{figure}

\section{Evaluation}


\end{document}