1Which algorithmic technique is generally used to efficiently compute the Binomial Coefficient by avoiding recomputation of subproblems?
Dynamic Programming: Computing a Binomial Coefficient
Easy
A.Greedy Technique
B.Dynamic Programming
C.Divide and Conquer
D.Backtracking
Correct Answer: Dynamic Programming
Explanation:
Dynamic Programming is used to compute binomial coefficients by storing previously calculated values in a table to avoid redundant calculations.
Incorrect! Try again.
2What is the primary purpose of Warshall's algorithm?
Warshall's and Floyd's Algorithm
Easy
A.To find the minimum spanning tree
B.To find the transitive closure of a directed graph
C.To find the shortest path between all pairs of vertices
D.To perform a topological sort
Correct Answer: To find the transitive closure of a directed graph
Explanation:
Warshall's algorithm is specifically designed to compute the transitive closure (reachability matrix) of a directed graph.
Incorrect! Try again.
3Floyd's algorithm is used to solve which of the following problems?
Warshall's and Floyd's Algorithm
Easy
A.Single-Source Shortest Paths
B.Minimum Spanning Tree
C.All-Pairs Shortest Paths
D.Maximum Flow
Correct Answer: All-Pairs Shortest Paths
Explanation:
Floyd's algorithm computes the shortest paths between every pair of vertices in a weighted graph.
Incorrect! Try again.
4In an Optimal Binary Search Tree, what is minimized?
Optimal Binary Search Trees
Easy
A.The height of the tree
B.The number of leaf nodes
C.The average search cost
D.The number of edges
Correct Answer: The average search cost
Explanation:
An Optimal Binary Search Tree minimizes the expected search cost (average number of comparisons) based on the probabilities of searching for each key.
Incorrect! Try again.
5Which of the following problems can be optimally solved using dynamic programming by building a 2D table representing item weights and knapsack capacity?
Knapsack Problem and Memory Functions
Easy
A.Maximum Flow Problem
B.Travelling Salesperson Problem
C.Fractional Knapsack Problem
D.0/1 Knapsack Problem
Correct Answer: 0/1 Knapsack Problem
Explanation:
The 0/1 Knapsack Problem is a classic dynamic programming problem solved using a 2D table of items and capacities.
Incorrect! Try again.
6What is a 'memory function' in the context of dynamic programming?
Knapsack Problem and Memory Functions
Easy
A.A function that limits memory usage of an algorithm
B.A hardware component to store array elements
C.A top-down approach that caches results of solved subproblems
D.A bottom-up approach that fills an entire table
Correct Answer: A top-down approach that caches results of solved subproblems
Explanation:
A memory function (or memoization) combines the top-down recursive approach with the caching of subproblem solutions to avoid redundant work.
Incorrect! Try again.
7What is the goal of the Matrix-Chain Multiplication problem?
Matrix-Chain Multiplication
Easy
A.To sort the matrices in ascending order of size
B.To multiply matrices using minimum memory
C.To find the product of matrices as fast as possible by changing matrix values
D.To find the optimal parenthesization to minimize scalar multiplications
Correct Answer: To find the optimal parenthesization to minimize scalar multiplications
Explanation:
The Matrix-Chain Multiplication problem determines the most efficient way to multiply a sequence of matrices by finding the optimal parenthesization.
Incorrect! Try again.
8If string A is 'ABC' and string B is 'AC', what is the length of their Longest Common Subsequence?
Longest Common Subsequence
Easy
A.3
B.0
C.2
D.1
Correct Answer: 2
Explanation:
The Longest Common Subsequence between 'ABC' and 'AC' is 'AC', which has a length of 2.
Incorrect! Try again.
9A Minimum Spanning Tree of a connected, undirected graph with vertices will always have exactly how many edges?
Greedy Technique and Graph Algorithm: Minimum Spanning Trees
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
A spanning tree of a graph with vertices must contain exactly edges to connect all vertices without forming a cycle.
Incorrect! Try again.
10Prim's algorithm builds a minimum spanning tree by:
Prim's Algorithm
Easy
A.Connecting isolated components randomly
B.Sorting all edges and picking them one by one
C.Growing a single tree by adding the cheapest edge from the tree to a non-tree vertex
D.Finding the shortest path from a source vertex
Correct Answer: Growing a single tree by adding the cheapest edge from the tree to a non-tree vertex
Explanation:
Prim's algorithm starts with a single vertex and greedily grows the tree by adding the minimum weight edge that connects a tree vertex to a non-tree vertex.
Incorrect! Try again.
11Which data structure is most commonly used in Kruskal's algorithm to check for cycles efficiently?
Kruskal's Algorithm
Easy
A.Binary Search Tree
B.Stack
C.Hash Table
D.Disjoint-Set (Union-Find)
Correct Answer: Disjoint-Set (Union-Find)
Explanation:
Kruskal's algorithm uses a Disjoint-Set (Union-Find) data structure to efficiently keep track of connected components and detect cycles.
Incorrect! Try again.
12Dijkstra's algorithm is used to solve which problem?
Dijkstra's Algorithm
Easy
A.Maximum Flow
B.Minimum Spanning Tree
C.Single-Source Shortest Paths
D.All-Pairs Shortest Paths
Correct Answer: Single-Source Shortest Paths
Explanation:
Dijkstra's algorithm computes the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.
Incorrect! Try again.
13Which algorithmic design technique does Dijkstra's algorithm employ?
Dijkstra's Algorithm
Easy
A.Dynamic Programming
B.Divide and Conquer
C.Backtracking
D.Greedy Technique
Correct Answer: Greedy Technique
Explanation:
Dijkstra's algorithm uses a greedy approach by always selecting the unvisited vertex with the smallest known distance from the source.
Incorrect! Try again.
14Huffman coding is widely used for which application?
Huffman Code
Easy
A.Finding shortest paths
B.Sorting arrays
C.Data compression
D.Matrix multiplication
Correct Answer: Data compression
Explanation:
Huffman coding is a popular greedy algorithm used for lossless data compression by assigning variable-length codes based on character frequencies.
Incorrect! Try again.
15In a Huffman tree, where are the characters with the highest frequencies placed?
Huffman Code
Easy
A.In the middle levels
B.Only on the left branches
C.At the deepest leaves
D.Near the root
Correct Answer: Near the root
Explanation:
To minimize the total encoded file size, characters with high frequencies are placed closer to the root so they receive shorter binary codes.
Incorrect! Try again.
16Which algorithm is capable of finding single-source shortest paths even when the graph contains negative weight edges?
Single-Source Shortest Paths
Easy
A.Kruskal's Algorithm
B.Prim's Algorithm
C.Dijkstra's Algorithm
D.Bellman-Ford Algorithm
Correct Answer: Bellman-Ford Algorithm
Explanation:
Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can handle graphs with negative edge weights and can detect negative weight cycles.
Incorrect! Try again.
17What is the time complexity of Floyd's algorithm for a graph with vertices?
All-Pairs Shortest Paths
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Floyd's algorithm uses three nested loops over the vertices, resulting in a time complexity of .
Incorrect! Try again.
18Which method is commonly used to solve the Maximum-Flow problem by iteratively finding augmenting paths?
Iterative Improvement: The Maximum-Flow Problem
Easy
A.Floyd-Warshall method
B.Kruskal's method
C.Dijkstra's method
D.Ford-Fulkerson method
Correct Answer: Ford-Fulkerson method
Explanation:
The Ford-Fulkerson method solves the maximum-flow problem by repeatedly finding augmenting paths from the source to the sink and increasing the flow.
Incorrect! Try again.
19In a flow network, what condition must hold for every vertex other than the source and sink?
Iterative Improvement: The Maximum-Flow Problem
Easy
A.Flow in must be greater than flow out
B.Flow in must equal flow out
C.Capacity must be infinite
D.Flow out must be zero
Correct Answer: Flow in must equal flow out
Explanation:
Conservation of flow requires that for all nodes except the source and sink, the total flow entering the node equals the total flow leaving it.
Incorrect! Try again.
20What does a lower bound of a problem indicate?
Limitations of Algorithm Power: Lower-Bound Theory
Easy
A.The fastest algorithm possible has been found
B.The minimum amount of work (time/operations) required to solve the problem by any algorithm
C.The maximum amount of time an algorithm will take
D.The specific algorithm to use
Correct Answer: The minimum amount of work (time/operations) required to solve the problem by any algorithm
Explanation:
A lower bound establishes the minimum efficiency limit, meaning no algorithm can solve the problem in fewer operations than the lower bound.
Incorrect! Try again.
21What is the time complexity of computing a binomial coefficient using dynamic programming (Pascal's Triangle approach)?
Dynamic Programming: Computing a Binomial Coefficient
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The dynamic programming approach builds a table of size , taking time to fill.
Incorrect! Try again.
22In Floyd's algorithm for finding all-pairs shortest paths, what does the intermediate matrix represent?
Warshall's and Floyd's Algorithm
Medium
A.The shortest paths between all pairs using exactly edges.
B.The distances between all pairs after iterations of Breadth-First Search.
C.The shortest paths between all pairs of path length at most .
D.The shortest paths between all pairs using only the first vertices as intermediate nodes.
Correct Answer: The shortest paths between all pairs using only the first vertices as intermediate nodes.
Explanation:
Floyd's algorithm builds solutions iteratively by allowing vertices as intermediate nodes for the paths in the -th iteration.
Incorrect! Try again.
23When constructing an Optimal Binary Search Tree using dynamic programming, what is the primary objective?
Optimal Binary Search Trees
Medium
A.Minimize the number of nodes in the tree.
B.Minimize the height of the tree.
C.Minimize the expected number of comparisons for a search.
D.Maximize the search speed by keeping the tree strictly balanced.
Correct Answer: Minimize the expected number of comparisons for a search.
Explanation:
An Optimal BST minimizes the expected search cost, which depends on the probabilities of accessing each key, rather than just minimizing the tree's height.
Incorrect! Try again.
24How do memory functions improve the standard bottom-up dynamic programming approach for the Knapsack Problem?
Knapsack Problem and Memory Functions
Medium
A.They allow the problem to be solved with fractional items.
B.They reduce the space complexity from to .
C.They solve the problem using a greedy approach, reducing time complexity.
D.They compute only the necessary subproblems required to find the optimal solution.
Correct Answer: They compute only the necessary subproblems required to find the optimal solution.
Explanation:
Memory functions (top-down dynamic programming with memoization) avoid computing table entries that are never needed for the final solution, unlike the bottom-up approach which fills the entire table.
Incorrect! Try again.
25Given three matrices (dimensions ), (), and (), what is the minimum number of scalar multiplications required to compute ?
Matrix-Chain Multiplication
Medium
A.$7500$
B.$75000$
C.$52500$
D.$25000$
Correct Answer: $7500$
Explanation:
Computing takes multiplications. Computing takes multiplications. The minimum is $7500$.
Incorrect! Try again.
26What is the length of the Longest Common Subsequence (LCS) for the strings and ?
Longest Common Subsequence
Medium
A.$5$
B.$6$
C.$4$
D.$3$
Correct Answer: $4$
Explanation:
The Longest Common Subsequences include "BCBA", "BDAB", and "BCAB", all of which have a length of 4.
Incorrect! Try again.
27Which of the following properties is true for a Minimum Spanning Tree (MST) of a graph with distinct edge weights?
Greedy Technique and Graph Algorithm: Minimum Spanning Trees
Medium
A.There can be multiple MSTs.
B.The MST must be a binary tree.
C.The MST includes the edge with the maximum weight in the graph.
D.The MST is unique.
Correct Answer: The MST is unique.
Explanation:
If all edge weights in a connected graph are distinct, the Minimum Spanning Tree is strictly unique.
Incorrect! Try again.
28What data structure is typically used in Prim's Algorithm to achieve an optimal time complexity of ?
Prim's Algorithm
Medium
A.Min-Priority Queue
B.Stack
C.Disjoint Set (Union-Find)
D.Queue
Correct Answer: Min-Priority Queue
Explanation:
Prim's algorithm uses a min-priority queue (often implemented with a binary heap or Fibonacci heap) to efficiently extract the minimum weight edge connecting the tree to a new vertex.
Incorrect! Try again.
29Why is the Disjoint Set (Union-Find) data structure used in Kruskal's algorithm?
Kruskal's Algorithm
Medium
A.To quickly check if adding an edge forms a cycle.
B.To store the final Minimum Spanning Tree.
C.To find the shortest path between two vertices.
D.To sort the edges by weight.
Correct Answer: To quickly check if adding an edge forms a cycle.
Explanation:
The Union-Find data structure allows Kruskal's algorithm to efficiently determine whether two vertices are already in the same connected component, thus preventing cycles when adding edges.
Incorrect! Try again.
30In which scenario will Dijkstra's algorithm fail to produce the correct shortest paths?
Dijkstra's Algorithm
Medium
A.When the graph is dense.
B.When the graph contains edges with negative weights.
C.When the graph is a directed acyclic graph.
D.When the graph contains a cycle.
Correct Answer: When the graph contains edges with negative weights.
Explanation:
Dijkstra's algorithm assumes all edge weights are non-negative. A negative edge weight can cause the algorithm to falsely settle a vertex's shortest distance too early.
Incorrect! Try again.
31Given characters A, B, C, D with frequencies 45, 13, 12, 16 respectively. What is the length of the Huffman code for character A?
Huffman Code
Medium
A.1 bit
B.3 bits
C.4 bits
D.2 bits
Correct Answer: 1 bit
Explanation:
The sum of frequencies of B, C, and D is , which is less than A (45). In the Huffman tree, A will be a child of the root, so its code length is 1 bit.
Incorrect! Try again.
32Which algorithm is suitable for finding single-source shortest paths in a graph that may contain negative weight edges (but no negative weight cycles)?
Single-Source Shortest Paths
Medium
A.Dijkstra's Algorithm
B.Prim's Algorithm
C.Bellman-Ford Algorithm
D.Floyd's Algorithm
Correct Answer: Bellman-Ford Algorithm
Explanation:
The Bellman-Ford algorithm handles graphs with negative weight edges and can also detect negative weight cycles, unlike Dijkstra's algorithm.
Incorrect! Try again.
33How does the time complexity of running Dijkstra's algorithm from every vertex compare to Floyd-Warshall for a dense graph with vertices?
All-Pairs Shortest Paths
Medium
A.Both are exactly .
B.Floyd-Warshall is strictly worse than Dijkstra for dense graphs.
C.Dijkstra is (using binary heap) while Floyd-Warshall is .
D.Dijkstra is while Floyd-Warshall is .
Correct Answer: Dijkstra is (using binary heap) while Floyd-Warshall is .
Explanation:
For a dense graph (), Dijkstra with a binary heap takes for all vertices, whereas Floyd-Warshall consistently takes .
Incorrect! Try again.
34In the Ford-Fulkerson method, what defines the residual capacity of a directed edge if its capacity is and current flow is ?
Iterative Improvement: The Maximum-Flow Problem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The residual capacity is the remaining capacity on an edge that can take more flow, calculated as the original capacity minus the current flow.
Incorrect! Try again.
35What happens if the Ford-Fulkerson algorithm is applied to a network with irrational edge capacities?
Iterative Improvement: The Maximum-Flow Problem
Medium
A.It might not terminate and may not converge to the true maximum flow.
B.It finds the maximum flow in time.
C.It converts irrational capacities to rational ones and solves the problem.
D.It always terminates but may yield an incorrect flow.
Correct Answer: It might not terminate and may not converge to the true maximum flow.
Explanation:
With irrational capacities, the Ford-Fulkerson method is not guaranteed to terminate, and the flow values might converge to a value strictly less than the maximum flow.
Incorrect! Try again.
36What is the information-theoretic lower bound for sorting distinct items using only comparisons?
Limitations of Algorithm Power: Lower-Bound Theory
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
A decision tree for sorting elements has leaves. The minimum height of such a binary tree is , which is by Stirling's approximation.
Incorrect! Try again.
37In the dynamic programming solution for Matrix-Chain Multiplication, how is the optimal split point chosen when computing the minimum cost ?
Matrix-Chain Multiplication
Medium
A.By selecting the midpoint
B.By selecting that maximizes
C.By selecting that minimizes
D.By recursively solving without evaluating costs
Correct Answer: By selecting that minimizes
Explanation:
The algorithm tests all possible split points between and , adding the cost of multiplying the two resulting matrices, and selects the minimum.
Incorrect! Try again.
38In the 0/1 Knapsack Problem, if item has weight (where is the current remaining capacity), what is the value of the dynamic programming table entry ?
Knapsack Problem and Memory Functions
Medium
A.$0$
B.
C.
D.
Correct Answer:
Explanation:
If the item's weight exceeds the current capacity, it cannot be included in the knapsack. Hence, the maximum value remains the same as without considering this item, which is .
Incorrect! Try again.
39Which of the following guarantees that a Huffman code is a prefix code?
Huffman Code
Medium
A.The most frequent character gets the longest code.
B.The tree is built as a complete binary tree.
C.Characters are placed only at the leaves of the Huffman tree.
D.Characters are assigned codes of equal length.
Correct Answer: Characters are placed only at the leaves of the Huffman tree.
Explanation:
Because the characters are strictly at the leaves of the tree, no character's path from the root can be a prefix of another character's path, making it a prefix-free code.
Incorrect! Try again.
40Warshall's algorithm is specifically designed to compute which of the following?
Warshall's and Floyd's Algorithm
Medium
A.The transitive closure of a directed graph.
B.The shortest path tree of a graph.
C.The Minimum Spanning Tree of a graph.
D.The maximum flow in a network.
Correct Answer: The transitive closure of a directed graph.
Explanation:
Warshall's algorithm computes the transitive closure (reachability matrix) of a directed graph using logical operations, whereas Floyd's extends it to compute all-pairs shortest paths.
Incorrect! Try again.
41When computing a binomial coefficient using dynamic programming to avoid redundant calculations, what is the optimal space complexity that can be achieved if only the final value is needed?
Dynamic Programming: Computing a Binomial Coefficient
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By using a 1D array to store the current row of Pascal's triangle and updating it from right to left, the space complexity can be reduced to since only requires values up to index .
Incorrect! Try again.
42In Floyd-Warshall's algorithm, what happens to the distance matrix if the graph contains a negative-weight cycle?
Warshall's and Floyd's Algorithm
Hard
A.The matrix elements become complex numbers.
B.The algorithm goes into an infinite loop.
C.The algorithm correctly computes the shortest path assuming the cycle is traversed once.
D.The diagonal elements of the distance matrix become negative.
Correct Answer: The diagonal elements of the distance matrix become negative.
Explanation:
A negative-weight cycle implies that a vertex can reach itself with a cost less than zero. In the Floyd-Warshall algorithm, this manifests as one or more diagonal elements becoming strictly negative.
Incorrect! Try again.
43For an Optimal Binary Search Tree with keys and dummy keys, Knuth's optimization reduces the time complexity from to . Which property allows this optimization?
Optimal Binary Search Trees
Hard
A.The principle of optimality
B.The triangle inequality
C.The subadditivity of the cost function
D.The monotonicity of the optimal roots
Correct Answer: The monotonicity of the optimal roots
Explanation:
Knuth's optimization relies on the fact that the optimal root satisfies the monotonic property , limiting the search space for the root and reducing time complexity to .
Incorrect! Try again.
44Consider the 0/1 Knapsack problem with a weight capacity and items. If the weights are extremely large but the values are small integers bounded by , how can the problem be solved optimally in pseudo-polynomial time?
Knapsack Problem and Memory Functions
Hard
A.It is impossible; the problem is strictly NP-Hard and cannot be solved in pseudo-polynomial time if is large.
B.Define DP state representing the minimum weight needed to achieve exactly value .
C.Use the standard DP with state representing max value.
D.Use a greedy fractional approach and round down.
Correct Answer: Define DP state representing the minimum weight needed to achieve exactly value .
Explanation:
When is huge but values are small, we swap the roles of weight and value. We compute the minimum weight required to attain a specific value , which takes time.
Incorrect! Try again.
45If the dimension of matrix is for , what is the cost function for the minimum number of scalar multiplications to compute ?
Matrix-Chain Multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
To multiply the chain and , the dimensions of the resulting matrices are and . The number of scalar multiplications is .
Incorrect! Try again.
46Given two sequences of lengths and , what is the lower bound on the space complexity to find just the length of the LCS using DP?
Longest Common Subsequence
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
To find the length of the LCS, we only need the current and the previous row (or column) of the DP table. By iterating over the longer string and maintaining an array of the size of the shorter string, space is reduced to .
Incorrect! Try again.
47Let be a connected graph with distinct edge weights. Let be the edge of maximum weight in a cycle in . Which of the following statements is unconditionally true?
Greedy Technique and Graph Algorithm: Minimum Spanning Trees
Hard
A. might be part of the Minimum Spanning Tree if spans all vertices.
B. is part of the Maximum Spanning Tree but definitely not the Minimum Spanning Tree.
C. is not part of any Minimum Spanning Tree of .
D.The Minimum Spanning Tree is not unique.
Correct Answer: is not part of any Minimum Spanning Tree of .
Explanation:
By the cycle property of MSTs, the edge with the strictly maximum weight on any cycle in a graph cannot belong to the Minimum Spanning Tree.
Incorrect! Try again.
48When implementing Prim's algorithm using a Fibonacci heap on a dense graph where , what is the asymptotic time complexity?
Prim's Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Using a Fibonacci heap, decrease-key takes amortized time, and extract-min takes . Thus, the overall time complexity is .
Incorrect! Try again.
49If the edges of a graph are already sorted by weight, what is the tightest time complexity of Kruskal's algorithm using a Disjoint Set Union (DSU) with path compression and union by rank?
Kruskal's Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
If the edges are already sorted, the bottleneck is the DSU operations. For edges, finding and unioning takes , where is the inverse Ackermann function.
Incorrect! Try again.
50Dijkstra's algorithm fails for graphs with negative weight edges. However, if we simply add a large constant to all edge weights to make them non-negative, and then run Dijkstra's, what is the outcome?
Dijkstra's Algorithm
Hard
A.It will find the longest paths instead of shortest paths.
B.It will work correctly only if is greater than the absolute value of the most negative edge.
C.It will always yield the correct shortest paths.
D.It may yield incorrect shortest paths because paths with more edges are penalized more.
Correct Answer: It may yield incorrect shortest paths because paths with more edges are penalized more.
Explanation:
Adding a constant to all edges increases the total cost of a path with edges by . This disproportionately penalizes paths with a larger number of edges, potentially changing the shortest path structure.
Incorrect! Try again.
51Consider a set of characters where the frequency of the -th character is the -th Fibonacci number (). What is the depth of the optimal Huffman tree for this set (assuming , etc.)?
Huffman Code
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
When frequencies are Fibonacci numbers, the sum of the two smallest frequencies and equals , which is less than or equal to the next available frequency. This results in a highly unbalanced, linear tree of depth .
Incorrect! Try again.
52In the Bellman-Ford algorithm, if a graph has vertices, how many times can a vertex's shortest path distance be updated in the worst-case scenario before detecting a negative cycle?
Single-Source Shortest Paths
Hard
A. times
B. times
C. times
D. times
Correct Answer: times
Explanation:
In Bellman-Ford, each vertex's shortest path estimate can be updated at most once per pass. Since there are passes, a vertex distance can be updated at most times before the negative cycle detection pass.
Incorrect! Try again.
53Johnson's algorithm for All-Pairs Shortest Paths reweights edges to handle negative weights. The reweighting function uses a potential function . What is the transformed weight for an edge with original weight ?
All-Pairs Shortest Paths
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Johnson's algorithm reweights edges using the formula , where is typically the shortest path distance from a dummy node to . This guarantees non-negative edge weights while preserving the shortest path structure.
Incorrect! Try again.
54In the Ford-Fulkerson method, if the capacities of the edges are irrational numbers, which of the following statements is true?
Iterative Improvement: The Maximum-Flow Problem
Hard
A.The algorithm will always terminate but may yield a sub-optimal flow.
B.The algorithm might not terminate, and the flow value might converge to a value strictly less than the maximum flow.
C.The algorithm will always terminate with the correct maximum flow.
D.The algorithm is guaranteed to terminate in time.
Correct Answer: The algorithm might not terminate, and the flow value might converge to a value strictly less than the maximum flow.
Explanation:
If edge capacities are irrational, the Ford-Fulkerson algorithm (specifically depending on path selection) might never terminate, and the sequence of flows can converge to a value that is strictly smaller than the true maximum flow.
Incorrect! Try again.
55Using the decision tree model, what is the information-theoretic lower bound for sorting an array of distinct elements by comparisons?
Limitations of Algorithm Power: Lower-Bound Theory
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A decision tree for sorting elements must have at least leaves (one for each permutation). The height of a binary tree with leaves is at least , which by Stirling's approximation is .
Incorrect! Try again.
56In Dinic's algorithm, what is the time complexity to find the maximum flow in a bipartite graph for maximum bipartite matching?
Iterative Improvement: The Maximum-Flow Problem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
When Dinic's algorithm is applied to unit networks (such as bipartite matching graphs), the time complexity improves from to .
Incorrect! Try again.
57If you compute the binomial coefficient modulo a prime (where ), which theorem is optimally used alongside DP or recursion to compute it efficiently?
Dynamic Programming: Computing a Binomial Coefficient
Hard
A.Chinese Remainder Theorem
B.Fermat's Little Theorem
C.Lucas' Theorem
D.Wilson's Theorem
Correct Answer: Lucas' Theorem
Explanation:
Lucas' Theorem states that , where and are the digits of and in base . This drastically reduces the calculation required compared to standard DP.
Incorrect! Try again.
58When constructing an Optimal Binary Search Tree, let be the probability of searching for key and be the probability of a search falling in the interval between keys. What is the sum of all probabilities and ?
Optimal Binary Search Trees
Hard
A.$0.5$
B.
C.$1$
D.It depends on the depth of the tree.
Correct Answer: $1$
Explanation:
The problem assumes a valid probability distribution over all possible searches. A search either matches one of the keys or falls into one of the dummy intervals. Therefore, .
Incorrect! Try again.
59Is the greedy approach (always multiplying the two matrices that result in the smallest number of scalar multiplications at the current step) guaranteed to find the optimal order for matrix-chain multiplication?
Matrix-Chain Multiplication
Hard
A.No, because the subproblem optimality does not guarantee global optimality due to overlapping subproblems.
B.No, because greedy algorithms cannot be applied to matrices.
C.Yes, but only if matrix dimensions are strictly increasing.
D.Yes, it always finds the optimal solution.
Correct Answer: No, because the subproblem optimality does not guarantee global optimality due to overlapping subproblems.
Explanation:
Matrix-chain multiplication exhibits the optimal substructure property, but a local greedy choice (minimizing cost for a single pair) can lead to massive matrices for subsequent multiplications, violating global optimality.
Incorrect! Try again.
60What is the lower bound on the number of comparisons required to find both the maximum and the minimum of an array of elements simultaneously?
Limitations of Algorithm Power: Lower-Bound Theory
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By pairing elements and comparing them (taking comparisons), we can then find the max among the larger elements and the min among the smaller elements, totaling comparisons, which is proven to be the lower bound.