Write an algorithm that, for a given tree T, calculates the maximum sum achievable across all sets S (where no two elements have a parent/child relationship). You only need to return the maximal sum and not a set of nodes that achieves it (for simplicity). What is the runtime and space complexity of the algorithm? Hint: For any given node n, come up with a recursive solution MAX-SUM(n, include) which calculates the maximum possible sum over a non parent/child subset S over a tree rooted at node n. The parameter 'include' determines if node n should be included in a set S or not (this impacts which of the descendants of n can be used). Note that the maximum sum for the entire tree is given by MAX-SUM(T.root, true) + MAX-SUM(T.root, false). Then, use dynamic programming techniques to avoid solving the same call to MAX-SUM more than once. Memoization can be done by adding two new fields to each node (n.maxSumNodelncluded and n.maxSumNodeExcluded).

Write an algorithm that, for a given tree T, calculates the maximum sum achievable across all sets S (where no two elements have a parent/child relationship). You only need to return the maximal sum and not a set of nodes that achieves it (for simplicity). What is the runtime and space complexity of the algorithm? Hint: For any given node n, come up with a recursive solution MAX-SUM(n, include) which calculates the maximum possible sum over a non parent/child subset S over a tree rooted at node n. The parameter 'include' determines if node n should be included in a set S or not (this impacts which of the descendants of n can be used). Note that the maximum sum for the entire tree is given by MAX-SUM(T.root, true) + MAX-SUM(T.root, false). Then, use dynamic programming techniques to avoid solving the same call to MAX-SUM more than once. Memoization can be done by adding two new fields to each node (n.maxSumNodelncluded and n.maxSumNodeExcluded).

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Similar questions

Please answer all questions in detail and with pseudo codes.
Use a recursion tree to determine a good asymptotic upper bound on therecurrence T(n) = 3T(n/2) + n. Use the substitution method to prove your answer.
What is the time complexity of functions foo() and bar() respectively in below given code snippets, given that n is the total size of the input and L and R are Vectors def foo(L, R): S = Vector() for x in L: if x in R: S.add_back(x) return S def bar(L, R): R_hash= HashTable() for r in R: R_hash.insert(r, False) S = Vector() for x in L: if R_hash.contains(x): S.add_back(x) return S O(N^2), O(N) O(N), O(N) O(N^2), O(N^2) O(1), O(N)
How do I do this using the recursion tree method? Thanks
Apply quicksort to sort the list E, X, E, R, C, I, S, E in alphabetical order.Draw the tree of the recursive calls made.
Solve using the recursion tree T(n) = 4T(n-1) + c, where c is a positive constant, and T(0)=0.
Redesign the topsort algorithm below so that it selects the last node in each iteration rather than the first. Please use python ad show all work so I can better understand the problem. def topsort(G): count = dict((u, 0) for u in G) for u in G: # The in-degree for each node for v in G[u]: count[v] += 1 Q = [u for u in G if count[u] == 0] S = [] while Q: u = Q. pop() S.append (u) for v in G[u]: count[v] -- 1 if count[v] # Count every in-edge # Valid initial nodes # The result # While we have start nodes... # Pick one # Use it as first of the rest # "Uncount" its out-edges # New valid start nodes? 0: == Q. append (v) # Deal with them next return S
Consider the following variation on MergeSort: instead of dividing a list (say, of integers) evenly (that is, half and half or half and half plus 1) at all levels of recursion, we choose to divide a list this way - a left list that consists of exactly one integer and a right list that consists of the remaining integers. The time-complexity of this variation of MergeSort is: (a) O(n log n) (b) O(n²) (c) O(n) (d) none of the above
Use the recursion tree method to solve the following recurrence T(n) by finding the tightest function f(n) such that T(n) = O(f(n)). T(n) ≤ 4.T(n/3) +0(n³)