What does “Big O” notation represent in algorithm analysis?
A Space Complexity
B Worst‐Case Time Complexity
C Best‐Case Time Complexity
D Average Time Complexity
Big O notation describes the worst-case time complexity of an algorithm, indicating how the algorithm’s runtime increases as the input size grows. It focuses on the upper bound, ensuring that even the slowest case is considered.
Which algorithm is used to find the shortest path in a graph with non-negative weights?
A Floyd-Warshall Algorithm
B Bellman-Ford Algorithm
C Dijkstra’s Algorithm
D Kruskal’s Algorithm
Dijkstra’s algorithm is specifically designed to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It is a greedy algorithm that works efficiently with a priority queue.
What does the term “NP-Complete” refer to?
A A solvable problem in polynomial time
B Problems that can be solved in exponential time
C Problems for which no polynomial-time solution is known
D Problems with unknown solutions
NP-Complete problems are those for which no known algorithm can solve them in polynomial time. They are believed to be computationally difficult, and their solutions are fundamental in theoretical computer science.
What is the main advantage of the divide and conquer approach?
A Solves subproblems independently
B Better space complexity
C Guarantees optimal solution
D Simple to implement
The divide and conquer strategy breaks a problem into smaller subproblems, solves them independently, and then combines their solutions. This approach often leads to efficient algorithms, such as Merge Sort and Quick Sort.
Which of the following is a feature of dynamic programming?
A Greedy approach
B Randomized solution
C Subproblem overlap
D No recursion
Dynamic programming solves problems by breaking them into smaller subproblems and storing their solutions to avoid redundant work. It is particularly effective when subproblems overlap, as in the case of the Fibonacci sequence or shortest path problems.
What is the time complexity of Binary Search on a sorted array?
A O(n)
B O(n log n)
C O(1)
D O(log n)
Binary Search works by repeatedly dividing the search interval in half. If the value of the target is less than the value in the middle of the interval, the search continues on the left half, otherwise, on the right half. The time complexity is O(log n), where n is the number of elements.
Which sorting algorithm has the worst-case time complexity of O(n^2)?
A Bubble Sort
B Merge Sort
C Quick Sort
D Heap Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In the worst case, its time complexity is O(n^2).
What does the greedy algorithm approach ensure?
A Optimal solution for all problems
B The minimum space complexity
C Suboptimal solution with faster execution
D Always guarantees the best time complexity
Greedy algorithms focus on making locally optimal choices at each step, aiming for a globally optimal solution. However, they do not always guarantee the best solution, but they can be faster in finding a good solution for certain problems.
Which algorithm is used to find the longest common subsequence (LCS)?
A Merge Sort
B Dynamic Programming
C Quick Sort
D Dijkstra’s Algorithm
The Longest Common Subsequence (LCS) problem is solved using dynamic programming, which builds a solution incrementally by solving subproblems and storing their solutions. This approach avoids recalculating solutions for overlapping subproblems.
What does the “Theta” notation describe in algorithm complexity?
A Upper Bound
B Lower Bound
C Exact Bound
D Worst Case
Theta notation represents the exact asymptotic behavior of an algorithm. It provides both the upper and lower bounds of an algorithm’s complexity, indicating the precise rate of growth as the input size increases.
What is the primary advantage of Quick Sort over Merge Sort?
A Faster average time complexity
B Always stable
C Better for linked lists
D Requires extra space
Quick Sort generally performs faster than Merge Sort on average, with a time complexity of O(n log n). It operates by partitioning the array around a pivot, but it can degrade to O(n^2) in the worst case if not implemented properly.
In which case is a backtracking algorithm used?
A When the problem has a single solution
B When an exact solution is not necessary
C When a greedy algorithm is too slow
D When the problem has multiple valid solutions
Backtracking algorithms are used for problems that require exploring multiple solutions. It systematically searches through all possible configurations and “backs out” when a solution path fails, such as in the N-Queens problem.
Which of the following is true about NP-Hard problems?
A They can be solved in polynomial time
B They are at least as hard as NP-Complete problems
C They have an efficient approximation algorithm
D They can always be reduced to a simpler problem
NP-Hard problems are problems for which no polynomial-time solution is known, and they are at least as difficult as NP-Complete problems. However, unlike NP-Complete problems, NP-Hard problems do not have to be in NP.
What does the Floyd-Warshall algorithm solve?
A Shortest path in a weighted graph
B Longest path in an unweighted graph
C Minimum spanning tree
D All pairs shortest path
The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a graph. It works by iteratively considering whether each pair of vertices has a shorter path through another vertex.
What does the term “NP” stand for in computational complexity theory?
A Non-deterministic Polynomial
B Not Polynomial
C Non-Polynomial
D Normal Polynomial
“NP” stands for Non-deterministic Polynomial time. It refers to problems for which a solution can be verified in polynomial time by a non-deterministic machine. Solving these problems in polynomial time is still an open question in computer science.