#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyheadings}\usepackage{enumerate}\usepackage{xspace}
% 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{CS4104}\setsem{Fall2009}\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}
\end_preamble
\use_default_options false
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\author ""
\end_header
\begin_body
\begin_layout Title
\begin_inset VSpace -0.5in
\end_inset
\series bold
Homework
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
hwnum
\end_layout
\end_inset
\end_layout
\begin_layout Author
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
course
\end_layout
\end_inset
(
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
sem
\end_layout
\end_inset
)
\end_layout
\begin_layout Date
Assigned on November 2, 2009.
\begin_inset Newline newline
\end_inset
Hardcopy due at the beginning of class on November 9, 2009.
\end_layout
\begin_layout Paragraph
Instructions:
\end_layout
\begin_layout Itemize
\series bold
In this homework, we are experimenting with a new policy of working in teams
of two students.
\series default
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.
Do not discuss proofs of correctness or running time in detail with your
team-mate.
\emph on
Each student must write his/her solution individually, and write down the
name of the other member in your team.
\emph default
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.
\end_layout
\begin_layout Itemize
Your team is not allowed to consult any sources other than your textbook,
the slides on the course web page, your own class notes, the TA, and the
instructor.
In particular, do not use a search engine.
\end_layout
\begin_layout Itemize
Do not forget to typeset your solutions.
\emph on
Every mathematical expression must be typeset as a mathematical expression,
e.g., the square of
\begin_inset Formula $n$
\end_inset
must appear as
\begin_inset Formula $n^{2}$
\end_inset
and not as
\begin_inset Quotes eld
\end_inset
n‸2
\begin_inset Quotes erd
\end_inset
.
\emph default
Students using LaTeX
\begin_inset space \space{}
\end_inset
or LyX can use the corresponding versions of the homework problems to start
entering their solutions.
\end_layout
\begin_layout Itemize
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 on
However, if you submit detailed pseudo-code without an explanation, we will
not grade your solutions.
\end_layout
\begin_layout Itemize
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.
\end_layout
\begin_layout Itemize
Do not describe your algorithms only for a specific example you may have
worked out.
\end_layout
\begin_layout Itemize
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 on
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.
\end_layout
\begin_layout Itemize
Analyse your algorithm and state 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_layout
\begin_layout Description
Problem 1 (20 points) Solve exercise 1 in Chapter 6 (pages 312-313) of your
textbook.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
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 your sub-problems.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 3 (50 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
\begin_inset Formula $n$
\end_inset
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:
\end_layout
\begin_deeper
\begin_layout Standard
[(a)]
\end_layout
\begin_layout Enumerate
Each guard traverses a path in the shape of a triangle; each vertex of such
a triangle must a vertex of the polygon.
\end_layout
\begin_layout Enumerate
A guard can survey all the points inside his or her triangle and
\emph on
only
\emph default
these points; we say that these points are
\emph on
covered
\emph default
by the guard.
\end_layout
\begin_layout Enumerate
Every point inside the museum must be covered by some guard.
\end_layout
\begin_layout Enumerate
The triangles traversed by any pair of guards do not overlap in their interiors,
although they may share a common edge.
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
centerline{
\end_layout
\end_inset
\begin_inset Graphics
filename art-gallery.png
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
}
\end_layout
\end_inset
Each guard can be specified by the triangle he/she patrols.
We call a set of triangles that satisfy these rules
\emph on
legal
\emph default
.
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 will
traverse the perimeter of his or her triangle.
\end_layout
\begin_layout Itemize
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).
\end_layout
\begin_layout Itemize
The bottom two figures show a set of triangles that
\emph on
do not
\emph default
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 (not that the part of the green triangle in the image is
covered by the pink triangle).
\end_layout
\begin_layout Standard
Given these constraints, the
\emph on
cost
\emph default
incurred by a guard is the length of the perimeter of the triangle the
guard traverses.
The
\emph on
total
\emph default
cost of a set of 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
\begin_inset Formula $x$
\end_inset
- and
\begin_inset Formula $y$
\end_inset
-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
\begin_inset Formula $n$
\end_inset
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 is quite difficult, let us split up into two more digestible
pieces.
Let the museum be a convex polygon
\begin_inset Formula $P$
\end_inset
with
\begin_inset Formula $n$
\end_inset
vertices
\begin_inset Formula $p_{0},p_{1},\ldots p_{n-1}$
\end_inset
ordered consecutively in counter-clockwise order around
\begin_inset Formula $P$
\end_inset
.
A line segment
\begin_inset Formula $p_{i}p_{j}$
\end_inset
is a
\emph on
diagonal
\emph default
if
\begin_inset Formula $p_{i}$
\end_inset
and
\begin_inset Formula $p_{j}$
\end_inset
are not adjacent vertices, i.e.,
\begin_inset Formula $|i-j|\not=1$
\end_inset
.
Since
\begin_inset Formula $P$
\end_inset
is convex, every point of a diagonal (other than its end-points) lies in
the interior of
\begin_inset Formula $p$
\end_inset
.
Clearly, in any legal set of triangles, every triangle edge is either an
edge of
\begin_inset Formula $P$
\end_inset
or a diagonal of
\begin_inset Formula $P$
\end_inset
.
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).
\end_layout
\begin_layout Standard
[(i)]
\end_layout
\begin_layout Enumerate
(4 points) How many diagonals does
\begin_inset Formula $P$
\end_inset
contain in total?
\end_layout
\begin_layout Enumerate
(9 points) How many diagonals does any legal set of triangles contain?
\end_layout
\begin_layout Enumerate
(7 points) Given a legal set of triangles, express the total cost of these
triangles in terms of the perimeter of
\begin_inset Formula $P$
\end_inset
and the lengths of those edges of the triangles that are diagonals of
\begin_inset Formula $P$
\end_inset
.
\end_layout
\begin_layout Enumerate
(10 points) Let us consider one way to construct a dynamic programming solution,
which will not lead to an optimal solution.
Consider vertex
\begin_inset Formula $p_{0}$
\end_inset
.
There are two possibilities in the optimal solution:
\end_layout
\begin_deeper
\begin_layout Standard
[a.]
\end_layout
\begin_layout Enumerate
A diagonal is not incident on
\begin_inset Formula $p_{0}$
\end_inset
.
In this case,
\begin_inset Formula $p_{1}p_{n-1}$
\end_inset
must be a diagonal in the optimal solution.
(Try to prove yourself that the configuration is not legal otherwise.) Therefore
, we have a single sub-problem involving the convex polygon formed by the
sequence of vertices
\begin_inset Formula $p_{1},p_{2},\ldots p_{n-1}$
\end_inset
and the diagonal
\begin_inset Formula $p_{1}p_{n-1}$
\end_inset
.
\end_layout
\begin_layout Enumerate
A diagonal is incident on
\begin_inset Formula $p_{0}$
\end_inset
.
Suppose
\begin_inset Formula $p_{i}$
\end_inset
is the other vertex of the diagonal.
This diagonal yields two sub-problems, one involving the vertices
\begin_inset Formula $p_{i},p_{i+1},\ldots,p_{n-2},p_{n-1},p_{0}$
\end_inset
and the other involving the vertices
\begin_inset Formula $p_{0},p_{1},p_{2},\ldots p_{i}$
\end_inset
.
\end_layout
\begin_layout Standard
Try to develop a set of sub-problems based on these observations and point
out where the solution goes astray.
You do not need to prove anything here; simply discuss why this idea is
hard to finish.
\end_layout
\end_deeper
\begin_layout Enumerate
(20 points) Inspired by this wrong approach, define a new set of sub-problems
that you can use to compute the optimal solution.
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\backslash
solution{
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
% }
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\end_deeper
\end_body
\end_document