Solution

Statement-I: TRUE: Insertion sort runs faster than merge sort if input sequences are already sorted. The insertion sort time complexity depends on input sequence because the best case time complexity of insertion sort is O(n).

If all elements are sorted then insertion sort will take only O(n) time but merge sort will take O(nlogn) irrespective of input order.

Statement-II: TRUE: Heap and selection sort time complexity will not depend on input sequence because it remains same for best, average and worst case time complexity.

Heap sort will take O(nlogn) time for best, average and worst case time complexity.

Selection sort will take O(n^2) time for best, average and worst case time complexity.

Statement-III: TRUE: Heap sort and Quicksort are not stable algorithms.

Solution

Solution

The given function is a combination of nested and independent loops.

→ ith and jth loops are nested.

→ kth and mth loops are nested.

The above nested loops are independent to each other.

When there are nested loops, we are multiplying the values and summing the independent loops.

void Bob()

{

int i,j,k;

for(i=0; i<n*n; i++) → T(n*n)

for(j=0; j<i; j++) → T(n*n)

printf(“GATE 2021”); → T(1)

for(k=0; k<n*n; k++) → T(n*n)

for(m=0; m<k*k; m++) → T(n*n*n*n)

printf(“GATE 2021”); → T(1)

}

Time complexity for above code segment is

=T(n*n)*T(n*n)*T(1) + T(n*n*n*n) * T(1)

=O(n^4) + O(n^6)

=O(n^6)

Solution

Solution

The question looks very big but the concept behind it is very simple.

We are given a complete graph and every edge weight is the same. So, no need to use Kirchhoff's theorem to find the number of minimum spanning trees.

Step-1: There are total n(n-1)/2 edges. So, it is a complete graph.

Step-2: Total 10 edges and all edges are having the same weight.

Step-3: If all edges are having the same weight. The total number of spanning trees are n^(n-2)

Step-4: 5^(5-2) = 125 Spanning trees are possible.

Solution

Recurrence relation is T(n)<=T(⌊n/2⌋)+constant value, where n>0.

We can also write it as T(n)=T(n/2)+ 1

Using masters theorem. a=1, b=2,k=0,p=0

⇒ a=b^k

⇒ O(log₂n)

Solution

Primary Clustering is the tendency for a collision resolution scheme such as linear probing to create long runs of filled slots near the hash position of keys.

→ If the primary hash index is x, subsequent probes go to x+1, x+2, x+3 and so on, this results in Primary Clustering.

→ Once the primary cluster forms, the bigger the cluster gets, the faster it grows. And it reduces the performance.

Secondary Clustering is the tendency for a collision resolution scheme such as quadratic probing to create long runs of filled slots away from the hash position of keys.

→ If the primary hash index is x, probes go to x+1, x+4, x+9, x+16, x+25 and so on, this results in Secondary Clustering.

→ Secondary clustering is less severe in terms of performance hit than primary clustering, and is an attempt to keep clusters from forming by using Quadratic Probing. The idea is to probe more widely separated cells, instead of those adjacent to the primary hash site.

Solution

Step-1: Initial max heap

Step 1: Insert 55 into farthest leaf node

Step 2:

Step 3:

The array of elements after insertion of element 55 is

The index 5 value is 36

Solution

The only difference in CPU Scheduling and this question is "All jobs should execute at a time".

In CPU scheduling we are executing either preemptive or non preemptive nature but here, we don't have that option.

We need to execute all jobs at a time. Job C is ecuting from 1 and end time is 4.

Job A is started from 2 but Job C is executing in the first machine so it can't execute. It requires another machine to execute the job A in parallel.

Likewise we have to execute all jobs parallelly.

Solution

P: Binary search tree → divide and conquer technique.

Q: 0/1 knapsack problem → Dynamic programming approach.

R: Huffman Coding → Greedy

S: Depth-first Search → Stack

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

The MST

→ Using Kruskal’s algorithm, arrange each weights in ascending order.

→ The first MST cost is 18 and second MST coast is 19

Solution

The optimal substructure of the LCS problem gives the recursive formula

X→ pqsprutrts

Y→ qrstupqrs

Length of the longest common subsequence = 5

Total number of longest common subsequences = 5

qrtrs

qrurs

qsprs

qstrs

qsurs

Solution

→ To delete random elements, we have to search for an element.

→ Binary heap follows linear search to search an element. So, it takes O(n) for searching time.

→ To delete an element it will take O(1) time.

→ To perform heapify( ) operation, it will take O(logn) time.

So, the overall time complexity to delete a random element is

= O(n)+O(1)+O(logn)

= O(n)

[ Note: O(n) because it is leading term. ]

Solution

Method-1:

Find the minimum and maximum independently, using n-1 comparisons for each, for a total of 2n-2 comparisons. In fact, at most 3⌊n/2⌋ comparisons are sufficient to find both the minimum and the maximum. The strategy is to maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.

Setting up initial values for the current minimum and maximum depends on whether n is odd or even. If n is odd, we set both the minimum and maximum to the value of the first element,and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison on the first 2 elements to determine the initial values of the minimum and maximum, and then process the rest of the elements in pairs as in the case for odd n.

Let us analyze the total number of comparisons. If n is odd, then we perform 3⌊n/2⌋ comparisons. If n is even, we perform 1 initial comparison followed by 3(n-2)/2 comparisons, for a total of (3n/2)-2. Thus, in either case, the total number of comparisons is at most 3⌊n/2⌋.

Given an even number of elements. So, 3n/2 -2 comparisons.

= (3*512)/2 -2

= 768-2

= 766

Method-2:

By using Tournament Method:

Step-1: To find the minimum element in the array will take n-1 comparisons.

We are given 512 elements. So, to find the minimum element in the array will take 512-1= 511

Step-2: To find the largest element in the array using the tournament method.

1. After the first round of Tournament , there will be exactly n/2 numbers =256 that will lose the round.
2. The biggest loser (the largest number) should be among these 256 loosers.To find the largest number will take (n/2)−1 comparisons =256-1 = 255

Total 511+255= 766

Solution

Original sequence:

20, 16, 1, 10, 13, 15, 9, 12, 11

Pass-1: 20, 16, 1, 10, 13, 15, 9, 12, 11

→ 16, 20, 1, 10, 13, 15, 9, 12, 11

16, 1, 20, 10, 13, 15, 9, 12, 11

16, 1, 10, 20, 13, 15, 9, 12, 11

16, 1, 10, 13, 20, 15, 9, 12, 11

16, 1, 10, 13, 15, 20, 9, 12, 11

16, 1, 10, 13, 15, 9, 20, 12, 11

16, 1, 10, 13, 15, 9, 12, 20, 11

16, 1, 10, 13, 15, 9, 12, 11, 20

Pass-2: 16, 1, 10, 13, 15, 9, 12, 11, 20

→ 1, 16, 10, 13, 15, 9, 12, 11, 20

1, 10, 16, 13, 15, 9, 12, 11, 20

1, 10, 13, 16, 15, 9, 12, 11, 20

1, 10, 13, 15, 16, 9, 12, 11, 20

1, 10, 13, 15, 9, 16, 12, 11, 20

1, 10, 13, 15, 9, 12, 16, 11, 20

1, 10, 13, 15, 9, 12, 11, 16, 20

Pass-3: 1, 10, 13, 15, 9, 12, 11, 16, 20

→ 1, 10, 13, 9, 15, 12, 11, 16, 20

1, 10, 13, 9, 12, 15, 11, 16, 20

1, 10, 13, 9, 12, 11, 15, 16, 20

Pass-4: 1, 10, 13, 9, 12, 11, 15, 16, 20

→ 1, 10, 9, 13, 12, 11, 15, 16, 20

1, 10, 9, 12, 13, 11, 15, 16, 20

1, 10, 9, 12, 11, 13, 15, 16, 20

Pass-5: 1, 10, 9, 12, 11, 13, 15, 16, 20

→ 1, 9, 10, 12, 11, 13, 15, 16, 20

1, 9, 10, 11, 12, 13, 15, 16, 20

Solution

Given is

LCS of X = zazrpzqrst and Y = arzazrsatq is arzrst

Note: If the string length is small better to go for bruteforce method, and start with tracing X array.

X = zazrpzqrst

Y = arzazrsatq

As per the above table we will have the length of the longest common subsequence. The Longest common subsequence length is 6.

As per the directions of elements we will find the total number of longest common subsequences. The subsequences are { arzrst , azzrst, zazrst }

X= Length of the longest common subsequence = 6

Y= Total number of longest common subsequences =3

= (5*6+4*3)%(6+3)

= ( 30 + 12 ) % 9

= 6

Solution

According to kruskal’s algorithm, we have to sort an edge weights in ascending order.

→ We have to connect the edges according to spanning tree properties.

→ The minimum cost spanning tree graph having only n-1 edges.

Solution

Solution

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.

→ We first merge 25 and 29 and get a list of 54 using 53 worst case comparisons.

→ Then we merge 35 and 40 into a list of 75 using 74 worst case comparisons.

→ Then we merge 55 and 54 into a list of 109 using 108 comparisons.

→ Finally we merge 109 and 75 using 183 comparisons. So the total number of comparisons is 53 + 74 + 108 + 183 which is 418.

= (54-1) + (109-1) + (75-1) + (184-1)

= 53 + 108 + 74 + 183

= 418

Solution

→ Dijkstra’s algorithm is used to shortest paths from node ‘0’ are

Paths

0

1→ 0-1

2→ 0-2

3 → 0-3

4 → 0-4

5 → 0-1-5

6 → 0-2-6

7 → 0-4-7

The edges 1-2, 5-6, 5-7and 3-7 are never used in any of the shortest paths.

Solution

→ Given the last element as pivot.

→ The quicksort gives worst case time complexity for two scenarios.

1. If all the elements are in sorted order
2. All elements are having the same number.

According to above scenarios t₁ gives worst case time complexity and t₂ also gives worst case time complexity.

→ It would be t₁=t₂

→ The number of recursive calls remains the same for t₁ and t₂

→ In every step of quick sort, numbers are divided as per the following recurrence:

T(n) = T(n-1) + O(n)

T(n) = T(n-1) + n

T(n-1) = T(n-2) + n-1

T(n-2) = T(n-3) + n-2

⋮

T(n) = T(n-2) + n-1 + n

T(n) = T(n-3) + n-2 + n-1 + n

T(n) = T(n-k) + K_n - K(k-1)/2

For base case:

n-k = 1

k = n-1 substitute in above

T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

∴ O(n^2)

Solution

→ As per above information, the total number of scalar multiplications are 627.

→ Optimal Parenthesization is : ((A(BC))(DE))

→ But according to the problem statement we are only considering (BC) and (DE) explicitly computed pairs.

Solution

Initial sequence:

Arrange according to descending order:

Step 1:

Step-2:

Step-3:

Step-4:

Step-5:

Step-6:

(40.11)+(10.40)+(30.16)+(40.09)+(20.24)

Step-7:

0.44+0.40+0.48+0.36+0.48=2.16

Step-8:

Solution

As per the given condition, we will get the graph

The MST is

Edge weights in MST

= 3 + 4 + 6 + 8 + 10 + 12 + 14 + … + *(2(n - 1))

= 1 + (2 + 4 + 6 + … till n-1 terms)

= 1 + 2(1 + 2 + 3 + 4 + ... + n-1)

These can be obtained by drawing graphs for these graphs

= 1 + (n-1)*n

=162-16+1

Solution

int Bob(n)

{

if (n == 1) → T(1)

Alice(); → T(1)

else → T(1)

John() + Bob(n-1); → T(logn)+T(n-1)

}

The recurrence relation is for the above code segment is

T(n) = T(n-1) + O(logn)

= T(n-2) + log (n-1) + log n

= T(n-3) + log (n-2) + log(n-1) + log(n)

:

:

:

= T(1) + log1 + log2 + log3 + ... + log(n)

= log(1*2*3*... *n)

= log(n!)

= O(n log n)

Note: logn^n = nlogn

Solution

The recurrence relation is

K(W, wt[ ], p[ ], n) = max{p[n-1] + K(W-wt[n-1], wt, p, n-1), K(W, wt, p, n-1)}

= 0 when n=0 or W=0

Solution

The recurrence relation for the travelling salesman problem is

Solution

We can get the letters with their frequency is

Arrange the letters in increasing order (or) decreasing order.

As per the given problem statement, we have to consider the Huffman tree code as the left child with ‘1’ and the right child with ‘0’ from every node.

Total bits = (1*11)+(2*8)+(3*4)+(3*6)

= 11+16+12+18

= 57

Average length = 57/29 = 1.9655

From above solution, we get

Given message is : 1001010001

Solution

Let us take example

Step 1:

j = 1

Key = 10

i = 0

Condition while(i > -1 && A[i] > Key)

i.e., 0 > -1 && 25 > 10 TRUE

then A[i + 1] = A[i]; // A[i] = 25

After step 1 the array is

Continuing the process until performing a sorted order.

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

Solution

I: TRUE: Given an array of elements are already in sorted order. Then we can apply binary search. Time complexity of binary search is O(log n)

II: FALSE: Radix sort uses counting sort as a subroutine.

III. TRUE: Dynamic programing is an algorithm paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. To solve dynamic programming problems we need the following two properties.

(1) Overlapping Subproblems

(2) Optimal Substructure

Consider the following example

int fib(int n)

{

if(n<=1)

return n;

return fib(n-1) + fib(n-2);

}

fib(4) = fib(3) + fib(2)

fib(3) = fib(2) + fib(1)

fib(2) = fib(1) + fib(0)

Here we are computing the same sub problem again and again i.e overlapping subproblems.