CS502 Final Term Solved Subjective

CS502 Fundamentals of Algorithms

Final TERM Subjective

Differentiate between back edge and forward edge Suppose you could prove that an NP-complete problem can not be solved in polynomial time. What would be the consequence?

Back Edge

A back edge connects a vertex to an ancestor in a DFS-tree. Note that a self-loop is a back edge. from descendent to ancestor (u, v) where v is an ancestor of u in the tree. DFS tree may only have a single back edge A back edge is an arc whose head dominates its tail (tail -> head) a back edge must be a part of at least one loop

Forward Edge

from ancestor to descendent (u, v) where v is a proper descendent of u in the tree. A forward edge is a non-tree edge that connects a vertex to a descendent in a DFS-tree. Edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the capacity and the flow

According to the question this means that the problem can be solved in Polynomial time using known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete. The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time.

Recursive explanation of dynamic programming. Formulate the problem into smaller sub problems, find optimal solution to these sub problems in a bottom up fashion then write an algorithm to find the solution of whole problem starting with base case and works it way up to final solution.

Answer: Dynamic programming is essentially recursion without repetition. Developing a dynamic programming algorithm generally involves two separate steps: Formulate problem recursively. Write down a formula for the whole problem as a simple combination of answers to smaller sub problems. Build solution to recurrence from bottom up. Write an algorithm that starts with base cases and works its way up to the final solution.

What is the cost of the following graph?

Cost =33

The computational problem is called the minimum spanning tree (MST) problem. Formally, we are given a connected, undirected graph G = (V, E) Each edge (u, v) has numeric weight of cost. We define the cost of a spanning tree T to be the sum of the costs of edges in the spanning tree

w(T) = Σ w(u, v)

(u,v)2T

A minimum spanning tree is a tree of minimum weight The first is a spanning tree but is not a MST; Let the adjacency list representation of an undirected graph is given below. Explain what general property of the list indicates that the graph has an isolated vertex. a  b  c  e b  a  d c  a  d  e  f d  b  c  f e  a  c  f f  c  d  e g

Answer: The main theorem which drives both algorithms is the following: MST Lemma: Let G = (V, E) be a connected, undirected graph with real-valued weights on the edges. Let A be a viable subset of E (i.e., a subset of some MST). Let (S, V − S) be any cut that respects A and let (u, v) be a light edge crossing the cut. Then the edge (u, v) is safe for A.

MST Proof: It would simplify the proof if we assume that all edge weights are distinct. Let T be any MST for G. If T contains (u, v) then we are done. This is shown in Figure 8.47 where the lightest edge (u, v) with cost 4 has been chosen.

Floyd Warshal algorithm with three recursive steps · 1. Wij = 0 if I = j · 2. Wij = w(i,j) if i != j and (i,j) belongs to E · 3. Wij = infinity if i != j and (i,j) not belongs to E · Answer