Algorithms Test 4

Concepts:

for i = 0 to m

{

for j = 0 to n

{

If there is match, A[i, j] = A[i – 1, j  – 1] + 1

If not match: max(A[i – 1, j], A[i, j – 1])

}

}

Let x = ‘10010101 and y = ‘010110110’

Table of longest common subsequence:

The time complexity to fill this 2D array is O(m × n).

• Minimum spanning tree uses Greedy approach to solve the problem
• Binary Search is an efficient searching algorithm that uses a divide-and-conquer approach to search ements in an sorted array.
• Dynamic Programming is used in Fibonacci numbers

Kruskal’s algorithm is one of the algorithms used to find a minimum spanning tree of a graph G. Following are the steps for it.

1. Sort all the edges according to their weight in non-decreasing order. Sorting of edges takes O(mLogm) time
2. Pick the smallest edge. This step is called find-union algorithm and it takes O(mLogn) time
   1. If it forms a cycle with the spanning tree formed so far, skip it and move on to the next edge in the order.
   2. If cycle is not formed, include this edge.
3. Repeat step no 2 until there are (V-1) edges in the spanning tree.

So overall complexity is O(mLogm + mLogn) time. The value of m can be atmost O(n²), so O(Logn) and O(Logm) are same. Therefore, overall time complexity is O(mlogm) or O(mlogn).

Concept:

If we multiply two matrices of order l × m and m × n,

then number of scalar multiplications required = l × m × n

Data:

A₁ = 10 × 5, A₂ = 5× 20, A₃ = 20 × 10, A₄ = 10 × 5

Calculation:

There are 5 ways in which we can multiply these 4 matrices.

(A₁A₂)(A₃A₄) , A₁A₂(A₃A₄), A₁ ((A₂A₃) A₄) , (A₁(A₂A₃))A₄, ((A₁A₂)A₃)A₄

Minimum number of scalar multiplication can be find out using A₁ ((A₂A₃)A₄)

For A₂A₃ (order will become 5 ×10) = 5 × 20 × 10 = 1000

For (A₂A₃)A₄ (order will become 5 × 5) = 5 × 10 × 5 = 250

For A₁ ((A₂A₃)A₄) [Order will become 10 × 5] = 10×  5 × 5 = 250

Minimum number of scalar multiplication required = 1000 + 250 + 250 = 1500

Concept:

A spanning tree is a subset of Graph G, which has all the vertices covered with a minimum possible number of edges. Spanning tree doesn’t have cycles and it cannot be disconnected.

Formula:

in a completed graph, number of spanning trees possible with V vertices = VV-2

Calculation:

number of vertices is 7

In a complete graph

\(|E| = \frac{V(V-1)}{2} = \frac{7(7-1)}{2} = 21\)

Therefore G is a complete graph K₇

Concepts:

If there is match, A[i, j] = A[i – 1, j  – 1] + 1

If not match: max(A[i – 1, j], A[i, j – 1])

Table of longest common subsequence:

Length of longest common subsequence = x = 4

Possible longest common subsequence = 1301, 1201 and 1210

∴ y = 3

x³ + y³ + 3x²y + 3xy² = (x + y)³ = (4 + 3)³ = 343

Using Dynamic programming:

20 rupee coin = 3 = 60 Rs

10 rupee coin = 1 = 10 Rs

4 rupee coin = 2 = 8 Rs

Total coin = 3 + 1 + 2 = 6

Using greedy approach

20 rupee coin = 3 = 60 Rs

10 rupee coin = 1 = 10 Rs

5 rupee coin = 1 = 5 Rs

1 rupee coin = 3 = 3 Rs

Total coins = 8

|8 - 6| = 2