\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}

\title{CS140 - Assignment 3\\\small{Due: Sunday,  Feb. 12 at 8pm}}
\author{}
\date{}


\begin{document}
\maketitle

\begin{center}
\includegraphics[scale=0.6]{figures/proofs.jpg}

\footnotesize{http://www.smbc-comics.com/index.php?db=comics\&id=1099}
\end{center}


\begin{itemize}
\item You must work on this assignment with a partner, though it does not have to be within your learning group.  There are an odd number of people in the class right now, so I will allow one group of three, but you need to get permission from me first.
\item You must use \LaTeX $\;$ to format your solution.
\end{itemize}

\begin{enumerate}

\item \textbf{[4 points]} Give the asymptotic bounds for each of the recurrences below.  Assume that $T(n)$ is constant for sufficiently small $n$.  Make your bounds as tight as possible.  If you use the master method, you must specify $\Theta$ bounds, but only need to specify $O$ if you use another approach.

\begin{enumerate}

\item $T(n) = 3 T(n/2) + n \log n$

\item $T(n) = T(n - 2) + n$

\end{enumerate}

\newpage

\item \textbf{[5 points]} Algorithm $A$ has a running time described by the recurrence $T(n) = 7 T(n/2) + n^2$.  A competing algorithm $B$ has a running time described by the recurrence $T(n) = a T(n/4) + n^2$.  What is the largest integer value for $a$ such that $B$ is asymptotically faster than $A$?  Explain your answer.  (Hint: use the master method.)

\item \textbf{[7 points]} Halfsies 

In some situations, there is not a natural ordering to the data so we can't sort it, but we can check equality (e.g. images).  Given an array of elements $A$, we would like to determine if there exists a value that occurs in more than half of the entries of the array.  If so, return that value, otherwise, return $null$.  Assume you can only check equality of elements in the array which takes time $O(1)$.

Describe a divide-and-conquer algorithm whose running time is
  asymptotically better than $\Theta(n^{2})$.  Provide pseudocode
  and/or a clear English description of your algorithm and state the worst case running time of your solution (in terms of $\Theta$ or $O$ where appropriate) \emph{with justification}.
 
\item \textbf{[10 points]} Given a \emph{sorted} list of unique integers A[1...n], determine if an entry exists such that $A[i] = i$.  If an entry exists, return the index, otherwise, return $null$. (Hint: You can do better than $O(n)$.  Think divide-and-conquer.)  Write \textbf{pseudocode} to solve this problem and and \emph{state the worse case running time} (in terms of $\Theta$ or $O$ where appropriate).  You will be graded on the efficiency of your solutions.


\item \textbf{[25 points]} Stock Market Problem

  You're given an array of numbers representing a stock's prices over
  $n$ days.  You goal is to identify the longest consecutive number of
  days during which the stock's value does not decrease.  For example,
  consider the stock values below:
\begin{verbatim}
Day:      1   2   3   4   5   6   7   8
Value:    42  40  45  45  44  43  50  49
\end{verbatim}
In this example, the length of the longest consecutive non-decreasing 
run is 3.  This run goes from day 2 to day 4.  

\begin{enumerate}
\item Briefly describe 
  a very simple ``naive'' algorithm for this problem and explain
  why the worst-case running time is $\Theta(n^2)$.
\item Describe a divide-and-conquer algorithm whose running time is
  asymptotically better than $\Theta(n^{2})$.  Provide pseudocode
  and/or a clear English description of your algorithm.  (Note that
  your algorithm must be a divide-and-conquer algorithm.  And yes there
  are non-divide-and-conquer algorithms that are very, very good!)
  
  \emph{Hint:} Like writing recursive functions, when trying to come up with a divide-and-conquer solution, assume that your algorithm works
  correctly on the divided parts.  Then, how do you construct your answer to the overall solution?
\item Analyze the running time of your algorithm: what are tight
  bounds on the best and worst case behavior?
\end{enumerate}

(Note that next week's assignment will ask you to implement your divide-and-conquer algorithm.)

\end{enumerate}

\section*{Extra Credit}

\begin{itemize}

\item[] \textbf{[3 points]} Halfsies revisited

Here is another algorithm for solving the majority problem above (i.e, ``halfsies''):

\begin{verbatim}
repeat until a candidate majority element is found:
    If there are an odd number of elements, pick one element and see if 
    it's the majority.  If it is, mark it as the candidate majority and 
    exit the loop.  If not, remove that element and continue to next step.

    Randomly pair up elements.  If they're not equal, throw them both 
    away.  If they are equal, keep one of them. repeat.

Finally, check that the candidate majority element is a majority element 
in the entire array.  If it is, return it.  If not, return null.
\end{verbatim}

\begin{enumerate}

\item Give a brief justification (not a proof) for why this works.  It doesn't need to be more than a couple of sentences.

\item Write the recurrence for the worst case runtime of this algorithm.  Hint: consider two scenarios for the worst case: 1) all elements are identical or 2) n/2 + 1 of the items are identical and the rest are different.

\item What is the worst case runtime of this algorithm?

\end{enumerate}

\end{itemize}


\end{document}
