3. [10 pts] (U) A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. "acef" is a subsequence of "abcdef." Consider the problem of finding the longest common subsequence of two sequences this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct. (G) You are given a complete binary tree onn 2d-1 vertices (for d 1), rooted at vertex r. Further, each vertex i in the tree is assigned a weight wi > 0. The problem is to find the k-vertex subtree1 (with 1 s k