   Data Structures (CS130N) Major May 2, 2001

Name:                                 Entry:                 Grp:

Note: Maximum marks: 120 (a mark a minute). Answer only in the space provided. 5 pages in all. All questions carry equal marks. Q7 is bonus and will be considered only if the others have been answered.

1.
Show that a binary tree can be uniquely reconstructed from its inorder and preorder traversal sequences. What is the time complexity?

2.
Let S be a set of distinct binary strings whose lengths sum up to n. Show how to sort S in time. Note that since the input parameter n is unknown you cannot use a static structure like an array.

3.
Consider a simple list based implementation of the abstract data type ClearableStack which supports the usual operations create, push, pop, isempty and an additional clearstack operation which clears a stack containing n elements in time. Show that a series of n of the above operations on an initially empty ClearableStack takes O(n) time.

4.
An Euler tour of a directed graph G with n vertices and m edges is a cycle that traverses each edge of G exactly once according to its direction. Such a tour always exists if the in-degree equals the out-degree of each vertex in G. Give an efficient algorithm for finding a Euler tour in such a graph G.

5.
Consider the following algorithm for finding the Euclidean minimum spanning tree of a graph:
Sort the points on their x coordinates, then find the minimum spanning trees of the first half and the second half, then find the shortest edge that connects them.''
Is the algorithm correct? If yes, give a proof and run time analysis; if not, give a proof that it doesn't work.

6.
Consider the following greedy strategy for finding a shortest path from a vertex start to a vertex goal in a given connected graph:
(a)
Initialize path to start.
(b)
Initialize VisitedVertices to .
(c)
If start = goal, return path and exit.
(d)
Find the edge (start,v) of minimum weight such that v is adjacent to start and .
(e)
(f)
(g)
Set start = v and go to step 3.
Is the algorithm correct? If yes, give a proof and run time analysis; if not, give a proof that it doesn't work.

7.
Bonus:
Consider the Bellman-Ford algorithm for finding the single source shortest path in a connected digraph: Prove the following:
If after performing the above computation there is an edge (u,z) that can be relaxed (that is D[u] + w(u,z) < D[z]), then the graph contains a negative weight cycle. Otherwise D[u] = d(v,u), the length of the shortest path from v to u for all u in the graph even if there are negative weights.   