Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS130A Homework 2

1. Word Path (35%)

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  = a while s2  = 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 PvV (T) s(v) is as large as possible. Compute the value of PvV (T) s(v) for the tree T that you drew.

(c) Draw a full rooted binary tree T with 8 leaves such that vV (T)p(v) is as large as possible. Compute the value of    vV (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

≥ 2|{uV (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:

 Algorithm 1 Find(i) return A[i] The Union operation is a bit more tricky: Algorithm 2 Union(i,j) a ← Find(i) b ← Find(j) if |L[a]| < |L[b]| then Swap(a, b) end if for x ∈ L[b] do A[x] ← a Append x to L[a] Delete x from L[b] end for

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

Your task: Describe a sequence of operations such that the last operation in this sequence is Union(1,n), and this operation takes Ω(n) time.

(h) Even though each individual Union operation can be slow, usually the operations

are much faster. We will analyze it as follows: Make a forest (a forest is a set of trees) whose leaves are the elements 1, . . . ,n.

For each Union operation that changes the data structure, we make a new vertex in the tree, the two children of this vertex are the two vertices corresponding to the sets the Union operation is merging.

For example, if n = 6, the sequence Union(1, 2), Union(2, 3), Union(2, 3), Union(6, 4), Union(1, 6) results in the following tree. We will call the resulting forest the union forest  Your task: Explain why the running time of a Union operation is upper bounded by O(p(x) + 1) where x is the node corresponding to the Union operation in the union forest.

(i) Show that Union operations are amortized O(log n) time.  In particular, prove that a sequence of t union operations takes at most time O(tlog t) in total.