Algorithms Algorithms 5 — Questions and Answers
Question 1: Which algorithm is used in practice for string pattern matching with O(n+m) time complexity?
- Naive pattern matching
- Rabin-Karp
- KMP (Knuth-Morris-Pratt) (Correct answer)
- Boyer-Moore (worst case)
Correct answer: KMP (Knuth-Morris-Pratt)
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?
- Solving recurrence relations for divide-and-conquer algorithms (Correct answer)
- Proving NP-completeness of problems
- Analyzing greedy algorithm correctness
- Computing amortized complexity of data structures
Correct answer: Solving recurrence relations for divide-and-conquer algorithms
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?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n/k) where k is bucket count
Correct answer: O(1)
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?
- Prim's works on directed graphs; Kruskal's works on undirected graphs
- Prim's grows the MST from a starting vertex; Kruskal's adds globally smallest edges (Correct answer)
- Prim's is O(V²); Kruskal's is O(V³)
- Prim's uses BFS; Kruskal's uses DFS
Correct answer: Prim's grows the MST from a starting vertex; Kruskal's adds globally smallest edges
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?
- Merge Sort
- Quick Sort
- Counting Sort (Correct answer)
- Heap Sort
Correct answer: Counting Sort
Counting Sort uses element values as indices rather than comparing elements, allowing O(n+k) time complexity.
Question 6: What is the purpose of the Union-Find (Disjoint Set Union) data structure?
- Sorting elements in O(n log n)
- Efficiently tracking connected components and merging sets (Correct answer)
- Finding shortest paths in a graph
- Balancing binary search trees
Correct answer: Efficiently tracking connected components and merging sets
Union-Find supports near-O(1) operations to merge sets and determine if two elements belong to the same component.
Question 7: What is the worst-case time complexity of Quick Sort, and what input pattern causes it?
- O(n log n) caused by random input
- O(n²) caused by already-sorted or reverse-sorted input with bad pivot selection (Correct answer)
- O(n) caused by all elements being equal
- O(n²) caused by random input
Correct answer: O(n²) caused by already-sorted or reverse-sorted input with bad pivot selection
When the pivot is always the smallest or largest element (e.g., sorted input with first-element pivot), Quick Sort degrades to O(n²).
Algorithms Algorithms 5
Which algorithm is used in practice for string pattern matching with O(n+m) time complexity?