Solution

As per the inversion definition, we have to consider the

18 > 4, 18 > 12 , 18 > 15 → 3 inversions

38 > 19, 38 > 12, 38> 15, 38 > 22 → 4 inversions

19 > 12, 19 > 15 → 2 inversions.

12, 15, 22, 55, 100, 200 are in ascending order, so we won’t get single inversion from these elements.

Total= 3 + 4 + 2

= 9

Key points in inversion array:

1. If the array is already sorted then the inversion count is 0.

2. If the array is sorted in reverse order that inversion count is the maximum.

Time Complexity: Using divide and conquer we will get O(n log n).

Space Complexity: No extra space is required for this algorithm.

Solution

Solution

Step-1: Initial heap structure

Step-2: To convert max-heap, we need to perform max-heapify().

Solution

Hash table has 9 slots.

h(k) = k mod 9

Collisions are resolved using chaining.

Keys: 15, 20, 25, 30, 35, 40, 45

15%7 → 1

20%7 → 6

25%7 → 4

30%7 → 2

35%7 → 0

40%7 → 5

45%7 → 3

Maximum chain length is 1

Minimum chain length is 1

[ Note: We have to calculate the address of the pointer. So, the minimum chain length is 1 ]

Solution

h(14)= ((10*14)+3) mod 7 = 143 mod 7 = 3

h(12)= ((10*12)+3) mod 7 = 123 mod 7 = 4

h(18)= ((10*18)+3) mod 7 = 183 mod 7 = 1

h(31)= ((10*31)+3) mod 7 = 313 mod 7 = 5

h(20)= ((10*20)+3) mod 7 = 203 mod 7 = 0

h(22)=((10*22)+3) mod 7 = 223 mod 7 = 6

h(2)=((10*2)+3) mod 7 = 23 mod 7 = 2

Solution

Given h(k,i)=h1(k)+ih2(k)

where h1(k)=k mod m

h2(k)=1+k mod n

where n=m-2 and m=501. For k=15150

h₁(k)=15150 mod 501

h₁(k)=120

h₂(k)=1+(15150 mod 499)

h₂(k)=1+180

=181

1st probe: i=1

h(k,i)=h₁(k)+ih₂(k)

h(k,1)=h₁(k)+1*h₂(k)

h(k,1)=120+181

=301

h(k,1)=301

2nd probe: i=2

h(k,i)=h₁(k)+ih₂(k)

h(k,2)=h₁(k)+2*h₂(k)

h(k,2)=120+2*181

h(k,2)=120+362

h(k,2)=482

∴ Difference: h(k,2)-h(k,1)

= 482-301

=181

Solution

Solution

Since swaps are done between adjacent elements only. So this is nothing but Bubble sort.

In Bubble sort, the maximum number of swap is done when the elements are in non increasing order (or) descending order.

{100,100, 100, 100, 100, 50, 50, 50, 50, 25, 25, 25 }

Pass 1 - 7 swaps

→ 100, 100, 100, 50, 100, 50, 50, 50, 25, 25, 25 → Swap-1

→ 100, 100, 100, 50, 50, 100, 50, 50, 25, 25, 25 → Swap-2

→ 100, 100, 100, 50, 50, 50, 100, 50, 25, 25, 25 → Swap-3

→ 100, 100, 100, 50, 50, 50, 50, 100, 25, 25, 25 → Swap-4

→ 100, 100, 100, 50, 50, 50, 50, 25, 100, 25, 25 → Swap-5

→ 100, 100, 100, 50, 50, 50, 50, 25, 25, 100, 25 → Swap-6

→ 100, 100, 100, 50, 50, 50, 50, 25, 25, 25, 100 → Swap-7

Pass 2 - 7 swaps

Pass 3 - 7 swaps

Pass 4 - 7 swaps

Pass 5 - 7 swaps

Pass 6 - 3 swaps

Pass 7 - 3 swaps

Pass 8 - 3 swaps

Pass 9 - 3 swaps

Pass 10 - 0 swaps

Pass 11 - 0 swaps

Pass 12- 0 swaps

Total swaps = 47

Note: This question looks difficult but if you understand the concept of bubble sort then it will become an easy one.

Solution

38 is an ancestor of 26, so 26 must have come after 38. In the tree only, ancestor descendant relationships matter in determining the order in which elements arrive. An ancestor must always come before any of its descendants. Incomparable elements could come in any order.

Solution

P: FALSE: Suppose, when we make random choices, we cannot rule out the worst case behaviour, which is O(n2).

Worst case possibilities are mainly two

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

Q: TRUE: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

R: TRUE: All of the keys could hash to the same bucket (chaining), or all of the keys could have the same probe sequence (open addressing), resulting in a worst-case time of O(n) for a search.

Solution

P: Given array is divided into k parts and each of size (n-a) . Thus the size reduces to T(n-a), and there are k sub problems. So overall time complexity is T(n) = k * T(n-a) + O(1)

Q: Apply binary search algorithm.

First check whether the middle element is (A[mid] = mid) or not. If it is, then return it; otherwise check whether the index of the middle element is greater than value at the index. If the index is greater, then (A[i] = i) lies on the right side of the middle point . Else the A[i] =i element lies on the left side.

Solution

Option-A: FALSE: Sorting using quicksort will take O(n^2) time in worst case

Option-B: FALSE: Merging will take O(n) time and O(n) space

Option-C: FALSE: Binary search only works on a sorted array

Option-D: TRUE: We can simply index to binary search the element in the odd positions, and in the even positions separately.

This will take O(logn) + O(logn) =O(logn) time and O(1) space in the worst case.

Solution

There are n/k sequences and each sequence is of size k. so to sort each sequence we need klogk time and the total time for all the sequences is n/k(klogk) which is nlogk.

Solution

P: TRUE. The minimum number of elements in a heap of depth d is one more than the maximum number of elements in a heap of depth (d − 1). Since a level at depth d in a binary heap can have up to 2^d elements, the number of elements at depth (d − 1) is

So the minimum number of elements in a heap of depth d is (2^d − 1) + 1 = 2^d

Q: FALSE. The maximum element in a min-heap can be anywhere in the bottom level of the heap. There are up to n/2 elements in the bottom level, so finding the maximum can take up to O(n) time.

R: TRUE. Simply traverse each heap and read off all 2n elements into a new array. Then, make the array into a heap in O(n) time by calling MAX-HEAPIFY for i = 2n down to 1.

S: TRUE. In fact, we can build a heap in O(n) time by putting the elements in an array and then calling MAX-HEAPIFY for i = n down to 1.

Solution

I. False. The auxiliary sorting routine in radix sort needs to be stable, meaning that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array.

II. True. Simply call BUILD-HEAP at the root, which runs in O(n) time.

III. False: Merge sort is stable whenever the underlying merge operation always breaks ties by selecting from the left sub-array, and it is easy to ensure that this is the case.