Cs501 - Design & Analysis Of Algorithm - Iem
.
Questions and Answers
- 1.
What are the correct intermediate steps of the following data set when it is being sorted with the Quick sort? 15,20,10,18
- A.
15,10,20,18 -- 15,10,18,20 -- 10,15,18,20
- B.
15,20,10,18 -- 15,10,20,18 -- 10,15,20,18
- C.
10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20
- D.
10, 20,15,18 -- 10,18,15,20 -- 10,15,18,20
Correct Answer
D. 10, 20,15,18 -- 10,18,15,20 -- 10,15,18,20Explanation
The given answer shows the correct intermediate steps of the Quick sort algorithm for sorting the data set 15, 20, 10, 18. The first step is to partition the data set by choosing a pivot element, which is 10 in this case. Then, the elements are rearranged such that all elements smaller than the pivot are placed to its left, and all elements larger than the pivot are placed to its right. The next step involves recursively applying the same process to the sub-arrays on the left and right of the pivot until the entire array is sorted. The given answer correctly shows the intermediate steps of this process.Rate this question:
-
- 2.
Quick sort uses
- A.
Exchanging
- B.
Partitioning
- C.
Selection
- D.
Merging
Correct Answer
B. PartitioningExplanation
Quick sort uses partitioning to divide the input array into two smaller sub-arrays. It selects a pivot element and rearranges the array in such a way that all elements smaller than the pivot are placed before it, and all elements greater than the pivot are placed after it. This process is repeated recursively on the sub-arrays until the entire array is sorted. Partitioning is a crucial step in the quick sort algorithm as it determines the position of the pivot element and helps in dividing the array efficiently.Rate this question:
-
- 3.
Using quick sort is a stable way of sorting
- A.
True
- B.
False
Correct Answer
B. FalseExplanation
Quick sort is not a stable sorting algorithm. A sorting algorithm is considered stable if it maintains the relative order of elements with equal keys. In quick sort, the relative order of elements with equal keys may change during the sorting process, making it an unstable sorting algorithm. Therefore, the given statement is false.Rate this question:
-
- 4.
Which of the following is False about merge sort algorithm?
- A.
It is a comparison sorting algorithm.
- B.
The unsorted array is divided into sublists, which are in turn divided into more sublists.
- C.
The unsorted array is divided into sublists, each sublist is then sorted recursively by re-applying the algorithm.
- D.
All of the above statements are true
Correct Answer
B. The unsorted array is divided into sublists, which are in turn divided into more sublists.Explanation
Merge sort algorithm does not divide the unsorted array into sublists that are further divided into more sublists. Instead, it divides the array into two halves and recursively sorts each half before merging them back together. Therefore, the statement "The unsorted array is divided into sublists, which are in turn divided into more sublists" is false.Rate this question:
-
- 5.
An array has indices ranging from x to x+n; the merge sort would be applied from c to x+n, where c
- A.
Is the remainder of x/2, if x is an odd number
- B.
Is the the non-integer part of x/2
- C.
Is the integer part of x/2
- D.
Is an integer chosen arbitrarily, so long that it is smaller than x+n
Correct Answer
C. Is the integer part of x/2Explanation
The merge sort algorithm is being applied to an array with indices ranging from x to x+n. In this case, the starting point for the merge sort would be the integer part of x/2. This is because when x is divided by 2, the result may be a decimal number. Taking the integer part ensures that the starting index for the merge sort is a whole number.Rate this question:
-
- 6.
Which of the following Big O Notations has constant order of growth?
- A.
O(n)
- B.
O(1)
- C.
O(n2)
- D.
O(log n)
Correct Answer
B. O(1)Explanation
The Big O Notation O(1) represents constant order of growth. This means that the algorithm's runtime or space complexity remains constant, regardless of the size of the input. It indicates that the algorithm takes a fixed amount of time or space to complete its operations, making it highly efficient. This is in contrast to other notations like O(n), O(n^2), or O(log n), where the runtime or space requirements increase as the input size grows.Rate this question:
-
- 7.
To implement __________ search algorithm, the list should be sorted.
- A.
Linear
- B.
Binary
- C.
Both
- D.
None
Correct Answer
B. BinaryExplanation
To implement the Binary search algorithm, the list should be sorted. This is because the Binary search algorithm works by repeatedly dividing the sorted list into two halves and narrowing down the search range until the target element is found or the search range becomes empty. If the list is not sorted, the algorithm will not be able to accurately divide the list and locate the target element efficiently. Therefore, sorting the list is necessary for the Binary search algorithm to work correctly.Rate this question:
-
- 8.
Consider the algorithm of deleting a node from the beginning of a linked list and identify the error: 1. Mark the first node in the list as current 2. Make START point to the next node in sequence. 3. Release the memory for the node marked as current.
- A.
The algorithm has no error
- B.
The sequence is wrong, the correct one is 3->1->2
- C.
The sequence is wrong, the correct one is 2->1->3
- D.
The sequence is wrong, the correct one is 3->2->1
Correct Answer
A. The algorithm has no error -
- 9.
Is a data structure consisting of a collection of elements (values or variables), each identified by one or more integer indices, stored so that the address of each element can be computed from its index tuple by a simple mathematical formula
- A.
Loop
- B.
Array
- C.
Binary Search
- D.
One-dimensional array
- E.
Sorting
Correct Answer
B. ArrayExplanation
An array is a data structure that stores a collection of elements, where each element is identified by one or more integer indices. The elements are stored in such a way that the address of each element can be calculated using a simple mathematical formula based on its index tuple. Arrays are commonly used for storing and accessing a fixed-size sequence of elements efficiently. They provide random access to elements, allowing for quick retrieval and modification of values at specific indices.Rate this question:
-
- 10.
Is a technique for locating a particular value in a sorted list.
- A.
Sorting
- B.
Do Loop
- C.
One-dimensional array
- D.
Array
- E.
Binary Search
Correct Answer
E. Binary SearchExplanation
Binary search is a technique used to locate a particular value in a sorted list. It works by repeatedly dividing the search space in half and comparing the target value with the middle element. If the target value is smaller, the search continues in the lower half; if it is larger, the search continues in the upper half. This process is repeated until the target value is found or it is determined that the value does not exist in the list. Binary search is an efficient algorithm with a time complexity of O(log n) and is commonly used in computer science and data structures.Rate this question:
-
- 11.
The Big O Notation of the expression f(n) = 2n + 6n2 + 3n is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n)
- D.
None of these
Correct Answer
A. O( ) -
- 12.
Which algorithm design technique is used in quick sort?
- A.
Dynamic Programming
- B.
Divide and Conquer
- C.
Greedy Method
- D.
Branch and Bound
Correct Answer
B. Divide and ConquerExplanation
Quick sort is a sorting algorithm that uses the divide and conquer technique. It divides the array into two sub-arrays based on a pivot element and recursively sorts the sub-arrays. The divide and conquer technique involves breaking down a problem into smaller sub-problems, solving them independently, and then combining the solutions to obtain the final solution. In quick sort, the array is divided into smaller sub-arrays, sorted independently, and then combined to achieve the sorted array. Therefore, the correct answer is Divide and Conquer.Rate this question:
-
- 13.
ω Notation provides and asymptotic:
- A.
Upper Bound
- B.
Lower Bound
- C.
Between upper & lower bounds
- D.
None of these
Correct Answer
B. Lower BoundExplanation
The ω notation provides a lower bound on the growth rate of a function. It represents the best-case scenario for the function's growth rate, indicating that the function will not grow any slower than the lower bound.Rate this question:
-
- 14.
Complexity of binary search is:
- A.
O(n)
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n.
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
Correct Answer
C. O( ) -
- 15.
Optimal Substructure property is exploited by:
- A.
Dynamic Programming
- B.
Greedy Method
- C.
Both
- D.
None
Correct Answer
C. BothExplanation
Both dynamic programming and greedy method exploit the optimal substructure property. The optimal substructure property states that an optimal solution to a problem can be constructed from optimal solutions of its subproblems. Dynamic programming breaks down a problem into smaller overlapping subproblems and solves them in a bottom-up manner, storing the solutions in a table. Greedy method, on the other hand, makes locally optimal choices at each step, assuming that these choices will lead to a globally optimal solution. Both techniques rely on the optimal substructure property to find the best solution to a problem.Rate this question:
-
- 16.
Which of the following approaches is adopted in Divide & Conquer algorithms?
- A.
Top-down
- B.
Bottom-up
- C.
Both
- D.
None
Correct Answer
A. Top-downExplanation
The Divide & Conquer approach in algorithms involves breaking down a problem into smaller subproblems, solving them independently, and then combining the solutions to obtain the final result. In the top-down approach, the main problem is divided into smaller subproblems, and the solution is obtained by recursively solving these subproblems from top to bottom. This approach starts with the main problem and gradually breaks it down into smaller subproblems until a base case is reached.Rate this question:
-
- 17.
In a Backtracking algorithm the solution space is searched using:
- A.
BFS
- B.
DFS
- C.
Binary Search
- D.
None
Correct Answer
B. DFSExplanation
In a Backtracking algorithm, the solution space is searched using Depth-First Search (DFS). This is because DFS explores a path as far as possible before backtracking and exploring other paths. This approach is well-suited for backtracking algorithms as it allows for efficient exploration of the solution space by systematically trying all possible solutions and backtracking when a dead end is reached. BFS and Binary Search are not typically used for backtracking algorithms.Rate this question:
-
- 18.
Binary Search algorithm can't be applied to:
- A.
Sorted linked lists
- B.
Sorted binary trees
- C.
Sorted linear array
- D.
Sorted integer array
Correct Answer
A. Sorted linked listsExplanation
The binary search algorithm relies on accessing elements in the middle of a sorted list to determine whether the target element is present. However, linked lists do not provide direct access to elements in the middle. In order to access an element in a linked list, one must start from the beginning and traverse through each element until the desired element is reached. Therefore, binary search cannot be directly applied to sorted linked lists.Rate this question:
-
- 19.
The technique of Pruning is used in:
- A.
Branch & Bound
- B.
Backtracking
- C.
Divide & Conquer
- D.
Dynamic Programming
Correct Answer
A. Branch & BoundExplanation
Pruning is a technique used in Branch & Bound algorithms to improve efficiency by eliminating branches of the search tree that are determined to be unfruitful. It involves cutting off branches that are guaranteed to lead to suboptimal solutions, reducing the search space and allowing the algorithm to focus on more promising paths. Backtracking, Divide & Conquer, and Dynamic Programming do not typically involve pruning as a specific technique.Rate this question:
-
- 20.
Shortest path to all the vertices of a graph from a given vertex of the same graph is obtained by:
- A.
Kruskal's Algorithm
- B.
Dijkstra's Algorithm
- C.
BFS
- D.
DFS
Correct Answer
B. Dijkstra's AlgorithmExplanation
Dijkstra's Algorithm is used to find the shortest path from a given vertex to all other vertices in a graph. It works by maintaining a priority queue of vertices and continually selecting the vertex with the minimum distance from the source. It then updates the distances of its neighboring vertices and repeats the process until all vertices have been visited. This algorithm guarantees the shortest path to all vertices and is commonly used in routing and network optimization problems.Rate this question:
-
- 21.
Which of the following problems is solved using the branch and bound method?
- A.
Knapsack problem
- B.
Hamiltonian Problem
- C.
Graph coloring
- D.
15 puzzle problem
Correct Answer
D. 15 puzzle problemExplanation
The branch and bound method is used to solve optimization problems by systematically exploring the solution space. In the 15 puzzle problem, the objective is to rearrange a 4x4 grid of numbered tiles by sliding them into an empty space, with the goal of achieving a specific configuration. The branch and bound method can be applied to efficiently search through the possible moves and configurations, pruning branches that are guaranteed to lead to suboptimal solutions. Therefore, the branch and bound method is used to solve the 15 puzzle problem.Rate this question:
-
- 22.
Lower Bound for any comparison sort is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
Correct Answer
C. O(n )Explanation
The lower bound for any comparison sort is O(n) because in order to sort a list of n elements, at least n comparisons need to be made. This is because each element needs to be compared with every other element in order to determine its correct position in the sorted order. Therefore, the time complexity of any comparison sort algorithm cannot be better than O(n).Rate this question:
-
- 23.
O(g(n)) is [Read as small oh of g(n) is]
- A.
Asymptotically loose
- B.
asymptotically tight
- C.
Same as big oh
- D.
None of these
Correct Answer
A. Asymptotically looseExplanation
The correct answer is "asymptotically loose" because the notation "o(g(n))" represents a set of functions that grow strictly slower than the function "g(n)" as n approaches infinity. It is a stronger condition than "big oh" notation, which allows for functions that grow at the same rate or slower than "g(n)". Therefore, "o(g(n))" is considered asymptotically loose.Rate this question:
-
- 24.
Big O notation of the expression f(n) = nlog2 n + n2 + elog2 n
- A.
O(n)
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(e
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
Correct Answer
B. O( ) -
- 25.
Which one of the following statements is true?
- A.
All NP Hard problems are NP Complete
- B.
All NP Complete problems are NP Hard
- C.
Some NP Complete problems are NP Hard
- D.
None of these
Correct Answer
B. All NP Complete problems are NP HardExplanation
The correct answer is "All NP Complete problems are NP Hard." This statement is true because NP Complete problems are a subset of NP Hard problems. NP Hard problems are those that are at least as difficult as the hardest problems in the class NP, while NP Complete problems are those that are both in NP and are as hard as the hardest problems in NP. Therefore, since NP Complete problems are a subset of NP Hard problems, it is true to say that all NP Complete problems are NP Hard.Rate this question:
-
- 26.
Time complexity of non-deterministic algorithm is always
- A.
Less than deterministic algorithm
- B.
Greater than deterministic algorithm
- C.
Equal to deterministic algorithm
- D.
None of these
Correct Answer
A. Less than deterministic algorithmExplanation
The time complexity of a non-deterministic algorithm is always less than that of a deterministic algorithm because a non-deterministic algorithm can explore multiple possible paths simultaneously, while a deterministic algorithm can only follow a single path. This allows the non-deterministic algorithm to potentially find the solution faster by avoiding unnecessary computations.Rate this question:
-
- 27.
Time Complexity of the recurrence relation T(n) = 2T(√n) + 1 is
- A.
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
Correct Answer
A.Explanation
The time complexity of the recurrence relation T(n) = 2T(√n) + 1 is O(log log n). This can be determined by analyzing the recurrence tree. Each level of the tree has a square root of the previous level's size. Since the size decreases exponentially, the height of the tree is O(log log n). At each level, there is a constant amount of work, represented by the "+1" term. Therefore, the overall time complexity is O(log log n).Rate this question:
-
- 28.
If adjacency list representation is used, BFS has running time::
- A.
O(|V| + |E|)
- B.
O(|V|)
- C.
O(|E|)
- D.
None of these
Correct Answer
A. O(|V| + |E|)Explanation
The correct answer is O(|V| + |E|). This is because in the BFS algorithm, we visit each vertex once and each edge once. Therefore, the running time of BFS is proportional to the sum of the number of vertices and the number of edges in the graph, which is represented by O(|V| + |E|).Rate this question:
-
- 29.
The diagonal of the adjacency matrix of a graph with self loop contains:
- A.
1
- B.
0
- C.
-1
- D.
both 0 and 1
Correct Answer
A. 1Explanation
The diagonal of the adjacency matrix of a graph with self loops contains 1. This is because the diagonal represents the vertices of the graph, and a self loop means that a vertex is connected to itself. Therefore, the diagonal entries will be 1 to indicate this self connection.Rate this question:
-
- 30.
Time complexity of Strassen’s Matrix Multiplication algorithm is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
None of these
Correct Answer
C. O( ) -
- 31.
Tight bound for building a max heap algorithm is
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
C. O(n )Explanation
The correct answer is O(n) because building a max heap requires iterating through each element in the given array and performing heapify operation on each element. Since there are n elements in the array, the time complexity of building a max heap is O(n).Rate this question:
-
- 32.
Travelling Salesman Problem is:
- A.
P
- B.
NP
- C.
NP Complete
- D.
NP Hard
Correct Answer
C. NP CompleteExplanation
The Travelling Salesman Problem is classified as NP-Complete because it is a decision problem that belongs to the class of NP problems and is also as hard as the hardest problems in NP. In other words, if a solution to the Travelling Salesman Problem can be verified in polynomial time, then any problem in NP can be reduced to it in polynomial time as well. This means that solving the Travelling Salesman Problem efficiently would imply solving all NP problems efficiently.Rate this question:
-
- 33.
Complexity of merge sort is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
C. O(n )Explanation
The complexity of merge sort is O(n) because it has a time complexity of O(n log n) for the merge step and O(n) for the divide step. The merge step takes O(n log n) time because it repeatedly divides the array into halves until it reaches the base case of single elements, and then merges them back together in sorted order. The divide step takes O(n) time because it splits the array into halves recursively. Overall, the time complexity of merge sort is dominated by the merge step, resulting in a complexity of O(n log n), but the divide step still contributes a linear factor of O(n).Rate this question:
-
- 34.
Minimum spanning tree of a graph can be obtained by:
- A.
DFS
- B.
BFS
- C.
Prim's Algorithm
- D.
None of these
Correct Answer
C. Prim's AlgorithmExplanation
Prim's Algorithm is a well-known algorithm used to find the minimum spanning tree of a graph. It starts with an arbitrary vertex and gradually expands the tree by selecting the edge with the minimum weight that connects the tree to a new vertex. This process continues until all vertices are included in the tree. Prim's Algorithm guarantees that the resulting tree will have the minimum total weight among all possible spanning trees of the graph. Therefore, Prim's Algorithm is the correct choice for obtaining the minimum spanning tree.Rate this question:
-
- 35.
Using FFT a polynomial can be converted from coefficient to Point-value representation in time:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
C. O(n )Explanation
The given correct answer is O(n). This means that the time complexity of converting a polynomial from coefficient to point-value representation using FFT is linear with respect to the size of the polynomial, denoted by n. This implies that as the size of the polynomial increases, the time taken to perform the conversion also increases in a linear fashion.Rate this question:
-
- 36.
Time complexity of the recurrence relation T(n) = 8T(n/2) + n2 is
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
C. O( )Explanation
The time complexity of the given recurrence relation T(n) = 8T(n/2) + n^2 is O(n^3). This can be determined by using the Master Theorem, which states that for a recurrence relation of the form T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is an asymptotically positive function, the time complexity is given by O(n^log_b(a)).
In this case, a = 8, b = 2, and f(n) = n^2. Taking the logarithm base b of a, we get log_2(8) = 3. Since f(n) = n^2, which is polynomial, it falls under the case 3 of the Master Theorem. Therefore, the time complexity is O(n^3).Rate this question:
-
- 37.
Time complexity of the Tower of Hanoi problem is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
Correct Answer
D. O( ) -
- 38.
The minimum number of colors needed to color a graph having more than 3 vertices and 2 edges is:
- A.
2
- B.
3
- C.
4
- D.
1
Correct Answer
A. 2Explanation
In a graph, the minimum number of colors needed to color the vertices is determined by the maximum degree of the graph. In this case, since the graph has more than 3 vertices and 2 edges, it is possible for the maximum degree to be 2. This means that there is a possibility of two vertices being connected to the same vertex. Therefore, at least 2 colors are needed to ensure that no two adjacent vertices have the same color.Rate this question:
-
- 39.
The worst case running time of quick sort algorithm is:
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
B. O( ) -
- 40.
Time complexity of the recurrence relation T(n) = 2T(n/2) + n is
- A.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- B.
O( )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- C.
O(n )
![Cs501 - Design & Analysis Of Algorithm - Iem - Quiz]()
- D.
O(n)
Correct Answer
C. O(n )Explanation
The given recurrence relation T(n) = 2T(n/2) + n represents a divide and conquer algorithm. In this case, the problem is being divided into two equal-sized subproblems, and the solution to each subproblem is being combined in linear time. Since the size of the problem is reduced by half at each level of recursion, the number of levels in the recursion tree is log(n). At each level, the work done is n. Therefore, the overall time complexity is O(n log n).Rate this question:
-
Back to top