Question

Remarks: In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.

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. Is your solution an example of divide and conquer or dynamic programming? Hint: Think on solution with the root and solution without the root.

Answer 1

Any euler path in a directed graph exists if for every subset Q, number of edges u --> v such that u belongs to Q but not v equals to the number of edges u --> v such that v belongs to Q but not u.

The condition actually exists when all vertices of the directed graph with degree greater than 0 belongs to strongly connected component of the graph and the inner and outer degrees of every vertices are same.
To compare them , the inner and outer degrees should be stored in an empty stack and by traversing all the vertices one by one.

Outer degree = number of vertices going out the vertices
inner degree = number of vertices coming to the vertex

This way the euler path can be find out in O(|V|+|E| complexity.