Algorithms Test 2

Result

Algorithms Test 2

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

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

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 9
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 10
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 11
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 12
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 13
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 14
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 15
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 16
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.

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

-

SHARING IS CARING

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

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 9

T(n) = O(√n)

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

T(n) = O(log log n)

T(n) = )(log n)

Solution

Question 10

790-790

7904-7901

7907-7906

7909-7902

Solution

Question 11

77824-77824

778244-778241

778247-778246

778249-778242

Solution

Question 12

O(n×logm)

O(log(n×m) )

O(m×n)

O(m+n)

Solution

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

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