%%% Fall 2004, HMW 3
\documentclass[11pt]{article}
\usepackage{epsf}
\usepackage{pslatex}
\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\begin{document}
\thispagestyle{empty}
\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2004} \\[0.5cm]
{\large \bf Homework 3: Due by Wednesday October 6 2004} \\
\end{center}
{\large
\vspace*{2cm}\noindent
\begin{itemize}
\item This homework contains $4$ problems. They allow you to earn
$100$ points.
\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.
\item {\bf No late submissions will be accepted.}
\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).
\item For the first three problems an e-mail to the TA
should be sent that contains the code and the executable of
a (single) program that implements the solutions to the
problems as functions.
\item \textbf{Remote students} should send an e-mail of the
(typed) solutions to the TA independently of whether code
is required or not.
\end{itemize}
\vspace*{3cm}
Write your name here:\
\hrulefill
}
\setcounter{page}{0}
%----------------------------------------------------------------------
\newpage
\begin{itemize}
\item {\bf Problem \# 1\ \ [20 points]}. Consider the problem of
sorting $n$ integers stored in an array $A$ by first finding the
smallest element of $A$ and exchanging it with $A[1]$. Then find the
second smallest element of $A$, and exchange it with $A[2]$.
Continue in this manner for the first $n-1$ elements of $A$.
\textbf{(a)} Write both pseudo-code and a C++ program for this algorithm.
\textbf{(b)} What loop invariant does this algorithm maintain?
\textbf{(c)} Why does it need to run for only the first $n-1$
elements, rather than for all $n$ elements?
\textbf{(d)} Give the best-case and the worst-case running times of
this algorithm in $\Theta$ notation.
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [40 points]}.
Write the pseudo code and implement in C++ an
\emph{exponential time} algorithm for sorting an array of
$n$ integers, i.e., an algorithm that requires a number of
steps which is an exponential function of $n$.
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 3\ \ [20 points]}. Implement Merge-Sort in C++
using the C++ Standard Template Library.
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 4\ \ [30 points]}. Let $T_{MS}(n)$ be
the worst-case time complexity of Merge Sort. Prove that
$T_{MS}(n)$ is nondecreasing. (Hint: use strong induction.)
\end{itemize}
\end{document}