\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS5800}{Algorithms}{Spring 2011}{29 January 2011}{4}

\begin{center}
\Large{\bf Problem Set 2 (due Wednesday, February 9)}
\end{center}

{\bf 1. (3 + 3 + 4 = 10 points) Digital signatures}

Problem 1.45 parts (b), (c), and (d) of text.

{\bf 2. (10 points) Optimal location of store}

You are a new player in the mobile phone business and are planning to
open a physical store in Manhattan, to rival Apple's well-established
store there.  You want to determine an optimal location to place the
store.  Manhattan is organized as a grid, and a simple model is to
view it as an $m \times n$ grid consisting of points $(i,j)$, $1 \le i
\le m$ and $1 \le j \le n$.  Each of the $mn$ points constitutes both
a potential location for the store as well as a neighborhood of homes.
The distance between two points $(a,b)$ and $(c,d)$ in Manhattan --
$D((a,b), (c,d))$ -- is simply $|a-c| + |b-d|$.  For example, the
distance between $(5,3)$ and $(2,9)$ = $|5-2| + |3-9| = 9$.

After a detailed survey, you have found out which of the $mn$
neighborhoods are really potential customers -- so you have a set $C$
of potential customers:

\[C = \{(i,j): 1 \le i \le m, 1 \le j \le n, \mbox{ neighborhood at }
(i,j) \mbox{ is a potential customer}\}.\]

For example, the set $C$ could be $\{(1,4), (1,5), (1, 8), (2, 4), (3,
5), (6, 7), (2,9)\}$.  Since you have only one store to build, you
would like to locate it at a point that minimizes the total distance
from all the potential customers.  That is, you want to find $(x,y)$
in the grid that minimizes
\[
\sum_{(i,j) \in C} D((i,j), (x,y)).
\]

Give an efficient algorithm that takes as input the $m \times n$ grid
and the set $C$, and returns the optimal store location $(x,y)$.  

{\bf 3. (10 points) Optimizing a stock sale, in hindsight}

You are working for an investment firm that prides on its analysis of
the past to maximize future revenues.  One of the problems you
repeatedly face is the following.  You know the price of a particular
stock for each of the last $n$ days; let us number these days $1$,
$2$, \ldots, $n$.  Suppose during this time period, you wanted to buy
100 shares on some day and sell all the shares on some later day
(within the time period).  Then, which day would you have bought and
which day would you have sold?  For instance, suppose that $n$ was 10,
and the stock price data you had was the following.

\[
10, 11, 13, 16, 12, 8, 3, 7, 10, 9.
\]

Your optimal strategy would have been to buy on day 7 and sell on day
9.

Give an efficient (polynomial-time) algorithm that solves the above
problem.  Analyze the worst-case running time of the algorithm.

{\bf 4. (3 + 4 + 3 = 10 points) Finding good gadgets using pairwise
  testing}

You have $n$ supposedly identical gadgets that in principle can test
each other.  For instance, you can connect two gadgets A and B, each
of which then reports whether the other gadget is good or bad, but the
answer of a bad gadget cannot be trusted.  Thus, there are four
possible outcomes of such a pairwise test.

\begin{tabular}{lll}
Gadget A says & Gadget B says & Conclusion\\ \hline
B is good & A is good & both are good, or both are 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{tabular}

You are told that more than $n/2$ of the gadgets are good, and you are
asked to determine all of the good gadgets.

\begin{itemize}
\item[{\bf (a)}] Consider the problem of finding a single good
  gadget.  Show that $\lfloor n/2 \rfloor$ pairwise tests  are
  sufficient to reduce the problem to one of nearly half the size.

\item[{\bf (b)}] Using part (a), give a divide-and-conquer algorithm
  to find a single good chip using $\Theta(n)$ pairwise tests.  Give
  and solve the recurrence that describes the number of tests.

\item[{\bf (c)}] Using part (c), show that all the good chips can be
  identified using $\Theta(n)$ pairwise tests.
\end{itemize}

\end{document}