#LyX file created by tex2lyx 1.6.4
\lyxformat 264
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyhdr}\usepackage{enumerate}\usepackage{xspace}\chead{CS4104(Fall2009):FinalExamination}

%\usepackage{cs5114}
\newcommand{\solution}[1]{\textbf{Solution:} #1}\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}\newcommand{\opt}[1]{\ensuremath{\text{OPT}(#1)}}\newcommand{\length}[1]{\ensuremath{\overline{#1}}}\newcommand{\calnp}{\ensuremath{{\cal NP}}\xspace}\newcommand{\npc}{\calnp-Complete\xspace}

% macro for a set. extra pair of braces inside \ensuremath to ensure
% the set is typseset in one line.
\newcommand{\set}[1]{\ensuremath{{\{#1\}}}}


\end_preamble
\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
\papersize letterpaper
\use_geometry true
\use_amsmath 2
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\leftmargin 1in
\topmargin 1in
\rightmargin 1in
\bottommargin 1in
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\end_header

\begin_body

\begin_layout Title


\begin_inset VSpace -0.5in
\end_inset


\series bold
Final Examination
\series default

\end_layout

\begin_layout Author

CS 4104 (Fall 2009)
\end_layout

\begin_layout Date


\end_layout

\begin_layout Standard
\align center

Assigned: December 2, 2009.
\newline
 Due: at Torgerson 2160B by 5pm on December 14, 2009.
\newline
 
\series bold
DO NOT EMAIL YOUR SOLUTIONS TO ME!
\series default
 
\end_layout

\begin_layout Standard
\align center


\begin_inset Tabular 
<lyxtabular version="3" rows="3" columns="2">
<features>
<column alignment="right" valignment="top">
<column alignment="right" valignment="top">
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard

Name: 
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
underline{
\backslash
phantom{--------------------------------}}
\end_layout

\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="none" valignment="top" usebox="none">
\begin_inset Text

\end_inset
</cell>
<cell alignment="none" valignment="top" usebox="none">
\begin_inset Text

\end_inset
</cell>
</row>
<row>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard

9-digit PID: 
\end_layout

\end_inset
</cell>
<cell alignment="right" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
underline{
\backslash
phantom{--------------------------------}}
\end_layout

\end_inset

 
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Section*

Instructions
\end_layout

\begin_layout Standard


\begin_inset LatexCommand label
name "sec:instructions"

\end_inset


\end_layout

\begin_layout Enumerate

For every algorithm you describe, prove its correctness and analyse its running time and space used. I am looking for clear descriptions of algorithms and for the most efficient algorithms you can come up with.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
item If you prove that a problem is 
\backslash
npc, remember to state how long
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   the certificate is, how long it takes to check that the certificate
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   is correct, and what the running time of the transformation is. All
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   you need to show is that the transformation can be performed in
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   polynomial time. Your transformation need not be the most efficient
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   possible.
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate

You may consult the textbook, your notes, or the course web site to solve the problems in the examination. You 
\series bold
may not
\series default
 work on the exam with anyone else, ask anyone questions, or consult other textbooks or sites on the Web for answers. 
\series bold
Do not use
\series default
 concepts from chapters in the textbook that we have not covered.
\end_layout

\begin_layout Enumerate

You must prepare your solutions digitally and submit a hard-copy.
\end_layout

\begin_layout Enumerate

I prefer that you use LaTeX\InsetSpace \space{}
to prepare your solutions. However, I will not penalise you if you use a different system. To use LaTeX, you may find it convenient to download the LaTeX\InsetSpace \space{}
source file for this document from the link on the course web site. At the end of each problem are three commented lines that look like this:
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
begin{verbatim}
\end_layout

\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
end{verbatim}
\end_layout

\end_inset


\end_layout

\begin_layout Standard

You can uncomment these lines and type in your solution within the curly braces.
\end_layout

\end_deeper
\begin_layout Enumerate

Do not forget to staple the hard copy you hand in.
\end_layout

\begin_layout Standard

Good luck!
\end_layout

\begin_layout Standard


\newpage

\end_layout

\begin_layout Description

Problem 1 (10 points) Let us start with some quickies. For each statement below, except for the last one, say whether it is true or false. You do not need to provide a rationale for your solution.
\end_layout

\begin_deeper
\begin_layout Enumerate

For the problem of computing the largest matching in a bipartite graph, the Ford-Fulkerson algorithm runs asymptotically faster than the scaling algorithm. 
\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Standard

%   
\end_layout

\begin_layout Standard


\end_layout

\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\begin_layout Enumerate


\begin_inset Formula $\sum_{i=1}^{n} i = \Theta(n^2)$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

%      
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%      }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate

In a directed graph, 
\begin_inset Formula $G = (V, E)$
\end_inset

 let 
\begin_inset Formula $\pi(u, v)$
\end_inset

 denote the length of the shortest path that starts at 
\begin_inset Formula $u$
\end_inset

 and ends at 
\begin_inset Formula $v$
\end_inset

. If there is no such path, you can assume that 
\begin_inset Formula $\pi(u, v) =
    \infty$
\end_inset

. Since 
\begin_inset Formula $G$
\end_inset

 is directed, 
\begin_inset Formula $\pi(u, v) \not= \pi(v, u)$
\end_inset

, in general. Then, for any three nodes 
\begin_inset Formula $u, v, w \in V$
\end_inset

, 
\begin_inset Formula $\pi(u, v) + \pi(v, w)
    \geq \pi(u, w)$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate

Suppose we have an algorithm that when given a graph 
\begin_inset Formula $G$
\end_inset

 with 
\begin_inset Formula $n$
\end_inset

 nodes and an integer 
\begin_inset Formula $k$
\end_inset

, checks if 
\begin_inset Formula $G$
\end_inset

 has a vertex cover of size 
\begin_inset Formula $k$
\end_inset

 or less in 
\begin_inset Formula $O(2^kn)$
\end_inset

 time. Note that this time is polynomial in 
\begin_inset Formula $n$
\end_inset

 (but exponential in 
\begin_inset Formula $k$
\end_inset

). Since we reduced 
\shape smallcaps
Independent Set
\shape default
 to 
\shape smallcaps
Vertex Cover
\shape default
 in class, we have an algorithm that can check if a graph 
\begin_inset Formula $G$
\end_inset

 has an independent size of size at least 
\begin_inset Formula $l$
\end_inset

 (for some integer 
\begin_inset Formula $l > 0$
\end_inset

) in time polynomial in 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%   
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Enumerate

Estimate the probability that Homer Simpson will resolve the 
\begin_inset Formula ${\cal P} = \cal{NP}$
\end_inset

 conundrum in the series finale of the 
\emph on
The Simpsons
\emph default
. Please provide a probability. Do not answer 
\begin_inset Quotes eld
\end_inset

True
\begin_inset Quotes erd
\end_inset

 or 
\begin_inset Quotes eld
\end_inset

False
\begin_inset Quotes erd
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

%     
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

%     }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Description

Problem 2 (30 points) Many object-oriented programming languages implement a class for manipulating strings. A primitive operation supported by such languages is to split a string into two pieces. This operation usually involves copying the original string. Hence, a split operation takes 
\begin_inset Formula $n$
\end_inset

 units of time for a string of length 
\begin_inset Formula $n$
\end_inset

, 
\emph on
regardless of the location of the split
\emph default
. However, if we want to split a string into many pieces, the order in which we make the breaks can affect the total running time of all the splits.
\end_layout

\begin_deeper
\begin_layout Standard

For example, suppose we want to split a 20-character string at positions 3 and 8. If we make the first cut at position 3, the cost of the first cut is the length of the string, which is 20. Now the cut at position 8 falls within the second string, whose length is 17, so the cost of the second cut is 17. Therefore, the total cost is 20 + 17 = 37. Instead, if we make the first cut at position 8, the cost of this cut is still 20. However, the second cut at position 3 falls within the first string, which has length 8. Therefore, the cost of the second cut is 8, implying a total cost of 20 + 8 = 28. Since 
\begin_inset Formula $28
  < 37$
\end_inset

, it is better to make the first cut at position 8 and the second cut at position 3. However, if we want to split the same string at positions 3 and 18, you can convince yourself that the smallest total cost is achieved by first making the cut at position 3 and then at position 18.
\end_layout

\begin_layout Standard

Design an algorithm that, given the locations of 
\begin_inset Formula $m$
\end_inset

 cuts in a string of length 
\begin_inset Formula $n$
\end_inset

, finds the minimum cost of breaking the string into 
\begin_inset Formula $m +
  1$
\end_inset

 pieces at the given locations. Your algorithm must minimise the total cost of breaking the string at all the cut locations. You can assume that the cut locations are distinct and that no cut is at position 1 or at position 
\begin_inset Formula $n$
\end_inset

. 
\emph on
Hint:
\emph default
 A greedy approach will not work. Neither will divide and conquer.
\end_layout

\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Description

Problem 3 (40 points) You are given an undirected graph 
\begin_inset Formula $G = (V,
  E)$
\end_inset

. Each vertex 
\begin_inset Formula $v \in V$
\end_inset

 has a label 
\begin_inset Formula $l_v \in \set{-1, 0, 1}$
\end_inset

. Each edge 
\begin_inset Formula $e \in E$
\end_inset

 has a weight 
\begin_inset Formula $w_e > 0$
\end_inset

. Consider the set 
\begin_inset Formula $V_0$
\end_inset

 of nodes in 
\begin_inset Formula $V$
\end_inset

 whose label is 
\begin_inset Formula $0$
\end_inset

. A 
\emph on
labelling
\emph default
 of 
\begin_inset Formula $V_0$
\end_inset

 is an assignment of 
\begin_inset Formula $1$
\end_inset

 or 
\begin_inset Formula $-1$
\end_inset

 as the label of every node in 
\begin_inset Formula $V_0$
\end_inset

. Note that there are 
\begin_inset Formula $2^{|V_0|}$
\end_inset

 possible labellings of 
\begin_inset Formula $V_0$
\end_inset

. Your goal is to compute a labelling that takes the edge structure of 
\begin_inset Formula $G$
\end_inset

 into account. For example, if a node 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $V_0$
\end_inset

 has many more neighbours with label 
\begin_inset Formula $1$
\end_inset

 than 
\begin_inset Formula $-1$
\end_inset

, you may want to change 
\begin_inset Formula $v$
\end_inset

's label to 
\begin_inset Formula $1$
\end_inset

. Therefore, you decide to compute a labelling that maximises the 
\emph on
consistency
\emph default
 
\begin_inset Formula $c(G)$
\end_inset

 of 
\begin_inset Formula $G$
\end_inset

, defined as 
\begin_inset Formula \[c(G) = \sum_{e = (u, v) \in E} w_{e}l_ul_v.\]
\end_inset

 Devise a polynomial time algorithm to maximise 
\begin_inset Formula $c(G)$
\end_inset

. Note that your algorithm must produce a label of 
\begin_inset Formula $1$
\end_inset

 or 
\begin_inset Formula $-1$
\end_inset

 for 
\emph on
every
\emph default
 node in 
\begin_inset Formula $V_0$
\end_inset

. Therefore, when your algorithm completes, every node in 
\begin_inset Formula $V$
\end_inset

 should have a label of either 
\begin_inset Formula $1$
\end_inset

 or 
\begin_inset Formula $-1$
\end_inset

. 
\emph on
Hint:
\emph default
 A greedy approach will not work. Neither will divide and conquer.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Description

Problem 4 (20 points) This problem deals with cost-effective purchase of candy, a resource-allocation problem of particular importance. You enter a candy store. In front of you are glass jars, each filled with a different mouth-watering type of candy. You are on a strict budget: you have at most 
\begin_inset Formula $\$b$
\end_inset

 with you. There are 
\begin_inset Formula $n$
\end_inset

 types of candy, each in a unique jar. For each 
\begin_inset Formula $1 \leq i \leq n$
\end_inset

, the entire jar containing the 
\begin_inset Formula $i$
\end_inset

th type of candy costs 
\begin_inset Formula $\$c_i$
\end_inset

 and weighs 
\begin_inset Formula $w_i$
\end_inset

 kilogrammes. You are allowed to purchase as much candy as you want from each jar. You can purchase as tiny a portion of any piece of candy as you want. Put another way, you can think of the candy as being powdered
\begin_inset Foot
status collapsed


\begin_layout Standard

I am not suggesting that anyone will actually want to 
\emph on
eat
\emph default
 powdered candy.
\end_layout

\end_inset

 and you can scoop up whatever weight you want from each jar. Devise an algorithm that maximises the total weight of the candy you purchase, as long as the total cost of the candy you buy is at most 
\begin_inset Formula $\$b$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard


\backslash
centerline{
\end_layout

\end_inset


\begin_inset Graphics 
	filename Gumballs.jpg
	width 40text%

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

}
\end_layout

\end_inset


\end_layout

\begin_layout Standard


\begin_inset ERT
status collapsed

\begin_layout Standard

% 
\backslash
solution{
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\begin_inset ERT
status collapsed

\begin_layout Standard

% }
\end_layout

\begin_layout Standard


\end_layout

\end_inset


\end_layout

\end_deeper
\end_body
\end_document