\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newcommand{\ignore}[1]{}
\newcommand{\remark}[1]{[{\small{\bf Editorial Remark: }#1}]}

\newtheorem{defi}{Definition}[section] % Specify Definition
\newtheorem{problem}[defi]{Problem}      % Specify Lemma


\begin{document}
{\large
\noindent
Algorithms Core 15-750 \hfill PROBLEM SET \# 3 \hfill Spring 1999
\begin{center}
DUE: 1:00PM Wednesday March 3 1999 \\
\end{center}}

\ignore{
\section{Backwards Analysis for Quicksort}

Consider the following process.
Start with a row of $n$ coins, all showing heads.
The following step is repeated $n$ times until all
the coins are tails:
\begin{quote}
Pick a head (at random) and flip it so it becomes
a tail.  The cost of the operation is the length
of the run of heads immediately to the left plus
the length of the run of heads immediately to the
right.
\end{quote}
So if a step converts TTTHTTTTHHT to TTTTTTTHHT
its cost is 7.  And if the next step produces
TTTTTTTHTT, its cost is 1.

\begin{mylist}{(a)x}
\litem{(a)}
Use backward analysis to prove that the expected
cost of this random process is at most 
$2n H_n$.
\litem{(b)}
Show how the analysis of the process in part (a)
proves that the expected number of comparisons
done by quicksort on a randomly permuted file
of $n$ distinct keys is $2n H_n$.
(Recall that quicksort reorders the array of 
$n$ keys into those less than the pivot (the first element),
the pivot and those greater than the pivot.
It does this by comparing the pivot
with each of the $n-1$ other elements.
It then recursively sorts the stuff less then the
pivot and the stuff greater than the pivot.)
\litem{(c)}
(Optional) Modify your analysis to give a lower
bound on the expected number of comparisions done by quicksort.

\end{mylist}
}

\section{Backwards Analysis for Quicksort}

Consider the following randomized version of quicksort: Given an array
of $n$ keys as input, it first picks a pivot element at random from
among the $n$ keys.  It then reorders the keys so that those less than
the pivot are first, followed by those equal to the pivot, followed by
those greater than the pivot.  It does this by comparing the pivot with
each of the $n-1$ other elements.  It then recursively sorts the stuff
less then the pivot and the stuff greater than the pivot.

\begin{mylist}{(a):}
\litem{(a)}
Suppose that the $n$ keys to be sorted are distinct.  Using backwards
analysis show that the expected number of comparisons done by this
version of quicksort is at most $2 n (H_n-1)$.  (Here $H_n$ is the $n$th
harmonic number, which satisfies $H_n =
\ln n + \gamma +o(1)$, and $\gamma$ is Euler's constant
$\gamma=.57721\cdots$.

\litem{(b)}
(Optional) Show a lower bound on the expected number comparisons of
\[
2 n \ln n - O(n)
\]
\end{mylist}
 
Hint: Modify the algorithm (without changing the expected number of
comparisons) by capturing all of the randomness of the algorithm in a
random permutation, $A=a_1, \ldots, a_n$ of the keys.  In the forward
direction the algorithm runs through the keys $a_1, a_2, \ldots, a_n$
sequentially, using each of these in turn as a pivot element within the
appropriate sub-array.  You may also assume that the input is sorted
since this does not change the number comparisons performed.

\section{Hamiltonian Planar Graphs}

\ignore{
We would like you to construct a linear time planarity testing
algorithm. But to make the problem more tractable we will but some
restrictions on the problem. First we will assume the every node has
degree 3,.i.e., it is 3-regular. We make one further restriction.
}

Let $G=(V,E)$ an undirected graph with no multiple edges or
self-loops. A simple cycle in $G$ is called {\bf Hamiltonian} if includes
every vertex of $G$. 

A graph $G$ is called {\bf 3-regular} if every node has degree 3.

Give an $O(n)$ time algorithm takes as input a 3-regular graph $G$ and a
Hamiltonian cycle in $G$, and determines if the graph $G$ is planar.

Note: An edge $e$ with respect to a simple cycle $C$ is called a {\bf cord} if
it is not an edge of $C$ but both of its nodes are on $C$.  Thus, this
problem boils-down to the following problem: Given a simple cycle of
size $n$ and a collection of cords determine if the cords can be
embedded with no crossing using either the outside face or the inside
face.

Hint: Suppose the vertices are on the cycle in order are $v_1, \ldots,
v_n$. Let $V_i$ be the vertices $v_1, \ldots, v_i$ and $E_i$ be the
edges from $V_i$ to $V-V_i$ not including the edge from $v_n$ to
$v_1$. Give a data structure which represents all possible arrangements
of the edges in $E_i$ as we consider all planar embeddings of $G$
restricted to $V_i$.

\section{Series-Parallel Graphs}

A directed acyclic graph $G$ with two distinguished vertices $s,t$ is a
{\bf series-parallel graph} if it is obtained from the following
inductive definition:
\begin{enumerate}
\item
The graph consisting of a single edge from $s$ to $t$ is
series-parallel.
\item
If $G=(V,E,s,t)$ and $G'=(V',E',s',t')$ are series-parallel then   
\begin{enumerate}
\item {\bf [parallel]} the new graph obtained by identifying $s$ with $s'$ and
$t$ with $t'$ is series-parallel (with distinguished vertices $s$ and $t$)
\item {\bf [series]} the new graph obtained by identifying $t$ with $s'$
is series-parallel (with distinguished vertices $s$ and $t'$)
\end{enumerate}
\end{enumerate}


We extend the notion of an $f(n)$-separator to 
directed graphs simply by ignoring the directions of the
edges and applying the standard definition for undirected
graphs.

Show that every series-parallel graph has a 2-separator.  Also give an
$O(m+n)$ time algorithm to find this separator in a graph of $n$
vertices and $m$ edges.  You may assume that the series-parallel graph
is given to you with its underlying ``parse tree''.

\section{3-Coloring planar Graphs}

Give an $O(2^{c\sqrt{n}})$ time algorithm to 3-color a planar graph,
where $c$ is some fixed constant.

Hint: Use the Planar Separator Theorem.

\end{document}
