\documentclass[12pt]{article}
\usepackage{fullpage}
\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{0.8in}
\newcommand{\Header}[1]{\begin{center} {\Large\bf #1} \end{center}}
\newcommand{\header}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\orr}{\vee}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{1ex}
\newcommand{\andd}{\wedge}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\inv}[1]{\frac{1}{#1}}
\newcommand{\prob}{{\bf Prob}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mathqed}{\mbox{\ \ \ \rule{6pt}{7pt}}}
\newcommand{\D}{{\cal D}}
\renewcommand{\Pr}{{\bf Pr}}
\newcommand{\pair}[1]{\langle #1 \rangle}
\newcommand{\mod}{\bmod}
\newcommand{\proof}{{\em Proof. }}
\newcommand{\E}{{\bf E}}
\newcommand{\comment}[1]{}
\newcommand{\bigcenter}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\ceiling}[1]{\left\lceil #1 \right\rceil }
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor }

\addtolength{\textheight}{0.3in}
\begin{document}
\header{15-451 Algorithms, Fall 2011}
{\bf Homework \# 1} \hfill {\bf Due: September 13, 2011}

\medskip

\hrule

\medskip
Please hand in each problem on a separate sheet and put
your {\bf name} and {\bf recitation} (time or letter) at the top of
each page.  You will be handing each problem into a separate box in lecture,
and we will then give homeworks back in recitation.

Remember: written homeworks are to be done {\em individually}.  Group work is only
for the oral-presentation assignments.

\medskip

\hrule
\medskip
{\bf Problems:}
\begin{enumerate}
\item[(25 pts) 1.] {\bf Recurrences.}  Solve the following recurrences, giving your
answer in $\Theta$ notation.  For each of them, assume the base case
$T(x) = 1$ for $x \leq 10$. Show your work.
\begin{enumerate}
\item $T(n) = T(n-2) + n^4$.

\item $T(n) = 3T(n/4) + n$.

\item $T(n) = 5T(n-2)$.

\item $T(n) = \sqrt{n}\:T(\sqrt{n}) + n$.  (E.g., we might get this from
a divide-and-conquer procedure that uses linear time to break the
problem into $\sqrt{n}$ pieces of size $\sqrt{n}$ each.  Hint: write
out the recursion tree.)
\end{enumerate}

\item[(25 pts) 2.] {\bf Recurrences and proofs by induction.}  Consider the
following recurrence:
\begin{eqnarray*}
T(n) & = & 2T(n/2) + n\lg n.
\end{eqnarray*}
Let's use a base-case of $T(2)=2$ and let's assume $n$ is a
power of 2.  We would like you to solve this recurrence using the ``guess
and prove by induction'' method. 
\begin{enumerate}
\item Try to prove by induction that $T(n) \leq cn\lg n$.
In other words, assume inductively that $T(n') \leq cn'\lg n'$ for all
$n'<n$ and try to show it holds for $n$. This guess is {\em incorrect} and so your proof should {\em fail}.
(If your proof succeeds, then there is a problem!!)  Point out where
this proof fails.  
\item Use the way the above proof failed to suggest a better
guess $g(n)$.  Explain why you chose this guess and prove by induction
that $T(n) \leq g(n)$ as desired.
\item Now give a proof by induction to show that $T(n) \geq c'g(n)$
where $c'>0$ is some constant and $g(n)$ is your guess from (b).
Combining this with (b), this implies that $T(n) = \Theta(g(n))$. 
\end{enumerate}

\item[(10 pts) 3.] {\bf Probability and expectation.}
An {\em inversion} in an array $A = [a_1, a_2, \ldots, a_n]$ is a pair
$(a_i,a_j)$ such that $i<j$ but $a_i>a_j$.  For example, in the array
$[4,2,5,3]$ there are three inversions.  A sorted array has no
inversions, and more generally, the number of inversions is a measure
of how ``well-sorted'' an array is.  
\begin{enumerate}
\item What is the {\em expected} number of inversions in a random array
of $n$ elements?   By ``random array'' we mean a random permutation of
$n$ distinct elements $a_1, \ldots, a_n$.  
Show your work.  Hint: use linearity of expectation.

\item It turns out that the number of comparisons made by the
Insertion-Sort sorting algorithm is between $I$ 
and $n+I-1$, where $I$ is the number of inversions in the array. Given
this fact, what does your answer to part (a) say about the
average-case running time of Insertion Sort (in $\Theta$ notation)?
\end{enumerate}

\newcommand{\one}{{\sf one}}
\newcommand{\two}{{\sf two}}
\item[(40 pts) 4.] {\bf Sorting and matrix games.} [Note: parts (c) and (d)
are the harder ones]

Al Gorithm wants to optimize some code for sorting arrays of
size 3, since it is in the inner loop of a climate modeling system.
Using quicksort, given an array $A=[a,b,c]$, the code will
choose one element as the pivot and compare it to the other two.  If
it was lucky and the pivot was between the other two (e.g., it chose
$a$ and we had $b < a < c$) then it is done.  Otherwise, it needs to
make one more comparison (between the non-pivots) to finish sorting.

In order to precisely describe what is going on, Al writes down a matrix
with the rows corresponding to different pivot choices, columns
corresponding to different possible locations for the middle (median)
element, and filling in the matrix with the total number of
comparisons used by that choice of pivot in that situation.
Specifically, the matrix is as follows:

$$\mbox{Pivot choice}  \begin{array}{l}\mbox{Median element is}\\
\begin{array}{r|rrr|} 
  & a & b & c \\ \hline
a & 2 & 3 & 3 \\
b & 3 & 2 & 3 \\
c & 3 & 3 & 2 \\ \hline
\end{array}\\ \\ \\
\end{array}
\!\!\!\!\!\!\!\leftarrow \mbox{ total cost for sorting (\# comparisons)}
$$

\begin{enumerate}
\item Suppose that based on how these arrays are generated, Al believes
there is a 25\% chance element $a$ will be the median, a 30\% chance
element $b$ will be the median, and a 45\% chance element $c$ will be
the median.  In that case, what is the best pivot to use and what
is the expected cost for sorting using that pivot?

\item Suppose that Al suspects that these arrays are being generated
by his nemesis Doc Chiney.  Because of this, Al decides to randomize.
\begin{enumerate}
\item With what probabilities should Al choose pivots $a$, $b$, and $c$ so
that no matter what ordering Doc selects, Al's expected sorting cost is
as small as possible? (I.e., Al wants $$\textstyle\max_{\rm
Doc's~choices}\E_{\rm Al's~choices}[\mbox{sorting cost}]$$ to be as small as possible).
\item What is the expected cost under this distribution?
\end{enumerate}

\item Suppose that Al's processor has special features that result in
the following improved matrix (the only change is the upper-left-corner):
$$\mbox{Pivot choice}  \begin{array}{l}\mbox{Median element is}\\
\begin{array}{r|rrr|} 
  & a & b & c \\ \hline
a & 1 & 3 & 3 \\
b & 3 & 2 & 3 \\
c & 3 & 3 & 2 \\ \hline
\end{array}
\end{array}
\!\!\!\!\!\!\!\leftarrow \mbox{ total cost with Al's special processor}
$$


\begin{enumerate}
\item {\em Now} what probabilities should Al use for pivots $a$, $b$, and
$c$ so that the worst-case expected cost ($\max_{\rm Doc's~choices}\E_{\rm
Al's~choices}[\mbox{sorting cost}]$) is as small as possible?

Hint:
by symmetry, you can assume Al's probabilities on $b$ and $c$ are
equal.  So, for some value $p$, Al has probability $p$ on $b$, $p$ on
$c$, and $1-2p$ on $a$.\\
\item And what {\em is} Al's expected cost when using
those probabilities?\\
\item Was there anything unexpected about the probabilities you
came up with in part (c)i?  [There is no right or wrong answer here -
but was your intuition that $a$ should have higher or
lower probability than $b$ and $c$?]\\
\end{enumerate}
\item Considering the matrix in part (c) above, suppose now {\em Doc} is
going to probabilistically decide which element to make the median.
\begin{enumerate}
\item What probabilities should Doc use so that no matter which pivot
Al picks, Al's expected cost is as {\em high} as possible?
(Formally, $$\textstyle\min_{\rm Al's~choices}\E_{\rm
Doc's~choices}[\mbox{sorting cost}]$$ is as high as possible?)\\
\item And what is Al's expected cost in this case?
\end{enumerate}
\end{enumerate}
The above is an example of something called a ``matrix game'' or a
``2-player zero-sum game'' between players Al and Doc.  If
you did this correctly, the values you computed in parts c(ii) and
d(ii) should be identical.  The fact that they are identical is a case
of von Neumann's minimax theorem (which we will discuss later in the
course), and this value is called the {\em 
value} of the game.  In class, when we talk about giving ``upper
bounds'' and ``lower bounds'' for a problem like sorting, we are
really talking about upper and lower bounds on the value of the
associated game. An upper bound of $O(n \log n)$ means we have an
algorithm that guarantees expected cost $O(n \log n)$ no matter what
input it is given.  A lower bound of $\Omega(n \log n)$ means that no
algorithm can do better, which we typically will show by giving an
adversarial probability distribution on inputs (an ``algorithm for
Doc'') that is bad for all algorithms.

Also note that while in the case of $n=3$ we have been examining, we
are talking very small differences in performance between the various
options,  as we saw in class the gap becomes quite
substantial for large values of $n$.  E.g., using the first element as
pivot has a worst-case of $\Omega(n^2)$, whereas randomizing over
pivots guarantees any input has expected cost $O(n \log n)$.

\end{enumerate}
\end{document}