Algorithms Trivia Questions
- According to the Master Theorem, what is the complexity of a recurrence T(n) = 8T(n/2) + n^2?
- Besides the aggregate and accounting methods, what is the third common method of amortized analysis?
- Dynamic programming requires two key properties: Overlapping subproblems and what else?
- Huffman coding is used primarily for what purpose in computer science?
- In a B-tree with a minimum degree t ≥ 2, what is the maximum number of keys that a single node can contain?
- In a Depth-First Search (DFS) forest, what type of edge connects a vertex to an ancestor in the same DFS tree?
- In a Disjoint Set Union (DSU) data structure, what is the nearly-constant time complexity achieved by using both union-by-rank and path compression?
- According to the max-flow min-cut theorem, the maximum flow from a source to a sink equals the capacity of what structure?
- In a flow network, what theorem states that if all edge capacities are integers, there exists a maximum flow where all flow values are integers?
- In a Red-Black tree, what color must the root always be?
- In an AVL tree, what is the maximum allowed difference in height between the left and right subtrees of any node?
- In hash tables, what is the name of the collision resolution technique where each bucket contains a pointer to a linked list of records?
- In the context of NP-completeness, what is the term for a problem that is at least as hard as the hardest problems in NP, but might not be in NP itself?
- In the context of optimization, what is the primary difference between the items in the Fractional Knapsack problem versus the 0/1 Knapsack problem?
- In the context of the Ford-Fulkerson method, what is a path from the source to the sink in the residual graph called?
- In the Master Theorem formula T(n) = aT(n/b) + f(n), what does the constant 'a' represent?
- In the Master Theorem, what is the asymptotic solution for the recurrence T(n) = 4T(n/2) + n?
- In the Master Theorem, which case applies to the recurrence T(n) = 2T(n/2) + n?
- In the push-relabel algorithm for maximum flow, what is the term for a flow function that satisfies capacity constraints but allows the net flow into a vertex to exceed the net flow out?
- Is Heapsort an example of a stable sorting algorithm?
- Is the standard array-based implementation of Merge Sort considered an in-place sorting algorithm?
- Is Merge Sort considered a stable sorting algorithm?
- The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that uses which search strategy?
- To perform a topological sort on a DAG, one can order the vertices in the reverse order of which DFS-calculated value?
- What color must every leaf (NIL) be in a valid Red-Black Tree?
- What fundamental tree operation is used by AVL trees and Red-Black trees to restore balance after an insertion or deletion?
- What greedy selection criteria provides an optimal solution to the fractional knapsack problem?
- What is the amortized time complexity of a 'Find-Set' operation when using both path compression and union-by-rank heuristics?
- What is the amortized time complexity of the Decrease-Key operation in a Fibonacci Heap?
- What is the amortized time complexity of the 'push' operation for a dynamic array that doubles in size when full?
- What is the asymptotic time complexity of finding the Longest Common Subsequence of two strings of length m and n using dynamic programming?
- Assuming uniform hashing and a constant load factor, what is the average-case time complexity of searching for an element in a hash table whose collisions are resolved by chaining?
- What is the lower bound for the height of a binary search tree with n nodes?
- What is the lower bound for the worst-case time complexity of any comparison-based sorting algorithm?
- What upper bound does a Red-Black Tree with n internal nodes have on its height?
- What is the maximum number of nodes in a binary tree of height h, where height is defined as the number of edges on the longest path from the root to a leaf?
- In the KMP string-search algorithm, what function assigns to each prefix of the pattern the length of its longest proper prefix that is also a suffix?
- What is the name of the 'divide and conquer' algorithm used to find the median of an unsorted array in O(n) worst-case time?
- What is the preprocessing time complexity of the Knuth-Morris-Pratt (KMP) string matching algorithm for a pattern of length m?
- What is the space complexity of a graph represented as an adjacency list with V vertices and E edges?
- What is the tightest asymptotic time complexity for building a binary max-heap from an unsorted array of n elements?
- What is the time complexity of a single forward pass through a fully connected layer with N input neurons and M output neurons?
- What is the time complexity of the Bellman-Ford algorithm?
- What is the time complexity of the Binary Search algorithm on a sorted array of size n?
- What is the time complexity of the Master Theorem's 'Case 1', where the work at the leaves dominates the total cost?
- What is the time complexity of the standard dynamic programming algorithm for the Matrix Chain Multiplication problem with n matrices?
- What is the time complexity to extract the maximum element from a binary max-heap of n elements?
- What is the worst-case running time of the Randomized Quicksort algorithm?
- What is the worst-case time complexity of searching for an element in a Hash Table of size m containing n elements when using chaining?
- What is the worst-case time complexity of the Karatsuba algorithm for multiplying two n-digit numbers?