\documentclass[12pt]{article}

\input{6006-stuff}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{epsfig}
\usepackage{wrapfig}
\usepackage{synttree}
%\usepackage{bbm}

\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

\newif\ifsolutions
%\solutionstrue
\solutionsfalse

\ifsolutions
\newcommand{\answer}[2][none]{\solution{#2}}
\else
\newcommand{\answer}[2]{}
\fi

% Usage: \blank{text under underline}{solution for when solutions turned on}
%     or \blank[how long the underline should be]{text under underline}{soln}
%     or \justification{solution}  (a particular kind of blank with more space)
\newlength\blanklength
\blanklength=2in
\newlength\blankover
\blankover=1em
\newcommand\blankpart[2]
  {\hbox to #1{\ifsolutions \hspace*\blankover #2\fi\hfil}}
\newcommand\blankline[3]{\mathop{\underline{\blankpart{#1}{#2}}}
                         \limits_{\vtop{\vskip 0pt\hbox{\scriptsize #3}\medskip}}}
\newcommand\blank[3][\blanklength]{\ifmmode \blankmath[#1]{#2}{#3}%
                                   \else \blanktext[#1]{#2}{#3}\fi}
\newcommand\blankmath[3][\blanklength]{{\displaystyle \blankline{#1}{$\displaystyle #3$}{#2}}}
\newcommand\blanktext[3][\blanklength]{$\displaystyle \blankline{#1}{#3}{#2}$}
\newlength\justificationlength
\justificationlength=20ex
\newcommand\justification[1]{\par
  \ifsolutions \else \vspace\justificationlength \fi
  \blank[\linewidth]{Give justification.}{\vbox to \justificationlength{\vss #1}}%
  \par}


\newcommand{\answerbox}[1]{\vspace{#1}}
\newcommand{\solution}[1]{\paragraph{Solution:}#1}

\newcommand{\str}{\mbox{\LARGE\strut}}  %Fix this!

\newcommand{\remark}[1]{\textbf{Remark:} #1}
\newcommand{\dontuse}[1]{}
%------------------------------------------------
%COVER PAGE INSTRUCTION
\begin{document}
\ifsolutions
\exam{Final Exam Solutions}{May 21, 2009}
\else
\exam{Final Exam}{May 21, 2009}

\renewcommand{\theproblem}{Problem \arabic{problemnum}}

%\handout{quiz1sol}{Quiz 1 Solutions}

\begin{closeitemize}

\item Do not open this quiz booklet until directed to do so.
Read all the instructions on this page.

\item When the quiz begins, write your name on every page of this quiz
booklet.

\item You have 180 minutes to earn \textbf{200} points.
Do not spend too much time on any one problem.  Read them all
through first, and attack them in the order that allows you to make
the most progress.

\item This quiz booklet contains \pageref{totalpages} pages, including
this one.  Two extra sheets of scratch paper are attached.  Please
detach them before turning in your quiz at the end of the exam period.

\item This quiz is closed book.  You may use \textbf{three} $8\frac{1}{2}''\times
  11''$ or A4 crib sheets (both sides).
  No calculators or programmable devices are permitted.
  No cell phones or other communications devices are permitted.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.
Pages may be separated for grading.

\item Do not waste time and paper rederiving facts that we have studied.
It is sufficient to cite known results.

\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  Be neat.

\item Good luck!

\end{closeitemize}
%-------------------------------------------



%-------------------------------------------
%COVERPAGE TABLE

\vfill

\begin{center}
\renewcommand{\arraystretch}{1}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline

Problem&Parts&Points&Grade&Grader&&
Problem&Parts&Points&Grade&Grader\\ \hline \hline
\str 1 & 8 & 24 & & & & 5 & 1 & 24 & & \\
\hline
\str 2 & 4 & 32 & & & & 6 & 1 & 24 & & \\
\hline
\str 3 & 3 & 24 & & & & 7 & 1 & 24 & &\\
\hline
\str 4 & 3 & 24 & & & & 8 & 1 & 24 & & \\
\hline
\str & & & & & & Total &  & 200 & & \\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\vfill
\bigskip
%\bigskip

%-------------------------------------------



%-------------------------------------------
%COVERPAGE NAME AND INSTRUCTOR
\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip

%% \newcommand{\recbox}[1]{\begin{minipage}{.13\textwidth} \begin{center} #1 \end{center} \end{minipage}}
%% \newcommand{\recboxlabel}[1]{\begin{minipage}{.20\textwidth} #1 \end{minipage}}

%% \noindent
%% \recboxlabel{Friday Recitation:} \hfill
%% \recbox{Rishabh\\\bf 10 AM} \hfill
%% \recbox{Rob\\\bf 12 PM} \hfill
%% \recbox{Chieu\\\bf 1 PM} \hfill
%% \recbox{Jason\\\bf 2 PM} \hfill
%% \recbox{Matthew\\\bf 3 PM}

\clearpage
\fi
%-------------------------------------------

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{True or False} \points{24} \parts{8}

For each of the following questions, circle either T (True) or F (False). 
\textbf{Explain your choice.} (No credit if no explanation given.)

\begin{truefalseproblemparts}

  \problempart There exists an algorithm to build a binary search tree
  from an unsorted list in $O(n)$ time. \\
  \textit{Explain:}

  \answer{
    False. Because an in-order walk can create a sorted list from a
    BST in $O(n)$ time, the existence of such an algorithm would
    violate the $\Omega(n\lg n)$ lower bound on comparison-based
    sorts.
  }
  
  \vfill


  \problempart There exists an algorithm to build a binary heap from
  an unsorted list in $O(n)$ time. \\
  \textit{Explain:}

  \answer{
    True. The standard \proc{build-heap} algorithm runs in $O(n)$
    time.
  }
  
  \vfill


  \problempart To solve the SSSP problem for a graph with no
  negative-weight edges, it is necessary that some edge be relaxed at
  least twice. \\
  \textit{Explain:}

  \answer{
    False. Dijkstra's algorithm solves the SSSP problem relaxing each
    edge at most once.
  }
  
  \vfill


  \problempart On a connected, directed graph with only positive edge
  weights, Bellman-Ford runs asymptotically as fast as
  Dijkstra. \\
  \textit{Explain:}

  \answer{
    False. Bellman-Ford requires $\Theta(VE)$, regardless of the edge
    weights. Dijkstra runs in $\Theta(E+V\lg V)$. Because the graph is
    connected, $E=\Omega(V)$, so $\Theta(VE)=\Omega(V^2)$, which is
    clearly worse than Dijkstra.
  }
  
  \vfill


%%   \problempart Performing a rotation on an AVL tree does not change
%%   its height. \\
%%   \textit{Explain:}

%%   \answer{
%%     False. It is possible for a rotation to change the height of an
%%     AVL tree, which is why it is sometimes necessary to perform
%%     $\Theta(\lg n)$ rotations to rebalance.
%%   }
  
%%   \vfill


  \newpage


  \problempart A Givens rotation requires $O(1)$ time. \\
  \textit{Explain:}

  \answer{
    False. It may take $O(1)$ time if the matrix is sparse, but in
    general a Givens rotation requires $O(n)$ for a matrix with $n$
    columns.
  }

  \vfill


  \problempart In the worst case, merge sort runs in $O(n^2)$ time. \\
  \textit{Explain:}

  \answer{
    True. Merge sort runs in $O(n\lg n)$ time which is $O(n^2)$.
  }

  \vfill


% REMOVED
%  \problempart Using perfect hashing, it is possible to find the value associated 
%  with an arbitrary $n$-bit number in worst-case $O(n)$ time, using $O(n)$ space. \\
%  \textit{Explain:}%

%  \answer{

%     False. Perfect hashing requires knowing beforehand all the keys that 
% 	will ever be hashed. There are $2^n$ possible $n$-bit numbers.
%        Therefore, perfect hashing can guarantee worst-case $O(n)$ access
%        only if the space used is $\Omega(2^n)$.
    
%  }

% \vfill


  \problempart There exists a stable implementation of merge sort. \\
  \textit{Explain:}

  \answer{
    True. If the items in the two lists being merged are equal, choose
    the item in the ``left'' half (the half that came first in the
    original array).
  }

  \vfill


  \problempart An AVL tree $T$ contains $n$ integers, all
  distinct. For a given integer $k$, there exists a $\Theta(\lg n)$
  algorithm to find the element $x$ in $T$ such that $|k-x|$ is
  minimized. \\
  \textit{Explain:}

  \answer{
    True. \proc{Insert} $k$, then find the \proc{Predecessor} and
    \proc{Successor} of $k$. Return the one whose difference with $k$
    is smaller. All three methods take $\Theta(\lg n)$ time.
  }

  \vfill


\end{truefalseproblemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{Short Answer} \points{32} \parts{4}

\begin{problemparts}
  
  \problempart The \emph{eccentricity} $\epsilon(u)$ of a vertex $u$
  in a connected, undirected, \emph{unweighted} graph $G$ is the
  maximum distance from $u$ to any other vertex in the graph. That is,
  if $\delta(u,v)$ is the shortest path from $u$ to $v$, then
  $\epsilon(u)=\max_{v\in V} \delta(u,v)$.

  Give an efficient algorithm to find the eccentricity of a given
  vertex $s$. Analyze its running time.
		
  \answer {
    Run BFS starting at $s$. Keep track of how many ``levels'' have
    been explored. The number of levels required to explore the entire
    graph is equal to $\epsilon(s)$. This requires $O(V+E)$ time.
  }

  \vfill


  %\problempart Consider two Python expressions:
  %\begin{normalenumerate}
  %\item \texttt{x - x + y}
  %\item \texttt{x + y - x}
  %\end{normalenumerate}
  %Explain a circumstance in which these two mathematically-equivalent
  %expressions might evaluate to substantially different results.
  %
  %\answer{
  %  Suppose \texttt{x = 1.0} and \texttt{y = 1e-17}. Because of limits
  %  on floating point precision \texttt{x + y} will evaluate to
  %  \texttt{1.0}, so expression 1 will yield approximately
  %  \texttt{1e-17}, while expression 2 yields \texttt{0.0}.
  %}
  
  \problempart
  What is the asymptotic cost of solving a linear system of equations with
  $n-1$ equations of the form
  $$ a_{i,i} x_i + a_{i,i+1} x_{i+1} = b_i \quad i=1,\ldots,n-1 $$
  and one equation of the form
  $$ a_{n,1} x_1 + a_{n,2} x_2 + \cdots + a_{n,n} x_n = b_n $$
  (none of the $a$'s in this equation are zero). The $a$'s and $b$'s are given
  numbers and the $x$'s are unknowns. Assume that we use Givens rotations
  to reduce the coefficient matrix to a triangular form. Justify your answer.
  
  \answer{
    If we form a matrix and apply Givens rotations, eliminating the first column will
    fill in all the elements below the main diagonal, so we will need to perform $\Theta(n^2)$
    rotations at a total cost of $\Theta(n^3)$.
    If we move the last equation (the one without zero coefficients) to the top,
    we only need to perform one Givens rotation per column, so the total cost reduces
    to $\Theta(n^2)$.
  }

  \vfill

  \newpage

  \problempart Suppose a hash function $h$ maps arbitrary keys to
  values between $0$ and $m-1$, inclusive. We hash $n$ keys,
  $k_1,k_2,\dots,k_n$. If $h(k_i)=h(k_j)$, we say that $k_i$ and $k_j$
  collide. Assuming simple uniform hashing, how should we choose $m$
  (in terms of $n$) such that the expected number of collisions is
  $O(1)$? Justify your answer.

  \answer{
    Any two keys collide with probability $1/m$. There are
    $\choose{n}{2}=O(n^2)$ pairs of elements, so the expected number
    of collisions is $O(n^2/m)$. Thus, let $m=\Omega(n^2)$.
  }

  \vfill

%%   \problempart The decision tree for comparison-based sorting of $n$
%%   elements has $n!$ leaves. How many leaves are present in the
%%   decision tree for comparison-based merging of two ordered lists,
%%   each of size $n$?

%%   \answer{
%%     The merged list has $2n$ elements. In this list, $n$ elements must
%%     have come from the first list being merged; there are
%%     $\choose{2n}{n}$ possible positions for those $n$ elements. Thus
%%     the decision tree has $\Theta\left(\choose{2n}{n}\right)$ leaves.
%%   }

%%   \vfill

	%%% shortest paths problem
   \problempart Suppose you have a directed acyclic graph with $n$ vertices and 
	$O(n)$ edges, all having nonnegative weights. Propose an efficient method of
	finding the shortest path to each vertex from a single source, and give its running time in terms of $n$.

	\answer{
	The given conditions allow us to use either the DAG shortest paths algorithm or Dijkstra's. 
	DAG shortest paths runs in $\Theta(V+E) = \Theta(n)$, and Dijkstra's runs in 
	$O((V+E)\lg V)$, or $O(V\lg V + E)$ if using a Fibonacci heap. In either case, Dijkstra's runs in
	$O(n\lg n)$. DAG shortest paths is faster in this case.
	}
  
   \vfill



\end{problemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{Judge Jill} \points{24} \parts{3}

Judge Jill has created a web site that allows people to file complaints about one another.
Each complaint contains exactly two names: that of the person who filed it and that of the person
he/she is complaining about.

Jill had hoped to resolve each complaint personally, but the site has received so
many complaints that she has realized she wants an automated approach.

She decides to try to label each person
as either good or evil. She only needs the labeling to be consistent, not necessarily
correct. A labeling is consistent if every complaint labels one person as good and the other person as evil, and no person gets labeled both as good and evil in different complaints.
%as long as no complaint names two people both labeled
%good or two people both labeled evil, the labeling is consistent.

\begin{problemparts}

\problempart \points{8}
Propose a way to model the consistent labeling problem as a graph problem.

\answer{
  We can model the problem using an undirected graph in which every edge represents one
  complaint and every vertex represents one name (one person).
}

\vfill

\newpage

\problempart \points{10} 
Propose an efficient algorithm to consistently label all the names as good or evil,
or to decide that no such classification exists.
Use the graph model you proposed in the previous part of the problem.
Analyze the running time of the algorithm.

\answer{
  The problem is quivalent to testing whether we can color the vertices of graph with two colors,
  or equivalently, whether the graph is bipartite. This can be done using DFS in $Theta(V+E)$ time.
  We label the root of DFS traversals arbitrarily good or bad. When we first visit a vertex,
  we label it differently than its parent. When we encounter back or cross edges, we check for
  consistency; if we find an inconsistency, the graph cannot be labeled consistently.
}

\vfill

\problempart \points{6}
Later, Judge Jill wants to be more thorough. She will interview some people
to figure out who is good and who is evil. She 
can always determine whether a person is good or evil by interviewing him or her.
Assuming that one person in every complaint is good and the other is evil, what
is the minimum number of people she needs to interview to correctly classify all the people named in the 
complaints?

\answer{
  She needs to interview one person in each connected component of the complaint graph.
}

\vfill
\end{problemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{Bitdiddle Bins} \points{24} \parts{3}

Ben Bitdiddle has devised a new data structure called a Bitdiddle Bin. Much
like an array or a set, you can {\sc Insert} values into it, and you can {\sc
Lookup} values to see if they are contained in the structure. (He'll figure out
{\sc Delete} later.)

A Bitdiddle Bin is implemented as a pair of lists (arrays), designated the {\em
neat list} and the {\em messy list}, with these properties:

\begin{normalitemize}
\item The {\em neat list} is always in sorted order. (The messy list may or may
not be sorted.)
\item The {\em messy list} has a size of at most $\sqrt{n}$,  where $n$ is the
total number of values in the entire Bitdiddle Bin.
\end{normalitemize}

The {\sc Lookup} algorithm for a Bitdiddle Bin is as follows:
\begin{normalenumerate}
\item Use binary search to look for the value in the neat list.
\item If it wasn't in the neat list, iterate over the entire messy list to
look for the value.
\end{normalenumerate}

The {\sc Insert} algorithm is as follows:
\begin{normalenumerate}
\item Append the value to the messy list.
\item If the messy list is now too big, {\sc Cleanup}.
\end{normalenumerate}

This {\sc Cleanup} subroutine is run whenever the messy list grows beyond
$\sqrt{n}$ items:
\begin{normalenumerate}
\item Sort the messy list.
\item Merge the messy list with the neat list.
\item The merge result is the new neat list. The new messy list is empty.
\end{normalenumerate}

\begin{problemparts}

\problempart \points{4}
What is the worst-case asymptotic runtime of {\sc Lookup} on a Bitdiddle Bin?

\answer{
  Binary search on the neat list takes $\Theta(\log n)$, and iterating
  over the messy list takes $\Theta(\sqrt{n})$, for a total time of
  $\Theta(\sqrt{n})$.
}

\vfill
\clearpage

\problempart \points{8} 
What is the worst-case asymptotic runtime of {\sc Insert} on a Bitdiddle Bin?
Explain.

\answer{
  Appending is $\Theta(1)$. Sorting the messy list is $\Theta(\sqrt{n}
  \log{\sqrt{n}})$. Merging is $\Theta(n)$. The $\Theta(n)$ term dominates, so
  the asymptotic runtime is $\Theta(n)$.
}

\vfill

\problempart \points{12}
What is the {\em amortized} asymptotic runtime of each {\sc Insert} operation,
when inserting $n$ values into an empty Bitdiddle Bin?
Explain.

\answer{

  Use the aggregate method. The cost is $\Theta(1)$ to append to the
  messy list, plus $\Theta(n)$ per \proc{Cleanup}. Because
  \proc{Cleanup} is called $\Theta(\sqrt{n})$ times, the total cost
  for the $n$ insertions is $O(n\sqrt{n})$, so the amortized cost
  per operation is $O(n\sqrt{n}/n) = O(\sqrt{n})$.

}

\vfill

\end{problemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{Local Minimum} \points{24} 

Consider an array $A$ containing $n$ distinct integers. We define a \emph{local minimum} of
$A$ to be an $x$ such that $x=A[i]$, for some $0\leq i < n$, with
$A[i-1] > A[i]$ and $A[i] < A[i+1]$. In other words, a local minimum $x$ is
less than its neighbors in $A$ (for boundary elements, there is
only one neighbor). Note that $A$ might have multiple local minima.

As an example, suppose $A=[10, 6, 4, 3, 12, 19, 18]$. Then $A$ has two
local minima: $3$ and $18$.

Of course, the absolute minimum of $A$ is always a local minimum, but
it requires $\Omega(n)$ time to compute.

%% \begin{problemparts}

%% \problempart \points{PTS}
Propose an efficient algorithm to find some local minimum of $A$, and
analyze the running time of your algorithm.

\answer{
  Use a divide-and-conquer algorithm. Let $m=n/2$, and examine the
  value $A[m]$ (that is, the element in the middle of the array).

  Case 1: $A[m-1] < A[m]$. Then the left half of the array must
  contain a local minimum, so recurse on the left half. We can show
  this by contradiction: assume that $A[i]$ is not a local minimum for
  each $0\leq i < m$. Then $A[m-1]$ is not a local minimum, which
  implies that $A[m-2] < A[m-1]$. Similarly, $A[m-3] <
  A[m-2]$. Continuing in this fashion, we obtain $A[0] < A[1]$. But
  then $A[0]$ is a local minimum, contrary to our initial assumption.

  Case 2: $A[m+1] > A[m]$. Then the right half of the array must
  contain a local minimum, so recurse on the right half. This is
  symmetrical to Case 1.

  Case 3: $A[m-1] > A[m]$ and $A[m+1] < A[m]$. Then $A[m]$ is a local
  minimum, so return it.

  The running time recurrence is $T(n) = T(n/2) + \Theta(1)$, which
  yields $T(n) = \Theta(\log n)$.
}

\vfill

%% \problempart \points{PTS} 
%% Now consider a two dimensional matrix $B$ of size $n \times n$ of integers. We define neighbourhood of an element $x=A[i][j]$ as $A[i+1][j]$, $A[i-1][j]$, $A[i][j+1]$ and $A[i][j-1]$. For elements at the boundary, we consider only three neigbours and for elements on the 4 corners, only two neighbours are considered. $x$ is defined to be a local minimum of $B$ if and only if it is less than or equal to all of its neighbours. Note that minimum element of $B$ is a possible solution for $x$ but that requires $O(n^2)$ time.

%% Propose an efficient algorithm to return any local minimum $x$ of $B$ and analyze the complexity of your algorithm.
%% \vfill

%% \end{problemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{Straits} \points{24} 

Let $G$ be a connected, weighted, undirected graph. All the edge weights are positive.
An edge $e$ is a {\em strait\/} between vertices $u$ and $v$
if it has weight $\ell$, is on a path from $u$ to $v$ whose other edges weigh $\ell$ or more,
and every path between $u$ and $v$ contains an edge of weight $\ell$ or less.
In other words, to go from $u$ to $v$ you must cross an edge of weight $\ell$, but you do not
need to cross edges lighter than $\ell$.  

%\begin{problemparts}

%\problempart \points{PTS}
%Suppose that $G$ is a tree. That is, it is connected, has $|V|-1$ edges, and no cycles. Describe
%an efficient algorithm for finding the weight of the strait between every pair of vertices in $G$.
%Analyze the running time of the algorithm. Hint: in a tree, there is only one path between every
%pair of vertices.

%\vfill

%\problempart \points{PTS} 
Describe
an efficient algorithm for finding the weight of the strait between every pair of vertices in $G$.
Analyze the running time of the algorithm. 

\emph{Hint:} Use a $|V|$-by-$|V|$ table to keep track of the weights of all the straits. Initialize it so
that it is correct for a graph with no edges. Then add the edges one by one.

\answer{
The initial table has infinity on the diagonal and zero everywhere else.
Suppose the table $T$ is correct for $E\setminus \{u,v\}$. We define the table $T'$
for $E$ using the rule
$$ T'[x,y] = \max\big[\;T(x,y),\ \min\big(T(x,u),w(u,v),T(v,y)\big),\ \min\big(T(x,v),w(v,u),T(u,y)\big)\;\big]. $$
The cost of this update is constant. We perform $V(V-1)$ such updates for every edge,
so the total cost is $\Theta(E V^2)$. 
}

\vfill

% \end{problemparts}

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{The Cake Is a Lie!} \points{24} 

%At Aperture Bakeries, every cake comes with a boolean expression
%indicating whether or not it is available. Each expression can consist of
%$T$ (\emph{true}), $F$ (\emph{false}), 
%$\wedge$ (binary \emph{and}), $\vee$ (binary \emph{or}), and parentheses. One example is the following,
% which evaluates to \emph{false}:

%\[
%((T \vee T) \wedge (F \vee F))
%\]

At Aperture Bakeries, every cake comes with a binary boolean-valued tree
indicating whether or not it is available. Each leaf in the tree has either a \emph{true}
or a \emph{false} value. Each of the remaining nodes has exactly two children and is labeled either \emph{and}
or \emph{or}; the value is the result of recursively applying the operator
to the values of the children. One example is the following tree:

\begin{center}
\synttree
[and [or [true] [false]] [and [true] [false]]]
\end{center}

If the root of a tree evaluates to \emph{false}, like the one above, the cake is a lie and you cannot have it. 
Any \emph{true} cake is free
for the taking. You may modify a tree to make it \emph{true}; the only thing you can do to change a tree is to 
turn a \emph{false} leaf into a \emph{true} leaf, or vice versa.
This costs \$1 for each leaf you change. You can't alter the
operators or the structure of the tree.

Cake is good. Cheap cake is even better. 
Describe an efficient algorithm to determine the minimum cost of a cake whose tree
has $n$ nodes, and analyze its running time.


\answer{

%We can treat each boolean expression as a binary tree whose leaves are $T$ and $F$ and whose other nodes represent $\vee$ and $\wedge$.

One can compute the truth value of each node in $O(n)$ time by starting with the leaves and going up. 
The precise order can be computed in $O(n)$ time using either a topological sort or BFS.
 If the root is \emph{true}, the cake is free, so return $\$0$.

Otherwise, we can use dynamic programming to determine this cost. Augment each node
with a field $C$, the minimum cost to make the node \emph{true}. Each node corresponds to the subproblem
of determining $C$  at that node. 

The base case consists of the leaves. For each $true$ leaf, set $C$ to $\$0$.
For each $false$ leaf, set $C$ to $\$1$.

Recursive cases:

For all \emph{and} nodes: Set $C$ to the sum of the children's $C$ values.

For all \emph{or} nodes: Set $C$ to the smaller of the children's $C$ values.

After computing $C$ for all nodes, in the same order in which the truth values were computed initially, return the $C$ value of the root.

Since there are $O(n)$ subproblems, and the cost of each subproblem is constant, the total running time is $O(n)$.

}


\clearpage




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem \textbf{I Am Locutus of Borg, You Will Respond To My Questions} \points{24} 
% ANOTHER reference to the same viral video? SURE, WHY NOT

% use minipage so the wrapfigure works correctly -- it gets upset when
% placed in a list environment such as the {problems} env
\begin{minipage}{\textwidth}

% re-set lengths. eugh, how ugly. oh well.
\setlength{\parskip}{0.5pc}

Upon arrival at the planet Vertex T, you and Ensign Treaps are
captured by the Borg. They promptly throw the ensign out of the
airlock. You had better solve their problem, lest you share his fate.

\begin{wrapfigure}{r}{0.28\textwidth}
  \vspace{-30pt}
  \begin{center}
    \includegraphics[width=0.26\textwidth]{H10-parkinglot}
  \end{center}
  \vspace{-30pt}
\end{wrapfigure}

The Vertex T parking lot is an $n\times n$ matrix $A$. There are
already a number of spaceships parked in the lot. For $0\leq i,j < n$,
let $A[i][j]=0$ if there is a ship occupying position $(i,j)$, and $1$
otherwise.

The Borg want to find the \emph{\textbf{largest square parking space}}
in which to park the Borg Cube. That is, find the largest $k$ such
that there exists a $k\times k$ square in $A$ containing all ones and
no zeros. In the example figure, the solution is $3$, as illustrated
by the $3\times 3$ highlighted box.

Describe an efficient algorithm that finds the size of the largest
square parking space in $A$. Analyze the running time of your
algorithm.

\emph{Hint:} Call $A[0][0]$ be the \emph{top-left} of the parking lot,
and call $A[n-1][n-1]$ the \emph{bottom-right}. Use dynamic
programming, with the subproblem $S[i,j]$ being the side length of the
largest square parking space whose bottom-right corner is at $(i,j)$.

\end{minipage}

\answer{
  The base cases are the positions along the top and left sides of the
  parking lot. In each of these positions, you can fit a $1\times 1$
  square parking space if and only if the space is unoccupied. Thus,
  for the base cases ($i=0$ or $j=0$), we have $S[i,j] = A[i][j]$.

  Now for the general case. Again, if $A[i][j]=0$, then $S[i,j]=0$,
  so we'll only consider the case where $A[i][j]=1$. There is a
  parking space of size $x$ with bottom-right corner at $(i,j)$ if and
  only if there are three (overlapping) spaces of size $x-1$ at each
  of the locations $(i-1,j)$, $(i,j-1)$, and $(i-1,j-1)$. Thus, the
  largest possible parking space is
  \[ S[i,j] = 1 + \min(\ S[i-1,j]\ ,\ S[i,j-1]\ ,\ S[i-1,j-1]\ ) \]

  The desired answer is $\max_{i,j} S[i,j]$, which requires $O(n^2)$
  to compute.

  There are $n^2$ subproblems, and each takes $O(1)$ time to solve,
  for a time of $O(n^2)$. This, added to the $O(n^2)$ to extract the
  desired answer, gives a total $O(n^2)$ running time, which is
  clearly optimal because all the data must be examined.
}

% don't \clearpage on the last page, or else the totalpages label gets
% messed up
% (surely there's a better way...)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\label{totalpages}

\ifsolutions
\else

\newpage

\pagestyle{empty}

\begin{center}
SCRATCH PAPER
\end{center}

\newpage

\begin{center}
SCRATCH PAPER
\end{center}

\fi

\end{document}
