Algorithms MCQ Quiz in मल्याळम - Objective Question with Answer for Algorithms - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക

Answer: 1.6 to 1.65

Explanation:

The worst-case happens for the recursive calls on the longer route.

There are 6 such recursive calls to A(n/3) in the worst case.

So, recurrence relation will become like this:

F (n) = 6F(n/3) + O(1)

where O(1) is constant

By using master’s theorem,

a = 6, b =3

\({\rm{O}}\left( {{{\rm{n}}^{{{\log }_3}6}}} \right) = {\rm{\;O}}({{\rm{n}}^{1.63}})\)

\({\rm{O}}({{\rm{n}}^{\rm{\lambda }}}) = {\rm{O}}({{\rm{n}}^{1.63}}){\rm{\;}}\)

λ = 1.63

Answer:3 to 3

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

The minimum weight in the graph is 0.1 choosing this we get.

Suppose we get two trees T₁ and T_2.

To connect to those two trees we got 3 possible edges of weight 0.9.

Hence we can choose any one of those 3 edges.

No of Minimum weight spanning tree is 3.

We have to check how many times inner loop will be executed here.

For i=1,

j will run 1 + 2 + 3 + …………. (n times)

For i=2

j will run for 1,3,5, 7, 9, 11,………..(n/2 times)

For i=3

j will run for 1,4,7,10, 13…………… (n/3 times)

So, in this way,

\(T\left( n \right) = n + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5} + \frac{n}{6} \ldots + \frac{n}{n}\)

\(= n\left( {1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \ldots + \frac{1}{n}} \right)\;\)

So, Time complexity of given program = Θ (n log n)

Concept:

External sorting is sorting the lists that are so large that the whole list cannot be contained in the internal memory of a computer.

Explanation:

All heap sort, quick sort and insertion sort uses the concept of internal sorting. In internal sorting, data that has to be stored will be in main memory always and it implies faster access.

Important Point:

Example of external sorting is merge sort algorithm

External merge sort algorithm steps:

→ Data is stored in intermediate files

→ intermediate files are sorted and merged.

External sorting algorithms by external memory model in which a cache or internal memory is considered and an unbounded external memory is divided into blocks and time complexity is the number of memory transfers between internal and external memory.

Data:

K₅ is a complete graph with 5 vertex, that is, n = 5

Formula:

maximum number of spanning tree possible = nn - 2

Calculation:

maximum number of spanning tree = 5^5-2 = 125

Concept:

Sin function value ranges from -1 to + 1. (-1, 0, 1)

Explanation:

Case 1: when sin(n) is -1,

g(n) = n^{(1 - 1)} = n⁰ = 1

so, for this case f(n) > g(n) i.e. g(n) = O (f(n))

So, statement 1 is incorrect.

Case 2: when sin(n) is +1,

g(n) = n^{(1 + 1)} = n²

so, for this case f(n) < g(n) i.e. f(n) = O(g(n))

but for this, second statement i.e. f(n) = Ω(g(n)) is incorrect.

Both statements are not true for all values of sin(n).

Hence, option 4 is correct answer.

The optimal algorithm always selects the smallest sequences for merging.

Given sequence: 41, 30, 15, 80, 25, 50

Ascending order: 15, 25, 30, 41, 50, 80

Merge(15, 25) → new size (40)

Number of comparisons = 25 + 15 – 1 = 39  

Merge(30, 40) → new size (70)

Number of comparisons = 30 + 40 – 1 = 69  

Merge(41, 50) → new size (91)

Number of comparisons = 41 + 50 – 1 = 90

Merge(70, 80) → new size (150)

Number of comparisons = 70 + 80 – 1 = 149  

Merge(91, 150) → new size (241)

Number of comparisons = 91 + 150 – 1 = 240

Therefore, total number of comparisons, 39 + 69 + 90 + 149 + 240 = 587

The correct answer is option 3.

Concept

• A flowchart is a diagrammatic representation that illustrates a solution model to a given problem. It is used to depict the process of an operation or task, from startups to completion. It's a useful tool for visualizing a process, which can help to better understand, analyze, or improve it.​

Key Points

Key Points

The time complexity of selection sort = Number of swaps + number of comparisons.

= n swaps + n² comparisons.

The time complexity of selection sort = O(n²).

Hence the correct answer is O(n2).

Additional Information

Algorithm	Time Complexity
	Best	Average	Worst
Selection Sort	(Ωn2)	θ(n2)	O(n2)
Bubble Sort	Ω(n)	θ(n2)	O(n2)
Insertion Sort	Ω(n)	θ(n2)	O(n2)
Heap Sort	Ω(n log(n))	θ(n log(n))	O(n log(n))
Quick Sort	Ω(n log(n))	θ(n log(n))	O(n2)
Merge Sort	Ω(n log(n))	θ(n log(n))	O(n log(n))
Bucket Sort	Ω(n+k)	θ(n+k)	O(n2)
Radix Sort	Ω(nk)	θ(nk)	O(nk)

Code Explanation:

int i= 0, j = 0, val = 1;

for (i = 1; i < = n; i++) / n times Time complexity = O(n)

{

j = n;

if (i% 2 == 0)   / out of n only n/2 times if will run

{

while (j > 1) {  /log n times, since j = n

val = val * j;

j = j/2;           / j decrease in power of 2 leads to log n

}

}

}

Outer for loop = O(n)

Inner for loop = O(log n)

Since nested loop

Time complexity = O(n) × O(log n) = O(n log n)