Algorithms Algorithms 5

Question 1

Which algorithm is used in practice for string pattern matching with O(n+m) time complexity?

Accepted Answer

KMP (Knuth-Morris-Pratt)

Answer

KMP preprocesses the pattern to build a failure function, allowing O(n+m) worst-case string matching.

Question 2

What is the master theorem used for?

Accepted Answer

Solving recurrence relations for divide-and-conquer algorithms

Answer

The master theorem provides a formula to solve recurrences of the form T(n) = aT(n/b) + f(n), common in divide-and-conquer.

Question 3

In a hash table using chaining, what is the average-case time complexity for search assuming a uniform hash function?

Accepted Answer

O(1)

Answer

With a good hash function and load factor α = n/m kept constant, search averages O(1+α) = O(1).

Question 4

What is the difference between Prim's and Kruskal's algorithms for finding a Minimum Spanning Tree?

Accepted Answer

Prim's grows the MST from a starting vertex; Kruskal's adds globally smallest edges

Answer

Prim's expands the MST greedily from a vertex, while Kruskal's sorts all edges and adds the cheapest non-cycle-forming edge.

Question 5

Which of the following sorting algorithms is NOT comparison-based?

Accepted Answer

Counting Sort

Answer

Counting Sort uses element values as indices rather than comparing elements, allowing O(n+k) time complexity.

Algorithms Practice Test