Which of these algorithms uses the divide and conquer technique?
A Merge Sort
B Binary Search
C Quick Sort
D All of the above
Merge Sort, Binary Search, and Quick Sort all utilize the divide and conquer technique. In this approach, problems are divided into smaller subproblems, solved independently, and combined to form the final solution.
(“All of the above” remains in position D.)
Which problem is solved using Dynamic Programming?
A Knapsack Problem
B Quick Sort
C Merge Sort
D Fibonacci Sequence
The Knapsack Problem is commonly solved using dynamic programming. It involves finding the most valuable combination of items that fit within a given weight capacity, ensuring optimal solutions by solving smaller subproblems.
What is the space complexity of Merge Sort?
A O(log n)
B O(n)
C O(n log n)
D O(1)
Merge Sort has a space complexity of O(n) because it requires additional space to store the left and right subarrays during the merge process. This extra space grows with the input size.
What does “Big O” notation describe?
A Average case
B Best-case complexity
C Worst-case complexity
D Space requirement
Big O notation is used to describe the worst-case time complexity of an algorithm, showing how the algorithm’s runtime increases as the input size grows, providing an upper bound for performance.
Which of the following is true about a greedy algorithm?
A Always finds optimal solution
B Uses dynamic programming
C Solves all problems optimally
D Makes locally optimal choices
A greedy algorithm makes the locally optimal choice at each step, hoping that these choices will lead to an optimal solution. However, it does not always guarantee the best solution for all problems.
What does the Bellman-Ford algorithm find?
A Shortest path with negative weights
B Maximum flow
C Minimum spanning tree
D All pairs shortest path
The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a graph, even if the graph contains edges with negative weights.
Which sorting algorithm has the worst-case time complexity of O(n log n)?
A Quick Sort
B Merge Sort
C Heap Sort
D Bubble Sort
Merge Sort has a worst-case time complexity of O(n log n). It divides the array into halves, recursively sorts each half, and then merges them, ensuring consistent performance even in the worst case.
What is the primary feature of dynamic programming?
A Greedy choice
B Sorting
C Recursion with overlapping subproblems
D Parallel computation
Dynamic programming is used for problems with overlapping subproblems, where the solution to a larger problem can be constructed from solutions to smaller subproblems. It stores intermediate results to avoid redundant calculations.
What does the Floyd-Warshall algorithm solve?
A Shortest path between two vertices
B Minimum spanning tree
C All-pairs shortest path
D Longest path
The Floyd-Warshall algorithm solves the problem of finding the shortest paths between all pairs of vertices in a weighted graph. It works by considering whether a path through an intermediate vertex offers a shorter path.
Which sorting algorithm is based on the divide and conquer paradigm?
A Insertion Sort
B Bubble Sort
C Quick Sort
D Selection Sort
Quick Sort uses the divide and conquer paradigm, where it divides the array into two subarrays around a pivot element and recursively sorts them. This makes it efficient with an average time complexity of O(n log n).
Which algorithm is used for optimal substructure problems?
A Dynamic Programming
B Greedy Algorithm
C Divide and Conquer
D Brute Force
Dynamic programming is used for problems that exhibit optimal substructure, where the solution to a problem can be derived from solutions to its subproblems. It is particularly useful in problems like the Fibonacci sequence or shortest paths.
Which algorithm is used to solve the minimum spanning tree problem?
A Dijkstra’s Algorithm
B Bellman-Ford
C Floyd-Warshall
D Prim’s Algorithm
Prim’s Algorithm is a greedy algorithm that finds the minimum spanning tree for a connected graph by starting with an arbitrary vertex and adding the smallest edge that connects a vertex in the tree to one outside.
What is the time complexity of the Binary Search algorithm?
A O(log n)
B O(n)
C O(n log n)
D O(1)
Binary Search is efficient with a time complexity of O(log n) because it repeatedly divides the search space in half, making it much faster than linear search for large datasets when the array is sorted.
What is the purpose of the Rabin-Karp algorithm?
A Sorting strings
B Searching a string in a text
C Calculating hashes
D Finding maximum flow
The Rabin-Karp algorithm is used for string matching. It calculates hash values of the pattern and substrings of the text to find a match efficiently, especially useful when searching for multiple patterns.
Which algorithm is used for optimal substructure problems?
A Merge Sort
B Quick Sort
C Dijkstra’s Algorithm
D Insertion Sort
Dijkstra’s algorithm uses a priority queue to repeatedly select the vertex with the smallest tentative distance, ensuring efficient calculation of the shortest path in a graph with non-negative weights.