\documentclass[12pt]{article}
\usepackage{geometry}
\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012\\
	\rm
	Homework 1b\\
	Due Tuesday, January 24
\end{center}

\begin{itemize}
	\item Please use \LaTeX\ to typeset your solutions to this assignment.
	\item \large{\textbf{Please remember to submit each problem on a separate sheet of paper with your name on the top.}} \normalsize (If a problem requires multiple sheets, please staple them together).
	\item About bonus problems:  Please take a look at the bonus problems when they are given.  
	If you have the time and inclination, work on them!  Working on these problems will give you a deeper understanding
	of the material.  Moreover, the extra points on these problems are potentially substantial (bonus points have the same value as regular homework points).
\end{itemize}

\begin{enumerate}

	\item \textbf{[15 points]}  Indicate whether each of the following statements
is true or false and then carefully {\bf prove} your answer using the formal
definition of Big-Oh, Big-Omega, and Big-Theta notation and properties of logarithms from Homework
1a.  Remember that to show that one of these statements is false, you must
obtain a formal contradiction; it does not suffice to just say ``false''. 
\begin{enumerate}
        \item $2^{n+1} \in O(2^{n})$.
        \item $2^{2n} \in O(2^{n})$.
        \item $3 n^{2} \log_{2} n + 16 n \in O(n^{3})$.
        \item $25 \log_{2} 8n^{10} \in  O(\log_{10} n)$.
        \item $4^{\log_{2} n} \in O(n^{3})$.
        \item $5 n^2 + 42 \in \Omega(n)$.
        \item $6 n^3 + 26 n \in \Theta(n^3)$.
\end{enumerate}


\item \textbf{ [25 Points] Curly, Mo, and Larry's Totally Excellent (?) Sorting Algorithm!} Professors
Curly, Mo, and Larry of the Pasadena Institute of Technology
 have proposed the following sorting algorithm:
First sort the first two-thirds of the elements in the array. Next 
sort the last two thirds of the array.  
Finally, sort the first two thirds again.  (Notice that this
algorithm is similar to Mergesort except that it uses
three recursive calls rather than two and there is no merging step!  As a consequence, this algorithm is very easy to implement!)  The code is given below.  Notice that the floor function, $\lfloor x \rfloor$, simply
rounds down to the nearest integer.  This is just used to compute the appropriate two-thirds and 
round to an integer so that we don't use non-integer indices into our array!
\small
        \begin{tabbing}
        Stooge-sort ($A$,$i$,$j$) \\
        \textbf{begin}\\
        \ \ \ \ \ \= {\bf if} $A[i] > A[j]$ {\bf then} \\
                  \> \ \ \ \ \ {\bf swap} $A[i]$ and $A[j]$ \\
                  \> {\bf if} $i+1 \geq j$ {\bf then} \\
                  \> \ \ \ \ \ {\bf return} \\
                  \> $k = \lfloor (j-i+1)/3 \rfloor$. \\
                  \> Stooge-sort$(A,i,j-k)$ \ \ \ \ \ \= {\bf Comment:} Sort first two-thirds. \\
                  \> Stooge-sort$(A,i+k,j)$ \> {\bf Comment:} Sort last two-thirds.\\            
                  \> Stooge-sort$(A,i,j-k)$\> {\bf Comment:} Sort first two-thirds again! \\     
        \textbf{end}
        \end{tabbing}
\normalsize
        \begin{enumerate}

		\item Give an informal but convincing explanation (not a rigorous proof by induction) of why the 
		approach of sorting the first two-thirds of the array, then sorting the last two-thirds of the array,
		and then sorting again the first two-thirds of the array yields a sorted array.  A few well-chosen sentences should suffice here.
					
                \item Find a recurrence relation for the worst-case running time of Stooge-sort.  To simplify your recurrence relation, you may assume  each of the recursive calls is on a portion of the array that is \emph{exactly} two-thirds the length of the original array.

                \item Next, solve the recurrence relation using the 
                work tree method.  \textbf{Show all of your work.}   In your analysis, it will be 
                convenient to choose $n$ to be $c^{k}$ for some fixed
                constant $c$. (For example, we used $c=2$ when
                 analyzing Mergesort.  Here you will want to
                use a different value of $c$.  The value of $c$ that you choose might not even be an integer!  As we've seen in class, this is valid and allows us to significantly simplify the analysis!)
                                
		
                \item How does the worst-case running time of Stooge-Sort 
                compare with the worst-case running times of the other sorting algorithms that we've seen so far?


        \end{enumerate}
        
\item \textbf{[20 Points] Stock Ratings!}
A remarkable number of algorithms experts work on Wall Street and in other sectors of the finance industry.
Throughout this semester, we'll see a number of applications of algorithms to finance.

Here's the gratuitous backstory for this problem:
You've been hired as the Director of Algorithm Design by the brokerage
firm of Weil, Proffet, and Howe (WPH).  The firm specializes in rating stocks.
Their measure of the quality of a stock is the longest consecutive number 
of days in which the stock did not decrease in value.  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.  (In some cases there could be ties for the longest run, but that's OK!
We are only looking for the length of the longest run, not the actual run itself.)

Here are your tasks:
\begin{enumerate}
	\item Your predecessor at WPH proposed the following algorithm for stock rating:  Using a for loop, iterate through each element in the array.  For each such element, use another (nested) for loop to find the longest run from that point forward.  Keep track of the longest run that you've found and return that in the end.  Show that for some input, the algorithm can use $\Theta(n^2)$ running time.
	\item Next, use the divide-and-conquer paradigm to devise an algorithm whose running time is
	asymptotically better than $\Theta(n^{2})$.  Provide pseudo-code (the syntax is up to you, as long as
	it is clear to any computationally literate reader) or a very clear English description of your algorithm.  	(\emph{Note:  There are algorithms
	that are fast and do not use divide-and-conquer.  Please use divide-and-conquer here though!  That is, divide the array into two halves and use recursion on these two halves to help solve the problem.  There are several different divide-and-conquer algorithms for this problem.  Some are asymptotically
	faster than $n^2$ and some are asymptotically MUCH faster than $n^2$.  Any algorithm asymptotically
	faster than $n^2$ suffices here, but if you find an algorithm \textbf{and} can prove that your algorithm
	is asymptotically optimal, then you will receive 5 extra bonus points.  It's not too hard!  Try it!)}
	\item Assuming that $n$ is a power of $2$, give a  recurrence relation that describes the worst-case running 	time of your algorithm.
	\item Solve your recurrence relation -- using the work tree method that we've used in class -- to get a simple closed form for the running time of your algorithm and
	then give the asymptotic ($\Theta$ notation) running time.  Show your analysis in detail.  
	\tiny % Start using tiny font
	If you want to use a picture to help explain the running time, you may just leave some space in your  	document and draw it by 	hand or embed a figure that you've drawn in another tool.  Download the
	source for this document from the course website and read the embedded comments on how to 
	do all this in \LaTeX.
	\normalsize % Back to normal font size
	% To leave a vertical space in your document, use the command \vspace{3cm} or \vspace{2in} for
	% spacing 3 centimeters or 2 inches, respectively.  Of course, you can change those numbers to 
	% insert as much space as you wish.  To embed a figure drawn in another tool, draw your figure
	% and export it as a pdf.  Then, at the top of your document, right after the documentclass line,
	% include the command
	%\usepackage{graphicx}
	% Finally, wherever you wish to include your pdf file, let's call it myfigure.pdf for this example, use:
	% \begin{figure}
   	% \centering % Optional to center your figure
   	% \includegraphics[width=4in]{myfigure.pdf} % width is optional.  You can use height or nothing at all!
	% \caption{Check out this amazing figure!}  % caption is optional
	% \end{figure}
	\item Explain briefly why the asymptotic running time still holds even if $n$ is not a power of 2.
	\item Prove the correctness of your algorithm using mathematical induction.
\end{enumerate}

\item \textbf{[20 Point Optional Bonus Problem] Chip Testing!}
\emph{This is a fun and interesting problem!  It is highly recommended!}

Professor Chip Testor has $n$ supposedly identical computer chips that in principle are capable of testing each other. The professor's test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows:
\begin{verbatim}
Chip A says          Chip B says               Conclusion
------------         -------------             ------------

B is good             A is good                Both good, or both bad
B is good             A is bad                 At least one is bad
B is bad              A is good                At least one is bad
B is bad              A is bad                 At least one is bad
\end{verbatim}

\begin{enumerate}
	\item Consider the problem of finding a single good chip from among $n$ chips, assuming that more than $\frac{n}{2}$ of the chips are good. Show that $\lfloor \frac{n}{2} \rfloor$ pairwise tests are sufficient to reduce the problem to one of nearly half the size.  (You might find it convenient to begin by assuming that $n$ is even.   The case that $n$ is odd is just a bit more involved.)
	\item Using the result of part (a) above, show that the good chips can be identified with $\Theta(n)$ pairwise tests, assuming that more than $\frac{n}{2}$ of the chips are good.  Explain clearly why your algorithm identifies all of the good chips.  Then give and solve the recurrence that describes the number of tests.
\end{enumerate}

\end{enumerate}
\end{document}

