\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}

\begin{document}
{\large
Algorithms Core 15-750 \hfill PROBLEM SET \# 5 \hfill Spring 1998
\begin{center}

DUE: 12Noon Friday 10 April 1998 \\
\end{center}}


Answer each question on separate sheets of paper for grading purposes.
Make sure that each page has your name and email address.

Make sure that each algorithm you consider includes the following
three bullets. 
\begin{mylist}{.1 in}
\item[DESCRIPTION:] A high level description of the algorithm.
\item[CORRECTNESS:] At least a high level outline of how the full proof 
would go. Possibly citing lemmas from class.   
\item[TIMING:] A timing analysis.
\end{mylist}
The algorithms will be graded based on what you put in each bullet.

\section{Making an edge separator into a vertex separator}

Suppose you are given a very good edge separator $S \subseteq E$ for
some graph $G=(V,E)$.  You are ask to convert it to a vertex separator
by picking a minimum number of vertices from the end points of $S$ so
as to ``cut'' all the edges of $S$ by removing at least one endpoint of
each edge in $S$.

Give an efficient algorithm to find such a vertex set.

Hint: Use flow or bipartite matching.




\section{Scans and polynomial evaluation}
Show how to evaluate a polynomial $f(x)=a_nX^n+ \cdots a_0$ in
constant time on an EREW PRAM augmented with unit time prefix
operators $+$ and$\times$. Note that in unit time you can construct a
vector of length $n$ with each equal to the same value, say zero.


\section{Ordered traversal of a tree}

Suppose that $T=(V,E)$ is a rooted tree embedded in the plane as a
planar graph.  Thus, the tree $T$ as planar graph has but one face. We
shall call the cycle of arcs on that face enumerated in
counter-clockwise order an {\bf Euler Tour} of $T$


Show how using the Euler Tour to find the following orderings of a
tree efficiently in parallel. Inorder, Postorder, Preorder.
Use these orderings to construct a unit time algorithm which determines
if one node is an ancestor of another. 
 
You may assume that the list ranking problem is $O(\log n)$ time and
$O(n)$ work. You may mark each arc as either pointing towards the root or
away from the root. In the case of inorder tarversl you may assume the
there is at most a left and a right child.
  
\end{document}