Algorithms Test 2

Result

Algorithms Test 2

Score
-
out of -
Rank
-
out of -

TIME Taken - -

Weekly Quiz Competition

Question 1
2 / -0.33

The following paradigm can be used to find the solution of the problem in minimum time:
Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:

A
Divide and Conquer

B
Dynamic Programming

C
Greedy Algorithm

D
branch and Bound
Solution
Concept:
“Subset sum problem”:
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum(K).
Explanation:
Assume array of non-negative integer of size n. This problem can u solved by -
Method 1: Using recursion
- Time complexity - O(2ⁿ)
- Space complexity - O(n)
Method 1: Using Dynamic Programming (Optimal solution of “Subset sum problem”)
- Time complexity - O(n.k)
- Space complexity - O(n.k)
Dynamic Programming paradigm can be used to find the solution of the problem in minimum time.
Additional Note:
Subset sum problem is NP Complete Problem, because 0/1 Knapsack problem polynomial reduced to sum of
subset problem and 0/1 Knapsack problem is NP complete problem.
Question 2
2 / -0.33

What is the complexity of finding the 100th largest element in an already constructed binary max-heap?
NOTE:
Max-heap doesn't contain duplicate elements

A
θ (1)

B
θ (log n)

C
θ (n)

D
θ (n × log n)

Solution

Concept:
Time is constant.as long as the number is independent of n and it is a constant value.
Calculation:
The 100th largest element must be within the first 100 levels of maxheap.
Therefore time complexity is θ (1 )
Question 3
2 / -0.33

Let us consider that the capacity of the knapsack W = 55 and the list of provided items are shown in the following table.

1
2
3
4
5
Profit
100
50
150
200
130
Weight
25
10
20
45
15

Find the maximum profit gain by applying fractional knapsack.

A
374-375

B
3744-3751

C
3747-3756

D
3749-3752

Solution

1
2
3
4
5
Profit
100
50
150
200
130
Weight
25
10
20
45
15
Profit/Weight
4
5
7.5
4.44
8

Sort according to the Profit/Weight ratio.

5
3
2
4
1
Profit
130
150
50
200
100
Weight
15
20
10
45
25
Profit/Weight
8
7.5
5
4.44
4

Choose item 5, 3, 2
Profit = 130 + 150 + 50 = 330
Wight remaining = 55 - (15 + 20 + 10) = 10
Chose item 4 (fraction part of it)
Profit from item 4 = \(\frac{10}{45} \times200 = 44.44\)
Total profit = 330 + 44.44 = 374.44
Question 4
2 / -0.33

What is the minimum number of comparisons required in an array to find the minimum and maximum of 202 integers?

A
202

B
401

C
301

D
303

Solution

Data:
n = 50
Formula:
minimum number of comparisons = \(\frac{{3n}}{2} - 2\;\)
Calculation:
minimum number of comparisons = \(\frac{{3 \times 202}}{2} - 2 = 301\)
Important Points:
Divide and conquer is used to achieve minimum comparison
Question 5
2 / -0.33

If Bubble sort is implemented to sort a collection of numbers on a singly linked list then which of the following statements are TRUE?

A
Additional O(n) space is needed to sorted the linked list

B
The time complexity for this would remained unchanged i.e, O(n²)

C
Only one additional pointer to the node is required to iterate through the list and comparing the elements

D
Two additional pointers are mandatory, one to the node are required to compare the consecutive elements and after each iteration they have to be incremented.

Solution

Option 1: FALSE

O(1) extra space is needed to sort the linked list

Option 2: TRUE

The time complexity would remain unchanged as we can pass through the list only in O(n) time and also it will be sorted in O(n²) because maximum time for comparison and sorting will be O(n²) in case of bubble sort .

Option 3: TRUE

Only one pointer can be used to iterate the linked list and compared with the next element using the ‘→’ next operator.

Option 4: FALSE

Two pointers are not required as one additional pointer is sufficient.
Question 6
2 / -0.33

Consider the following elements:
15, 105, 37, 50, 63, 131, 8, 34, 205, 405, 5 and Hash table size = 13
How many collisions occur when these key’s are first folded by adding their digits together and then reducing to mod hash table size.

A
5

B
4

C
3

D
2

Solution

Key After Folding Location Collision
15 6 6
105 6 6 Yes
37 10 10
50 5 5
63 9 9
131 5 5 Yes
8 8 8
34 7 7
205 7 7 Yes
405 9 9 Yes
5 5 5 Yes

Therefore, the number of collisions is 5.
Question 7
2 / -0.33

An array of 100 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.

A
0.02-0.02

B
0.024-0.021

C
0.027-0.026

D
0.029-0.022

Solution

Since the given array is sorted
Let given array be 1, 2, 3, 4, 5, 6, 7, …. 100
Probability of choosing each element is \(\frac{1}{100}\)
Worst case for quicksort will only we arise if 1 is chosen or 100 is chosen as the pivot element
Assume 1 is chosen as a pivot element
After the first round of partitioning, the pivot will be in its same position (1^st position), this gives rise to worst-case in quick sort since the complexity will be O(n²).
Assume 100 is chosen as a pivot element
After the first round of partitioning, the pivot will be in its same position (last position), this gives rise to the worst case, in quick sort since the complexity will be O(n²).
P(X = 1) =\(\frac{1}{100}\) = 0.01
and P(X = 100) = \(\frac{1}{100}\) = 0.01
P(X = 1 or X = 100)
= 0.01 + 0.01
= 0.02
Question 8
2 / -0.33

The cost of minimum cost spanning tree of the following graph is:

A
72

B
73

C
74

D
75

Solution

Concept:

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.

It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

Minimum Spanning tree:

Calculation:

cost of minimum cost spinning tree = 7 + 8 + 9 + 10 + 11 + 12 + 16 = 73
Question 9
2 / -0.33

Which is/are complexities of their corresponding algorithms?

A
Towers of Hanoi with n disks → Θ (2n )

B
Addition of two n × m matrices → Θ ( n × m )

C
Heap sort given n numbers at the worst case → Θ (n²)

D
Binary search given n sorted numbers at the worst case → Θ (n)
Solution
- Recurrence relation for tower of Hanoi problem is T (n) = 2 T (n - 1) + 1, So, the time complexity for the tower of Hanoi problem is Θ (2n).
- Binary search algorithm searches a sorted array by repeatedly dividing the search interval in half. If value of search key is less than the item in middle, search in the lower half otherwise, search in upper half. In this way, time complexity of binary search in sorted array becomes Θ (log n).
- Heap sort algorithm worst case time complexity is Θ (n log n).
- Addition of two n × m matrices takes Θ (n × m) time to execute. As there are two for loop used while addition of two n × m matrices.
Question 10
2 / -0.33

What is the time complexity of the following fragment of code

void testbook(int n ) {

int i, j, k;

for(i=0; i

for(j=i; j≤n-1; j++) {

for(k=1; k≤n; k=k*2) {

printf(“Hello Testbook”) }

} } }

A
O(n log n )

B
O(n²log n )

C
O(n³log n )

D
O(n³)

Solution

For i = 0, the j loop executes n times

For i = 1, the j loop executes n-1 times

For i = 2, the j loop executes n-2 times

For i = 3, the j loop executes n-3 times

This process goes on till

For i = n-2, the j loop executes 2 times

The number of times the inner loop (with j as index) executes is \(\frac{{n\left( {n + 1} \right)}}{2} - 1\) = O(n²)

The innermost loop (with ‘k’ as the counter) is going to execute O(log n) times.

Therefore, the total number of times the inner most loop will execute is O(n² log n)
Question 11
2 / -0.33

The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max heap. The resultant max-heap is stored in an array implementation as

A
<42, 35, 40, 22, 25, 26, 30>

B
<42, 35, 40, 22, 25, 30, 26>

C
<42, 40, 35, 25, 22, 26, 30>

D
<42, 40, 35, 25, 22, 30, 26>

Solution

Concepts:

After inserting each element, we will apply MAX-Heapify operation to get the MAX-Heap.

Insert: 42, 25 and 30

Insert: 40 apply MAX-Heapify

New order: 42, 40, 30, 25, 22

Insert: 35 apply MAX-Heapify

New order: 42, 40, 35, 25, 22, 30 and 26

Diagram: resultant MAX_Heap
Question 12
2 / -0.33

The recurrence equation T(n) = T(√n) + O(1) has the following asymptotic solution:

A
T(n) = O(√n)

B
T(n) = O(n1/log n)

C
T(n) = O(log log n)

D
T(n) = )(log n)

Solution

Explanation:
T(n) = T(√n) + O(1) ≡ T(√n) + 1
T(2) = 1
\(T(2^{2^1}) = T(4) = T(2) + 1 = 2\)
\(T(2^{2^2}) =T(16) = T(4) + 1 = 3\)
\(T(2^{2^3}) = T(256) = T(16)+ 1 = 4\)
\(T(2^{2^4}) = T(65536) = T(256)+ 1 = 5\)
Option 3:
\(loglog(2^{2^4}) + 1= log2^4 + 1= 4+1 = 5\)
T(n) = O(log log n) + 1 = O(log log n)
Important Point:
Taking T(2) = 1
or T(2) = 100 it wont' change the result
Question 13
2 / -0.33

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

A
^θ(n)

B
^θ(nLogn)

C
^θ(n^2)

D
^θ(n^2 log n)

Solution

Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get heta(nLogn).
Question 14
2 / -0.33

Let the length of sorted arrays of X₁, X₂, X₃, X_4, and X₅ be 70, 91, 79, 92, and 20 respectively. To merge them into a single array X by merging two arrays at a time using an optimal algorithm. In the worst case, the maximum number of comparisons needed is _____.

A
790-790

B
7904-7901

C
7907-7906

D
7909-7902

Solution

The optimal algorithm always selects the smallest sequences for merging.
Given sequence: 70, 91, 79, 92, 20
Ascending order: 20, 70, 79, 91, 92
Merge(20, 70) → new size (90)
Number of comparisons = 20 + 70 – 1 = 89
Merge(79, 90) → new size (169)
Number of comparisons = 90 + 79 – 1 = 168
Merge(91, 92) → new size (183)
Number of comparisons = 91 + 92 – 1 = 182
Merge(169, 183) → new size (352)
Number of comparisons = 183 + 169 – 1 = 351
Therefore, total number of comparisons, 89 + 168 + 182 + 351 = 790
Question 15
2 / -0.33

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

A
T(n) <= 2T(n/5) + n

B
T(n) <= T(n/5) + T(4n/5) + n

C
T(n) <= 2T(4n/5) + n

D
T(n) <= 2T(n/2) + n

Solution

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
Question 16
2 / -0.33

If in best case quicksort is implemented for an input of size 1024 takes 80 seconds. How much time in seconds will require to process the input of size 524288?

A
77824-77824

B
778244-778241

C
778247-778246

D
778249-778242

Solution

Data:
n = 1024, t = 80 s
Formula:
The time complexity for quicksort is n log n
C \(×\) n log₂n = t
Calculation:
C \(×\) 1024 log21024 = 60
C × 1024 × 10 = 80
\(C = \frac{80}{1024 \times10} = \frac{1}{128}\)
For n = 524288 = 2¹⁹,
\(t = \frac{1}{128}\times2^{19}log_2{2^{19}}\)
t = 77824 seconds
Question 17
2 / -0.33
What is the most efficient algorithm that searches for a value in an m x n matrix. The matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
A
O(n×logm)

B
O(log(n×m) )

C
O(m×n)

D
O(m+n)
Solution
Concept:
Binary search runs in logarithmic time in the worst case, making O(log₂n) comparisons, where n is the number of elements in the array.
Explanation:
Properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Therefore matrix is sorted both row and column-wise
m rows correspond to O(log m) and n columns correspond to O(log n)
Therefore total complexity is equal to O(log n×m )
Question 18
2 / -0.33

Consider the following set of tasks with their associated profits and deadlines, provided that 2 tasks can be completed in a unit time if the optimal schedule is able to get a profit of 128, then maximum value of ‘x’ possible is _____ .
Task
Profit
Deadline
1
21
5
2
12
4
3
9
1
4
7
4
5
16
3
6
14
2
7
8
5
8
6
‘x’
9
7
2
10
17
7
11
17
1
12
5
2

A
2-2

B
24-21

C
27-26

D
29-22

Solution

In order to get the optimal schedule we need to sort the tasks in decreasing order of profits and schedule them as late as possible, as it is given that 2 tasks can be completed in a given time slot we are scheduling 2 in a time slot, on ding so we will get the following schedule.
Time
1

2

3

4

5

6

7

Task
T3
T11
T6
T9
T5

T2
T4
T1
T7

T10

Profit
9
17
14
7
16

12
7
21
8

17

It is not possible to schedule T12. If we count the profit of this schedule it is –
Profit = 9 + 17 + 14 + 7 + 16 + 12 + 7 + 21 + 8 + 17 = 128
This means that T8 is not scheduled, therefore the maximum value of x is 2 because up to time slot 2 all the time slots are full.
Hence, the value of x = 2
Question 19
2 / -0.33

Consider 4 matrics A, B, C, and D of dimensions 10 × 9, 9 × 12, 12 × 10, and 10 × 15, respectively. Which of the following is/are true about the number of scalar multiplications required to find the product ABCD using the basic matrix multiplication method?

A
Minimum number of scalar multiplication is 3480

B
Distinct number of ways to multiply ABCD is 5

C
Maximum number of scalar multiplication is 4680

D
Sum of Minimum and maximum number of scalar multiplication is 8160

Solution

There are 5 ways to multiply the matrices
((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD))
((AB)C)D
((AB)C)D = (10 × 9, 9 × 12), 12 × 10, 10 × 15
            = 10 × 9 × 12 + 10 × 12 × 10 + 10 × 10 × 15
            = 3780
(A(BC))D
A(BC)D = 9 × 12 × 10 + 10 × 9 × 10 + 10 × 10 × 15
            = 3480
A((BC)D)
A(BC)D = 9 × 12 × 10 + 9 × 10 × 15 + 10 × 9 × 15
            = 3780
A(B(CD))
A(B(CD)) = 12 × 10 × 15 + 9 × 12 × 15 + 10 × 9 × 15
            = 4770
(AB)(CD)
(AB)(CD) = 10 × 9 × 12 + 12 × 10 × 15 + 10 × 12 × 15
            = 4680
Minimum = 3480
Maximum = 4770
Sum = 8250
Therefore options 1 and 2 are correct.
Question 20
2 / -0.33

Consider an array A of size 63, which consists of only 1’s or 0’s in it. In array A elements are arranged in ascending order. The maximum number of probes needed to find the minimum index j of A for which A[j] = 1 using optimal algorithm is _____.

A
5

B
6

C
7

D
8

Solution

Optimal Algorithm: Binary search
Consider element containing 7 elements
Index
0
1
2
3
4
5
6
Element
0
0
0
0
0
0
1
1^stprobe

↑

Index
0
1
2
3
4
5
6
Element
0
0
0
0
0
0
1
2^nd probe

↑

Index
0
1
2
3
4
5
6
Element
0
0
0
0
0
0
1
3^rd probe

↑

Maximum probes = ⌈ log₂7 ⌉ = 3
For 63 elements,
Maximum probes = ⌈ log₂63 ⌉ = 6
Question 21
2 / -0.33

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

A
t1 = 5

B
t1 < t2

C
t1 > t2

D
t1 = t2

Solution

When first element or last element is chosen as pivot, Quick Sort's worst case occurs for the sorted arrays. In every step of quick sort, numbers are divided as per the following recurrence. T(n) = T(n-1) + O(n)
Question 22
2 / -0.33

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

A
O(n²)

B
O(nLogn)

C
Theta(nLogn)

D
O(n³)

Solution

The central element may always be an extreme element, therefore time complexity in worst case becomes O(n²).
Question 23
2 / -0.33

Consider the following C code segment int Ls Prime (n)
{
int i, n;
for (i=2; i<= sqrt(n); i++)
if (n % i == 0)
{
printf (“ Not Prime.\n”);
return 0;
}
return 1;
}
Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is true?

A
T (n) = 0 (√n) and T (n) = Ω (√n)

B
T (n) = 0 (√n) and T (n) = Ω (1)

C
T (n) = 0 (n) and T (n) = Ω (√n)

D
None of these

Solution

Concept:
Big o Notation = Upper bound of an algorithm
Big omega Notation = Lower bound of an algorithm
Explanation:
In worst case:
Take n = 97
Since it is a prime number it will 10 loops to return 1
∴T(n) = O(√n)
In best case:
Take n = 1024
Since it is not a prime number and divides by 2 it will 1 loop to return 0
∴T(n) = Ω (1)
Hence, T (n) = 0 (√n) in worst case
T (n) = Ω (1) in Best case.
Question 24
2 / -0.33

In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?

A
Θ (n²)

B
Θ (n log n)

C
Θ (n^1.5)

D
Θ (n)

Solution

Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.
Question 25
2 / -0.33

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

A
O(n)

B
O(n Log n)

C
O(n²)

D
O(n!)

Solution

Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same. In worst case the randomized function can pick the index of corner element every time.

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

	1	2	3	4	5
Profit	100	50	150	200	130
Weight	25	10	20	45	15
Profit/Weight	4	5	7.5	4.44	8

Key	After Folding	Location	Collision
15	6	6
105	6	6	Yes
37	10	10
50	5	5
63	9	9
131	5	5	Yes
8	8	8
34	7	7
205	7	7	Yes
405	9	9	Yes
5	5	5	Yes

Task	Profit	Deadline
1	21	5
2	12	4
3	9	1
4	7	4
5	16	3
6	14	2
7	8	5
8	6	‘x’
9	7	2
10	17	7
11	17	1
12	5	2

Time	1		2		3	4		5		6	7
Task	T3	T11	T6	T9	T5	T2	T4	T1	T7		T10
Profit	9	17	14	7	16	12	7	21	8		17

Index	0	1	2	3	4	5	6
Element	0	0	0	0	0	0	1
1^stprobe				↑

Index	0	1	2	3	4	5	6
Element	0	0	0	0	0	0	1
2^nd probe						↑

Index	0	1	2	3	4	5	6
Element	0	0	0	0	0	0	1
3^rd probe							↑

Algorithms Test 2

Result

Algorithms Test 2

Score

-

Rank

-

Question 1

Divide and Conquer

Dynamic Programming

Greedy Algorithm

branch and Bound

Solution

Question 2

θ (1)

θ (log n)

θ (n)

θ (n × log n)

Solution

Question 3

374-375

3744-3751

3747-3756

3749-3752

Solution

Question 4

202

401

301

303

Solution

Question 5

Additional O(n) space is needed to sorted the linked list

The time complexity for this would remained unchanged i.e, O(n2)

Only one additional pointer to the node is required to iterate through the list and comparing the elements

Two additional pointers are mandatory, one to the node are required to compare the consecutive elements and after each iteration they have to be incremented.

Solution

Question 6

5

4

3

2

Solution

Question 7

0.02-0.02

0.024-0.021

0.027-0.026

0.029-0.022

Solution

Question 8

72

73

74

75

Solution

Question 9

Towers of Hanoi with n disks → Θ (2n )

Addition of two n × m matrices → Θ ( n × m )

Heap sort given n numbers at the worst case → Θ (n2 )

Binary search given n sorted numbers at the worst case → Θ (n)

Solution

Question 10

O(n log n )

O(n2 log n )

O(n3 log n )

O(n3)

Solution

Question 11

<42, 35, 40, 22, 25, 26, 30>

<42, 35, 40, 22, 25, 30, 26>

<42, 40, 35, 25, 22, 26, 30>

<42, 40, 35, 25, 22, 30, 26>

Solution

Question 12

T(n) = O(√n)

T(n) = O(n1/log n)

T(n) = O(log log n)

T(n) = )(log n)

Solution

Question 13

The time complexity for this would remained unchanged i.e, O(n²)

Heap sort given n numbers at the worst case → Θ (n²)

O(n²log n )

O(n³log n )

O(n³)

^θ(n)

^θ(nLogn)

^θ(n^2)

^θ(n^2 log n)

O(n²)

O(n³)

Θ (n²)

Θ (n^1.5)