Divide and Conquer & Dynamic Programming

What is the main idea behind the Divide and Conquer methodology?

• To ignore the smaller parts and focus on the overall problem.

• To combine all parts without solving them individually.

• To solve the problem in one step without breaking it down.

• The main idea is to break a problem into smaller parts, solve each part, and combine the results.

How does the Merge Sort algorithm work?

• Merge Sort algorithm sorts elements by swapping them in place.

• Merge Sort algorithm only works on linked lists, not arrays.

• Merge Sort algorithm sorts the array in a single pass without recursion.

• Merge Sort algorithm works by recursively dividing the array into halves and merging them back in sorted order.

What is the time complexity of Quick Sort in the average case?

• O(n)

• O(log n)

• O(n log n)

• O(n^2)

Explain how finding the maximum and minimum can be optimized using Divide and Conquer.

• Finding maximum and minimum can be optimized using Divide and Conquer by recursively splitting the array and comparing results.

• Using a single comparison to find both maximum and minimum is the most efficient method.

• The maximum and minimum can only be found by scanning the array sequentially.

• Finding maximum and minimum requires sorting the entire array first.

What are the key elements of dynamic programming?

• Greedy algorithms and recursion.

• Divide and conquer techniques.

• Linear programming and heuristics.

• Optimal substructure and overlapping subproblems.

Describe the Matrix-chain multiplication problem.

• The Matrix-chain multiplication problem deals with the arrangement of matrices in a physical space.

• The Matrix-chain multiplication problem is about finding the optimal order of matrix multiplications to minimize computational cost.

• The Matrix-chain multiplication problem is about finding the largest matrix in a chain.

• The Matrix-chain multiplication problem focuses on the addition of matrices.

How can dynamic programming be applied to solve the Multi-stage graph problem?

• Utilizing a breadth-first search to find the longest path from source to destination.

• Applying a greedy algorithm to select the shortest edge at each stage.

• Dynamic programming can be applied by using a cost table to iteratively compute the minimum cost to reach each node from the source through all stages.

• Using a depth-first search to explore all paths in the graph.

What is an Optimal Binary Search Tree?

• An Optimal Binary Search Tree minimizes the expected search cost for a set of keys based on their access frequencies.

• A binary tree that allows duplicate keys for faster insertion.

• A tree that maximizes the height to improve search speed.

• A tree that only contains unique keys without considering access frequencies.

How does the recursive approach differ from the dynamic programming approach in solving problems?

• The recursive approach is always faster than dynamic programming.

• Dynamic programming does not use any previous results.

• The recursive approach requires more memory than dynamic programming.

• The recursive approach may lead to repeated calculations, while dynamic programming optimizes by storing results of subproblems.

What is the worst-case time complexity of Merge Sort?

• O(n log n)

• O(n^2)

• O(n)

• O(log n)