Algorithms MCQ Quiz - Objective Question with Answer for Algorithms - Download Free PDF

The correct option is Search by Hashing.

CONCEPT:

In linear search, every element of a given list is compared one by one with the given key without skipping any element.

It is useful when we need to search for an item in a small unsorted list, but the time taken to search the list increases as the size of the list increases.

For example, consider a list of length 5 and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 5

If we increase the size of the same list (say 15) and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 15

In binary search, the key to be searched is compared with the middle element of a sorted list, If the element at the middle position:

i)  Matches the key the search is successful

ii) Is greater than the key then the key element may be present in the left part of the list

iii) Is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

Thus the time taken to search the list increases as the size of the list increases. But it will not be as large as the time required by linear search

Hash-based searching requires only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function. 

For example, consider a list of length 5 and the hash function: h(element) = element % size(list)

A hashing function is a mathematical function that generates unique results for each unique value supplied to the hash function in constant time.

For example: Consider a list of length 5 and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 2  and requires only one key comparison to find the key at that index

Similarly increasing the size of the list (say 15) and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 12  and requires only one key comparison to find the key at that index

Thus it is independent of the length of the list.

Primary clustering:

• It is one of two major failure modes of open addressing based hash tables, especially those using linear probing.
• It occurs after a hash collision causes two of the records in the hash table to hash to the same position, and causes one of the records to be moved to the next location in its probe sequence.

Secondary clustering:

Secondary clustering occurs more generally with open addressing modes including linear probing and quadratic probing in which the probe sequence is independent of the key, as well as in hash chaining.

Double hashing:

Double hashing is a computer programming technique used in conjunction with open-addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs.

Double hashing technique is free from Clustering problems

Concept :

Stack is a data structure in which elements can be inserted and deleted only from one end i.e. top of the stack. It follows the LIFO property i.e. last in first out.

Explanation:

(a) Binary search in an array

Binary search in an array can be performed with the help of stack.  Binary search works on the divide and conquer approach and finds the middle element and then perform the search in the left side if element is smaller than the middle element otherwise search proceed in the right of middle element.

(b) Breadth first search

Breadth first search is graph traversal algorithm. It uses queue data structure to traverse the graph or the tree. It is also used to find the connected components in a graph.

(c) Implementing function calls

Function calls are implemented using the stack data structure. As, when a function call arrives then the state or the data currently operated on is stored on the stack where it is resumed after the execution of function call.

(d) Process scheduling

Process scheduling is implemented using the queue data structure . Ready queue is maintained for the processes which are ready for the execution.

• In comparison-based sorting, elements of an array are compared with each other to find the sorted array.
• Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.
• Insertion sort, Bubble sort and Selection sort are comparison based sorting algorithms.

The correct answer is Unsupervised Learning.

Key Points 

1. Supervised Learning:

• In supervised learning, the algorithm is trained on a labeled dataset, where the input data is paired with corresponding output labels.
• The goal is to learn a mapping function from input to output so that the algorithm can make predictions or classifications on new, unseen data.

2. Unsupervised Learning:

• In unsupervised learning, the algorithm is given data without explicit instructions on what to do with it.
• The algorithm tries to find patterns, relationships, or structures within the data on its own.
• Clustering algorithms, like k-Means, fall under unsupervised learning because they group similar data points together without using labeled output information.

3. Semi-supervised Learning:

• Semi-supervised learning is a combination of supervised and unsupervised learning.
• It involves a dataset that contains both labeled and unlabeled examples.
• The algorithm is trained on the labeled data, and then it tries to make predictions on the unlabeled data by leveraging the patterns learned from the labeled data.

4. Reinforcement Learning:

• Reinforcement learning involves an agent interacting with an environment and learning to make decisions by receiving feedback in the form of rewards or punishments.
• The agent learns to take actions that maximize the cumulative reward over time.
• Unlike supervised learning, where the algorithm is provided with explicit labeled examples, in reinforcement learning, the algorithm learns by trial and error.

In the case of the k-Means algorithm, it is unsupervised learning because it doesn't rely on labeled output data. Instead, it aims to partition the input data into clusters based on similarity, without using predefined class labels.

Concept:

Flowcharts use special shapes to represent different types of actions or steps in a process. Lines and arrows show the sequence of the steps, and the relationships among them. These are known as flowchart symbols.

Hence Option 4 is correct

Answer: Option 1

Explanation: 

f(n) =  n + module(n-1);  / since return (n + module(n-1));

Here recurrence relation will be

T(n) = T(n-1) + c

≡ T(n-2) + c + c

≡ T(n-3) + 3c

≡ T(n-k) + kc

when n-k = 1 ; k = n-1 and T(1) = 1

≡ T(1) + (n-1)c

≡ (n-1)c

≡ O(n) 

Hence Option 1 is correct answer.

Here some of you might have cam up with recurrence relation T(n) = T(n-1) + n, which is incorrect because in function n is just a variable it will have a constant value which will get added to call return value and In recurrence variable n indicate cost.  

\(T\left( n \right) = 2\;T\left( {\sqrt n } \right) + 1\)

Put n= 2^m, m = log₂n

\(T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1\)

\(Put\;T\left( {{2^m}} \right) = S\left( m \right)\)

\(S\left( m \right) = 2\;S\;\left( {\frac{m}{2}} \right) + 1\)

Now, calculate \({n^{log_b^a}}\)

\({m^{log_b^a}} = m\)

S (m) = m + 1

S(m) = m

Put the value of m 

Therefore, T(n) in terms of Θ notation is Θ (logn).

\({\rm{T}}\left( {\rm{n}} \right) = 2{\rm{T}}\left( {\frac{{\rm{n}}}{2}} \right) + \log {\rm{n}}\)

Comparing with:

\({\rm{T}}\left( {\rm{n}} \right) = {\rm{aT}}\left( {\frac{{\rm{n}}}{{\rm{b}}}} \right) + f\left( n \right)\)

a = 2, b = 2, f(n) = log n

\({n^{{{\log }_2}2}} = n\) > f(n)

By Master’s theorem

\(T\left( {\rm{n}} \right) = {\rm{O}}\left( {\rm{n}} \right)\)

\(\begin{array}{l} \therefore p\; = \;\log n,\;q\; = \;\log p\; = \;\log \left( {\log n} \right)\\ \therefore q\; = \;n.\log \left( {\log n} \right) \end{array}\)

Explanation:

• An oval represents a start or end point
• A line is a connector that shows relationships between the representative shapes
• A parallelogram represents input and output
• A rectangle represents a process
• A diamond indicates a decision

The given symbol represents the predefined process such as a sub-routine or a module.

\(T\left( n \right) = 4T\left( {√ n } \right) + lo{g^2}n\)

Consider n = 2^m

m = log₂n

n = 2m

Taking square root

√n = 2m/2

T(2^m) = 4T(2^m/2) + m²

Put S(m) = T (2^m/2)

S(m) = 4 S(m/2) + m²

Comparing with

T(m) = a T(m/k) + cmk

a = 4, b = 2, k = 2

a = b^k = 4

Now use master’s theorem :

T(m) = O(mklog m)

So, Time complexity will be O(m²log m)

Put the value of m

Time complexity will be :  O (log²n log (logn))

Since we are using random probing:

Insert 15:

(15)%7 = 1

Insert 11:

(11)%7 = 4

Insert 25:

(25)%7 = 4 / collision:

i = 4

 i = (i + 5) % 7    / using random function

i = (4 + 5)%7 = 2

Hence 25 position is 2^nd

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)