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

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

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

→ 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

Inorder traversal has the sequence of left-root-right.

And Binary search tree has the property that, for every node, the elements if left subtree are less that the noded value. Similarly the nodes in right subtree are always greater than the node.

Hence when we do inorder traversal of any such BST it will give a sorted sequence of elements. Take following example:

Inorder traversal of above tree is: 2, 9, 12, 16, 20

Solution

Inorder traversal of a binary search tree always produces the keys in increasing order.

But the question Reverse ordering of natural numbers are used i.e. 19 is assumed to be the smallest and 10 to be the largest. So the sequence in increasing order will be 19, 18, 17, 16, 15, 14, 13, 12, 11, 10. So, option (D) is correct.

Solution

The starting vertex can be any one of the N vertices. Once the starting vertex has been chosen, the next vertex can be chosen in N-1 ways, as every other vertex is directly connected to starting vertex.

Again next vertex can be picked in (N-2) ways.

next vertex can be picked in (N-3) ways.

…

….

Last vertex can be picked in 1 way.

Total number of DFS traversals = N * (N-1) * (N-2)* (N-3)....* 1 = N!

Solution

Preorder:

Inorder:

Answer:

E M X S B P N T H C W A

Solution

All give the same resultant AVL tree.

I)

II)

Solution

On the execution of first for loop, all the elements will be enqueued.

i=1 => dequeue 1, enqueue(2)

i=2 => dequeue 3, enqueue(4)

i=3 => dequeue 5, enqueue(6)

i=4 => dequeue 7, enqueue(8)

i=5 => dequeue 2, enqueue(4)

i=6 => dequeue 6, enqueue(8)

i=7 => dequeue 4, enqueue(8)

At the end of the execution only 8 will remain in the queue.

Solution

To count labeled trees, we can use above count for unlabeled trees.

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

Here, every unlabeled tree with n nodes can create n! different labeled trees by assigning different permutations of labels to all nodes.

Therefore,

Number of Labeled Tees = (Number of unlabeled trees) * n!

= [(2n)! / (n+1)!n!] × n!

For example for n = 3, there are 5 * 3! = 5*6 = 30 different labeled trees

Solution

Total number of distinct BST with n nodes(key)

B(5) = 1/(n+1) [2n C n]

= 1/(5+1) [10 C 5]

= ⅙ * 252

= 42

Solution

The variable y is initially assigned to refer to the same list as x.

The statement y += [4, 5] modifies the list in place, meaning that both x and y will reflect the change since they point to the same list.

Therefore, both x and y output [1, 2, 3, 4, 5].

Solution

The *a syntax unpacks the tuple args into positional arguments, and **k unpacks the dictionary k into keyword arguments.

The function func receives the arguments as func(1, 2, c=3, d=4), which matches its signature, so it prints 1 2 3 4.

Solution

The generator() function yields "Hello" and "World".

The next() function retrieves the next item from the iterator. The first two next(g) calls output "Hello" and "World".

The third next(g, "Done") provides a default value ("Done") that is returned when the generator is exhausted, avoiding a StopIteration exception.

Solution

The fun() function modifies the input list arr to store the cumulative sum. For each element arr[i], it adds the value of the previous element arr[i-1] to it. This operation results in each element representing the sum of all previous elements in the list.

Example: If arr = [1, 2, 3, 4], after the function runs, arr becomes [1, 3, 6, 10].

Solution

The function fun() swaps the elements at positions start and end. After swapping, it recursively calls itself with start + 1 and end - 1. This process continues until start is no longer less than end, which effectively reverses the segment of the list between these two indices.

Example: If arr = [1, 2, 3, 4, 5], start = 0, and end = 4, after the function call, arr becomes [5, 4, 3, 2, 1].

Solution

This function appears to simulate a game between two players who alternately take numbers from either end of the list arr. The goal is to maximize the difference between the sum of numbers picked by the first player and the sum of numbers

picked by the second player. The helper(l, r) function is a recursive function that computes the maximum possible score difference for the subarray arr[l:r+1].

When l > r, the subarray is empty, so the score difference is 0.

Otherwise, the function tries taking arr[l] or arr[r] and recursively calculates the result.

The max function ensures that the player chooses the option that maximizes their score.

For arr = [20, 30, 2, 2, 2, 10], the optimal strategy for maximizing the difference would lead to the output being 30.

Solution

This function recursively calculates a sum based on whether the number is even or odd.

If n is even, it adds n to the result and continues with n-1.

If n is odd, it skips adding n and instead calls the function with n//2.

For n = 10, the execution is as follows:

10 is even, so it adds 10 and continues with 9.

9 is odd, so it continues with 4.

4 is even, so it adds 4 and continues with 3.

3 is odd, so it continues with 1.

1 is odd, so it continues with 0.

0 returns 0.

So the final sum is 10 + 4 = 14.

Solution

This function calculates a value based on the difference between the first and last elements of the array, gradually shrinking the range.

If the current subarray has an even number of elements, it subtracts the first element from the last and adds the result to the recursive call on the reduced array.

If the subarray has an odd number of elements, it compares two recursive calls: one excluding the first element and one excluding the last element, taking the maximum of the two.

For the array [7, 1, 3, 4, 8, 2], the sequence of calls leads to a final result of 6.

Solution

This function iterates over the list, and depending on whether the index i is even or odd, it appends either the sublist from the start to i or from i to the end to the result. For even indices, it extends the result with the sublist lst[:i+1]. For odd indices, it extends the result with the sublist lst[i:].

For the list [1, 2, 3, 4, 5], this results in [1, 1, 2, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5].

Solution

The function fun multiplies the result by i, then divides by (i % 3 + 1) at each step.

For n = 6, the operation sequence is as follows:

For i = 2: result = 1 * 2 // 3 = 0

For i = 3; result = 0 * 3 // 1 = 0

For i = 4; result = 0 * 4 // 2 = 0

For i = 5; result = 0 * 5 // 3 = 0

For i = 6; result = 0 * 6 // 1 = 0

After all the iterations result remains "0".