B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 2

Question 1

What is the recurrence relation for merge sort, and what does the Master Theorem give as its solution?

Accepted Answer

T(n) = 2T(n/2) + O(n) → O(n log n)

Answer

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?

Accepted Answer

Problems solvable in polynomial time

Answer

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?

Accepted Answer

Caching the results of subproblems in a table to avoid recomputation

Answer

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?

Accepted Answer

It makes the locally optimal choice at each step without reconsidering past decisions

Answer

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?

Accepted Answer

Prim's Algorithm

Answer

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.

B CompE Bachelor of Computer Engineering Practice Test

B CompE Bachelor of Computer Engineering Practice Test

B CompE Bachelor of Computer Engineering Algorithm Design and Analysis 2