%---------change this every homework
% place your email id between the braces so that your homework has a name
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{thu oct6, 2016 at 11.59p}
\def\duelocation{via \href{https://gradescope.com/courses/4095}{gradescope}}
\def\hnumber{2}
\def\course{\href{https://shelat.ccis.neu.edu/16f-4800}{cs4800 - algorithms - f'16}}
%-------------------------------------

\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02} 
\definecolor{cit}{rgb}{0.05,0.2,0.45} 
%\pagestyle{myheadings}
\markboth{\yourname}{\yourname}

\thispagestyle{empty}

\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
   \renewcommand{\thepage}{H\hnumber-\arabic{page}}
   \noindent
   \begin{center}
      \vbox{
    \hbox to \columnwidth {\sc{\course} --- shelat/nguyen \hfill}
    \vspace{-2mm}
    \hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
      }
   \end{center}
   \vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent\textbf{Solution:}#1}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\usepackage{clrscode}


\begin{document}
\handout
\begin{itemize}
\item The assignment is due at Gradescope on Thursday, October 6 at 11:59pm. Late assignments will not be accepted. Submit early and often.

\item You are permitted to study with friends and
      discuss the problems; however, {\em you must write up you own
        solutions, in your own words}. Do not submit anything you
        cannot explain. 
     If you do collaborate with any of the other students on any
      problem, please do list all your collaborators in your
      submission for each problem. 
      
      \item Finding solutions to homework problems on the web, or by asking
 students not enrolled in the class is strictly prohibited. 

\item We require that all homework submissions are prepared in Latex. If you need to draw any diagrams,
however, you may draw them with your hand.  Please use \emph{a new page to begin each answer.} 
\end{itemize}

\begin{problem}Flip-flop\end{problem}
 Consider the recurrence
$T(n) = 2T(n/2) + f(n)$ in which
$$f(n) = \left\{\begin{array}{ll} n^3 & \mbox{if $\lceil \log(n) \rceil$ is even} \\ n^2 & \mbox{otherwise}\end{array}\right.$$
Show that $f(n)=\Omega(n^{\log_b(a) +\epsilon})$. 
Explain why  the third case of the Master's theorem stated above does not apply.
 Prove a $\Theta$-bound for the  recurrence.

\newpage

\begin{problem}Why 5 in Median?\end{problem}
Recall the deterministic selection algorithm:
\begin{codebox}
\Procname{$\proc{Select}(A[1,\ldots,n], i)$}
\li Base case if $|A|<5$.
\li $p \gets \proc{MedianOfMedians}(A)$
\li $A_\ell,A_r,i_p \gets \proc{Partition}(A,p)$
\li \If $i_p=i$ \Return $A[i_p]$ 
\li \ElseIf $i_p<i$ \Return $\proc{Select}(A_r, i-i_p)$
\li \Else \Return $\proc{Select}(A_\ell,i_p-i)$ \End
\end{codebox}
\begin{codebox}
\Procname{$\proc{MedianOfMedians}(A[1\twodots n])$}
\li Divide $A$ into lists of 5 elements. If only one element, return it.\label{divideline}
\li Compute the median of each small list, store these medians in a new list $B$
\li $p\gets \proc{Select}(B,\lceil n/10 \rceil)$
\li \Return $p$
\end{codebox}
\begin{enumerate}
\item Suppose Line~\ref{divideline} of $\proc{MedianOfMedians}$
  divides $A$ into lists of 3 elements each instead of $5$ elements and
  line 3 is modified to pick the $\lceil n/6 \rceil$\textsuperscript{th} element.
  State an upper and lower bound on the size of $A_{\ell}$.  Be as precise as you can.
  
\item Show a lower-bound for the running time of $\proc{Select}$ under the 3-element version of 
$\proc{MedianOfMedians}$.
\end{enumerate}

\newpage


\begin{problem}{Planet Laser}\end{problem}

The NASA Near Earth Object Program  lists potential future Earth impact events that the JPL Sentry System has detected based on currently available observations.   Sentry is a highly automated collision monitoring system that continually scans the most current asteroid catalog for possibilities of future impact with Earth over the next 100 years. 

This system allows us to predict that $i$ years from now, there will be $x_i$ tons of asteroid material that has near-Earth trajectories.  In the mean time, we can build a space laser that can blast asteroids.  However,  each laser blast will require \emph{exajoules} of energy, and so there will need to be a recharge period on the order of \emph{years} between each use of the laser.  The longer the recharge period, the stronger the laser blast; e.g. after $j$ years of charging, the laser will have enough power to obliterate $d_j$ tons of asteroid material.  This problem explores the best way to use such a laser.

The input to the algorithm consists of the vectors $(x_1,\ldots,x_n)$ and $(d_1,\ldots,d_n)$ representing the incoming asteroid material in years $1$ to $n$, and the power of the laser $d_i$ if it charges for $i$ years.  The output consists of the optimal schedule for firing the laser which obliterates the most material.

\paragraph{Example} Suppose $(x_1,x_2,x_3,x_4)=(1,10,10,1)$ and $(d_1,d_2,d_3,d_4) = (1,2,4,8)$.  
The best solution is to fire the laser at times $3,4$ in order to blast $5$ tons of asteroids.

\begin{enumerate}
\item[(a)] Construct an instance of the problem on which  the following ``greedy" algorithm returns
 the wrong answer:
 \begin{codebox}
\Procname{$\proc{BadLaser}((x_1,\ldots,x_n),(d_1,\ldots,d_n))$}
\li Compute the smallest $j$ such that $d_j\geq x_n$. Set $j=n$ if no such $j$ exists.
\li Shoot the laser at time $n$.
\li \If $n>j$ then $\proc{BadLaser}( (x_1,\ldots,x_{n-j}),(d_1,\ldots,d_{n-j}))$.
\end{codebox}
Intuitively, the algorithm figures out how many years ($j$) are needed to blast all the material in the last time slot.  It shoots during that last time slot, and then accounts for the $j$ years required to recharge for that last slot, and recursively considers the best solution for the smaller problem of size $n-j$.
\item[(b)]
Given an array holding $x_i$ and $d_i$, devise an algorithm that blasts the most asteroid material.  Analyze the running time of your solution.\end{enumerate}

\newpage


\begin{problem}{Price Run}\end{problem}
Given a list of closing stock ticker prices $p_1,p_2,\ldots,p_n$, devise an $O(n^2)$ algorithm that finds
 the longest (not necessarily consecutive) streak of prices  that  increase or stays the same. 
For example, given the prices $2,5,2,6,3,3,6,7,4,5$, there is the streak $2,5,6,6,7$ of prices that increase or stay the same, but an even longer streak is $2,2,3,3,4,5$.

(Challenge: by using both dynamic programming and binary search, you can solve this problem in $O(n \log n)$ time.)


\newpage


\begin{problem}{Tug of War}\end{problem}
We want to play {\em roughly fair} tug of war in cs4800.  
You are given an array that holds the weights of $n$ people in the class  $W=(w_1,w_2,\ldots,w_n)$.  Your goal is to divide the $n$ people into two teams such that the total weight of the two teams is equal or as close as possible to equal.  Describe such an algorithm and give its running time.  The total number of people on each team should differ by at most $1$.  Assume that $M$ is the maximum weight of a person, i.e., $\forall i, w_i\leq M$.   The running time should be $O(n^3M)$.  The output should be the list of people on each team and the difference in weight between the teams.

\begin{problem}Programming Tug of War\end{problem}

In this part, you will implement your algorithm for Tug of War and test it on real data. Register and take on the
challenge at \url{https://www.hackerrank.com/contests/cs4800f16}



\end{document}
