%---------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{sat oct 22, 2016 at 11.59p}
\def\duelocation{via \href{https://gradescope.com/courses/4095}{gradescope}}
\def\hnumber{3}
\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/nguy{\~{\^{e}}}n \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}
\usepackage[T1]{fontenc}

\begin{document}
\handout
\begin{itemize}
\item The assignment is due at Gradescope on Saturday, October 22 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} Mashup\end{problem}
For simplicity, let $x$ and $y$
be {\em snippets of music} represented as strings over the alphabet of notes $\{A,B,C,\ldots,G\}$.
For example, $x=ABC$ and $y=ADEF$.   We say that $z$ is a
{\em loop} of $x$ if $z$ is a prefix of $x^k$ for some integer $k>0$.  For example,
$z=ABCABCA$ is a loop of $x$ since it is a prefix of $x^3 = ABCABCABC$.

A song $s$ is a {\em mashup} of loops $z$ and $w$ if it is an interleaving of $z$ and $w$.
For example, one mashup of the loops $z=ABCABCA$ and $w=ADEFADE$ could be $ABCADEABFADECA$. 
Given song $s$ and snippets (or hooks) of music $x,y$, devise an algorithm
that determines if $s$ is a mashup of loops of $x$ and $y$.  

Describe a dynamic programming solution to this problem as we have done in class by specifying a 
variable and then providing an equation that relates that variable to smaller instances of itself.
Describe an algorithm based on your equation from above.  Analyze the running time.



\begin{problem}{Chompo bar}\end{problem}
You are given an $n\times m$ chompo bar.  Your goal is to devise an algorithm $A$ that
takes as input $(n,m)$ and returns the minimal number of cuts needed to divide the bar 
into perfect squares of either 1x1, 2x2, 3x3, $\ldots$, $j$x$j$.  With each cut, you can split the bar
either horizontally or vertically. For example,  $A(2,3)=2$ because 2x3 $\rightarrow$ (2x2, 1x2) $\rightarrow$ (2x2, 1x1, 1x1).

\begin{enumerate}
	\item Notice that no matter the rectangle, it is always possible to make a perfect square in the first cut.
	Show that this strategy fails.  Namely, show an input size for which the strategy of picking the cut which creates the 
	largest box leads to extra cuts in total.
	\item Devise a DP algorithm which determines the minimal number of cuts.	
\end{enumerate}


\begin{problem}Lifeguards\end{problem}
You run the pool on Saturdays. There must always be a lifeguard on duty.  There are $n$ lifeguards who can work, but they are busy college students with complex social obligations; lifeguard $i$ can work starting at time $a_i$ and ending at time $b_i$ on Saturdays.  Your goal is to cover the entire day from 8a--8p \emph{using the fewest lifeguards as possible}.

The first idea that comes to mind is to start with an empty schedule, and then add the guard who covers \emph{the most amount of time that is not already covered}.  Show that this algorithm fails by providing a counter-example.

Devise and analyze a greedy algorithm that solves the problem in linear time.

\begin{problem}{ExpressEspresso}\end{problem}

Every morning, customers $1,\ldots,n$ show up to get their espresso drink.  Suppose the omniscient barista  knows all of the customers, and knows their orders, $o_1,\ldots,o_n$.   Some customers are nicer people; let 
$T_i$ be the barista's expected tip from customer $i$.  Some drinks  like a simple double-shot, are easy and fast, while some other orders, like a soy-milk latte take longer.   Let $t_i$ be the time it takes to make drink $o_i$.
Assume the barista  can make the drinks in any order that she wishes, and that she makes drinks back-to-back (without any breaks) until all orders are done.
Based on the order that she chooses to complete all drinks, 
let $D_i$ be the time that the barista finishes order $i$.  Devise an algorithm that helps the barista pick  a schedule that minimizes the
quantity $$ \sum_{i}^n T_i D_i$$
In other words, she wants to serve the high-tippers the fastest but she also wants to take into consideration the time it takes to make each drink.
(Hint: think about a property that is true about an optimal solution.)



\begin{problem}{Homework}\label{lastproblem}\end{problem}
College life is hard.  You are given $n$ assignments $a_1,\ldots,a_n$ in your courses.
Each assignment $a_i=(d_{i},t_{i})$ has a deadline $d_i$ when it is due and an estimated amount
of time it will take to complete, $t_i$.  You would like to get the most out of your
college education, and so you plan to finish all of your assignments.   Let us assume
that when you work on one assignment, you give it your full attention and do not work on
any other assignment.

In some cases, your outrageous professors demand too much of you.  It may not be possible to
finish all of your assignments on time given the deadlines $d_1,\ldots,d_n$; indeed, some assignments
may have to be turned in late.  Your goal as a sincere
college student is to minimize the lateness of any assignment.
If you start assignment $a_i$ at time $s_i$, you will finish at time $f_i=s_i + t_i$.  
The lateness value---denoted $\ell_i$---for $a_i$ is the value
$$ \ell_i = \left\{ \begin{array}{rl} f_i - d_i & \mbox{ if } f_i > d_i \\ 0 & \mbox{otherwise}\end{array}\right.$$
Devise a polynomial-time algorithm that computes a schedule $O$ that specifies the order in which you complete assignments which minimizes the maximum $\ell_i$ for all assignments, i.e.
$$
\min_O \max_i \ell_i
$$
In other words, you do not want to turn in {\em any} assignment {\em too} late, so you minimize the
lateness of the latest assignment you turn in.
Prove that your algorithm produces an optimal schedule. Analyze the running time of your algorithm.




\end{document}
