\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}
\newcommand{\remove}[1]{}

\addtolength{\topmargin}{-.25in}
\setlength{\textheight}{9in}

\begin{document}

\handout{ps3}{Problem Set 3}{February 15, 1994}

\pset{3}

{\bf Reading:\ }Maurer \& Ralston: Chapter 1.  Cormen, Leiserson \&
Rivest: Chapters 1 and 11 (Handout~\ref{clr-chaps1&11}).

\medskip

The problems are divided into oral problems (prefixed~``{\bf O}'') and
written problems (prefixed~``{\bf W}'').
Monday the 21st is a holiday, so you will not be asked to present them 
in tutorial.
The written problems are due at the beginning of class on Tuesday, February~22.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bigskip

\begin{problems}

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

\oproblem Imagine that you have an array $A[1\twodots n]$, and you
would like to implement two stacks using two pointers into the
array.  Moreover, you would like neither stack to run out of space
until the number of the elements in both stacks combined is~$n$.
Describe a simple and efficient implemention of the two stacks.

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

\oproblem Give code or pseudocode of an algorithm to merge two sorted
lists.  The algorithm should take two sorted lists of numbers as input
and produce a single sorted list as output.  Write another merging
algorithm in which the input and output lists are terminated with an
$\infty$ sentinel.  Compare the coding complexity of the two
algorithms.  What are the asymptotic ($\Theta$) running times of your
algorithms in terms of the total number of elements in the lists.

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

\oproblem 
Consider a multiple-array representation of a doubly linked list as
described in Chapter 11 of CLR (Handout~\ref{clr-chaps1&11}).  It is sometimes
desirable to maintain such a list in a compact fashion, using only the
first $m$ locations in the multiple-array representation if there are
$m$ items in the linked list.  In other words, the unused objects
always occupy the highest locations.  Explain how to allocate and free
objects in $\Theta(1)$ (constant) time per operation, preserving the
compact representation from operation to operation.  Recall that the
elements of a linked list need not be kept in any particular order.
Assume that there are no pointers to elements of the linked list
outside the list itself.  Can this method be made to work if the list
is singly linked?

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

\remove{
	\oproblem (Hard problem.) Devise a multiple-array representation of a
	doubly linked list so that the list can be traversed efficiently in
	both directions, yet only one link field is used per node.   
	The only requirement is that from any point in the list, you can 
	efficiently move to either the next element or the previous element.
	(\hint There are at least two clever methods, each of which makes 
	some minor but limiting assumptions. 
	The fields are, of course, modifiable, and you may use more than 
	one pointer.)
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Look at the {\bf while} loop in lines 5--7 of the
\proc{Insertion-Sort} procedure on page 3 of the CLR handout.  The
loop essentially executes a linear search backward through the sorted
array to find a place for the key.  Recall that unlike a linked list,
an array has its items in specific, consecutive locations in memory.
Can we replace this search with a binary search (see M\&R, page 129)
to improve the worst-case running time of insertion sort
to $\Theta(n\lg n)$ for sorting $n$ numbers?
How does the answer change if the items to be sorted were stored in a 
linked list rather than an array?

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem{\bf Euclid's Algorithm for GCD.} The greatest common divisor
of two natural numbers $a$ and $b$, denoted $\gcd(a,b)$, is the
largest natural number that (evenly) divides both.  We write $d\mid a$
if $a=kd$ for some natural number~$k$.  Euclid's algorithm for
computing $\gcd(a,b)$ is

\codebox{
\<  $\proc{Euclid}(a,b)$\\
\li \If $b=0$\\
\li \Then \Return $a$ \\
\li \Else \Return $\proc{Euclid}(b, a \bmod b)$
}

where $a\bmod b)$ is the remainder when $a$ is divided by~$b$.
As an example, the computation of $\proc{Euclid}(30,21)$ 
makes three recursive calls:
\begin{eqnarray*}
\proc{Euclid}(30,21) & = & \proc{Euclid}(21, 9)\\
& = & \proc{Euclid}(9, 3)\\
& = & \proc{Euclid}(3, 0)\\
& = & 3.
\end{eqnarray*}
Prove this algorithm is correct by first showing
\[
\gcd ( a,b) \mid \gcd \left( b, a\bmod b\right)
\] 
and 
\[
\gcd \left( b, a\bmod b\right) \mid \gcd (a,b)
\] 
to conclude $\gcd ( a,b) = \gcd \left( b, a\bmod b\right)$,
and then arguing that the algorithm must terminate.

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

\oproblem
The following algorithm partitions an array $A[1 \twodots n]$
into two regions, $A[1\twodots i]$ and $A[i+1\twodots n]$, such that
every element in the first region is less than or equal to an input
value $x$, and every element in the second region is greater than~$x$.

\codebox{%
\<$\procdecl{Partition}(x, A)$\\
\li $i \gets 0$\\
\li \For $j\gets 1$ \To $n$\\
\li \Do \If $A[j] \leq x$\\
\li \>\>\Then $i\gets i+1$\\
\li \>\>\>\>exchange $A[i] \leftrightarrow A[j]$\\
\li \Return i
}

\begin{problemparts}

\problempart Argue that \proc{Partition} is correct.

\problempart What is the maximum number of times that any single
element can be moved by \proc{Partition}?

\problempart Argue that \proc{Partition} runs in $\Theta(n)$ time on
an $n$-element array.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	\oproblem
%	Topological sort algorithm?
%
%	PS2 asked to prove the existence of an ordering;
%	the best way to do that is with an algorithm,
%	so this would be a little redundant.

%	\oproblem	% MINIMUM SPANNING TREE?
%	Recall that any connected graph $G$ contains a free tree as a subgraph.
%	Such a tree is called a {\em spanning tree} for $G$.

%	\oproblem	% BINARY SEARCH TREES--INORDER WALK?


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

\newpage
\oproblem {\bf Radix sort.} Suppose that you have the complete set of
792 Topps baseball cards, and you would like to put them in numerical
order.  Each card has a photo on the front and a unique number on the
back.  You could sort them by the hundred's digit first, and then sort
each of the resulting ten sets by the ten's digit, and so on, but that
would create too many intermediate piles and too much confusion.

Instead, you use the following algorithm.  First, you partition the
cards into ten piles according to the {\em one's\/} digit.  Then, you
stack the piles face-up, with the 0's pile on top and the 9's pile on
bottom.  You repeat the procedure, sorting this time by the ten's
digit, going through the cards from top to bottom and placing each
card {\em face-down\/} in its proper pile.  Placing the cards
face-down maintains the relative order of cards that have the same
digit in this round of sorting.  (Sorting algorithms with this
property are called \defn{stable}.)  Finally, you repeat for the
hundred's digit.

Generalize this algorithm to an arbitrary number of digits.  Use
induction on the number of digits to prove that the algorithm properly
sorts the cards.


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	WRITTENS:

\newpage

\wproblem Read Section 3.8 of M\&R, which gives three systematic
methods to process all nodes in a binary tree: preorder, inorder, and
postorder tree walks (or tree traversals).
\begin{problemparts}

\problempart Ignoring internal nodes of a binary tree, how do the
orders that leaf nodes are processed differ among the three methods?

\problempart Using a stack, give a {\em non}recursive algorithm to
perform an inorder walk of the nodes in a binary tree.
Asymptotically, how large a stack do you require as a function of some
parameter of the binary tree?

\problempart One node $u$ is an \defi{ancestor} of another node $v$ in
a binary tree if the unique simple path from the root of the binary
tree to $v$ contains $u$.  (Thus, by this definition, $u$ can be its
own ancestor.)  Prove that if $u$ and $v$ are nodes in a binary tree,
%%	should add  $u \neq v$  
then $u$ is an ancestor of $v$ if and only if $u$ precedes $v$ in
preorder and $u$ follows $v$ in postorder.

\end{problemparts}

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

\wproblem
A string of parentheses and brackets is said to be {\em well
formed} if the parentheses and brackets ``match up'' correctly, as for
example, they do in the string $[\,(\,(\,)\,[\,]\,)\,]$ but not in the
strings $[\,(\,(\,)\,]\,)$ and $[\,[\,(\,)\,]$.  Formally, we can give
an inductive definition for well-formed strings.  A string $w$ of
parentheses and brackets is well formed if
\begin{enumerate}
\item	$\ w = (\,)$ or $w = [\,]$, or
\item	$\ w = (\,v\,)$ or $w = [\,v\,]$, where $v$ is well formed, or
\item	$\ w = u\,v$, where $u$ and $v$ are well formed.
\end{enumerate}
%	\note{Is this too hard?  What are we asking for?}
%	\note{Simply push the left's on and pop when a right is seen...no?}

\begin{problemparts}

\problempart
Give a simple algorithm using a stack for testing whether a string of
parentheses and brackets is well formed.  

\problempart
Sketch a correctness proof for your algorithm.  

\problempart
What is the asymptotic ($\Theta$) worst-case 
running time of your algorithm on a string of length~$n$?

\end{problemparts}

%	\wproblem (Knuth)  Determining which permutations are computable
%	with a stack.   (Well-formed parenthesizations; catalan number.)

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

\wproblem You have a collection of $n$ boxes that have the same
dimension but distinct weights.  Suppose you wish to find the heaviest
of $n$ boxes using only a balance which can tell you which of two
boxes is heavier.  A \defi{comparison} consists of using the balance
to compare the weights of two boxes.

\begin{problemparts}

\problempart Give an algorithm for determining the heaviest box using
$n-1$ comparisons.

\problempart
%Prove that fewer than $n-1$ comparisons are not sufficient to
Prove that $n-1$ comparisons are necessary to
determine the heaviest box in the worst case.
Argue by looking at a directed graph on $n$
nodes---one node for each box---with an edge from node $u$ to node $v$
if a direct comparison showed that box $u$ was heavier than box~$v$.

\problempart Give an algorithm for determining both the heaviest {\em
and the second-heaviest} boxes using only $n+\lg n -2$ comparisons.
%	(\hint Single-elimination playoffs.)

\problempart Give an algorithm for determining both the heaviest and
the lightest boxes using only $\ceil{3n/2}-2$ comparisons.  
%	(\hint Process the boxes 2 at a time.)

\end{problemparts}




\end{problems}


\end{document}


