I. In-Class Exercises

Programming Exercises

1. Tower of Hanoi: L3101

II. Knowledge Summary

✨ Core Idea

The core idea of Divide and Conquer is to "divide and rule." It breaks a complex large problem into multiple smaller subproblems that share the same structure, solves them individually, and then merges the results to obtain the solution to the original problem. Divide and Conquer is one of the most important strategies in algorithm design, and many classic algorithms (such as merge sort and quick sort) are based on this approach.

✨ Applicable Problems

Divide and Conquer is suitable for problems that can naturally be decomposed into repeated subproblems. Specifically, a problem is a good fit for Divide and Conquer when it satisfies the following conditions:

• The problem can be broken down into multiple subproblems with the same structure
• The subproblems are mutually independent with no dependencies between them
• The solutions to the subproblems can be merged into the solution of the original problem
• There is a clear base case (the smallest subproblem can be solved directly)

✨ Problem-Solving Approach

The Divide and Conquer approach typically follows three steps:

1. Divide: Break the original problem into several smaller problems of the same type. These subproblems are independent of each other and share the same form as the original problem.
2. Conquer: Recursively solve these subproblems. If a subproblem is small enough (reaching the base case), solve it directly without further decomposition.
3. Combine: Merge the solutions of the subproblems into the solution of the original problem. The efficiency of the combine step often determines the overall efficiency of the divide and conquer algorithm.

✨ Execution Example

Using the classic Tower of Hanoi problem to demonstrate the complete execution of Divide and Conquer.

Problem: Move 3 disks from peg A to peg C, using peg B as an auxiliary. The rules are: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller disk.

Divide and Conquer approach: Break "move n disks from A to C" into three steps:

1. Move the top n-1 disks from A to B (using C)
2. Move the largest disk from A to C
3. Move the n-1 disks from B to C (using A)

1hanoi(3, A, B, C)  — Move 3 disks from A to C
2├── hanoi(2, A, C, B)  — First move top 2 from A to B
3│   ├── hanoi(1, A, B, C)  — Move 1 from A to C
4│   │   └── Move: A → C        (Step 1)
5│   ├── Move: A → B              (Step 2)
6│   └── hanoi(1, C, A, B)  — Move 1 from C to B
7│       └── Move: C → B        (Step 3)
8├── Move: A → C                  (Step 4) ★ Move the largest disk
9└── hanoi(2, B, A, C)  — Then move 2 from B to C
10    ├── hanoi(1, B, C, A)  — Move 1 from B to A
11    │   └── Move: B → A        (Step 5)
12    ├── Move: B → C              (Step 6)
13    └── hanoi(1, A, B, C)  — Move 1 from A to C
14        └── Move: A → C        (Step 7)

A total of 7 steps (2^3 - 1 = 7). As you can see, n disks require 2^n - 1 steps, and each recursive call reduces the problem size by 1.

✨ Detailed Problem-Solving Steps

When encountering a problem, determine whether it is suitable for Divide and Conquer and design a solution:

1. Determine if Divide and Conquer applies: Can the problem be split into several subproblems with the same structure? Are the subproblems independent? Can the subproblem solutions be merged into the original solution? If all three conditions are met, Divide and Conquer can be used.
2. Determine the decomposition method: Typically, the data is split in half from the middle (as in merge sort), or a pivot is chosen to divide the data into two groups (as in quick sort).
3. Determine the base case: At what problem size can the problem be solved directly? For example, an array with only one element is naturally sorted.
4. Design the combine step: This is often the most critical and challenging part of Divide and Conquer. For example, "merging two sorted arrays" is the combine step in merge sort.
5. Analyze time complexity: The time complexity of Divide and Conquer can be analyzed using the Master Theorem. A common result: splitting into 2 parts with O(n) merging yields O(n log n) total.

✨ Common Mistakes

• Using Divide and Conquer when subproblems are not independent: If subproblems overlap (such as in the recursive computation of Fibonacci numbers), direct Divide and Conquer leads to massive redundant computation. Dynamic programming should be used instead.
• Improper base case handling: Forgetting to write the base case causes infinite recursion. Setting the base case condition too early (e.g., returning directly when n<=2) may miss edge cases.
• Incorrect combine step: The combine step is the core of Divide and Conquer. If the merging logic is wrong, even if all subproblems are solved correctly, the final result will be incorrect.
• Uneven decomposition: If each decomposition is extremely uneven (e.g., always splitting into 1 and n-1), the time complexity degrades from O(n log n) to O(n^2). This is the cause of quick sort's worst case.
• Insufficient recursion stack space: The recursion depth of Divide and Conquer is typically O(log n), which generally does not cause stack overflow. However, if the decomposition is uneven, the recursion depth may reach O(n).

III. Homework

Programming Exercises

1. Round-Robin Tournament Schedule: L3102