PREVIOUS YEAR SOLVED PAPERS - December 2015 Paper 3
- Option : C
- Explanation : Two activities are compatible if their starting time and finish time does not overlap i.e. their execution must not overlap and starting time of one process must be greater then or equal to second process. i.e. si ≥ fj or sj ≥ fi. So, option (C) is correct.
- Option : D
- Explanation : A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A sequence G is said to be a common subsequence of X and Y, if Z is a subsequence of both X and Y. Here X = <a, b, c, b, d, a, >, the sequences <b,c,a>, <c,a,b>, <b,c,b,a> are subsequences of X. Given a second sequence of symbols Y = <b, d, c, a, b, a>, then <b,c,a>, <c,a,b>, <b,c,b,a> are common subsequences to both X and Y. However, the longest common subsequence of X and Y is <b,c,b,a>
- Option : C
- Explanation : Floyd-Warshall algorithm utilizes dynamic programming to solve the all-pairs shortest paths problem on a directed graph in θ (V3) time.
