% -*- latex -*-
% FILE: "/home/evmik/jobs/wm/2011_fall_practical_computing_for_scientists/hw04/hw04.tex"
% LAST MODIFICATION: "Sun, 18 Sep 2011 19:01:28 -0400 (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{04}

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 All sorting algorithm should sort in ascending order unless
		mentioned otherwise.
	\item Do not forget to run some test cases. 
\end{itemize}

\problem{Problem 1 (5 points)}
%---------------------------------------------------------------
Write your own implementation of the bubble sort algorithm.
Call it 'bubblesort'.


\problem{Problem 2 (5 points)}
%---------------------------------------------------------------
Base on provided qsort implementation, write your own implementation of the qsort sort algorithm but the one which 
sort vector in the descending order. Call this function 'qsortDesc'.


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



\problem{Problem 4 (5 points)}
%---------------------------------------------------------------
For your algorithms 'bubblesort' and 'heapsort',  'qsortDesc', 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.

\begin{itemize}
	\item N should span from 1 to 10000 (at least 10 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; qsort(xtest); toc}
\end{itemize}


Which algorithm is better for a small N and which is for a large?

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