\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,graphicx,amsmath}
\pagestyle{fancy}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}
\newcommand{\solution}[1]{\textbf{Solution:} #1}
\setcourse{CS 4104}
\setsem{Spring 2014}
\sethwnum{6}
\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}
\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}
\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\chead{\course (\sem): Homework \hwnum}
\begin{document}
\title{\vspace{-0.5in}\textbf{Homework \hwnum}}
\author{\course (\sem)}
\date{Assigned on April 14, 2014. \\Submit PDF solutions by
email on Scholar\\ by the
beginning of class on April 21, 2014.}
\maketitle
\paragraph{Instructions:}
\begin{itemize}
\item You can pair up with another student to solve the homework. You
are allowed to discuss possible algorithms and bounce ideas with your
team-mate. \textbf{Do not discuss proofs of correctness or running time in
detail with your team-mate.} Please form teams yourselves. Of course,
you can ask me for help if you cannot find a team-mate. You may choose
to work alone. \emph{Each of you must write down your solution
individually, and write down the name of the other member in your
team. If you do not have a team-mate, please say so.} \textbf{If
your solution is largely identical to that of your team-mate or
another student, we will return it ungraded.}
\item Apart from your team-mate, you are not allowed to consult any
sources other than your textbook, the slides on the course web page,
your own class notes, the TAs, and the instructor. In particular, do
not use a search engine.
\item Do not forget to typeset your solutions. \emph{Every mathematical
expression must be typeset as a mathematical expression, e.g., the
square of $n$ must appear as $n^2$ and not as ``n\^{}2''.} Students
can use the \LaTeX\ version of the
homework problems to start entering their solutions.
\item Describe your algorithms as clearly as possible. The style used in
the book is fine, as long as your description is not
ambiguous. Explain your algorithm in words. A step-wise description is
fine. \emph{However, if you submit detailed pseudo-code without an
explanation, we will not grade your solutions.}
\item Do not make any assumptions not stated in the problem. If you do
make any assumptions, state them clearly, and explain why the
assumption does not decrease the generality of your solution.
\item Do not describe your algorithms only for a specific example you
may have worked out.
\item You must also provide a clear proof that your solution is correct
(or a counter-example, where applicable). Type out all the statements you
need to complete your proof. \emph{You must convince us that you can
write out the complete proof. You will lose points if you work out
some details of the proof in your head but do not type them out in
your solution.}
\item Describe an analysis of your algorithm and state and prove the
running time. You will only get partial credit if your analysis is not
tight, i.e., if the bound you prove for your algorithm is not the best
upper bound possible.
\end{itemize}
\begin{description}
\item[Problem 1] (20 points) Solve exercise 1 in Chapter 6 (pages
312-313) of your textbook.
% \solution{
% }
\item[Problem 2] (30 points) Solve exercise 17 in Chapter 6 (pages
327-328) of your textbook. For part (b) of this exercise, keep in mind
that a rising trend must begin on the first day. You should find this
requirement important in defining all your sub-problems.
% \solution{
% }
\item[Problem 3] (10 points) In this problem, you will analyse the
worst-case running time of weighted interval scheduling without
memoisation. Recall that we sorted the $n$ jobs in increasing order of
finish time and renumbered these jobs in this order, so that $f_i \leq
f_{i+1}$, for all $1 \leq i < n$, where $f_i$ is the finish time of
job $i$. For every job $j$, we defined $p(j)$ to be the job with the
largest index that finishes earlier than job $j$. Consider the input
in Figure 6.4 on page 256 of your textbook. Here all jobs have weight
1 and $p(j) = j-2$, for all
$3 \leq j \leq n$ and $p(1) = p(2) = 0$. Let $T(n)$ be the running
time of the dynamic programming algorithm \emph{without memoisation}
for this particular input. As we discussed in class, we
can write down the following recurrence:
\begin{align*}
T(n) & = T(n-1) + T(n-2), n > 2\\
T(2) & = T(1) = 1
\end{align*}
Prove an \emph{exponential} lower bound on $T(n)$. Specifically, prove
that $T(n) \geq 1.5^{n-2}$, for all $n \geq 1$.
\item[Problem 4] (40 points) A convex polygon is a polygon where very
interior angle is less than 180 degrees. A museum is in the shape of a
convex polygon with $n$ vertices. The museum is patrolled by
guards. The Directory of Security at the museum has the following
rules to ensure the most safety in as time-economical a way as
possible:
\begin{enumerate}[(a)]
\item Each guard traverses a path in the shape of a triangle; each
vertex of such a triangle must a vertex of the polygon.
\item A guard can survey all the points inside his or her triangle and
\emph{only} these points; we say that these points are
\emph{covered} by the guard.
\item Every point inside the museum must be covered by some guard.
\item The triangles traversed by any pair of guards do not overlap in
their interiors, although they may share a common edge.
\end{enumerate}
\centerline{\includegraphics{art-gallery.pdf}} Each guard can be
specified by the triangle he/she patrols. We call a set of triangles
that satisfy these rules \emph{legal}. Above are four figures that
illustrate the problem. The museum is the polygon ABCDEFG. Each
coloured (shaded) triangle corresponds to a guard and the guard
traverses the perimeter of his or her triangle.
\begin{itemize}
\item The top two figures show a set of triangles that are legal,
since they satisfy the constraints laid down by the Directory of
Security. In the top left figure, the guards traverse the boundaries
of triangles AFG (blue), ABF (green), BEF (pale red), BDE (light
red), and BCD (brown). In the top right figure, the guards traverse
ABG (blue), BCG (green), CDG (brown), DFG (light red), and DEF (pale
red).
\item The bottom two figures show a set of triangles that \emph{do
not} satisfy these constraints: in the figure on the bottom left,
part of the museum is not covered by any guard (the unshaded
triangle BEF) while in the figure on the bottom right, the pink
triangle (AEF) and the green triangle (BEF) intersect (note that the
part of the green triangle in the image is covered by the pink
triangle).
\end{itemize}
Given these constraints, the \emph{cost} incurred by a guard is the
length of the perimeter of the triangle the guard traverses. The
\emph{total} cost of a set of legal triangles is the sum of the length of
their perimeters. Our goal is to find a legal set of triangles such
that the total cost of the triangles is as small as possible. Given
the $x$- and $y$-coordinates of the vertices of the art gallery and
the ordering of these vertices along the boundary of the art gallery,
devise an algorithm whose running time is polynomial in $n$ to solve
this problem. Note that we are not trying to minimise the number of
guards; we want to minimise the total lengths of the routes patrolled
by the guards. You may assume that the length of any line segment is
the Euclidean distance between the end-points of the line segment and
that this length can be computed in constant time.
Since this problem may be quite difficult, let us split up into more
digestible pieces. Let the museum be a convex polygon $P$ with $n$
vertices $p_0, p_1, \ldots p_{n-1}$ ordered consecutively in
counter-clockwise order around $P$. Except for $p_{n-1}p_0$, which is an
edge of the polygon, a line segment $p_ip_j$ is a
\emph{diagonal} if $p_i$ and $p_j$ are not adjacent vertices, i.e.,
$|i - j| \not = 1$. The order of the endpoints does not matter, i.e.,
the diagonals $p_ip_j$ and $p_jp_i$ are identical. Since $P$ is
convex, every point of a diagonal (other than its end-points) lies in
the interior of $P$. Clearly, in any legal set of triangles, every
triangle edge is either an edge of $P$ or a diagonal of $P$. For each
of the questions below, you must provide a proof for your answer. Some
of the proofs may be short, especially for parts (i) and (iii).
\begin{enumerate}[(i)]
\item (5 points) How many diagonals does $P$ contain in total?
\item (10 points) How many diagonals does any legal set of triangles
contain? If you use a proof by induction, please be sure to state
the base case, inductive hypothesis, and inductive step clearly.
\item (7 points) Given a legal set of triangles, express the total
cost of these triangles in terms of the perimeter of $P$ and the
lengths of those edges of the triangles that are diagonals of $P$.
\item (18 points) To start formulating the dynamic programming
recursion, consider the edge $p_0p_{n-1}$. This edge must be part of
some triangle $T$ in the optimal solution. Think about where the
third vertex in $T$ can be. Since the optimal solution contains a
legal set of triangles, the edges of the other triangles in the
optimal solution cannot intersect the edges of $T$. Use this fact to
derive a recursion to compute the optimal solution. State and prove
the running time of the resulting algorithm.
\end{enumerate}
% \solution{
% }
\end{description}
\end{document}