Algorithms Algorithms 3 ā Questions and Answers
Question 1: What does the term 'amortized time complexity' refer to?
- The worst-case time for a single operation
- The average time per operation over a sequence of operations (Correct answer)
- The best-case time for all operations
- The time complexity after optimization
Correct answer: The average time per operation over a sequence of operations
Amortized analysis spreads the cost of expensive operations across many operations to give a per-operation average.
Question 2: Which algorithm is used to find the Minimum Spanning Tree of a graph by always adding the globally cheapest edge that doesn't create a cycle?
- Prim's Algorithm
- Kruskal's Algorithm (Correct answer)
- Dijkstra's Algorithm
- Bellman-Ford Algorithm
Correct answer: Kruskal's Algorithm
Kruskal's algorithm sorts all edges by weight and greedily adds the smallest edge that doesn't form a cycle.
Question 3: What is the time complexity of heap sort in the worst case?
- O(n)
- O(n log n) (Correct answer)
- O(nĀ²)
- O(log n)
Correct answer: O(n log n)
Heap sort builds a max-heap in O(n) and extracts elements n times each in O(log n), giving O(n log n) worst case.
Question 4: In the context of dynamic programming, what is memoization?
- Storing only the final result of a computation
- Caching the results of subproblems to avoid redundant computation (Correct answer)
- Breaking a problem into non-overlapping subproblems
- Optimizing memory usage by reusing variables
Correct answer: Caching the results of subproblems to avoid redundant computation
Memoization stores results of already-computed subproblems in a table so they aren't recomputed.
Question 5: Which graph algorithm can detect negative-weight cycles?
- Dijkstra's Algorithm
- BFS
- Bellman-Ford Algorithm (Correct answer)
- Floyd-Warshall only
Correct answer: Bellman-Ford Algorithm
Bellman-Ford detects negative-weight cycles by checking if any distance can still be reduced after V-1 relaxations.
Question 6: What is the output of the Longest Common Subsequence (LCS) algorithm for strings 'ABCBDAB' and 'BDCABA'?
- 3
- 4 (Correct answer)
- 5
- 6
Correct answer: 4
The LCS of 'ABCBDAB' and 'BDCABA' is 'BCBA' or 'BDAB', both of length 4.
Question 7: Which of the following best describes a greedy algorithm?
- It always backtracks to find the globally optimal solution
- It makes the locally optimal choice at each step hoping to reach a global optimum (Correct answer)
- It divides the problem into equal halves and solves recursively
- It exhaustively searches all possible solutions
Correct answer: It makes the locally optimal choice at each step hoping to reach a global optimum
Greedy algorithms make the best local choice at each step without reconsidering previous decisions.
Algorithms Algorithms 3
What does the term 'amortized time complexity' refer to?