Solution

P: TSP Space complexity using dynamic programming is O(n * 2^n)

Q: All pair shortest path problem using floyd warshall algorithm will take O(V^3)

R: Longest common subsequence takes O(m*n)

S: 0/1 knapsack using recursion tree time complexity is O(2^n)

Solution

A negative cycle is one in which the overall sum of the cycle comes negative.

Option A: C-D, D-H, H-G and G-C → -2 + 4 + 5 + -1 = 6 [positive]

Option B: C-D, D-H, H-J, J-I, I-F, F-G and G-C → -2 + 4 + 3 + 6 + 3 + -2 + -1 = 11 [positive]

Option C: C-D, D-H, H-J, J-G and G-C → -2 + 4 + 3 + -1 + -1 = 3 [positive]

Note: This graph doesn’t contain a negative weight cycle.

Solution

LCS of X = GOOGLE and Y = YAHOOE

The optimal substructure of the LCS problem gives the recursive formula

The sequence is OOE

Solution

We can get a maximum of 5 possible parentheses using standard dynamic programming method (or) using catalan numbers.

→ We can find all possible parentheses using catalan numbers.

Here, n=4 because there are 5 different possibilities.

Note: Catalan numbers start with 0 so we have to do (n-1) calculations.

= (2n)! / (n+1)!n!

= 5

The sequence are

Sequence-1: ((AB)C)D

Sequence-2: (A(BC))D

Sequence-3: (AB)(CD)

Sequence-4: A((BC)D)

Sequence-5: A(B(CD))

Solution

A: Prim’s algorithm→ Using greedy technique to solve MST

B: Bellman Ford algorithm→ Using dynamic programming technique to solve Single source. shortest path

C: Dijktra’s algorithm→ Using greedy technique to solve Single source shortest path.

D: Kruskal’s algorithm→ Using greedy techniques to solve MST.

E: Floyd Warshall→ Using dynamic programming technique to solve all pairs shortest path.

Solution

The recurrence relation for 0/1 Knapsack problem using bottom-up dynamic programming algorithm.

We have one more shortcut method to solve this problem. We will follow a fractional knapsack profit/weight approach and identify the objects higher precedence. Otherwise, difficult to calculate M*N matrix to find a solution for large capacities.

According to profit/weights, will calculate upto the end of capacity. If the capacity is not full then we will backtrack the values and check for another condition to fill the capacity.

So, The objects for calculation are C, E, D and B.

The profits are 25+16+27+12 = 80

Note: If we are not considering object “B” we will not get optimality. This method is easy to solve big capacity problems but before finalizing the result cross verify once.

Solution

Step 1: In this problem, we are applying bottom up dynamic programming technique. Recurrence relation for bottom-up dynamic programming.

Step 2: For calculation purpose, we are modifying node names into values

A→1, B→2, C→3, D→4, E→5, F→6, G→7, H→8, I→9, J→10, K→11, L→12

Step 3: Initially, the array will be

Here, destination value zero, because we are using bottom-up dynamic programming.

Step 4: Find out T[11] value using recurrence relation until we reach T[1].

Optimal path from source to destination: 1→3→7→10→12.

Solution

The recurrence relation to get minimum number of scalar multiplications are

We can get a maximum of 5 possible parentheses using standard dynamic programming method (or) using catalan numbers.

Given the matrices A,B,C,D

Assume the dimensions of A=d₀×d₁, etc..,

Below are the five possible parenthesizations of these arrays, along with the number of multiplications:

(AB)(CD) → d₀d₁d₂ + d₂d₃d₄ + d₀d₂d₄ → 300 + 378 + 540 = 1218

((AB)C)D → d₀d₁d₂ + d₀d₂d₃ + d₀d₃d₄ → 300 + 420 + 630 = 1350

(A(BC))D → d₁d₂d₃ + d₀d₁d₃ + d₀d₃d₄ → 210 + 350 + 630 = 1190

A((BC)D) → d₁d₂d₃ + d₁d₃d₄ + d₀d₁d₄ → 210 + 315 + 450 = 975

A(B(CD)) → d₂d₃d₄ + d₁d₂d₄ + d₀d₁d₄ → 378 + 270 + 450 = 1098

→ The minimum number of scalar multiplications are 975 and optimal parenthesization is A((BC)D)

Solution

→ According to the given problem statement Bob used a 0/1 knapsack and Alice used a fractional knapsack technique.

→ The recurrence relation for 0/1 Knapsack problem using bottom-up dynamic programming algorithm.

We have one more shortcut method to solve this problem. We will follow a fractional knapsack profit/weight approach and identify the objects higher precedence. Otherwise, difficult to calculate M*N matrix to find a solution for large capacities.

According to profit/weights, will calculate upto the end of capacity. If the capacity is not full then we will backtrack the values and check for another condition to fill the capacity.

So, The objects for calculation are C, E, D and B.

The profits are 25+16+27+12 = 80

Note: If we are not considering object “B” we will not get optimality. This method is easy to solve big capacity problems but before finalizing the result cross verify once.

→ Alice using a fractional knapsack to get maximum profit.

Alice maximum profit is 25+16+27+6+6.85=80.85

→ Difference between alice and bob is 80.85-80=0.85

Solution

Option-A: TRUE: By using kruskals, the edge weight 60 always present in the maximum cost spanning tree

Option-B: TRUE: The edge weights 60 and 50 always present in maximum cost spanning tree

Option-C: FALSE: The edge weight 10 may be present if any other higher weighted edge forms a cycle

Option-D: TRUE: There always is a unique maximum cost spanning tree possible for the above given weights. But may be different orderings are possible but always unique maximum cost.

Solution

Solution

Solution

For a subset of cities S ⊆ {1, 2, . . . , n} that includes 1, and j ∈ S, let C(S, j) be the

length of the shortest path visiting each node in S exactly once, starting at 1 and

ending at j.

Solution

→ If V is number of vertices in graph, then MST has maximum V-1 edges

→ Edges= 50-1= 49

→ The weight of each edge in G is increased by 5

→ Old weight of MST + [ Edges * Increment in weight of each edge ] = New weight of MST

→ 250+(49*5)

→ 250+245

→ 495

Solution

P: False. A bottom-up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster than a bottom-up implementation.

Q: False. The running time of a dynamic program is the number of subproblems times the time per subproblem. This would only be true if the time per subproblem is O(1).