Techno Blender
Digitally Yours.

Algorithms – GATE CSE Previous Year Questions

0 37


Solving GATE Previous Year’s Questions (PYQs) not only clears the concepts but also helps to gain flexibility, speed, accuracy, and understanding of the level of questions generally asked in the GATE exam, and that eventually helps you to gain good marks in the examination. Previous Year Questions help a candidate practice and revise for GATE, which helps crack GATE with a good score. 

Algorithms Previous Year GATE Questions help in analyzing the question pattern of a subject and marking scheme as well as it helps in time management which overall increases the score in the GATE exam. With regular practice of PYQs, candidates can easily crack GATE with a good GATE Score.

Before 2006, questions asked in GATE were mainly theoretical, but in recent years, the questions asked were multiple-choice questions with a single correct option or multiple correct options. We are looking to provide the multiple-choice questions that are asked in GATE.

Algorithms GATE Previous Year Questions

In this article, we are mainly focusing on the Algorithms GATE Questions that are asked in Previous Years with their solutions, and where an explanation is required, we have also provided the reason.

In Algorithms, we will deal with the following concepts. We have also provided GATE Previous Year’s Questions on these topics. Here is the list of those topics along with their links.

Also, here we are going to discuss some basic PYQs related to Algorithms.

1. Which one of the following statements is TRUE for all positive functions f(n)? [GATE CSE 2022]

(A) f(n2) = θ(f(n)2), when f(n) is a polynomial

(B) f(n2) = o(f(n)2)

(C) f(n2) = O(f(n)2), when f(n) is an exponential function

(D) f(n2) = Ω(f(n)2)

Solution: Correct answer is (A)

For more, refer to GATE | CS 2022 | Question 11.

2. For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1. Then T(n) is [GATE 2020]

(A) θ(logalogbn)

(B) θ(logabn)

(C) θ(logblogan)

(D) θ(log2log2n)

Solution: Correct answer is (A)

For more, refer to GATE | GATE CS 2020 | Question 12.

3. The Floyd-Warshall algorithm for all-pair shortest paths computation is based on [GATE CSE 2016]

(A) Greedy Algorithm

(B) Divide-and-Conquer Paradigm

(C) Dynamic Programming Paradigm

(D) neither Greedy nor Divide-and-Conquer nor Dynamic Programming Paradigm

Solution: Correct answer is (C)

For more, refer to GATE | GATE-CS-2016 (Set 2) | Question 24.

4. Which one of the following is the recurrence equation for the worst-case time complexity of the Quicksort algorithm for sorting (n ≥ 2) numbers? In the recurrence equations given in the options below, c is a constant. [GATE CSE 2015]

(A) T(n) = 2T(n/2) + cn

(B) T(n) = T(n-1) + T(0) + cn

(C) T(n) = 2T(n-1) + cn

(D) T(n) = T(n/2) + cn

Solution: Correct answer is (B)

For more, refer to GATE | GATE-CS-2015 (Set 1) | Question 12.

5. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is [GATE CSE 2015]

(A) θ(n log n)

(B) θ(n)

(C) θ(log n)

(D) θ(1)

Solution: Correct answer is (D)

For more, refer to GATE | GATE-CS-2015 (Set 2) | Question 65.

6. Consider the following array of elements: (89,19,50,17,12,15,2,5,7,11,6,9,100). The minimum number of interchanges needed to convert it into a max-heap is [GATE CSE 2015]

(A) 4

(B) 5 

(C) 2 

(D) 3

Solution: Correct answer is (D)

For more, refer to GATE | GATE-CS-2015 (Set 3) | Question 65.

7. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of [GATE CSE 2004]

(A) n

(B) n2

(C) n log n

(D) n log2 n

Solution: Correct answer is (C)

For more, refer to Algorithms | Sorting | Question 13.

8. The problems 3-SAT and 2-SAT are [GATE CSE 2004]

(A) both in P

(B) both NP-Complete

(C) NP-Complete and in P respectively

(D) Undecidable and NP-Complete respectively

Solution: Correct answer is (C)

For more, refer to GATE-CS-2004 | Question 30.

9. A sorting technique is called stable if: [GATE CSE 1999]

(A) It takes O(n log n) time

(B) It maintains the relative order of occurrence of non-distinct elements.

(C) It uses divide and conquers paradigm

(D) It takes O(n) space

Solution: Correct answer is (B)

For more, refer to GATE | GATE CS 1999 | Question 12.

10. For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of [GATE CSE 1995]

(A) O(m)

(B) O(n)

(C) O(m+n)

(D) O(log m + log n)

Solution: Correct answer is (C)

GATE CSE Previous Year Question Papers

These previous year’s questions help you in understanding the question patterns followed by GATE that directly help a candidate in scoring good marks in GATE. Below are the mentioned links of year-wise GATE Previous Question Papers.

Last Updated :
20 May, 2023

Like Article

Save Article


Solving GATE Previous Year’s Questions (PYQs) not only clears the concepts but also helps to gain flexibility, speed, accuracy, and understanding of the level of questions generally asked in the GATE exam, and that eventually helps you to gain good marks in the examination. Previous Year Questions help a candidate practice and revise for GATE, which helps crack GATE with a good score. 

Algorithms Previous Year GATE Questions help in analyzing the question pattern of a subject and marking scheme as well as it helps in time management which overall increases the score in the GATE exam. With regular practice of PYQs, candidates can easily crack GATE with a good GATE Score.

Before 2006, questions asked in GATE were mainly theoretical, but in recent years, the questions asked were multiple-choice questions with a single correct option or multiple correct options. We are looking to provide the multiple-choice questions that are asked in GATE.

Algorithms GATE Previous Year Questions

In this article, we are mainly focusing on the Algorithms GATE Questions that are asked in Previous Years with their solutions, and where an explanation is required, we have also provided the reason.

In Algorithms, we will deal with the following concepts. We have also provided GATE Previous Year’s Questions on these topics. Here is the list of those topics along with their links.

Also, here we are going to discuss some basic PYQs related to Algorithms.

1. Which one of the following statements is TRUE for all positive functions f(n)? [GATE CSE 2022]

(A) f(n2) = θ(f(n)2), when f(n) is a polynomial

(B) f(n2) = o(f(n)2)

(C) f(n2) = O(f(n)2), when f(n) is an exponential function

(D) f(n2) = Ω(f(n)2)

Solution: Correct answer is (A)

For more, refer to GATE | CS 2022 | Question 11.

2. For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1. Then T(n) is [GATE 2020]

(A) θ(logalogbn)

(B) θ(logabn)

(C) θ(logblogan)

(D) θ(log2log2n)

Solution: Correct answer is (A)

For more, refer to GATE | GATE CS 2020 | Question 12.

3. The Floyd-Warshall algorithm for all-pair shortest paths computation is based on [GATE CSE 2016]

(A) Greedy Algorithm

(B) Divide-and-Conquer Paradigm

(C) Dynamic Programming Paradigm

(D) neither Greedy nor Divide-and-Conquer nor Dynamic Programming Paradigm

Solution: Correct answer is (C)

For more, refer to GATE | GATE-CS-2016 (Set 2) | Question 24.

4. Which one of the following is the recurrence equation for the worst-case time complexity of the Quicksort algorithm for sorting (n ≥ 2) numbers? In the recurrence equations given in the options below, c is a constant. [GATE CSE 2015]

(A) T(n) = 2T(n/2) + cn

(B) T(n) = T(n-1) + T(0) + cn

(C) T(n) = 2T(n-1) + cn

(D) T(n) = T(n/2) + cn

Solution: Correct answer is (B)

For more, refer to GATE | GATE-CS-2015 (Set 1) | Question 12.

5. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is [GATE CSE 2015]

(A) θ(n log n)

(B) θ(n)

(C) θ(log n)

(D) θ(1)

Solution: Correct answer is (D)

For more, refer to GATE | GATE-CS-2015 (Set 2) | Question 65.

6. Consider the following array of elements: (89,19,50,17,12,15,2,5,7,11,6,9,100). The minimum number of interchanges needed to convert it into a max-heap is [GATE CSE 2015]

(A) 4

(B) 5 

(C) 2 

(D) 3

Solution: Correct answer is (D)

For more, refer to GATE | GATE-CS-2015 (Set 3) | Question 65.

7. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of [GATE CSE 2004]

(A) n

(B) n2

(C) n log n

(D) n log2 n

Solution: Correct answer is (C)

For more, refer to Algorithms | Sorting | Question 13.

8. The problems 3-SAT and 2-SAT are [GATE CSE 2004]

(A) both in P

(B) both NP-Complete

(C) NP-Complete and in P respectively

(D) Undecidable and NP-Complete respectively

Solution: Correct answer is (C)

For more, refer to GATE-CS-2004 | Question 30.

9. A sorting technique is called stable if: [GATE CSE 1999]

(A) It takes O(n log n) time

(B) It maintains the relative order of occurrence of non-distinct elements.

(C) It uses divide and conquers paradigm

(D) It takes O(n) space

Solution: Correct answer is (B)

For more, refer to GATE | GATE CS 1999 | Question 12.

10. For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of [GATE CSE 1995]

(A) O(m)

(B) O(n)

(C) O(m+n)

(D) O(log m + log n)

Solution: Correct answer is (C)

GATE CSE Previous Year Question Papers

These previous year’s questions help you in understanding the question patterns followed by GATE that directly help a candidate in scoring good marks in GATE. Below are the mentioned links of year-wise GATE Previous Question Papers.

Last Updated :
20 May, 2023

Like Article

Save Article

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment