% -*- latex -*-
% FILE: "/home/evmik/jobs/wm/2012_fall_practical_computing_for_scientists/hw12/hw12.tex"
% LAST MODIFICATION: "Wed, 28 Nov 2012 14:31:00 -0500 (evmik)"
% (C) 2010 by Eugeniy Mikhailov, <evgmik@gmail.com>
% $Id:$
\documentclass[letter,12pt]{article}

%---------------------------------------------------------------
\usepackage{listings}
\usepackage{color}
\usepackage{fullpage}
%---------------------------------------------------------------

\begin{document}
\newcommand{\problem}[1]{%
	{\flushleft  \bf #1\\}
}
\newcommand{\hw}[1]{%
	\begin{center}
		\Large  \bf Homework #1%
	\end{center}%
}
\newcommand{\mat}[1]{% matlab code
{\color{blue}\texttt{#1}}%
}

%---------------------------------------------------------------
\hw{12 - optional}

General comments: 
\begin{itemize}
	\item For test cases use vector x generated with \texttt{rand(1,N)}
		where N number of elements in test vector. See more help
		about \texttt{rand}, but in short it fills matrix of
		specified size with random numbers in the range of 0 to 1.
		In our case this matrix is a vector since we specified its
		size as $1 \times N$.
	\item Try your sort  algorithms with reasonably small N (less  then 10) at
		first.  Then you can check that output is fine by yourself.
	\item Your sorting algorithm should sort in ascending order.
	\item Do not forget to run some test cases. 
\end{itemize}

\problem{Problem 1 (10 points)}
%---------------------------------------------------------------
Write your own implementation of the heap sort algorithm. Call it
'heapsort'.



\problem{Problem 4 (5 points)}
%---------------------------------------------------------------
For your algorithm 'heapsort' and 
Matlab built in 'sort'. Plot (on the same figure) their time of execution
vs number (N) of the elements of the input test vector. Do not forget to
label each curve, see \mat{legend} command. How is your algorithm
performing in comparison to Matlab's one?

\begin{itemize}
	\item N should span from 1 to 1000000 (at least 100 points).
	\item You may like \mat{loglog} plot presentation better.
	\item Hint. To find the execution time use tic and toc, see more
		help for them.  For example \\
		\texttt{tic; sort(xtest); toc} \\
		There is also a way to save execution time to a variable or
		array.
\end{itemize}

%---------------------------------------------------------------
\end{document}
%---------------------------------------------------------------