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 break a complex problem into smaller subproblems of the same structure, solve them independently, and then combine 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 suitable for divide and conquer if it satisfies the following conditions:

• The problem can be broken down into multiple subproblems with the same structure
• The subproblems are independent of each other, with no dependencies
• The solutions to the subproblems can be combined 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: Decompose the original problem into several smaller subproblems of the same form. These subproblems are independent and have the same structure as the original problem.
2. Conquer: Recursively solve these subproblems. If a subproblem is small enough (reaches 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 process of divide and conquer.

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

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 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 we can see, n disks require 2^n - 1 steps, and each recursion reduces the problem size by 1.

Detailed Problem-Solving Steps

When encountering a problem, determine whether divide and conquer is appropriate and design the solution:

1. Determine if divide and conquer applies: Can the problem be split into several subproblems of the same structure? Are the subproblems independent? Can the subproblem solutions be combined into the original solution? If all three conditions are met, divide and conquer can be used.
2. Determine the decomposition method: Usually split the data in half from the middle (like merge sort), or choose a pivot to split data into two groups (like quick sort).
3. Determine the base case: At what problem size can you solve it directly? For example, an array with only one element is naturally sorted.
4. Design the combine step: This is often the most critical and difficult 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. Common result: splitting into 2 parts with O(n) merge gives O(n log n) total.

Common Mistakes

• Using divide and conquer when subproblems are not independent: If subproblems overlap (like recursive Fibonacci), direct divide and conquer leads to massive redundant computation; dynamic programming should be used instead.
• Improper base case handling: Forgetting 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 wrong.
• Uneven decomposition: If the decomposition is extremely uneven each time (e.g., always splitting into 1 and n-1), 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: Divide and conquer recursion depth is usually O(log n), so stack overflow is rare. But with uneven decomposition, recursion depth can reach O(n).

III. Homework

Programming Exercises

1. Round-Robin Tournament Schedule: L3102