Suppose we are given an n-node rooted tree T, such that each node v in T is give

Question

Suppose we are given an n-node rooted tree T, such that each node v in T is given a weight w(v) R +. An independent set of T is a subset S of the nodes of T such that no node in S is a child or parent of any other node in S. Design an efficient dynamic programming algorithm to find the maximum-weight independent set of the nodes in T, where the weight of a set of nodes is simply the sum of the weights of the nodes in that set. For this question we need to write a pseudocode for your algorithm and show its running time.

Explanation / Answer

Answer:

set = {}
i = input.length - 1
while i >= 1
if input[i] == input[i - 1]
    i--
else
    set << vertex i
    i -= 2
end
end
return set

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.