B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 2 — Questions and Answers
Question 1: What is the recurrence relation for merge sort, and what does the Master Theorem give as its solution?
- T(n) = T(n-1) + O(1) → O(n)
- T(n) = 2T(n/2) + O(n) → O(n log n) (Correct answer)
- T(n) = T(n/2) + O(1) → O(log n)
- T(n) = 2T(n/2) + O(n²) → O(n²)
Correct answer: T(n) = 2T(n/2) + O(n) → O(n log n)
Merge sort divides into 2 halves (2T(n/2)) and merges in O(n) time; by the Master Theorem case 2, this solves to O(n log n).
Question 2: In which problem class does P reside in the P vs NP question?
- Problems solvable in polynomial time (Correct answer)
- Problems verifiable in polynomial time but not solvable
- Problems requiring exponential time to solve and verify
- Problems that are undecidable
Correct answer: Problems solvable in polynomial time
P is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, representing 'tractable' or efficiently solvable problems.
Question 3: What is memoization in the context of dynamic programming?
- Sorting results before storing them
- Caching the results of subproblems in a table to avoid recomputation (Correct answer)
- Breaking a problem into independent subproblems
- Choosing locally optimal solutions at each step
Correct answer: Caching the results of subproblems in a table to avoid recomputation
Memoization is a top-down DP technique where computed subproblem results are stored (usually in a hash map or array) so they can be retrieved instantly if needed again.
Question 4: What is the key property of a greedy algorithm?
- It explores all possible solutions before choosing the best one
- It makes the locally optimal choice at each step without reconsidering past decisions (Correct answer)
- It divides the problem into equal halves recursively
- It uses randomness to find near-optimal solutions
Correct answer: It makes the locally optimal choice at each step without reconsidering past decisions
A greedy algorithm makes the best choice available at each step and never revisits or undoes those choices, hoping the locally optimal selections lead to a global optimum.
Question 5: Which algorithm is used to find the Minimum Spanning Tree of a graph using a priority queue?
- Kruskal's Algorithm
- Dijkstra's Algorithm
- Prim's Algorithm (Correct answer)
- Bellman-Ford Algorithm
Correct answer: Prim's Algorithm
Prim's algorithm builds a Minimum Spanning Tree by greedily adding the minimum-weight edge connecting the current tree to an unvisited vertex, using a priority queue.
Question 6: What is the worst-case time complexity of Quick Sort?
- O(n log n)
- O(n²) (Correct answer)
- O(log n)
- O(n)
Correct answer: O(n²)
Quick Sort degrades to O(n²) in the worst case when the pivot is always the smallest or largest element, causing maximally unbalanced partitions.
B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 2
What is the recurrence relation for merge sort, and what does the Master Theorem give as its solution?