Algorithms Test 1

Result

Algorithms Test 1

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

What is the worst-case and average-case time complexity of the Binary search?

A
O(n²)

B
O(1)

C
O(n log n)

D
O(log n)

Solution

Binary search algorithm:
Binary search algorithm is used to find an element in an already sorted array.
STEPS 1:
It finds the middle element of the array and compare the element with the element to be searched, if it matches then return true.
STEPS 2:
If not, then divide the array into two halves in which if element to be search is less than middle element then search takes place in left part otherwise search in right half.
STEP 3:
Repeat this process, until you get the element.
Explanation:
For worst case 52
Worst Case: Search 50 in below give array
11
12
15
24
35
50
51
63

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)
50 > 32
\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)
50 < 63
\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)
matched
T(n) = O(log n)
Also, for average case:
T(n) = O(log n)
Question 2
2 / -0.33

Consider the below-given statement written in C language:
int A = {25, 9, 15, 30, 11, 17 , 22}
Bubble sort is applied on array A. Which element is present at index 2 after the second iteration?

A
11-11

B
114-111

C
117-116

D
119-112

Solution

Concept:
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Explanation:
In 1^st iteration: 25, 9, 15, 30, 11, 17 , 22
Output: 9, 15, 25, 11, 17, 22, 30
In 2^nd iteration: 9 15 25 11 17 22 30
Output: 9 15 11 17 22 25 30
11 is at index 2.
Important Point:
int A = {25, 9, 15, 30, 11, 17 , 22} //index starts with 0
Question 3
2 / -0.33

What is the time complexity for the below given block of code where i, j, n are integers and lines of code do contain any extra line space between them?
for(i = 0; i < n; i ++ )
for(j = m ; j > 0; j = j/2)
printf(“Hello world” );

A
O(n) + O(log2m)

B
O(n × m)

C
O(n × log₂m)

D
O(n + log₂m)

Solution

For the first loop it will run n times
for(i = 0; i < n; i ++ ) → complexity is O(n).
For the second loop it will run for ⌈log₂ m⌉
for(int j = m ; j > 0; j= j/2) → complexity is O(log₂m).
Since Outer loop has complexity O(n) and inner loop has complexity O(log₂m)
Time complexity for code block = O(n × log₂m)
Question 4
2 / -0.33

Consider the following table:
Algorithms
Design Paradigms
(A) Huffman Coding
(I) Divide and Conquer
(B) Merge sort
(II) Greedy
(C) Coin change problem
(III) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

A
(A) ↔ (I), (B) ↔ (II), (C) ↔ (III)

B
(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)

C
(A) ↔ (III), (B) ↔ (I), (C) ↔ (II)

D
(A) ↔ (II), (B) ↔ (I), (C) ↔ (III)
Solution
- Huffman Coding uses Greedy approach to solve the problem
- Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to order elements in an array.
- Dynamic Programming is used in Coin change problem
Question 5
2 / -0.33

If T(n) = 2T(n/2)+nlogn then T(n)?

A
O(nlogn)

B
O(n²)

C
O(n(logn)²)

D
O(2ⁿ)

Solution

Master Theorem: T(n)= aT(n/b)+f(n); a>=1,b>1.
Therefore a = 2, b = 2, f(n) = nlogn
\(n^{log_ba} = n^{log_22}=n\)
\({f(n) > n^{log_ba}}\)
∴ T(n) = O(n(logn)²)
Question 6
2 / -0.33

If G = (V,E) is a directed graph, then length of adjacency list is ______ and it requires ______ amount of memory.

A
2|E|, θ(V)

B
|E|, θ(V+E)

C
|E|, θ(E)

D
2|E|, θ(V+E)

Solution

If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|. If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2|E|. For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is θ(V+E).
Question 7
2 / -0.33

Consider 5 array of size 25, 31, 37, 49, 57 respectively. All arrays are sorted. All the arrays into a single array by using the optimal algorithm and the single array is again a sorted array. What is the maximum number of comparisons that will be needed in the worst case?

A
450-450

B
4504-4501

C
4507-4506

D
4509-4502

Solution

Using optimal algorithm (merge sort)
Sequence: 25, 31, 37, 49, 57
Ascending order: 25, 31, 37, 49, 57
Merge(25, 31) → new size (56)
Number of comparisons = 25 + 31 – 1 = 55
Sequence: 37, 49, 56, 57
Merge(37, 49) → new size (86)
Number of comparisons = 37 + 49 – 1 = 85
Sequence: 56, 57, 86
Merge(56, 57) → new size (113)
Number of comparisons = 56 + 57 – 1 = 112
Sequence: 86, 113
Merge(86, 113) → new size (199)
Number of comparisons = 86 + 113 – 1 = 198
Therefore, total number of comparisons, 55+ 85 + 112 + 198 = 450
Question 8
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
6-6

B
64-61

C
67-66

D
69-62

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 9
2 / -0.33

Consider a hypothetical system in which merge sort is implemented on an array of size of 2 bytes each. The size of the array is 2 MB. The maximum time taken by the merge sort to process the array is 256 seconds. What is the size of the input in MB of a problem that can be solved in 81.92 minutes?

A
16

B
32

C
48

D
64

Solution

Data:
T1 = 256 sec = 28 sec
number of elements = n₁ = (2÷ 2) M = 2²⁰
T2 = 81.92 min = 81.92 × 60 sec
Formula:
Time complexity of merge sort is O(nlog2n),
T = c × n × log2n
where c is constant
Calculation:
T1 = c × n1 × log2 n1
28 = c × 2²0 × log2 220
1 = c × 212 × 20
\(\therefore c = \frac{1}{{{5×2^{14}}}}\)
T2 = c × n × log2n
\(81.92 × 60 = \frac{1}{{{5×2^{14}}}}\;{n_2}{\log _2}{n_2}\)
nLog2n = 24576 × 214
nLog2n = 24 × 224
∴ n = 224
Size = 2× 224 = 32 MB
Question 10
2 / -0.33

Consider two strings M = ”abababbaa” and N = ”babaa”. The length of the longest common subsequence between two given string is r and the number of times the length of the longest common subsequence repeated in the matrix is n while using Dynamic programming. What is the value of r + r×n + n² ?
NOTE: Common subsequence may not necessarily be contiguous

A
19-19

B
194-191

C
197-196

D
199-192

Solution

Concepts:
Initialize the first row and first column with 0.
If there is match, A[i, j] = A[i – 1, j – 1] + 1
If not match: max(A[i – 1, j], A[i, j – 1])
Table of longest common subsequence:

M →
a
b
a
b
a
b
b
a
a
N↓
0
0
0
0
0
0
0
0
0
0
b
0
0
1
1
1
1
1
1
1
1
a
0
1
1
2
2
2
2
2
2
2
b
0
1
2
2
3
3
3
3
3
3
a
0
1
2
3
3
4
4
4
4
4
a
0
1
2
3
3
4
4
4
5
5
Length of longest common subsequence = r = 5
5 is repeated 2 times
r + r×n + n2 = 5 + 5×2 + 22 = 19
The value is 19.
Question 11
2 / -0.33

Consider the following statements:
(i). The height of any binary search tree with n nodes is \(O(logn)\)
(ii). Inserting into an AVL tree with n nodes requires \(\theta (logn)\) rotations.
(iii). In a max-heap, k^th largest element will always be on k^th level.
Which of the above statements is/are FALSE?

A
(i) only

B
(i) and (ii) only

C
(iii) only

D
(i), (ii) and (iii)

Solution

Statement i: FALSE
Maximum height of a binary search tree is O(n)
The height of any balanced binary search tree with n nodes is \(O(logn)\)
Statement ii: FALSE
Inserting into an AVL tree requires O(1) rotations.
Statement iii: FALSE
In a max heap, k^th largest element will always within k levels.
Question 12
2 / -0.33

Consider the 10 Jobs for A to J. The execution of each job takes 1 unit of time. One job can be executed at a time. Each job is related with a profit and a deadline. If job is completed before deadline then the corresponding profit is earned. The maximum profit earned is _____.
Job
A
B
C
D
E
F
G
H
I
J
Profit
25
35
40
30
18
25
33
43
19
25
Deadline
4
7
4
7
1
4
6
5
3
6

A
231-231

B
2314-2311

C
2317-2316

D
2319-2312

Solution

1. Array size = min(max(deadline)), number of jobs) = (7, 10) = 7
2. Sort the Jobs in descending order based on profit
3. Fill the array in reverse order of deadline
Array
Job
A
J
D
C
H
G
B
Profit
25
25
30
40
43
33
35
0 1 2 3 4 5 6 7
Maximum profit = 25 + 25 + 30 + 40 + 43 + 33 + 35 = 231

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Algorithms	Design Paradigms
(A) Huffman Coding	(I) Divide and Conquer
(B) Merge sort	(II) Greedy
(C) Coin change problem	(III) Dynamic Programming

	M →	a	b	a	b	a	b	b	a	a
N↓	0	0	0	0	0	0	0	0	0	0
b	0	0	1	1	1	1	1	1	1	1
a	0	1	1	2	2	2	2	2	2	2
b	0	1	2	2	3	3	3	3	3	3
a	0	1	2	3	3	4	4	4	4	4
a	0	1	2	3	3	4	4	4	5	5

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							↑

Job	A	B	C	D	E	F	G	H	I	J
Profit	25	35	40	30	18	25	33	43	19	25
Deadline	4	7	4	7	1	4	6	5	3	6

Algorithms Test 1

Result

Algorithms Test 1

Score

-

Rank

-

SHARING IS CARING

Question 1

O(n2)

O(1)

O(n log n)

O(log n)

Solution

Question 2

11-11

114-111

117-116

119-112

Solution

Question 3

O(n) + O(log2m)

O(n × m)

O(n × log2m)

O(n + log2m)

Solution

Question 4

(A) ↔ (I), (B) ↔ (II), (C) ↔ (III)

(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)​​

(A) ↔ (III), (B) ↔ (I), (C) ↔ (II)

(A) ↔ (II), (B) ↔ (I), (C) ↔ (III)

Solution

Question 5

O(nlogn)

O(n2)

O(n(logn)2)

O(2n)

Solution

Question 6

2|E|, θ(V)

|E|, θ(V+E)

|E|, θ(E)

2|E|, θ(V+E)

Solution

Question 7

450-450

4504-4501

4507-4506

4509-4502

Solution

Question 8

6-6

64-61

67-66

69-62

Solution

Question 9

16

32

48

64

Solution

Question 10

19-19

194-191

197-196

199-192

Solution

Question 11

(i) only

(i) and (ii) only

(iii) only

(i), (ii) and (iii)

Solution

Question 12

231-231

2314-2311

2317-2316

2319-2312

Solution

O(n²)

O(n × log₂m)

O(n + log₂m)

(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)

O(n²)

O(n(logn)²)

O(2ⁿ)