The lexicographical  ordering of strings is the alphabetical ordering you find in the dictionary.  Individual characters are ordered by the alphabet a < b < c < . . . < z . When we compare two strings s1  and s2  we will say that s1  ≤ s2  if

• s1  is a prefix of s2  (e.g. s1  = cat and s2  = catapult), or

• s2  is not a prefix of s1   and the first position i such that s1 [i]  s2 [i] satisfies s1 [i] < s2 [i] (e.g.  s1  = catalog and s2  = catnip.  Here i = 4 and s1 [4] = a while s2 [4] = n)

(a) Give an algorithm for the following problem: Input is a directed graph G = (V,E),

two vertices s and t in G, and a function z that assigns to every edge e ∈ E a string z(e) (using lower case characters from the English alphabet).                    The algorithm should ouput a path P from s to t in G such that the lexicograph- ically largest word w in the set {z(e)  :  e ∈ E(P)} is as (lexicographically) small as possible.

The algorithm does not need to produce the path P itself, it is sufficient to output the lexicographically largest word w on P .  ( Faster algorithms in terms of big- oh will be rewarded more points,  assuming that they always produce the correct answer. )

Figure 1:  The s-t path whose lexicographically largest word is as small as possible is s-c-e- d-a-t, and its lexicographically largest word is dog. All other s-t paths use at least one word lexicographically larger than dog.

(b) Give a brief justification of the correctness of your algorithm.

(c) What is the running time of your algorithm, assuming that two strings can be compared in O(1) time?

2. Faulty Dijkstra (10%) Let G be a directed graph with vertices s,a,b,t and edge set E = {sa,sb,ab,at,bt}. Assign weights to the edges of E(G) such that (i) all edge weights are non-negative except for one edge, which gets weight −10, and (ii) Dijkstra’s algorithm, when run on G with the assigned edge weights, fails to compute the shortest s-t path.

Your task: write out the weights of the edges in E satisfying the specifications above, and explain why Dijsktra fails with these weights.

3. Alternative Union Find (55%)

A rooted binary tree is full if every non-leaf v of T has precisely two children, denoted by left(v) and right(v) respectively.

Let T be a full rooted binary tree. For each vertex v in T we define s(v) as the number of vertices in the sub-tree rooted at v .  Thus, for every leaf ℓ we have s(ℓ) = 1 while the root r of the tree has s(r) = n.

We also define a function P that assigns to each vertex v of T a set of leaves of T as follows.  If v is a leaf, then P(v) = ∅.  If v is a non-leaf, and s(left(v)) ≥ s(right(v)) then P(v) is the set of leaves of the sub-tree of T rooted at right(v). Othwerwise (that is, if v is a non-leaf, and s(left(v)) < s(right(v)) ) then P(v) is the set of leaves of the

sub-tree of T rooted at left(v). Finally, for every vertex v, we define p(v) = |P(v)|.     Hint:  In this task you may assume the statements of the previous sub-tasks without proof when proving all subsequent sub-tasks.

(a) For the tree in the figure below, compute s(v), P(v) and p(v) for every vertex v .

(b) Draw a full rooted binary tree T with 8 leaves such that Pv∈V (T) s(v) is as large as possible. Compute the value of Pv∈V (T) s(v) for the tree T that you drew.

(c) Draw a full rooted binary tree T with 8 leaves such that  v∈V (T)p(v) is as large as possible. Compute the value of    v∈V (T)p(v) for the tree T that you drew.

(d) Let T be a full rooted binary tree with t leaves. Prove that, for every leaf ℓ of T it holds that

t ≥ 2|{u∈V (T)  : ℓ∈P(u)}|

(e) Let T be a full rooted binary tree with t leaves. Let L be the set of leaves of T.

Prove that

  p(u) =       |{u ∈ V (T)  :  ℓ ∈ P(u)}|

u∈V (T)                   ℓ∈L

(f) Let T be a full rooted binary tree with t leaves. Prove that

  p(u) = O(tlog t)

u∈V (T)

(g) Consider the following implementation of the Union-Find data structure.   At

initialization it takes as input the size n of the universe U  =  {1, . . . ,n} and creates an array A of integers, with A[i] = i for all i ∈ U . It also creates an array L of lists of integers, and initializes L[i] = {i} for every i ∈ U .

The idea is that A[i] stores the name of the set that contains element i. Further L[i] contains the names of all the elements that are contained in the set named i. The Find(i) operation is implemented in the “obvoius” way:

It is clear that Find(i) takes constant time. On the other hand, Union(i,j) could take as much as Ω(n) time.