You are given a rooted tree T = (V, E) with n nodes and the root...

Transcribed Image Text:

You are given a rooted tree T = (V, E) with n nodes and the root r. Each node u EV has an integer label 1(u). Suppose S CV. We say S is well-formed if for every u, v E S if u is an ancestor or the parent of v then l(w) ≤l(v). Let wf(T) be the maximum size of any well-formed set in T. (a) Show an example of a tree T with 5 nodes such that wf (T) = 1. (b) Suppose wf(T) = n - 1. Can you find the node with the smallest label using < n - 1 comparisons ? Explain why or why not. (d) Give a dynamic program to compute wf(T). 1. Determine the dynamic program DAG. 2. Determine the dynamic program recurrence. 3. Determine the running time and space usage. 4. Can you also find a set S such that |S| = wf(T)? You are given a rooted tree T = (V, E) with n nodes and the root r. Each node u EV has an integer label 1(u). Suppose S CV. We say S is well-formed if for every u, v E S if u is an ancestor or the parent of v then l(w) ≤l(v). Let wf(T) be the maximum size of any well-formed set in T. (a) Show an example of a tree T with 5 nodes such that wf (T) = 1. (b) Suppose wf(T) = n - 1. Can you find the node with the smallest label using < n - 1 comparisons ? Explain why or why not. (d) Give a dynamic program to compute wf(T). 1. Determine the dynamic program DAG. 2. Determine the dynamic program recurrence. 3. Determine the running time and space usage. 4. Can you also find a set S such that |S| = wf(T)?

Answer rating: 100% (QA)

a Example of a Tree T with 5 Nodes such that wfT 1 Consider a tree with a single path In this tree t... View the full answer