Algorithms Trivia Questions
- What property of a sorting algorithm ensures that the relative order of equal elements is preserved?
- What specific data structure is typically used to efficiently implement Kruskal's algorithm for finding a Minimum Spanning Tree?
- What term describes the tendency in linear probing where occupied slots tend to cluster, increasing search time?
- What type of graph must be used to allow for a topological sort?
- Which greedy algorithm is used to construct an optimal prefix code for lossless data compression?
- What was the first problem proven to be NP-complete by Stephen Cook and Leonid Levin?
- Which algorithm design paradigm is characterized by solving subproblems and storing their results to avoid redundant computations?
- Which algorithm finds the strongly connected components of a directed graph by performing two depth-first searches, the second on the transpose graph?
- Which algorithm for finding single-source shortest paths can handle negative edge weights (but not negative cycles)?
- Which algorithm for finding the Minimum Spanning Tree (MST) grows the tree one vertex at a time from an arbitrary starting root?
- Which algorithm for matrix multiplication improves upon the standard O(n^3) complexity by using a divide-and-conquer approach with only seven multiplications?
- Which algorithm for the maximum flow problem improves on Ford-Fulkerson by always choosing the shortest augmenting path using BFS?
- Which amortized analysis method assigns 'credits' to certain operations to pay for expensive future operations?
- Which amortized analysis technique uses a function to represent the 'stored energy' or 'prepaid work' of a data structure?
- Which asymptotic notation provides a strict upper bound, meaning the function grows strictly slower than the bound?
- Which asymptotic notation provides a tight bound, acting as both an upper and lower bound?
- Which computer scientist published the 1971 paper "The complexity of theorem-proving procedures," proving that the Boolean satisfiability problem is NP-complete?
- Which data structure is used in Prim's algorithm to efficiently select the next minimum-weight edge connecting to the growing MST?
- Which data structure technique is used to improve the performance of Union-Find by making the tree flatter?
- Which dynamic programming algorithm is used to find all-pairs shortest paths in a weighted graph in O(V³) time?
- Which graph algorithm uses a greedy approach to find the shortest path from a single source to all other vertices in a graph with non-negative weights?
- Which graph traversal uses a queue to visit vertices in increasing order of their distance from the source?
- Which greedy algorithm finds the Minimum Spanning Tree of a graph by always adding the cheapest edge that does not form a cycle?
- Which non-comparison-based sorting algorithm treats elements as sequences of digits to achieve linear-time performance?
- Which non-comparison sorting algorithm runs in O(n + k) time for n integers in the range 0 to k?
- Which sorting algorithm has an O(n) average-case time complexity by assuming the input is uniformly distributed over the interval [0, 1)?
- Which stable divide-and-conquer sorting algorithm recursively divides an input into halves, sorts each half, and then combines the two sorted halves?
- Which stable, in-place sorting algorithm with a worst-case complexity of O(n^2) works by repeatedly taking the next element and placing it into its correct position among the already-sorted elements?
- Which stable sorting algorithm is commonly used as a subroutine in Radix Sort to sort digits?
- Which string-matching algorithm uses a 'prefix function' (or failure function) to avoid redundant comparisons?
- Which string-matching algorithm uses hashing to find any one of a set of pattern strings in a text?
- Which theorem provides a standardized way to solve recurrence relations of the form T(n) = aT(n/b) + f(n)?
- While the 0/1 Knapsack problem is typically solved using dynamic programming, which algorithmic approach provides an optimal solution for the Fractional Knapsack problem?