Algorithms Test 2

Worst best-case complexity is for Merge sort and Quick Sort

Data: 

Total slots = total chain = 29

Average no. of elements stored in a chain = load factor = 175

Formula:

 \(load\; factor = \frac{Total\;elements}{number \;of \;slots}\)

Calculation:

\(130 = \frac{Total \;elements}{29}\)

Total number of elements = 130 × 29 = 3770.

Bubble sort repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Array elements: 8, 22, 7, 9, 31, 5, 13

1^st pass = 8, 7, 9, 22, 5, 13, 31

4 swaps

2^nd pass = 7, 8, 9, 5, 13, 22, 31

3 swaps

3^rd pass = 7, 8, 5, 9, 13, 22, 31

1 swap

4^th pass = 7, 5, 8, 9, 13, 22, 31

1 swap

5^th pass = 5, 7, 8, 9, 13, 22, 31

1 swap

Since array is sorted after 5^th pass

∴ no further swaps possible

Total number of swaps = 4 + 3 + 1 + 1 + 1 = 10 

Keys: 121, 142, 169, 30, 24, 78, 53, 154

Hash Function: K mod 13

Hash Table:

154 mod 13 = 11

By linear probing

Index of 154 is 11.

Delete once, get the smallest element in O(log n) time.

Delete twice, get the second smallest element in 2 * log n time.

The optimal algorithm always selects the smallest sequences for merging.

Given sequence: 41, 30, 15, 80, 25, 50

Ascending order: 15, 25, 30, 41, 50, 80

Merge(15, 25) → new size (40)

Number of comparisons = 25 + 15 – 1 = 39  

Merge(30, 40) → new size (70)

Number of comparisons = 30 + 40 – 1 = 69  

Merge(41, 50) → new size (91)

Number of comparisons = 41 + 50 – 1 = 90

Merge(70, 80) → new size (150)

Number of comparisons = 70 + 80 – 1 = 149  

Merge(91, 150) → new size (241)

Number of comparisons = 91 + 150 – 1 = 240

Therefore, total number of comparisons, 39 + 69 + 90 + 149 + 240 = 587

Worst case of the given problem is when a single 0 is followed by all 1’s i.e.

0111111111111……

Also, worst case can also be considered as when all 0’s are followed by single 1.

000000000………………1

Since in both the cases there is a sorted sequence of 0 and 1 and for sorted sequence binary search is preferred.

At each stage, the element index is compared and if it is 1, search towards left and if it is 0 search towards the right.

Total worst-case number of probes performed by an optimal algorithm = ⌈log2  63⌉ = 6

Example:

Optimal Algorithm: Binary search

Consider element containing 7 elements

Maximum probes = ⌈ log27 ⌉ = 3

For 31 elements

Maximum probes = ⌈ log2  63⌉ = 6

Since the given array is sorted

Let given array be 1, 2, 3, 4, 5, 6, 7, …. 50

Probability of choosing each element is 1 ÷ 50

Worst case for quick sort will only we arise if 1 is chosen or 50 is chosen as pivot element

Assume 1 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (1^st position), this gives rise to worst case in quicksort since the complexity will be O(n²).

Assume 25 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (last position), this gives rise to worst case, in quicksort since the complexity will be O(n²).

P(X = 1) = 1 ÷ 50 = 0.02

and P(X = 50) = 1 ÷ 02 = 0.02

P(X = 1 or X = 50)

= 0.02 + 0.02

= 0.04 

Data:

N= 31, K= 100

Formula:

For double hashing method of collision resolution in hash tables, the location for key K is determined by:

(H1(K) + i × H2(K)) mod N.

where N is the size of the hash table and, i = 0, 1, 2, 3…….  is the probe sequence.

Calculation:

H₁(K) = K mod 31 = 100 mod 31 = 7

H₂(K) = 1+( K mod 19) = 1 + 100 mod 17 = 1 + 15 = 16

Address returned by probe corresponding to i = 1

Retured address = (H₁(K) + i ×H₂(K)) mod N

= (7 + 1 × 16) mod 31 = 23 mod 31 = 23

The address returned by probe 1 is 23