Algorithms: Divide and Conquer vs Greedy

What is the time complexity of Merge Sort?

• O(n)

• O(n log n)

• O(log n)

• O(n^2)

Explain how Dijkstra's Algorithm finds the shortest path.

• Dijkstra's Algorithm finds the shortest path by iteratively selecting the nearest unvisited node and updating the distances to its neighbors until all nodes are processed.

• Dijkstra's Algorithm finds the shortest path by randomly selecting nodes until a path is found.

• Dijkstra's Algorithm uses a depth-first search approach to find the shortest path.

• Dijkstra's Algorithm calculates the shortest path by visiting all nodes in a random order.

What is the main difference between Prim's and Kruskal's algorithms?

• Prim's algorithm grows the MST from a starting vertex, while Kruskal's algorithm builds it by sorting edges and adding them without forming cycles.

• Kruskal's algorithm requires a starting vertex while Prim's algorithm does not.

• Prim's algorithm uses a greedy approach while Kruskal's algorithm does not.

• Prim's algorithm can only be used for directed graphs, whereas Kruskal's can be used for undirected graphs.

How does Binary Search improve search efficiency?

• Binary Search reduces the number of comparisons needed to find an element in a sorted array.

• Binary Search can only be used on linked lists.

• Binary Search increases the number of comparisons needed.

• Binary Search requires the array to be unsorted.

What are the two main types of Knapsack Problems?

• Bounded Knapsack Problem

• 0/1 Knapsack Problem and Fractional Knapsack Problem

• Dynamic Knapsack Problem

• Multi-dimensional Knapsack Problem

Describe the Strassen algorithm for matrix multiplication.

• The Strassen algorithm increases the complexity of matrix multiplication to O(n^4) using a brute-force method.

• The Strassen algorithm is a sequential approach that does not divide matrices.

• The Strassen algorithm is only applicable to square matrices of size 2x2.

• The Strassen algorithm reduces the complexity of matrix multiplication from O(n^3) to approximately O(n^2.81) by using a divide-and-conquer approach.

What is optimal reliable allocation in resource management?

• Optimal reliable allocation focuses solely on maximizing profits regardless of waste.

• Optimal reliable allocation is the strategic distribution of resources to maximize efficiency and minimize waste.

• Optimal reliable allocation is the random distribution of resources without any strategy.

• Optimal reliable allocation is the complete elimination of resource distribution.

How does the Bellman-Ford algorithm handle negative weight edges?

• The Bellman-Ford algorithm can handle negative weight edges by relaxing edges multiple times to find the shortest paths.

• The Bellman-Ford algorithm only works with positive weight edges.

• The Bellman-Ford algorithm ignores negative weight edges and returns the longest path.

• The Bellman-Ford algorithm cannot handle negative weight edges at all.

What is the purpose of the Convex Hull in computational geometry?

• To calculate the area of a polygon.

• To find the smallest convex polygon enclosing a set of points.

• To determine the centroid of a set of points.

• To find the longest line segment between two points.

Explain the greedy approach used in Prim's algorithm.

• Prim's algorithm randomly picks edges without considering their weights.

• Prim's algorithm builds the minimum spanning tree by always choosing the smallest edge that expands the tree.

• Prim's algorithm selects the largest edge to minimize the tree size.

• Prim's algorithm requires sorting all edges before selection.