FREE Bachelor of Science in Computer Science: Algorithms and Data Structures Questions and Answers
The problem of ascertaining whether a bipartite graph possesses a perfect matching finds its most natural reduction in the context of which other problem?
The correct answer is determining if there is a path from one vertex to another in a graph. The problem of determining whether a bipartite graph has a perfect matching can be reduced to checking if there is a path from one vertex to another in a related graph. This transformation allows for the exploration of alternative paths in the graph to understand the existence of a perfect matching, making this problem the most naturally connected one.
Which topic is the Subset Sum decision problem most closely linked to?
The correct answer is the Set Partition decision problem. The Subset Sum decision problem is closely related to the Set Partition decision problem, where it involves determining whether a given set of integers can be divided into two subsets with equal sums. In the Subset Sum problem, the focus is on finding a subset of integers that adds up to a specific target sum, while the Set Partition problem is concerned with finding two disjoint subsets with equal sums.
In Kruskal's algorithm, the decision that follows a greedy approach is to
The correct answer is add the edge of least cost to the forest so long as its addition does not create a cycle. In Kruskal's algorithm, the greedy choice is to select the edge with the smallest weight and add it to the growing minimum spanning tree (forest) as long as adding it does not result in the formation of a cycle. This ensures the gradual construction of a minimum spanning tree that spans all vertices while maintaining acyclic properties.
If we let k represent the degree of polynomial p(n) and l represent the degree of polynomial q(n), what must be true when p(n) = o(q(n))?
The correct answer is k < l. When it is stated that polynomial p(n) is little-o of q(n) (p(n) = o(q(n))), it implies that the degree of polynomial p(n) is lower than the degree of polynomial q(n). This relationship indicates that the growth rate of p(n) is significantly smaller than that of q(n), which aligns with the assertion that k < l.
Which of the provided expressions definitively indicates the validity of the assertion f(n) = Ω(g(n))?
The correct answer is B - f(n) ≥ 4g(n) for all n ≥ 136. This option states that the function f(n) grows at least as fast as 4 times the function g(n) for all values of n greater than or equal to 136. This supports the statement f(n) = Ω(g(n)) because it establishes a lower bound on the growth rate of f(n) relative to g(n). The concept of Big O notation and the relationships between different growth rates of functions are fundamental in computer science and algorithm analysis.
As long as the pivot is chosen in a certain way, Quicksort is assured to operate within a time complexity of O(n log n).
The correct answer is set to the median of the array. When the pivot is consistently selected as the median of the elements in the array, Quicksort's time complexity is guaranteed to be O(n log n). This approach optimally balances the partitioning step, leading to efficient sorting operations.
Flawless hashing technique
The correct answer is all of the above. The term "flawless hashing technique" encompasses all the provided options. It can indeed be applied to static hash tables, ensuring no collisions occur during data retrieval, and is considered one of the most efficient methods for retrieving data from a hash table. Therefore, all three options – static hash tables, collision-free retrieval, and high efficiency – are encompassed by the concept of a flawless hashing technique.
Which of the subsequent graph-related issues cannot be resolved within a time frame that scales linearly concerning the total number of vertices and edges within the graph (i.e., O(m + n))?
The correct answer is determining a minimum spanning tree for a connected weighted graph. This problem cannot be solved within a time complexity linear with both the total number of vertices and edges (O(m + n)). Efficient algorithms for finding minimum spanning trees often require more complex operations than simple linear traversal due to the nature of selecting and connecting edges while considering weights, leading to a higher time complexity than O(m + n).
If both f(n) = O(g(n)) and f(n) = Ω(g(n)), what is a consistent and definite conclusion that can be drawn?
The correct answer is b) f(n) = Θ(g(n)). When it is given that f(n) is both big-O of g(n) and big-Ω of g(n), it signifies that f(n) has a growth rate that is tightly bounded by g(n), implying that f(n) grows at a similar rate as g(n). This relationship is represented by the notation Θ(g(n)), making option b the accurate choice.
Due to Professor Jones' proof establishing the absence of a polynomial-time algorithm for the 0-1 Knapsack optimization problem, it follows that the same conclusion holds for several other problems, except for which one?
The correct answer is determining the longest path in a directed acyclic graph. Professor Jones' proof regarding the lack of a polynomial-time algorithm for the 0-1 Knapsack problem doesn't extend to the problem of finding the longest path in a directed acyclic graph. While both problems are challenging, the complexity of the Knapsack problem's proof doesn't directly imply the same for the longest path problem.
Except for one, all the following problems can be efficiently addressed using a dynamic-programming algorithm with a polynomial time complexity in the worst-case scenario.
The correct answer is 0-1 Knapsack. Among the listed problems, 0-1 Knapsack is the one that cannot be efficiently solved using a dynamic-programming algorithm with polynomial time complexity in the worst-case scenario. The problem involves an exponential number of subproblems due to its nature of considering all possible combinations of items in the knapsack, making the dynamic-programming approach less efficient.
A binary search tree T is considered balanced when, for every node n present in T.
The correct answer is n’s left and right subtrees have heights that differ by at most one. A balanced binary search tree is defined by the property that the heights of the left and right subtrees of every node should not differ by more than one. This condition ensures that the tree remains relatively balanced, helping to maintain efficient search and insertion operations.
The task of establishing whether a bipartite graph possesses a perfect matching is best transformed into which other problem?
The correct answer is finding the maximum flow in a directed network. The problem of determining if a bipartite graph has a perfect matching can be naturally reduced to finding the maximum flow in a directed network, where the bipartite graph is transformed into a flow network. This reduction allows for the utilization of algorithms such as the Ford-Fulkerson algorithm to solve the maximum flow problem, which in turn provides information about the existence of a perfect matching in the original bipartite graph.
Among the listed algorithms, which one can be efficiently implemented without the need for a heap data structure?
The correct answer is Kruskal's algorithm. Kruskal's algorithm for finding the minimum spanning tree in a graph does not require a heap data structure for its efficient implementation. Instead, it can be implemented using a simple sorting technique to manage the edges, making it independent of heap operations.
both a) and b) are always true When a separate-chaining hash table possesses a load factor λ of 5, what value does the average chain length assume?
The correct answer is 5. When the load factor of a separate-chaining hash table is λ = 5, it implies that on average, each slot in the table contains approximately 5 elements. Therefore, the average chain length, representing the average number of elements in each slot, is 5.
Within dynamic programming, the term "memoization" pertains to
The correct answer is storing solutions to smaller subproblems for future lookup when solving larger subproblems. In dynamic programming, memoization involves keeping a record of previously computed solutions to subproblems, which can be reused to avoid redundant calculations when solving larger instances of the same problem. This technique significantly improves the efficiency of the algorithm by preventing the need to recompute solutions for subproblems that have already been solved.