Algorithm Gate Questions

Here, We will see Algorithm GATE Questions from previous year’s papers and the syllabus of Algorithm for GATE Exam.

1. Algorithm in Gate CSE Exam

Algorithms form the backbone of problem-solving in computer science and hold significant weightage in the GATE CSE exam. This section evaluates a candidate’s ability to design efficient solutions, analyze complexities, and apply algorithmic paradigms to real-world scenarios.

2. Algorithm Syllabus

The syllabus for Algorithm in GATE CSE includes:

1. Algorithm Analysis: Asymptotic notations (Big-O, Omega, Theta) and worst-case time/space complexity analysis. Recurrence relations and solving techniques (e.g., Master’s Theorem).
2. Design Techniques: Divide and Conquer– Merge Sort, QuickSort, Strassen’s Matrix Multiplication. Greedy Algorithms– Fractional Knapsack, Huffman Coding, Activity Selection. Dynamic Programming– Longest Common Subsequence, Matrix Chain Multiplication, Bellman-Ford. Backtracking– N-Queens, Graph Coloring
3. Graph Algorithms: Traversal (BFS, DFS), Shortest Path (Dijkstra, Floyd-Warshall), Minimum Spanning Trees (Prim’s, Kruskal’s). NP-Completeness and reductions.
4. Advanced Topics: Hashing techniques, String Matching (KMP, Rabin-Karp), and Branch-and-Bound methods

Algorithm Gate Questions

Q. A hash table has space for 100 records. Then the probability of collision before the table is 10% full, is

1. 0.45
2. 0.5
3. 0.3
4. 0.34(approximately)

Q. What is the type of the algorithm used in solving the 4 Queens problem?

1. Greedy
2. Branch and Bound
3. Dynamic
4. Backtracking

Q. The Knapsack problem belongs to which domain of problems?

1. Optimization
2. NP complete
3. Linear Solution
4. Sorting

Q. Dijkstra’s algorithm is based on

1. Greedy approach
2. Dynamic programming
3. Backtracking paradigm
4. Divide and conquer paradigm

Q. Which notation gives the lower bound of a function

1. Θ–notation
2. O–notation
3. Ω–notation
4. None of the these

Q. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

1. solves it in linear time using a left to right pass of the array
2. solves in linear time using a right-to-left pass of the array
3. solves it using divide and conquer in time θ(nlogn)
4. solves it in time θ(n²)

Q. Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

1. SDT
2. SBDT
3. SACDT
4. SACET

Q. What will be the Eulerian tour of the following graph G?

1. 1-2-3-4-5-6-7-8-6-4-2-8-1
2. 1-2-3-4-5-6-7-8
3. 1-2-3-4-5-6-7-8-1
4. 8-7-6-5-4-3-2-1

Q. Which of the following methods can be used to solve the Knapsack problem?

1. Brute force algorithm
2. Recursion
3. Dynamic programming
4. Brute force, Recursion, and Dynamic Programming

Q. Arrange the following in increasing orders of asymptotic complexity.
f₁(n)=2ⁿ, f₂(n)=n^3/2, f₃(n)=nlogn, f₄(n)=n^logn

1. f₃,f₂,f₄,f₁
2. f₃,f₂,f₁,f₄
3. f₂,f₃,f₁,f₄
4. f₂,f₃,f₄,f₁

Q. Two alternative package A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires 10nlog₁₀​n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

1. 12
2. 10
3. 6
4. 5

Q. What is the running time of the following function (specified as a function of the input value)?

void Function(int n) {
  int i = 1;
  int s = 1;
  while (s <= n) {
    i++;
    s = s + i;
  }
}

1. O(n)
2. O(n²)
3. O(1)
4. O(√n)

Q. Which type of algorithm is used to solve the “8 Queens” problem ?

1. Greedy
2. Dynamic
3. Divide and conquer
4. Backtracking

Q. The given array is arr={1,2,3,4}. Bubble sort is used to sort the array elements. How many passes will be done to sort the array?

1. 4
2. 2
3. 1
4. 3

Q. Find the odd one out

1. Merge Sort
2. TVSP Problem
3. Knapsack Problem
4. OBST Problem

Q. Let B_n denote the number of full binary trees with n vertices. Then a recurrence relation for B_n is :

1. B_n = B_n-1+O(1)
2. B_n = 2B_n-1+O(1)
3. B_n = B_n-1+O(n)
4. B_n = 2B_n-1+O(n)

Q. Merge sort uses :

1. Divide-and-conquer
2. Backtracking
3. Heuristic approach
4. Greedy approach

Q. Which of the following standard algorithms is not Dynamic Programming based?

1. Bellman-Ford Algorithm for single source shortest path
2. Floyd Warshall Algorithm for all pairs shortest paths
3. 0-1 Knapsack problem
4. Prim’s Minimum Spanning Tree

Q. Worst case scenario in case of linear search algorithm is ________ .

1. Item is somewhere in the middle of the array.
2. Item is not in the array at all.
3. Item is the last element in the array.
4. Item is the last element in the array or is not there at all.

Q. Which of the following sorting algorithms has the lowest worst-case complexity

1. Merge sort
2. Bubble sort
3. Quick sort
4. Insertion sort

Q. Four Matrices M1, M2, M3 and M4 of dimensions p×q, q×r , r×s and s×t respectively can be multiplied in several ways with different number of total scalar multiplications. For example, when multiplied as ((M1×M2)×(M3×M4)), the total number of multiplications is pqr+rst+prt. When multiplied as (((M1×M2)×M3)×M4), the total number of scalar multiplications is pqr+prs+pst.
If p=10, q=100, r=20, s=5 and t=80, then the number of scalar multiplications needed is

1. 248000
2. 44000
3. 19000
4. 25000

Q. Which type of illustration lists the functionality of whole project?

1. DFD-0
2. Class Diagram
3. Use case Diagram
4. State Diagram

Q. Let G be a graph with n vertices and m edges.What is the tightest upper bound on the running time of Depth First Search of G, when G is represented using adjacency matrix?

1. O(n)
2. O(m+n)
3. O(n²)
4. O(mn)

Q. Dijkstra’s Algorithm cannot be applied on ___________ .

1. Directed and weighted graphs
2. Graphs having negative weight function
3. Unweighted graph
4. Undirected and unweighted graphs

Q. Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be :

1. m*n
2. minimum of m,n
3. maximum of m,n
4. m+n-1

Q. Consider the algorithm that solves problems of size n by recursively solving two sub problems of size n-1 and then combining the solutions in constant time. Then the running time of the algorithm would be:

1. O(2ⁿ)
2. O(logn)
3. O(nlogn)
4. O(n²)

Q. Which of the following algorithm solve the all-pair shortest path problem?

1. Dijakstra’s algorithm
2. Floyd’s algorithm
3. Prim’s algorithm
4. Warshall’s algorithm

Q. Which of the following Page Replacement Algorithm suffers from the Belady’s anomaly?

1. LRU
2. Optimal page Replacement
3. FIFO
4. Both LRU and FIFO

Q. Which of the following algorithms can be used to most efficiently find whether a cycle is present in a given graph?

1. Prim’s Minimum Spanning Tree Algorithm
2. Breadth First Search
3. Depth First Search
4. Kruskal’s Minimum Spanning Tree Algorithm

Q. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to __________.

1. Total number of vertices
2. Total number of edges
3. Number of vertices-1
4. Number of edges-1

Q. Write Recurrence of Quick Sort in worst case.

1. T(n) = T(n-1)+1
2. T(n) = T(n-1)+n
3. T(n) = 2T(n-1)+n
4. T(n) = T(n/3)+T(2n/2)+n

Q. A hash function f defined as f(key)=key mod7, with linear probing, insert the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 11 will be stored in the location

1. 3
2. 4
3. 5
4. 8

Q. The average search time of hashing, with linear probing will be less if the load factor :

1. is far less than 1
2. equals 1
3. is far greater than 1
4. none of the options

Q. The average search time for hashing with linear probing will be less if the load factor

1. is far less than one
2. Equals one
3. is far greater than one
4. None of the above

Q. 100 elements can be sorted in 100 sec using bubble sort. In 400 sec, approximately ________ elements can be sorted.

1. 100
2. 200
3. 300
4. 400

Q. 0/1-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing n items (each item is having some weight and associated profit) into a knapsack of capacity W. The table given below shows the weights and associated profits for 5 items, where one unit of each item is available to you. It is also given that the knapsack capacity W is 8. If the given 0/1 knapsack problem is solved using Dynamic Programming, which one of the following will be maximum earned profit by placing the items into the knapsack of capacity 8.

1. 19
2. 18
3. 17
4. 20

Q. Which of the following is a correct time complexity to solve the 0/1 knapsack problem where n and w represents the number of items and capacity of knapsack respectively?

1. O(n)
2. O(w)
3. O(nw)
4. O(n+w)

Q. The running time of an algorithm T(n), where ‘n’ is the input size , is given by
T(n)=8T(n/2)+qn, if n>1
=p, if n=1 where p,q are constants.
The order of this algorithm is

1. n²
2. nⁿ
3. n³
4. n

Q. The running time of Quick sort algorithm depends heavily on the selection of:

1. No. of inputs
2. Arrangement of elements in an array
3. Size of elements
4. Pivot Element

Q. Which of the following is correct recurrence for worst case of QuickSort?

1. T(n)=T(n-4)+T(n-2)+O(1)
2. T(n)=T(n-1)+T(0)+O(n)
3. T(n)=2T(n/2)+O(n)
4. T(n)=4T(n/2)+O(n)

Q. Consider an array of positive integers between 123456 to 876543, which sorting algorithm can be used to sort these number in linear time?

1. Impossible to sort in linear time
2. Radix Sort
3. Insertion Sort
4. Bubble Sort

Q. What is the solution to the recurrence T(n)=T(n/2)+n?

1. O(logn)
2. O(n)
3. O(nlogn)
4. None of these

Q. Time complexity of an algorithm T(n), where n is the input size is given by
T(n)=T(n-1)+1/n, if n>1
=1, otherwise
The order of this algorithm

1. logn
2. n
3. n²
4. nⁿ

Q. The time complexity of solving the Longest Common Subsequence problem using Dynamic Programming is : (m and n are lengths of subsequences)

1. O(m.n)
2. O(m+n)
3. O(log m.n)
4. O(m/n)

Q. Suppose T(n)=2T(N/2)+n, T(0)=T(1)=1, which one of the following is false?

1. T(N)=O(n²)
2. T(n)=Θ(nlogn)
3. T(n)=Ω(n²)
4. T(n)=O(nlogn)

Q. For the given recurrence equation

(n) = 2 T(n - 1),
  if n > 0 = 1, otherwise

1. O(nlogn)
2. O(n²)
3. O(2ⁿ)
4. O(n)

Q. What is the time complexity of the following recursive function?

int ComputFun(int n) {
  if (n <= 2)
    return 1;
  else
    return (ComputFun(floor(sqrt(n))) + n);
}

1. Θ(n)
2. Θ(logn)
3. Θ(nlogn)
4. Θ(loglogn)

Q. The recurrence relation for binary search algorithm is :

1. T(n) = 2T(n/2) + O(1)
2. T(n) = 2T(n/2) + O(n)
3. T(n) = T(n/2) + O(1)
4. T(n) = T(n/2) + O(n)

Q. Which of the following is not a stable sorting algorithm?

1. Insertion sort
2. Selection sort
3. Bubble sort
4. Merge sort

Q. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in 1. The worst case number of probes performed by an optimal algorithm is

1. 2
2. 4
3. 3
4. 5

Q. Assembly line scheduling and Longest Common Subsequence problems are an example of _.

1. Dynamic Programming
2. Greedy Algorithms
3. Greedy Algorithms and Dynamic Programming respectively
4. Dynamic Programming and Branch and Bound respectively

Q. Finding the location of the element with a given value is

1. Traversal
2. Search
3. Sort
4. None of the options

Q. Which of the following sorting procedures is the slowest?

1. Quick Sort
2. Merge Sort
3. Shell Sort
4. Bubble Sort

Q. Selection sort, quick sort is a stable sorting method

1. True,True
2. False,False
3. True,False
4. False,True

Q. The Highest Lower Bound on the number of Comparisons in the worst case for comparison-based sorting order of :

1. n
2. n²
3. n logn
4. n log₂n

Q. Which of the following sorting algorithms does not have a worst case running time of O(n²)?

1. Insertion sort.
2. Merge sort.
3. Quick sort.
4. Bubble sort.

Q. ____________ sorting algorithms has the lowest worst-case complexity.

1. Selection Sort
2. Bubble Sort
3. Merge Sort
4. Quick Sort

Q. Complexity of Kruskal’s algorithm for finding minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is:

1. O(mn)
2. O(m)
3. O(m+n)
4. O(n)

Q. Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this:
16 14 15 10 12 27 28
How many heapify operations have been performed on root of heap ?

1. 1
2. 2
3. 3 or 4
4. 5 or 6

Q. If a hash table is implemented as a search tree, the expected time required to enter n names and make m searches is proportional to :

1. (n+m) log₂n
2. (n+m) log₂m
3. mn log₂n
4. mn log₂m

Q. The concept of order Big O is important because

1. It can be used to decide the best algorithm that solves a given problem
2. It is the lower bound of the growth rate of algorithm
3. It determines the maximum size of a problem that can be solved in a given amount of time
4. Both (A) and (B)

Q. The time complexity of heap sort in worst case is :

1. O(logn)
2. O(n)
3. O(nlogn)
4. O(n²)

Q. The most efficient algorithm for finding the number of connected components in a n undirected graph on n vertices and m edges has time complexity

1. Θ(n)
2. Θ(m)
3. Θ(m+n)
4. Θ(mn)

Q. In the recurrence relation
T(n) = 0.5*T(n/2)+1/n, which case of Master Theorem is suitable?

1. Case 1
2. Master Theorem not applicable in this situation
3. Case 2
4. Case 3

Q. Which of the following Page Replacement Algorithm suffers from the belady’s anomaly?

1. LRU
2. Optimal Page Replacement
3. FIFO
4. Both LRU and FIFO

Q. Which sorting algorithm sorts by moving the current data element past the already sorted values and repeatedly interchanges it with the preceding value until it is in its correct place?

1. Insertion sort
2. Internal sort
3. External sort
4. Radix sort

Q. Consider the following two statements:
i. A hash function (these are often used for computing digital signatures) is an injective function.
ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?

1. Both are false
2. Statement (i) is true and the other is false
3. Statement (ii) is true and the other is false
4. Both are true

Q. To the detection of up to 5 errors in all cases, the minimum Hamming distance in a block code must be _________ .

1. 5
2. 6
3. 10
4. 8

Q. What is the best case complexity of QuickSort?

1. O(nlogn)
2. O(logn)
3. O(n)
4. O(n²)

Q. Typical time requirement for operations on queues is :

1. O(1)
2. O(n)
3. O(logn)
4. O(n²)

Q. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are

1. Θ(nlogn), Θ(nlogn) and Θ(n²)
2. Θ(n²), Θ(n²) and Θ(nlogn)
3. Θ(n²), Θ(nlogn) and Θ(nlogn)
4. Θ(n²), Θ(nlogn) and Θ(n²)

Q. What is the time complexity of the following recursive function?

int ComputFun(int n) {
  if (n <= 2)
    return 1;
  else
    return (DoSomething(floor(sqrt(n))) + n);
}

1. Θ(n)
2. Θ(logn)
3. Θ(n logn)
4. Θ(log logn)

Q. An algorithm is made up of two modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order of algorithm is

1. max(f(n),g(n))
2. min(f(n),g(n))
3. f(n)+g(n)
4. f(n)×g(n)

Q. Division in merge sort algorithm is based on which approach:

1. Parallel
2. Random
3. Interactive
4. Recursive

Q. Consider the following C code segment:

int Ls Prime(n) {
  int i, n;
  for (i = 2; i <= sqrt(n); i++)
    if (n % i == 0) {
      printf(“NOT Prime.\n”);
      return 0;
    }
  return 1;
}

Let T(n) denote the number of times the for loop is executed by the program on input n.Which of the following is true?

1. T(n)=O(√n) and T(n)=Ω(√n)
2. T(n)=O(√n) and T(n)=Ω(1)
3. T(n)=O(n) and T(n)=Ω(√n)
4. None of these

Q. ALU does not perform the operation of

1. Data transfer
2. Logical operation
3. Arithmetic operation
4. Comparison operation

Q. The recurrence relation T(n)=7T(n/7)+n has the solution:

1. O(n)
2. O(logn)
3. O(nlog(n))
4. O(n²)

Q. If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20,47,15,8,9,4,40,30,12,17 then the order of these elements after the second pass of the algorithm is:

1. 8,9,15,20,47,4,12,17,30,40
2. 8,15,20,47,4,9,30,40,12,17
3. 15,20,47,4,8,9,12,30,40,17
4. 4,8,9,15,20,47,12,17,30,40

Q. The best running time is defined as/obtained as/by:

1. the least or smallest of all the running times the algorithm takes, on inputs of a particular size
2. an input that requires maximum computations or resources
3. averaging the different running times for all inputs of a particular kind
4. none of the options

Q. In which of the following hash functions, do consecutive keys map to consecutive hash values?

1. Division method
2. Multiplication method
3. Folding method
4. Mid-square method

Q. Which of the following property is related to a cryptographic hash functions?

1. One way Function
2. Inversible
3. Non-Deterministic
4. All of the options

Q. A sorting algorithm which passes through a list to exchange the first element with smallest element in the remaining elements is known as____________.

1. Insertion sort
2. Selection sort
3. Heap sort
4. Bubble sort

Q. What is the advantage of bubble sort over other sorting techniques?

1. It is faster
2. Consumes less memory
3. Detects whether the input is already sorted
4. All of the options

Q. ______ uses pretty good privacy algorithm.

1. Electronic mails
2. File encryption
3. Both Electronic mails and File encryption
4. None of the options

Q. Which of the following can be used when creating a pool of global addresses instead of the netmask command?

1. /(slash notation)
2. prefix-length
3. no mask
4. block-size

Q. In the congestion avoidance algorithm, the size of the congestion window increases _________ until congestion is detected.

1. Exponentially
2. Additively
3. Multiplicatively
4. Suddenly

Q. What is the time complexity of the following function?

void myfun() {
  int a, b;
  for (a = 1; a <= n; a++)
    for (b = 1; b <= log(a); b++)
      printf(“My Function”);
}

1. θ(n)
2. θ(n²)
3. θ(nlogn)
4. θ(n²(logn))

Q. Merge Sort divides the input list in:

1. N equal parts
2. Three equal parts
3. Two parts which may not be equal
4. N parts which may not be equal

Q. Two main measures for the efficiency of an algorithm are:

1. Processor and Memory
2. Complexity and Capacity
3. Time and Space
4. Data and Space