8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

Ada Assignment 2 Gate Based Aptitude

Total points 16/20

Ada Assignment 2 Gate Based Aptitude

Email *

[email protected]

NAME

Himanshu Chouhan

USN NO

1ST22CY018

1. Which of the following statements is true about the time complexity of 1/1
an algorithm?

It gives an exact runtime of the algorithm.

It provides an upper bound on the runtime

It provides a lower bound on the runtime

It provides a average bound on the runtime.

Feedback

Explanation: Time complexity typically provides an upper bound on the runtime of an

algorithm.

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 1/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

2.Which of the following is the correct Big O notation for the time 1/1
complexity of binary search?

O(n)

O(n log n)

O(log n)

O(1)

3. Which of the following sorting algorithms has the worst-case time 1/1
complexity of O(n^2)?

a) Merge Sort

b) Quick Sort

c) Bubble Sort

d) Heap Sort

4. The time complexity to search an element in a balanced binary search 1/1

tree with n nodes is:

O(1)

b) O(log n)

c) O(n)

d) O(n log n)

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 2/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

5. In the context of algorithm analysis, which of the following asymptotic 1/1

notations is used to denote the lower bound of an algorithm's running
time?

Big O (O)

b) Big Omega (Ω)

c) Big Theta (Θ)

d) Little o (o)

6. Which data structure is used to implement a LIFO (Last In, First Out) 1/1
structure?

a) Queue

b) Stack

c) Linked List

d) Tree

7. In a directed graph, a topological sort is possible only if the graph 1/1

a) Contains no cycles

b) Contains at least one cycle

c) Is fully connected

d) Has a unique path between every pair of vertices

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 3/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

8. What is the best-case time complexity of the insertion sort algorithm? 1/1

O(n)

O(n log n)

O(n^2)

O(log n)

9. Which of the following problems is a classic example of a problem that 0/1

can be solved using dynamic programming?

Longest Common Subsequence

Breadth-First Search

Depth-First Search

Binary Search

Correct answer

Longest Common Subsequence

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 4/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

10. The primary operation performed by Prim's algorithm in finding the 0/1
Minimum Spanning Tree is:

Selection

Insertion

Comparison

Deletion

Correct answer

Selection

11. Dijkstra’s algorithm is used to find: 1/1

a) Shortest path in an unweighted graph

b) Shortest path in a weighted graph with non-negative weights

c) Shortest path in a weighted graph with negative weights

d) Minimum Spanning Tree in a graph

12. Which of the following techniques is used by the quicksort algorithm? 1/1

a) Greedy approach

b) Divide and conquer

c) Dynamic programming

d) Backtracking

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 5/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

13. The complexity class NP consists of decision problems that can be 1/1

Solved in polynomial time by a deterministic Turing machine

Solved in polynomial time by a non-deterministic Turing machine

Solved in exponential time by a deterministic Turing machine

Verified in polynomial time by a deterministic Turing machine

14. In the context of graph algorithms, which algorithm is used to detect 1/1
cycles in a directed graph?

a) Depth-First Search

b) Breadth-First Search

c) Dijkstra’s Algorithm

d) Floyd-Warshall Algorithm

15. Which of the following statements is true about the complexity classes 0/1
P and NP?

a) P = NP

b) P is a subset of NP

c) NP is a subset of P

d) P and NP are disjoint sets

Correct answer

b) P is a subset of NP

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 6/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

16. In the context of dynamic programming, what is memoization? 1/1

a) Storing the results of subproblems to avoid redundant computations

b) Dividing a problem into subproblems

c) Combining solutions of subproblems

d) Using a stack to keep track of recursive calls

17. Which of the following is an example of a greedy algorithm? 1/1

a) Merge Sort

b) Quick Sort

c) Kruskal's Algorithm

d) Depth-First Search

18. In a heap data structure, the time complexity to extract the maximum 0/1
element is

a) O(1)

b) O(log n)

c) O(n)

d) O(n log n)

Correct answer

b) O(log n)

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 7/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

19. The Floyd-Warshall algorithm is used to find 1/1

a) Single-source shortest path

b) Minimum spanning tree

c) All-pairs shortest paths

d) Maximum flow in a network

20. Which sorting algorithm is not based on the divide-and-conquer *1/1

technique?

A. Merge Sort

B. Quick Sort

C. Heap Sort

D. Binary Search

This content is neither created nor endorsed by Google. Report Abuse - Terms of Service - Privacy Policy

Forms

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 8/9
8/10/24, 10:29 AM Ada Assignment 2 Gate Based Aptitude

https://docs.google.com/forms/d/e/1FAIpQLSduV5K6CYCiv_1WUSoHRNkKwO23wCCOUFD19HQhCioKKm2mew/viewscore?vc=0&c=0&w=1&flr… 9/9