Let’s begin:
2018
(a) Which algorithm is better for sorting between bubble sort and quicksort?
- (i) Bubble sort
- (ii) Quicksort
- (iii) Both are equally good
- (iv) These cannot be compared
- Correct Answer: (ii) Quicksort
- Explanation: Quicksort has an average time complexity of O(n log n), while bubble sort has a time complexity of O(n^2).
(b) An algorithm which uses the past results and uses them to find the new results is
- (i) brute force
- (ii) divide and conquer
- (iii) dynamic programming algorithm
- (iv) None of the mentioned
- Correct Answer: (iii) dynamic programming algorithm
- Explanation: Dynamic programming stores the results of subproblems to avoid recomputation.
(c) Out of the following which property of algorithm does not share?
- (i) Input
- (ii) Finiteness
- (iii) Generality
- (iv) Constancy
- Correct Answer: (iv) Constancy
- Explanation: Algorithms should be general enough to work for a range of inputs. While algorithms should have inputs, should be finite and general, algorithms do not need to remain constant.
(d) Which of the following standard algorithms is not a greedy algorithm?
- (i) Dijkstra’s shortest path algorithm
- (ii) Kruskal algorithm
- (iii) Bellmen Ford shortest path algorithm
- (iv) Prim’s algorithm
- Correct Answer: (iii) Bellmen Ford shortest path algorithm
- Explanation: Dijkstra’s, Kruskal’s, and Prim’s are greedy algorithms. Bellman-Ford uses dynamic programming.
(e) What is the time complexity of Huffman coding?
- (i) O(N)
- (ii) O(Nlog N)
- (iii) O(N(log N)^2)
- (iv) O(N^2)
- Correct Answer: (ii) O(Nlog N)
- Explanation: Huffman coding typically uses a priority queue, which has a time complexity of O(log N) for insertion and extraction. Building the Huffman tree takes O(Nlog N) time.
(f) _____ comparisons are required to sort the list 1, 2, 3, … n using insertion sort.
- (i) (n^2+n+2)/2
- (ii) (n^3+n-2)/2
- (iii) (n^2+n-2)/2
- (iv) (n^2-n-2)/2
- Correct Answer: (iii) (n^2+n-2)/2
- Explanation: Worst case insertion sort need to compare most of time. We can write (n(n-1))/2 == (n^2-n)/2 and for some reason the answer is (iii)
(g) Which of the following is true about Huffman coding?
- (i) Huffman coding may become lossy in some cases
- (ii) Huffman codes may not be optimal lossless codes in some cases
- (iii) In Huffman coding, no code is prefix of any other code
- (iv) All of the above
- Correct Answer: (iii) In Huffman coding, no code is prefix of any other code
- Explanation: Huffman coding is lossless and prefix free.
(h) A complexity of algorithm depends upon
- (i) time only
- (ii) space only
- (iii) both time and space
- (iv) None of the mentioned
- Correct Answer: (iii) both time and space
- Explanation: Algorithm complexity is determined by both the time it takes to run and the amount of space it requires.
(i) A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of
- (i) 2.40
- (ii) 2.16
- (iii) 2.26
- (iv) 2.15
- Correct Answer: (ii) 2.16
(j) Build heap is used in heap sort as a first step for sorting. What is the time complexity of build heap operation?
- (i) O(nlogn)
- (ii) O(n^2)
- (iii) O(log n)
- (iv) O(n)
- Correct Answer: (iv) O(n)
- Explanation: Building a heap can be done in O(n) time using a bottom-up approach.
2019
(a) In the following C++ function, let n>=m.
What is the time complexity of the above function assuming n > m?
- (i) (logn)
- (ii) Ω(n)
- (iii) (loglogn)
- (iv) (sqrt(n))
- Correct Answer: (i) O(logn)
- Explanation: In the worst-case scenario, the loop will iterate log(n) times and swap.
(b) Time complexity of Kadane’s Algorithm is
- (i) O(n)
- (ii) O(n^2)
- (iii) O(nlogn)
- (iv) O(n(logn)^2)
- Correct Answer: (i) O(n)
- Explanation: Kadane’s algorithm iterates through the array once.
(c) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?
- (i) 1/8
- (ii) 1
- (iii) 7
- (iv) 8
- Correct Answer: (iii) 7
- Explanation: Number of possible length 3 cycle = 8C3 = 56. So, the possibility of getting a 3 length cycle = 56*(1/2)^3 = 7.
(d) Any decision tree that sorts ‘n’ elements has height
- (i) 2(1g n)
- (ii) Ω(n)
- (iii) Ω(nlgn)
- (iv) Ω(n^2)
- Correct Answer: (iii) Ω(nlgn)
- Explanation: Any decision tree that sorts n elements must have at least n! leaves (one for each permutation). A binary tree of height h can have at most 2h leaves. Therefore, 2h ≥ n!. Taking logarithms, h ≥ log2(n!). Since log2(n!) is Θ(n log n), then height is Ω (nlgn)
(e) An all-pairs shortest-paths problem is efficiently solved using
- (i) Dijkstra’s algorithm
- (ii) Bellman-Ford algorithm
- (iii) Kruskal algorithm
- (iv) Floyd-Warshall algorithm
- Correct Answer: (iv) Floyd-Warshall algorithm
- Explanation: Floyd-Warshall is specifically designed to find all-pairs shortest paths.
(f) Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
- (i) In adjacency list representation, space is saved for sparse graphs.
- (ii) DFS and BFS can be done in O(V+E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here V and E are number of vertices and edges respectively.
- (iii) Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
- (iv) All of the above
- Correct Answer: (iv) All of the above
- Explanation: All the options are advantages
(g) Which of the following is true about Huffman Coding?
- (i) Huffman coding may become lossy in some cases.
- (ii) Huffman codes may not be optimal lossless codes in some cases.
- (iii) In Huffman coding, no code is prefix of any other code.
- (iv) All of the above
- Correct Answer: (iii) In Huffman coding, no code is prefix of any other code
Huffman coding is a lossless data compression algorithm, so it is not lossy. Huffman codes are also prefix-free, meaning that no code is a prefix of any other code.
(h) Which one of the following is an application of Queue Data Structure?
- (i) When a resource is shared among multiple consumers
- (ii) When data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes
- (iii) Load balancing
- (iv) All of the above
- Correct Answer: (iv) All of the above
- Explanation: Queues are fundamental for all listed application
(i) In linear search algorithm the worst case occurs when
- (i) the item is somewhere in the middle of the array
- (ii) the item is not in the array at all
- (iii) the item is the last element in the array
- (iv) the item is the last element in the array or is not there at all
- Correct Answer: (iv) the item is the last element in the array or is not there at all
- Explanation: Linear search has to check every element.
(j) The complexity of binary search algorithm is
- (i) O(n)
- (ii) O(log n)
- (iii) O(n^2)
- (iv) O(n log n)
- Correct Answer: (ii) O(log n)
- Explanation: Binary Search split by 2 every search
2020
(a) Find the complexity of the below program: void function(int n) { ... } (C++ GCD function)
- (i) Ω(n)
- (ii) O(√n)
- (iii) Θ(loglogn)
- (iv) Θ(sqrt(n))
- Correct Answer: (i) O(logn)
(b) How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V1, V2,, Vn) of n vertices?
- (i) n(n-1)/2
- (ii) 2^n
- (iii) n!
- (iv) 2^(n (n-1)/2)
- Correct Answer: (iv) 2^(n (n-1)/2)
(c) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is
- (i) T(n)=2T(n-2)+2
- (ii) T(n)=2T(n-1)+n
- (iii) T(n)=2T(n/2)+1
- (iv) T(n) = 2T(n-1)+1
- Correct Answer: (iv) T(n) = 2T(n-1)+1
(d) Dijkstra’s algorithm is based on
- (i) dynamic programming
- (ii) divide and conquer
- (iii) greedy programming
- (iv) None of the above
- Correct Answer: (iii) greedy programming
(e) Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
- (i) O(n)
- (ii) O(nlogn)
- (iii) O(n^2)
- (iv) O(n!)
- Correct Answer: (iii) O(n^2)
(f) Name three sorting algorithms which are stable by nature.
- (i) Bubble sort, Insertion sort, Merge sort
- (ii) Bubble sort, Quick sort, Heap sort
- (iii) Insertion sort, Radix sort, Heap sort
- (iv) Count sort, Radix sort, Quick sort
- Correct Answer: (i) Bubble sort, Insertion sort, Merge sort
(g) What is the worst time complexity of insertion sort?
- (i) nlogn
- (ii) log n
- (iii) n
- (iv) n^2
- Correct Answer: (iv) n^2
(h) The most efficient algorithm for finding the number of connected components in an undirected graph of n vertices and m edges has the time complexity
- (i) (n)
- (ii) (m)
- (iii) (m+n)
- (iv) (mn)
- Correct Answer: (iii) (m+n)
(i) Which of the following statement is not true about breadth-first search (BFS) in an undirected graph starting at a vertex v?
- (i) BFS identifies all vertices reachable from v.
- (ii) Using an adjacency list instead of an adjacency matrix can improve the worst case complexity to O(n + m).
- (iii) BFS cannot be used to check for cycles in the graph.
- (iv) BFS can be used to identify the furthest vertex from v in any graph, in terms of number of nodes.
- Correct Answer: (iii) BFS cannot be used to check for cycles in the graph.
(j) Finding the location of the element with a given value is
- (i) traversal
- (ii) search
- (iii) sort
- (iv) None of the above
- Correct Answer: (ii) search
2022
- (a) Any decision trees that sorts n elements has height…
- (i) Ω (1gn)
- (ii) Ω (n)
- (iii) Ω (nlgn)
- (iv) Ω (n²)
- Correct Answer: (iii) Ω (nlgn)
- Explanation: Any decision tree that sorts n elements must have at least n! leaves (one for each permutation). A binary tree of height h can have at most 2h leaves. Therefore, 2h ≥ n!. Taking logarithms, h ≥ log2(n!). Since log2(n!) is Θ(n log n), then height is Ω (nlgn).
- (b) Which one of the following is an application of Queue Data Structure?…
- (i) When a resource is shared among multiple consumers
- (ii) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
- (iii) Load balancing
- (iv) All of the above
- Correct Answer: (iv) All of the above
- Explanation: Queues are used for all listed applications.
- (c) The complexity of binary search algorithm is…
- (i) O(n)
- (ii) O(logn)
- (iii) O(n²)
- (iv) O(n logn)
- Correct Answer: (ii) O(logn)
- Explanation: Binary search divides the search space in half with each comparison.
- (d) In linear search algorithm the worst case occurs when…
- (i) the item is somewhere in the middle of the array
- (ii) the item is not in the array at all
- (iii) the item is the last element in the array
- (iv) the item is the last element in the array or is not there at all
- Correct Answer: (iv) the item is the last element in the array or is not there at all
- Explanation: In the worst case, linear search has to iterate all elements.
- (e) Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?…
- (i) Insertion sort with time complexity O(kn)
- (ii) Heap sort with time complexity O(nlogk)
- (iii) Quick sort with time complexity O(klogk)
- (iv) Merge sort with time complexity O (klogk)
- Correct Answer: (ii) Heap sort with time complexity O(nlogk)
- Explanation: Insertion sort is efficient on nearly sorted data.
- (f) Approach of dynamic programming is similar to…
- (i) parsing
- (ii) hash table
- (iii) divide and conquer algorithm
- (iv) greedy algorithm
- Correct Answer: (iii) divide and conquer algorithm
- Explanation: Both divide the problem and uses recursivity but dynamic programing store previous calculations.
- (g) In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of…
- (i) divide/break
- (ii) sorting/divide
- (iii) conquer/solve
- (iv) merge/combine
- Correct Answer: (i) divide/break
- Explanation: Obvious
- (h) A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements ‘1’ and ‘7’ are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is…
- (i) 10, 8, 7, 5, 3, 2, 1
- (ii) 10, 8, 7, 2, 3, 1, 5
- (iii) 10, 8, 7, 1, 2, 3, 5
- (iv) 10, 8, 7, 3, 2, 1, 5
- Correct Answer: (iii) 10, 8, 7, 1, 2, 3, 5
- Explanation: After inserting ‘7’ and reheapifying, ‘7’ will be in the third position.
- (i) If a problem can be solved by combining optimal solutions to non- overlapping problems, the strategy is called…
- (i) dynamic programming
- (ii) greedy
- (iii) divide and conquer
- (iv) recursion
- Correct Answer: (i) dynamic programming
- Explanation: By elimination
- (j) The choice of polynomial class has led to the development of an extensive theory called…
- (i) computational complexity
- (ii) time complexity
- (iii) problem complexity
- (iv) decision complexity
- Correct Answer: (i) computational complexity
- Explanation: By definition
2023
- (a) The fractional Knapsack problem can be solved by using…
- (i) Greedy method
- (ii) Divided and conquer method
- (iii) Dynamic programming
- (iv) None of the above
- Correct Answer: (i) Greedy method
- Explanation: Fractional Knapsack is a classic application of a greedy approach.
- (b) BFS on a graph G = (V,E) has running time…
- (i) O(|V|+|E|)
- (ii) 0 (V)
- (iii) O (|E|
- (iv) None of these
- Correct Answer: (i) O(|V|+|E|)
- Explanation: BFS visits each vertex and edge once
- (c) The minimum number of colors needed to color a graph having n > 3 vertices and 2 edges is…
- (i) 2
- (ii) 3
- (iii) 4
- (iv) 1
- Correct Answer: (i) 2
- Explanation: Can always be colored with 2 colors as it has so few edges
- (d) Complexity the recurrence relation T(n) = 8T (n/2) + n² is…
- (i) O (n)
- (ii) O (n²)
- (iii) O (log n)
- (iv) O(n³)
- Correct Answer: (iv) O(n³)
- Explanation: As already checked in previous answer
- (e) Travelling salesman problem belongs to…
- (i) P class
- (ii) NP class
- (iii) NP- hard
- (iv) NP- complete class
- Correct Answer: (iii) NP- hard
- Explanation: TSP is a classical NP-complete problem
- (f) Kruskal’s algorithm uses and Prism’ algorithm uses in determining the MST…
- (i) Edges, vertex
- (ii) vertex, edges
- (iii) Edges, edges
- (iv) Vertex, vertex
- Correct Answer: (i) Edges, vertex
- (g) Level order traversal of a rooted tree can be done by starting from root and performing…
- (i) Depth first search
- (ii) Breadth first search
- (iii) Pre-order traversal
- (iv) In-order traversal
- Correct Answer: (ii) Breadth first search
- Explanation: By definition
- (h) An algorithm is made up of two independent time complexities f(n) and g (n). Then the complexities of the algorithm is in order of…
- (i) f(n)x g(n)
- (ii) max(f(n)).g(n)
- (iii) min (f(n).g(n)
- (iv) f(n)+g(n)
- Correct Answer: ((ii) max(f(n)).g(n)
- Explanation: We have to add the complexity
- (i) Which of the following standard algorithms is not a greedy alogorithm?
- (i) Dijkstra’s shortest path algorithm
- (ii) Kruskal algorithm
- (iii) Bellmen ford shortest path algorithm
- (iv) Prim’s algorithm
- Correct Answer: (iii) Bellmen ford shortest path algorithm
- Explanation: Bellman Ford is based in dynamic programing
- (j) The node removal of which makes a graph disconnected is called
- (i) Pendant vertex
- (ii) Bridge
- (iii) Articulation point
- (iv) Coloured vertex
- Correct Answer: (iii) Articulation point
- Explanation: By definition
I hope this helps you in the preparation