CS502 Final Term Solved Subjective with References by Moaaz

CS502_ Fundamentals of algorithm · Solved Subjective · From Final Term Papers · 10 July,2013 · PSMD01 · Q No.1

Suppose you could prove that an NP-complete problem cannot be solved in polynomial time. What would be the consequence?

Answer: Page 173 If we can solve a problem in polynomial time, we can certainly verify the solution in polynomial time. More formally, we do not need to see a certificate to solve the problem; we can solve it in polynomial time anyway. However, it is not known whether P = NP. It seems unreasonable to think that this should be so. Being able to verify that you have a correct solution does not help you in finding the actual solution. The belief is that P 6= NP but no one has a proof for this.

Q No.3 Describe Dijkstra‟s algorithm working?

Answer: (Page 154) Dijkstra’s algorithm is a simple greedy algorithm for computing the single-source shortest-paths to all other vertices. Dijkstra’s algorithm works on a weighted directed graph G = (V, E) in which all edge weights are non-negative, i.e., w(u, v) _ 0 for each edge (u, v) 2 E. Negative edges weights maybe counter to intuition but this can occur in real life problems. However, we will not allow negative cycles because then there is no shortest path. If there is a negative cycle between, say, s and t, then we can always find a shorter path by going around the cycle one more time.

Q No.8 Explain the topological sort?

Answer: (Page 133) A topological sort of a DAG is a linear ordering of the vertices of the DAG such that for each edge (u, v), u appears before v in the ordering. Computing a topological ordering is actually quite easy, given a DFS of the DAG. For every edge (u, v) in a DAG, the finish time of u is greater than the finish time of v (by the lemma). Thus, it suffices to output the vertices in the reverse order of finish times.

Q No.5 In the solution of edit distance technique, please describe two solution given

(i) MATHS (ii) ARTS

Answer: (Page 77)

Q No.7 Explain the following two basic cases according to Floyd-Warshall Algorithm,

1. Don‟t go through vertex k at all.
2. Do go through vertex k.

Answer: (Page 162)

Q No.6Variants of shortest path solution briefly?

Answer: (Page 153) There are a few variants of the shortest path problem. Single-source shortest-path problem: Find shortest paths from a given (single) source vertex s 2 V to every other vertex v 2 V in the graph G. Single-destination shortest-paths problem: Find a shortest path to a given destination vertex t from each vertex v. We can reduce the this problem to a single-source problem by reversing the direction of each edge in the graph. Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. No algorithms for this problem are known to run asymptotically faster than the best single-source algorithms in the worst case. All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can usually be solved faster.

What is the Running time of Bellman Ford Algorithm?

Bellman–Ford runs in O(|V|·|E|) time,

Define Forward Edge from ancestor to descendent (u, v) where v is a proper descendent of u in the tree.

Answer: (Page 130) For a forward edge (u, v), v is a descendent of u and so v’s start-finish interval is contained within u’s implying that v has an earlier finish time. For a cross edge (u, v) we know that the two time intervals are

What is the common problem in communications networks and circuit designing?

Answer: (Page 142) A common problem is communications networks and circuit design is that of connecting together a set of nodes by a network of total minimum length. The length is the sum of lengths of connecting wires. Consider, for example, laying cable in a city for cable t.v