Multiple Choice Questions on Algorithm Design Strategies

📚 Quick Study Guide

• ⏱️ Greedy Algorithms: Make locally optimal choices at each step with the hope of finding a global optimum. Not always guaranteed to work!
• 🌳 Divide and Conquer: Break a problem into smaller subproblems, solve them recursively, and combine the solutions. Classic example: Merge Sort.
• 🧮 Dynamic Programming: Solve overlapping subproblems by storing their solutions to avoid redundant computations. Two main approaches: top-down (memoization) and bottom-up (tabulation).
• 🔄 Backtracking: Explore all possible solutions incrementally, abandoning a path (“backtracking”) as soon as it's clear it won't lead to a valid solution.
• 🌐 Branch and Bound: Similar to backtracking, but uses bounding functions to prune the search space more efficiently. Often used for optimization problems.
• 📈 Time Complexity: Crucial for evaluating algorithm efficiency. Common notations: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$, $O(n!)$.
• 💾 Space Complexity: Measures the amount of memory an algorithm uses.

🧠 Practice Quiz

1. Which algorithm design strategy involves breaking down a problem into smaller subproblems, solving them recursively, and then combining the results?
   1. Greedy Algorithm
   2. Dynamic Programming
   3. Divide and Conquer
   4. Backtracking
2. Which of the following is NOT a characteristic of Dynamic Programming?
   1. Overlapping subproblems
   2. Optimal substructure
   3. Making locally optimal choices
   4. Storing solutions to subproblems
3. A thief is trying to maximize the value of items he steals from a store, but he can only carry a limited weight. Which algorithm design strategy is most suitable for this problem?
   1. Divide and Conquer
   2. Greedy Algorithm
   3. Dynamic Programming
   4. Backtracking
4. What is the primary advantage of using Dynamic Programming over a simple recursive approach?
   1. Simpler code
   2. Reduced time complexity due to memoization
   3. Lower space complexity
   4. Guaranteed optimal solution for all problems
5. Which algorithm design strategy is typically used for solving constraint satisfaction problems like the N-Queens problem?
   1. Greedy Algorithm
   2. Divide and Conquer
   3. Dynamic Programming
   4. Backtracking
6. Which of the following algorithms has a time complexity of $O(n \log n)$ in the average case?
   1. Bubble Sort
   2. Insertion Sort
   3. Merge Sort
   4. Selection Sort
7. Which strategy explores all possible paths until a solution is found, abandoning paths that don't work?
   1. Greedy Algorithm
   2. Divide and Conquer
   3. Backtracking
   4. Branch and Bound