Algorithms Algorithms 2 — Questions and Answers
Question 1: Which sorting algorithm has the best average-case time complexity?
- Bubble Sort
- Merge Sort (Correct answer)
- Insertion Sort
- Selection Sort
Correct answer: Merge Sort
Merge Sort achieves O(n log n) average-case time, which is optimal for comparison-based sorting.
Question 2: In Dijkstra's algorithm, what data structure is typically used to efficiently select the next minimum-distance vertex?
- Stack
- Queue
- Min-Heap (Priority Queue) (Correct answer)
- Hash Table
Correct answer: Min-Heap (Priority Queue)
A min-heap allows extracting the minimum-distance unvisited vertex in O(log n) time, making Dijkstra's run in O((V+E) log V).
Question 3: What is the time complexity of the Floyd-Warshall algorithm?
- O(V²)
- O(V² log V)
- O(V³) (Correct answer)
- O(E log V)
Correct answer: O(V³)
Floyd-Warshall uses three nested loops over all vertices, resulting in O(V³) time complexity.
Question 4: Which algorithm strategy does the 0/1 Knapsack problem use?
- Greedy
- Divide and Conquer
- Dynamic Programming (Correct answer)
- Backtracking
Correct answer: Dynamic Programming
0/1 Knapsack uses dynamic programming to build an optimal solution by storing results of overlapping subproblems.
Question 5: What is the worst-case space complexity of recursive Merge Sort?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
Merge Sort requires O(n) auxiliary space for the temporary arrays used during merging.
Question 6: In a depth-first search (DFS) on a graph, which data structure is implicitly used?
- Queue
- Stack (Correct answer)
- Heap
- Deque
Correct answer: Stack
DFS uses a stack (either explicitly or via the call stack in recursion) to track the traversal path.
Question 7: Which of the following problems is NP-complete?
- Finding the shortest path in a weighted graph
- Sorting an array
- The Traveling Salesman Decision Problem (Correct answer)
- Binary search on a sorted array
Correct answer: The Traveling Salesman Decision Problem
The Traveling Salesman Decision Problem is NP-complete, meaning no known polynomial-time algorithm solves it.
Algorithms Algorithms 2
Which sorting algorithm has the best average-case time complexity?