Algorithms Test 2

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

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)

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

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

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.

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

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

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)

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)

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

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

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)

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

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

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

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

Submit Test

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

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

Algorithms Test...

Question 1

Divide and Conquer

Dynamic Programming

Greedy Algorithm

branch and Bound

Question 2

θ (1)

θ (log n)

θ (n)

θ (n × log n)

Question 3

374-375

3744-3751

3747-3756

3749-3752

Question 4

202

401

301

303

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.

Question 6

5

4

3

2

Question 7

0.02-0.02

0.024-0.021

0.027-0.026

0.029-0.022

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)

Question 9

T(n) = O(√n)

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

T(n) = O(log log n)

T(n) = )(log n)

Question 10

790-790

7904-7901

7907-7906

7909-7902

Question 11

77824-77824

778244-778241

778247-778246

778249-778242

Question 12

O(n×logm)

O(log(n×m) )

O(m×n)

O(m+n)

Question 13

2-2

24-21

27-26

29-22

Question 14

Minimum number of scalar multiplication is 3480

Distinct number of ways to multiply ABCD is 5

Maximum number of scalar multiplication is 4680

Sum of Minimum and maximum number of scalar multiplication is 8160

Question 15

5

6

7

8

Question 16

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

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

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

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

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