CL/ARVR

What does the Master Theorem provide a solution for?

• a) Space complexity of algorithms

• b) Time complexity of divide-and-conquer algorithms

• c) Sorting algorithms

• d) Dynamic programming algorithms

Which scenario would make the Master Theorem inapplicable?

• a) When the subproblems cannot be solved independently

• b) When the size of the subproblems decreases by a constant factor at each step

• c) When the problem size decreases exponentially with each recursive call

• d) When the time complexity cannot be expressed as a recurrence relation

What is the time complexity of the merge sort algorithm?

• a) O(n)

• b) O(n log n)

• c) O(n^2)

• d) O(1)

What is the space complexity of the binary search algorithm?

• a) O(1)

• b) O(log n)

• c) O(n)

• d) O(n^2)

What is the space complexity of Bubble Sort?

• a) O(1)

• b) O(log n)

• c) O(n)

• d) O(n^2)

Which of the following scenarios is BFS well-suited for?

• a) Finding the maximum flow in a network

• b) Topological sorting of a graph

• c) Finding the shortest path between two vertices in an unweighted graph

• d) Solving the traveling salesman problem

Which of the following data structures is used to keep track of visited vertices in BFS to avoid revisiting them?

• a) Stack

• b) Queue

• c) Hash Table or Set

• d) Binary Search Tree

Which of the following data structures is used to implement priority queue?

• a) Stack

• b) Queue

• c) Heap

• d) Linked List

What is the space complexity of the depth-first search (DFS) algorithm?

• a) O(n)

• b) O(log n)

• c) O(n^2)

• d) O(1)

DFS is often used to find:

• a) Shortest paths in graphs

• b) Longest paths in graphs

• c) Cycles in graphs

• d) All-pairs shortest paths in graphs