%% To students who wish to submit their homework in LaTeX format:
%%   Put your name(s) in the appropriate place.
%% Don't forget to include a statement with each problem indicating
%%   the contribution of each partner!

\documentclass[11pt]{article}

\newcommand{\NP}{\mbox{${\cal NP}$}}
\newcommand{\Poly}{\mbox{${\cal P}$}}

\usepackage{fullpage}

\newcommand{\solution}{\bigskip\hrule\bigskip}
\newcommand{\problembreak}{\bigskip\hrule\bigskip}

\begin{document}

\begin{center}
\Large CS4104 Fall 2010 Homework Assignment 11\\
Due at 11:00pm on Wednesday, November 10\\
50 Points
\end{center}
\vspace*{0.10in}
\medskip

\textbf{Pledge:
I (we) have not received unauthorized aid on this assignment.
I (we) understand the answers that I (we) have
submitted.
The answers submitted have not been directly copied from another
source, but instead are written in my (our) own words.}

\bigskip
%PutYourNameHere, PutYourIDNumberHere
%Put second name/ID here if there is one

\paragraph{1.}
[20 points]

Consider this algorithm for finding the maximum element in an array:
First sort the array and then select the last (maximum)
element.
What (if anything) does this reduction tell us about the upper and
lower bounds to the problem of finding the maximum element in a sequence?
Why can we not reduce SORTING to finding the maximum element?

\paragraph{2.}
[15 points]

Use a reduction to prove that multiplying two upper triangular
\(n \times n\) matrices is just as expensive (asymptotically) as
multiplying two arbitrary \(n \times n\) matrices.

\paragraph{3.}
[15 points]

Note that \Poly\ is the class of polynomial-time algorithms.
\begin{enumerate}
\item[(a)] If problem P isn't in \NP, is P not in \Poly?
\item[(b)] if problem P isn't in \Poly, is P not in \NP?
\end{enumerate}

\end{document}
