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

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

A
72

B
73

C
74

D
75

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)

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³)

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>

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)

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)

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

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

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

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)

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

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

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

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

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³)

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

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)

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!)

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

72

73

74

75

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)

Question 10

O(n log n )

O(n2 log n )

O(n3 log n )

O(n3)

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>

Question 12

T(n) = O(√n)

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

T(n) = O(log log n)

T(n) = )(log n)

Question 13

θ(n)

θ(nLogn)

θ(n^2)

θ(n^2 log n)

Question 14

790-790

7904-7901

7907-7906

7909-7902

Question 15

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

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

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

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

Question 16

77824-77824

778244-778241

778247-778246

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)

O(n²)