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.

→ Prim’s Algorithm→ O(ElogV)

→ Kruskal’s algorithm→ O(ElogV)

→ Huffman Coding → O(nlogn)

→ Optimal Merge Pattern→ O(nlogn)

→ BFS → O(V+E)

→ 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)

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

Solution

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:

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

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

Solution

Message = AAANNNAAAANNNDDDSSQ

Step 1:

Step-2:

Solution

→ To merge two lists of size m and n, we need to do m+n-1 comparisons in the worst case. Since we need to merge 2 at a time, the optimal strategy would be to take the smallest size lists first.

→ The reason for picking the smallest two items is to carry minimum items for repetition in merging.

→ Merge 25 and 29 and get a list of 54 using 53 worst case comparisons.

→ Merge 35 and 40 into a list of 75 using 74 worst case comparisons.

→ Merge 55 and 54 into a list of 109 using worst case 108 comparisons.

→ Merge 60 and 75 into a list of 135 using worst case 134 comparisons.

→ Merge 109 and 135 into a list of 244 using worst case 243 comparisons.

The total number of comparisons is (54-1) + (75-1) + (109-1) + (135-1) + (244-1)

= 53 + 74 + 108 + 134 + 243

= 612

Solution

I. TRUE: It takes O(1) time to add/remove an edge in an adjacency matrix. In an adjacency list, you need O(δ(v)) time for both operations, where δ(v) is the number of neighbours of node v. δ(v) = O(V)

II. TRUE: There are V extract-min operations, and E decreases key operations for the Dijkstra’s algorithm using priority queue. So, time complexity is O(V√V) + E log log V)

Solution

P: TRUE: The sum of distinct weights of the minimum spanning trees obtained by Prim's and Kruskal's algorithm are always equal.

Ex:

Solution: By using Prim’s and Kruskal’s

Q: TRUE: In Huffman Coding, the item with the highest probability is always at the leaf that is closest to the root

Ex: A:5, B:5, C:2 and D:1

R:TRUE. Both algorithms are guaranteed to produce the same shortest path weight, but if there are multiple shortest paths, Dijkstra’s will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.