Remarks: In all the algorithms, always explain their correctness and analyze their complexity. T

he complexity should be as small as possible.

A correct algorithm with large complexity, may not get full credit.

in Pseudocode

Question 1: Say that we are given a rooted tree so that any element in the tree has a profit. An independent set in the tree is a collection of vertices no two of which are a parent and a child. The goal is to find an independent set of maximum profit. Give an algorithm which finds the maximum profit independent set in the tree. Is your solution an example of divide and conquer or dynamic programming? Hint: Think on solution with the root and solution without the root