DAA MCQ
Algorithm
The algorithm is a step-by-step process to solve any problem and is a sequence of instructions that act on some input data to produce some output in a finite number of steps. The algorithm is independent of any programming language.
Why analysis of algorithms?
- For a given problem, there are many ways to design algorithms for it
- Analysis of algorithms to determine which algorithm should be chosen to solve the problem.
The complexity of algorithm on performance analysis of algorithm:
- Time complexity: time complexity of an algorithm is the total time required by the program to run till its completion
- Space complexity: Space complexity is the total space required by an algorithm to run till its completion.
Time and space complexity depends on lots of things like hardware, OS, processes, etc.
The analysis is of two types:
- Posteriori analysis: In Posteriori analysis, Algorithm is implemented and executed on certain fixed hardware and software. Then the algorithm is selected which takes the least amount of time to execute. Hence, the time used is given in time units like ms, ns, etc.
- Priori analysis: In Priori analysis, The time of the algorithm is found prior to implementation. Here time is not in terms of any such time units. Instead, it represents the number of operations that are carried out while executing the algorithm.
Asymptotic notations:
- Asymptotic notations are used to represent the complexity of an algorithm
- With the help of asymptotic notations, we can analyze the time performance of the algorithm.
There are three types of asymptotic notations:
- Theta notation
- Omega notation
- Big Oh Notation
Design and Analysis of Algorithms MCQ
Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph?
BFS
Djikstra’s Algorithm
Prims Algorithm
Kruskal’s Algorithm
What is the maximum number of swaps that can be performed in the Selection Sort algorithm?
n - 1
n
1
n - 2
What is the technique called in which it does not require extra memory for carrying out the sorting procedure?
Stable
Unstable
In-place
In-partition
What is the time complexity in decreasing the node value in a binomial heap?
O(1)
O(N)
O(logN)
O(NlogN)
What is the time complexity of the binary search algorithm?
O(n)
O(1)
O(log2n)
O(n^2)
What is the time complexity of the following code snippet in C++?
void solve() {
string s = "scaler";
int n = s.size();
for(int i = 0; i < n; i++) {
s = s + s[i];
}
cout << s << endl;
}O(n)
O(n^2)
O(1)
O(log n)
What is the time complexity of the Sieve of Eratosthenes to check if a number is prime?
O(nlog(logn)) Precomputation, O(1) for check.
O(n) Precomputation, O(1) for the check.
O(n * logn) Precomputation, O(logn) for check.
O(n) Precomputation, O(logn) for check.
What is the time complexity to insert an element to the front of a LinkedList(head pointer given)?
O(n)
O(1)
O(logn)
O(n * logn)
What should be considered when designing an algorithm?
If this software is used correctly
In the hardware is used correctly
If there is more than one way to solve the problem
All of the above are correct
What will be the best sorting algorithm, given that the array elements are small (<= 1e6)?
Bubble Sort
Merge Sort
Counting Sort
Heap Sort
When a pop() operation is called on an empty queue, what is the condition called?
Overflow
Underflow
Syntax Error
Garbage Value
Which of the following algorithms are used for string and pattern matching problems??
Z Algorithm
Rabin Karp Algorithm
KMP Algorithm
All of the above
What is the best time complexity we can achieve to precompute all-pairs shortest paths in a weighted graph?
O(n^3)
O(n^2)
O(n)
O(n^4)
Which of the following are applications of Topological Sort of a graph?
Sentence Ordering
Course Scheduling
OS Deadlock Detection
All of the above
Which of the following data structure is used to perform recursion?
Linked list
Array
Queue
Stack
Which of the following functions provides the maximum asymptotic complexity?
f1(n) = n^(3/2)
f2(n) = n^(logn)
f3(n) = nlogn
f4(n) = 2^n.
Which of the following is a Divide and Conquer algorithm?
Bubble Sort
Selection Sort
Heap Sort
Merge Sort
Which of the following is incorrect? Algorithms can be represented:
As programs
As flow charts
As syntax
As pseudo-codes
Which of the following is known to be not an NP-Hard Problem?
Vertex Cover Problem
0/1 Knapsack Problem
Maximal Independent Set Problem
Travelling Salesman Problem
Which of the following is used for solving the N Queens Problem?
Greedy algorithm
Dynamic programming
Backtracking
Sorting
Which of the following sorting algorithms provide the best time complexity in the worst-case scenario?
Merge Sort
Quick Sort
Bubble Sort
Selection Sort
Which of the following statements is true about AVL Trees?
The difference between the heights of left and right nodes cannot be more than 1.
The height of an AVL Tree always remains of the order of O(logn)
AVL Trees are a type of self-balancing Binary Search Trees.
All of the above.
Worst-case time complexity to access an element in a BST can be?
O(n)
O(n * logn)
O(1)
O(logn)
In what time complexity can we find the diameter of a binary tree optimally?
O(V + E)
O(V)
O(E)
O(V * logE)
An algorithm is __________?
A problem
A procedure for solving a problem
A real-life mathematical problem
None of the above
Another name of the fractional knapsack is?
Non-continuous knapsack problem
Divisible knapsack problem
0/1 knapsack problem
Continuous Knapsack Problem
Dijkstra’s algorithm is used to solve __________ problems?
Network lock
Single source shortest path
All pair shortest path
Sorting
Hamiltonian path problem is _________?
NP problem
P class problem
NP-complete problem
N class problem
Heap is a _____________?
Tree structure
Complete binary tree
Binary tree
None of the above
Identify the approach followed in Floyd Warshall’s algorithm?
Linear programming
Dynamic Programming
Greedy Technique
Backtracking
Identify the best case time complexity of selection sort?
O(nlogn)
O(n^2)
O(n)
O(1)
Identify the function of the stack that returns the top data element of the stack?
pop()
peek()
push()
findTop()
Identify the slowest sorting technique among the following?
Merge Sort
Quick Sort
Bubble Sort
Selection Sort
Identify the sorting technique which compares adjacent elements in a list and switches whenever necessary?
Merge Sort
Quick Sort
Bubble Sort
Selection Sort
In a graph of n nodes and n edges, how many cycles will be present?
Exactly 1
At most 1
At most 2
Depending on the graph
Among the following options which is the best sorting algorithm when the list is already sorted?
Merge Sort
Insertion Sort
Bubble Sort
Selection Sort
Kruskal’s Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a?
DP Problem
Greedy Algorithm
Adhoc Problem
None of the above
Representation of data structure in memory is known as?
Storage structure
File structure
Recursive
Abstract Data Type
Select the correct recurrence relation for Tower of Hanoi?
T(N) = 2T(N-1)+1
T(N) = 2T(N/2)+1
T(N) = 2T(N-1)+N
T(N) = 2T(N-2)+2
The Bellmann Ford Algorithm returns __________ value?
String
Boolean
Double
Integer
The time complexity for travel Singh all nodes in a binary search tree with n nodes and printing them in order is?
O(n)
O(1)
O(nlog2n)
O(n^2)
The time complexity to find the longest common subsequence of two strings of length M and N is?
O(N)
O(M * N)
O(M)
O(log N)
The worst-case time complexity of Quicksort is?
O(n)
O(1)
O(log2n)
O(n^2)
The worst-case time complexity of Selection Exchange Sort is?
O(n)
O(1)
O(log2n)
O(n^2)
To main measures of the efficiency of an algorithm are?
Time and space complexity
Data and space
Processor and memory
Complexity and capacity
What is the best case time complexity of the binary search algorithm?
O(1)
O(n)
O(log2n)
O(n^2)
