\documentclass{article}

\usepackage{fancyhdr}
\usepackage{float}
\usepacakge{multirow}
\usepacakge{rotating}

\pagestyle{fancy}
\lhead{CS 260}
\chead{Programming Assignment 1: Timing Data Analysis}
\rhead{Sean Barag}

\newcommand{\tbf}{\textbf{#1}}

\begin{document}
Programming assignment one required students to time various functions.  As all code for this assignment was written in Python, execution time was calculated via the \texttt{Timer} class within the \texttt{timeit} module.


\section{Lists}
Five operations (iterated insertion and deletion at the head and tail of the list, as well as traversal) were tested on each of three list implementations: Python's default list class, a custom array-based list, and a custom pointer-based list.  The results of timing for each combination of operation and list is shown in Table~\label{tab:listData}, below.
%
\begin{table}[H]
	\begin{tabular}{r|c|c|c|c|c|c|}
		\cline{2-7}
		&&
		\tbf{Head Insertion (\si{\micro\second})} &
		\tbf{Tail Insertion (\si{\micro\second})} &
		\tbf{Traversal (\si{\micro\second})} &
		\tbf{Head Deletion (\si{\micro\second})} &
		\tbf{Tail Deletion (\si{\micro\second})}\\ \cline{1-7}

		\multirow{3}{*}{\rotatebox{90}{\mbox{$n=10$}}} &
		\tbf{Python's List} &
			.3867 &
			.2235 &
			.1218 &
			.2250 &
			.1823\\ \cline{2-7}
		& \tbf{Array List} &
			1.703 &
			1.500 &
			1.371 &
			2.555 &
			2.087\\ \cline{2-7}
		& \tbf{Pointer List} &
			3.816 &
			16.146 &
			1.665 &
			.9760 &
			26.796\\ \cline{2-7} \cline{2-7}
			
		\multirow{3}{*}{\rotatebox{90}{\mbox{$n=100$}}} &
		\tbf{Python's List} &
			.4095 &
			.1396 &
			.0679 &
			.1591 &
			.1245\\ \cline{2-7}
		& \tbf{Array List} &
			2.839 &
			1.800 &
			1.775 &
			3.460 &
			2.425\\ \cline{2-7}
		& \tbf{Pointer List} &
			3.756 &
			79.602 &
			1.744 &
			.7416 &
			217.53\\ \cline{2-7} \cline{2-7}

		\multirow{3}{*}{\rotatebox{90}{\mbox{$n=1000$}}} &
		\tbf{Python's List} &
			1.576 &
			.1331 &
			.0643 &
			.3433 &
			.1161\\ \cline{2-7}
		& \tbf{Array List} &
			14.228 &
			7.474 &
			6.838 &
			13.445 &
			7.417\\ \cline{2-7}
		& \tbf{Pointer List} &
			4.167 &
			716.28 &
			1.719 &
			.4873 &
			2159.2\\ \cline{2-7}
	\end{tabular}
	\caption{Data recorded from testing of the various list implementations, as measured on an Intel Core2Duo with Python 2.7.2.2.}
	\label{tab:listData}
\end{table}
%
As is clearly visible, Python's default list implementation is the fastest in all cases, with a computational complexity of roughly $O(1)$.  Because the array implementation of lists uses Python's list at its base, it is the second fastest.  While it does not offer $O(1)$ computational complexity like its base structure, it still offeress complexity roughly equal to $O(n\log{n})$.  Head operations are the slowest in this case, as all of the data must be shifted in memory to accommodate the change in data size.  
The pointer implementation of lists is by far the slowest for tail insertion and deletion, whereas all other operations operations remain rather efficient, requiring roughly $O(1)$.  The complexity of tail operations in the linked list is the result of requiring multiple data comparisons for each node in the list while traversing through the entire list for each execution.  The opposite is true for all head insertions, as they require simply creating a node and pointing it towards the current head.

\section{Trees}
Trees were represented only in two ways, as Python does not provide a default implementation: one by storing each node's children in a pointer-based list, and the other by storing each node's left-most child and right sibling.  Full tree traversal for trees of degree three and varying height was tested for each implementation.
%
\begin{table}[H]
	\begin{tabular}{|c|c|c|c|}
		\tbf{Height} & \tbf{Total Nodes}
		\tbf{\rotatebox{90}{\mbox{List of Children (\si{\micro\second}) }}} &
		\tbf{\rotatebox{90}{\mbox{Left-most Child \& Right Sibling (\si{\micro\second}) }}} \\ \hline

		\tbf{0} & \tbf{1} &
			9.351 &
			1.175\\ \hline
		\tbf{1} & \tbf{4} &
			107.7 &
			4.517\\ \hline
		\tbf{2} & \tbf{13} &
			566.3 &
			16.68\\ \hline
		\tbf{3} & \tbf{40} &
			2108 &
			37.00\\ \hline
		\tbf{4} & \tbf{121} &
			6846 &
			340.2\\ \hline
	\end{tabular}
	\caption{Data recorded from traversal for two implementations of trees, as measured on an Intel Core2Duo using Python 2.7.2.2.}
	\label{tab:treeData}
\end{table}
%
The results of this testing data show that the implementation using a list of children is much less efficient to traverse than the left-most child and right sibling implementation.  This is directly related to the fact that a linked list is slower to traverse than a basic Python list, as the slower tree representation employs the former to store data, whereas the faster uses the latter.  The more complex implementation of trees appears to grow at $O(\log n)$, while the less complex seems to grow at $O(n\log n)$.

\section{Conclusions}
% ----- maybe do some conclusive stuff here, I guess.
\end{document}