%---------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{wed dec 7, 2016 at 11.59p}
\def\duelocation{via \href{https://gradescope.com/courses/4095}{gradescope}}
\def\hnumber{6}
\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[T1]{fontenc}
\usepackage{tikz}

\begin{document}
\handout
\begin{itemize}
\item The assignment is due at Gradescope on \textsc{\duedate}. 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}Flood Protection\end{problem}
You are in charge of the coastal flood prevention system for the corp of engineers.  You have currently deployed  large sandbags at coordinates $(x_1,y_1),(x_2,y_2),.\ldots,(x_n,y_n)$.  Your flood models for winter storms, however, show that these locations are not optimal.  Instead, it would be better to deploy these bags at positions $(x'_1,y'_1),\ldots,(x'_n,y'_n)$.  Your team has only one bulldozer to reconfigure the sandbags and your bulldozer can move each bag one unit of distance in 1 hour.  Formulate a linear program to compute the minimum amount of time it will take to reconfigure the sandbags.
\begin{figure}[h]
\centering\begin{tikzpicture}
\draw[step=0.5cm,gray,very thin] (0,0) grid (12,3.5);
\foreach \Point in {(0.3,2), (1.8,1), (3.1,2.2), (1.0,1.4), (7.4,0.4), (0.4,1.6), (9.1,2.4), (7.2,1.5), (11.3,1.2)}{
    \node at \Point {\textbullet};
}

\foreach \Point in {(0.25,1), (5,2), (10,3), (9,1.1), (6,2.8), (11,0.5), (6.5,2.2), (2,3), (4,1.4), (7,1.9)}{
    \node at \Point {$\circ$};
}

\end{tikzpicture}
\caption{Example instance of the problem. The filled dots are the original locations, and the unfilled  are the desired locations}
\end{figure}

\begin{problem}$k$ experts\end{problem}
Suppose that your team includes $k$ experts who are equally good at prediction (i.e., make roughly the same number of errors over period $T$).   In this case, we should expect better resulst.  For the deterministic or randomized strategy update rule, for $\epsilon<\frac{1}{2}$, show that 
	$$ M^{(T)} \leq 2(1+\epsilon)m_i^{(T)} + (2/\epsilon)\ln(n/k)$$
(You can also derive a better bound by analyzing the randomized version of the multiplicative update rule.)


\begin{problem}Pattern matching with 1 don't care\end{problem}
In class, we discussed a method for finding all occurrences of a pattern $p$ of length $m$ within a corpus of length $m$ in time $O(n+m)$.  Suppose that the pattern $p$ has one $\star$ symbol which is interpreted as a \emph{don't care} symbol, i.e., the symbol $\star$ matches any character of the alphabet. For example, if $p=a\star b$, then $p$ matches $adb$ as well as $azb$.  Devise an algorithm which finds all occurrences of a pattern $p$ that includes at most one \emph{don't care} symbol in a corpus of length $m$ in time $O(n+m)$.

(In general, when both $p$ and the corpus can have an arbitrary number of don't care symbols, then one can use the FFT algorithm to find all occurrences of $p$ in the corpus in time $O(n\log m$).)



\end{document}
