Consider the following pseudo code, a) Read in the graph and store the necessary
ID: 3727927 • Letter: C
Question
Consider the following pseudo code, a) Read in the graph and store the necessary information b) Find a topological order of the vertices, vi.v2, ., vn c) for (in 0; i--) d). f if vi does not have any children, fooli]0: e) else f) { foo[i] max(foo[J] + 1: for each edge ij } 9) geeli]-k where foo[k] is the largest among fooLjJs all edges i 2. ) Find the largest fooli], for i-1, 2, .., n j) Print out i, geeli], geelgeelill, gee[geelgeeli]]. (1) Apply this pseudo code to the graph in problem 1, what will be the output? (2) What is the meaning of foo ? (3) What is the meaning of geeli]? (4) Give a high level description of this pseudo code Gang Qu (gangqu@umd.edu)Explanation / Answer
In this pseudo code given , Solution for each question as follows
1) Apply the pseudo code on graph as follows
In this I’m trying to take one vertices to do complete
a) In the topology of vertices, starts from high vertices v8 (n=8)
b) Vertex v8 does not have children , so update foo[I] as 0
c) Repeat the process from next vertex v7, so n= 7
d) Vertex v7 has one child , mapping v7->v2, so coming to else block and update foo[7] = finding the maximum edge of the all child vertex of v7 as v2 only , so foo[I] = 2 , at i=7
e) next update the gee[i] at I=7 with largest among the all edges of foo[i] at I=7 , so gee[I] = foo[k] at k=7 , hence gee[i] = 2
f) Repeat the process for next vertices , keep on update foo and gee arrays
g) exit the loop
h) print the largest vertex in foo[]
i) print the gee[I]
2) foo[i] => for every ith vertex , it'll collect largest edge iterating over the n to 1
3) gee[i] => Index of the largest edge among the foo[i] (specific vertex max edge value) over the n to 1
4) Description: