CS 261, Spring 2013, Homework 8, Due Thursday, June 6

1. In the lecture we described a linear-time algorithm for finding the
Cartesian tree for an array of numbers, but we also described a more
general definition of a Cartesian tree from another tree, that applies
to the problem of finding maximum-bandwidth paths. Prove that it is not
always possible to construct the Cartesian tree of a tree in linear time
(in a comparison model of computation) by showing that, if you could do
that, you could use the construction to sort arbitrary sets of n numbers
in linear time.


2. In a binary tree (that is, a tree where each node may have at most
one parent, at most one left child, and at most one right child),
suppose that we wish to route a message from node u to node v. Describe
how to use lowest common ancestor queries to determine in constant time
which of the three neighbors of u is the one on the shortest path to v.


3. A queue data structure has two update operations (enqueue and
dequeue) and one query operation (top). The sequence of values returned
by top as dequeue operations are made should be the same as the sequence
in which the same values were added to the queue by enqueue operations.
A non-persistent queue can be represented by two pointers (head and
tail) into a collection of nodes that each have "data" and "next"
instance variables, and in which the condition of being an empty queue
is represented by the tail pointer being null. To perform an enqueue
operation in an empty queue, a new node is created with the given data
value and with next=null, and head and tail are both set to point to it.
To perform an enqueue operation in a non-empty queue, tail.next is set
to be a new node, with the given data value and with next=null, and then
tail is set to point to the new node. To perform a dequeue operation, head is set
to head.next, and if this is null then tail is also set to null. To
perform a top operation, head.top is returned.

Now suppose that we want to make a queue persistent. Which of the two
techniques (fat nodes or path copying) would be more effective for this
representation of a queue? Explain why.