Solution

→ When we have duplicate edge weights in a graph then chances to get worse n^(n-2).

but in this graph we get maximum one unique MST.

→ Use kruskal’s algorithm to find MST

Step-1: Sort an edge weights

2,2,3,4,4,5,5,5,6,9,9,15

Step-2: Connect the edges according to MST properties

Solution

Dijkstra complexity:

O(V) inserts into priority queue

O(V) EXTRACT-MIN operation

O(E) DECREASE-KEY operations

Using Binary-heap:

O(logV) for extract min

O(logV) for decrease key

= O(VlogV+ElogV)

= O(ElogV)

Additional Information:

Using Fibonacci heap:

O(logV) for extract min

O(1) for decrease key

amortized cost

= O(V log V + E)

Using Array implementation:

O(V) time for extra min

O(1) for decrease key

= O(V.V+E.1)

= O(V^2 + E)

= O(V^2)

Solution

Binary Search → Divide and conquer

Kruskal’s algorithm → Minimum Spanning Tree

Breadth First Search Tree → O(V+E) using adjacency matrix

Job sequence with deadlines → O(V^2)

It is worth remembering time complexities of various algorithms in greedy techniques.

→ Topological Sort → O(V+E)

→ Prim’s algorithm using Fibonacci heap → O(E+VlogV)

→ Dijkstra’s algorithm using Min Heap → O((V+E)logV)

→ DFS → O(V+E)

→ Fractional knapsack problem → O(nlogn)

→ Job sequencing with deadlines worst case time complexity → O(n^2)

→ Prim’s Algorithm→ O(ElogV)

→ Kruskal’s algorithm→ O(ElogV)

→ Huffman Coding → O(nlogn)

→ Optimal Merge Pattern→ O(nlogn)

→ BFS → O(V+E)

Solution

The topological ordering will take O(V+E) time. Topological sorting is simply DFS with an extra stack. So time complexity is the same as DFS which is O(V+E) using an adjacency list.

The extra space is needed for the stack is O(V)

Solution

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

The strongly connected components are

1. Time complexity is O(V+E) because using DFS
2. We can find strongly connected components using kosaraju algorithm and Trojan’s algorithm

Solution

To get a fractional knapsack problem we always consider profit/weights and sort according to profit/weight result.

Object D, Knapsack Capacity = 40-5=35, Profit=25

Object G, Knapsack Capacity = 35-10=25, Profit=45

Object A, Knapsack Capacity = 25-10=15, Profit=26

Object C, Knapsack Capacity = 15-12=3, Profit=30

Object F, Knapsack Capacity = 3-3=0, Profit=(2*3=6)

The weight of the object F is greater than Knapsack capacity. So, consider the given problem statement.

Then the total profit= 25+45+26+30+6

= 132

Solution

Step 1: Arrange each task in descending order according to their profit.

Step 2: Deadlines 4 of T10and T5are actually colloids. So we are always decreasing by 1 cell until we get the free cell.

Like all the collision places we are placing into their corresponding location.

Step 3: Calculate all profits

= 55 + 50 + 45 + 40 + 35 + 30 + 25 + 20 + 15

= 315

Step 4: Scheduled tasks are

Solution

→ The Dijkstra's algorithm is a greedy algorithm and works when weights are all non-negative.

Logical representation:

Vertex Cost Path

0 0 0

1 3 0→1

2 5 0→2

3 2 0→3

4 8 0→2→4

5 6 0→1→5

6 6 0→2→6

7 4 0→3→7

Total cost for reaching Source node to all other nodes

= 0 + 3 + 5 + 2 + 8 + 6 + 6 + 4

= 34

Resulting graph:

Solution

Step 1:

Step-2:

Step-3:

110100 → M

1100 → I

11011 → T

110101 → H

Solution

We sort the objects based on profit/Weight Ratio in descending order and place it accordingly in the knapsack.

The objects are in sorted order according to their profits are: P,W,X,V,Q,R,T,S

Object P, Knapsack Capacity = 50-18=32, Profit=36

Object W, Knapsack Capacity = 32-10=22, Profit=18

Object X, Knapsack Capacity = 22-15=7, Profit=26

Weight of object V is greater than Knapsack capacity. So, just add a part of object V to 7.

The profit will be (7*32)/20=11.2

The Knapsack bag capacity=0

Then the total profit= 36+18+26+11.2= 91.2

→ We are not using Q,R,T and S objects to calculate maximum profit because of maximum capacity restriction.

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

Using the recurrence relation we will get

Solution

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

It is very easy if you understand the question clearly otherwise it is difficult to solve the problem.

→ In every cycle, the weight of an edge that is not part of MST must be greater than or equal to weights of other edges which are part of MST.

→ Since all edge weights are distinct, the weight must be greater.

We have

→ First we compare A-B, B-D and D-C values that are part of MST and distinct. So the minimum possible weight of AC is 7.

→ Second we compare E-G and G-F values that are part of MST and distinct. So the minimum possible weight of E-F is 10.

→ Third we compare B-E, B-D and E-F values that are part of MST and distinct. So the minimum possible weight of F-D is 13.

Therefore the minimum possible sum of weights is 72.

⇒ Total sum = 3 + 4 + 6 + 7 + 8 + 9 + 10 + 12 + 13

= 72