Question 96
Which algorithm is suitable for solving the Fractional Knapsack problem?
Fractional Knapsack allows taking fractions of items. Sorting items by value-to-weight ratio and taking greedily yields the optimal solution in O(N log N) time.
Which algorithm is suitable for solving the Fractional Knapsack problem?
Fractional Knapsack allows taking fractions of items. Sorting items by value-to-weight ratio and taking greedily yields the optimal solution in O(N log N) time.
What is the worst-case time complexity of Quick Sort when using Randomized Pivot selection?
Randomized pivot selection makes the worst case O($N^2)$ extremely unlikely in practice, but the theoretical worst case remains O($N^2)$ if bad pivots are repeatedly chosen.
In an Adjacency List representation of a directed graph with V vertices and E edges, what is the sum of lengths of all adjacency lists?
In a directed graph, each edge (u, v) appears exactly once in u's adjacency list, so the total sum of list lengths is E.
Which graph algorithm uses the Greedy approach to find the Minimum Spanning Tree by growing a single tree from a starting vertex?
Prim's algorithm grows a single minimum spanning tree from an arbitrary starting vertex by greedily adding the cheapest edge connecting a vertex inside the tree to a vertex outside.
Which data structure is used to implement Breadth-First Search (BFS)?
BFS uses a First-In-First-Out (FIFO) Queue to explore graph vertices level by level in increasing order of distance from the source.