Font size
WorksheetsCL/ARVR
Total questions: 15
Worksheet time: 15mins
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
Which of the following recurrence relations can be solved using the substitution method?
a) T(n) = T(n/2) + n
b) T(n) = 2T(n/2) + n
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + 1
What is the key principle behind the substitution method?
a) Breaking down complex problems into simpler subproblems.
b) Substituting variables to simplify mathematical expressions.
c) Making educated guesses and verifying them through induction.
d) Iteratively refining algorithms to improve performance.
In Big O notation, what does O(n) represent?
a) Constant time complexity
b) Linear time complexity
c) Quadratic time complexity
d) Exponential time complexity
Which sorting algorithm is not recommended for large datasets due to its poor time complexity?
a) Insertion Sort
b) Quick Sort
c) Merge Sort
d) Bubble Sort
Which searching algorithm is commonly used to search in trees and graphs?
a) Linear Search
b) Binary Search
c) Depth-First Search
d) Breadth-First Search
