Which sorting algorithm has the best average time complexity?
A Merge Sort
B Heap Sort
C Quick Sort
D Bubble Sort
Quick Sort has an average time complexity of O(n log n), which makes it faster than other algorithms such as Merge Sort or Heap Sort in most practical scenarios. However, its worst-case complexity is O(n^2) if the pivot is poorly chosen.
What does the “Omega” notation describe in algorithm analysis?
A Best Case
B Worst Case
C Upper Bound
D Exact Bound
Omega notation describes the lower bound of an algorithm, indicating the best possible performance of the algorithm in the best-case scenario. It provides a guarantee that the algorithm will not perform better than a certain threshold.
Which algorithm is used to find the minimum spanning tree in a graph?
A Dijkstra’s Algorithm
B Bellman-Ford Algorithm
C Floyd-Warshall Algorithm
D Prim’s Algorithm
Prim’s algorithm is used to find the minimum spanning tree of a connected, weighted graph. It adds edges in such a way that the total weight of the tree is minimized, and it works efficiently with a priority queue.
Which of these problems is classified as NP-Complete?
A Sorting Problem
B Travelling Salesman Problem
C Binary Search
D Linear Search
The Travelling Salesman Problem (TSP) is classified as NP-Complete because it is computationally hard, and no polynomial-time algorithm is known. The problem involves finding the shortest possible route that visits each city exactly once and returns to the origin.
Which of the following is true about the time complexity of Merge Sort?
A O(n^2)
B O(n)
C O(n log n)
D O(log n)
Merge Sort has a time complexity of O(n log n) in the best, worst, and average cases. It works by recursively dividing the array and merging the sorted subarrays, making it efficient for large datasets.
Which algorithm is based on the principle of “divide and conquer”?
A Quick Sort
B Merge Sort
C Both A and B
D Dijkstra’s Algorithm
Both Merge Sort and Quick Sort use the divide and conquer approach. In Merge Sort, the array is divided into subarrays, sorted, and then merged. In Quick Sort, the array is partitioned around a pivot, and the subarrays are sorted recursively.
What is the primary use of the Binary Search algorithm?
A Sorting
B Searching in a sorted array
C Finding maximum
D Graph traversal
Binary Search is used to find an element in a sorted array by repeatedly dividing the search interval in half. It eliminates half of the remaining elements with each comparison, making it highly efficient with a time complexity of O(log n).
Which algorithm is used for string matching in a text?
A Merge Sort
B Binary Search
C Rabin-Karp
D Floyd-Warshall
The Rabin-Karp algorithm is used for string matching, where it compares hash values of substrings in the text with the pattern. It efficiently handles multiple pattern searches but has a worst-case time complexity of O(nm) if collisions occur.
Which of the following best describes the complexity class NP?
A Solvable in polynomial time
B Can be verified in polynomial time
C Not solvable
D Always solvable in logarithmic time
NP (Non-deterministic Polynomial time) is the class of problems for which a solution can be verified in polynomial time. However, finding the solution may not necessarily be efficient, and polynomial-time algorithms may not always exist.
What is the purpose of dynamic programming?
A To reduce space complexity
B To solve sorting problems
C To avoid redundant calculations
D To optimize graph traversal
Dynamic programming is used to optimize problems by storing the results of subproblems and reusing them, thus avoiding redundant calculations. It is highly effective in problems with overlapping subproblems, such as the Fibonacci sequence or shortest path problems.
What is the worst-case time complexity of Bubble Sort?
A O(n^2)
B O(n log n)
C O(log n)
D O(n)
Bubble Sort has a worst-case time complexity of O(n^2), where n is the number of elements to be sorted. The algorithm repeatedly compares adjacent elements and swaps them, resulting in quadratic time complexity when the list is in reverse order.
Which algorithm is used to find the longest path in a graph?
A Dijkstra’s Algorithm
B Bellman-Ford Algorithm
C Floyd-Warshall Algorithm
D There is no known polynomial-time algorithm
Finding the longest path in a graph is an NP-Hard problem. Unlike the shortest path, there is no known polynomial-time algorithm to solve it efficiently for all graphs, especially in graphs with negative edges or cycles.
What is a characteristic of a greedy algorithm?
A Solves by choosing the best overall solution
B Always finds an optimal solution
C Makes local choices to build a global solution
D Solves problems in exponential time
Greedy algorithms make a series of local optimal choices, aiming for a globally optimal solution. They work well for problems like Minimum Spanning Tree but do not guarantee an optimal solution for all problems.
What is the primary disadvantage of the Quick Sort algorithm?
A Requires a lot of space
B It has a high worst-case time complexity
C It is not stable
D It is too slow for large inputs
Quick Sort has a worst-case time complexity of O(n^2) when the pivot is poorly chosen, such as when the array is already sorted or nearly sorted. However, it is generally fast in practice with a good pivot selection strategy.
What does the “P” complexity class represent?
A Problems that can be solved in polynomial time
B Problems that can be solved in exponential time
C Problems that are verifiable in polynomial time
D Problems that have no known solution
The “P” complexity class includes problems that can be solved in polynomial time. These problems are considered efficiently solvable and are contrasted with NP problems, where solutions can be verified but not necessarily found efficiently.