Lesson 3.2: Problem Decomposition

Duration: 75 minutes

Introduction

Some problems are too complex to solve in one step, even with Chain of Thought. The solution? Break them down into smaller, manageable sub-problems. In this lesson, you’ll learn systematic decomposition strategies that transform overwhelming challenges into solvable pieces.

Why Decomposition Matters

Reduces Complexity

Transforms hard problems into easier sub-problems

Improves Accuracy

Each sub-problem is simpler and less error-prone

Enables Verification

Easier to verify correctness of smaller pieces

Handles Hierarchy

Natural for problems with hierarchical structure

Least-to-Most Prompting

Start with the simplest sub-problem and build up to the complex one.

The Pattern

Identify Sub-Problems

Break the main problem into ordered sub-problems

Solve Sequentially

Solve each sub-problem, using previous solutions

Build to Solution

Combine sub-solutions to solve the original problem

Basic Example

Problem: Write a function to find the longest palindromic substring in a string.

Let's break this down from least to most complex:

Sub-problem 1: How do we check if a string is a palindrome?
Solution: Compare the string with its reverse, or check characters from both ends moving inward.

Sub-problem 2: How do we generate all possible substrings?
Solution: Use nested loops - outer loop for start position, inner loop for end position.

Sub-problem 3: How do we find the longest among palindromic substrings?
Solution: Track the longest palindrome found while checking each substring.

Now, combining these solutions:

def longest_palindrome(s):
    def is_palindrome(substr):
        return substr == substr[::-1]
    
    longest = ""
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substr = s[i:j]
            if is_palindrome(substr) and len(substr) > len(longest):
                longest = substr
    
    return longest

Key Insight: Each sub-problem is simpler than the original, and solving them in order builds toward the complete solution.

Complex Example: Multi-Step Planning

Problem: Plan a cross-country road trip from New York to Los Angeles with stops at national parks, 
staying within a $3000 budget for a family of 4.

Let's decompose this from least to most complex:

Sub-problem 1: What is the basic route from NY to LA?
Answer: I-80 West is the most direct route, approximately 2,800 miles.

Sub-problem 2: Which national parks are along or near this route?
Answer: 
- Cuyahoga Valley (Ohio)
- Indiana Dunes (Indiana)
- Badlands (South Dakota)
- Yellowstone (Wyoming)
- Grand Teton (Wyoming)
- Zion (Utah)
- Death Valley (California)

Sub-problem 3: How many days will this take?
Answer: 
- Driving: ~40 hours = 5-6 driving days
- Park visits: 1-2 days each × 7 parks = 7-14 days
- Total: 12-20 days (let's plan for 14 days)

Sub-problem 4: What are the major cost categories?
Answer:
- Gas: ~2,800 miles ÷ 25 mpg × $3.50/gallon = $392
- Lodging: 13 nights × $100/night = $1,300
- Food: 14 days × $150/day = $2,100
- Park fees: ~$200
- Total estimated: $3,992

Sub-problem 5: How can we reduce costs to meet the $3000 budget?
Answer:
- Camp instead of hotels: Save $650 (7 nights camping at $30 vs $100)
- Pack lunches: Save $400 (reduce food budget)
- Skip 2 parks: Save $100 in fees and gas
- Revised total: ~$2,942

Final Plan:
- Route: NY → Cuyahoga → Badlands → Yellowstone → Grand Teton → Zion → LA
- Duration: 14 days
- Lodging: Mix of camping (7 nights) and budget hotels (6 nights)
- Budget: $2,942 (within $3000 limit)

Recursive Problem Solving

Use the solution to simpler versions of the problem to solve the complex version.

The Recursive Pattern

Problem: [COMPLEX PROBLEM]

Step 1: Identify the base case (simplest version)
Step 2: Solve the base case
Step 3: Show how to build from simpler to more complex
Step 4: Apply recursively to reach the solution

Example: Factorial Calculation

Problem: Calculate 5! (5 factorial)

Let's solve this recursively:

Base case: What is 1!?
Answer: 1! = 1

Recursive relationship: How does n! relate to (n-1)!?
Answer: n! = n × (n-1)!

Building up:
- 1! = 1 (base case)
- 2! = 2 × 1! = 2 × 1 = 2
- 3! = 3 × 2! = 3 × 2 = 6
- 4! = 4 × 3! = 4 × 6 = 24
- 5! = 5 × 4! = 5 × 24 = 120

Answer: 5! = 120

Example: Tower of Hanoi

Problem: Solve Tower of Hanoi with 3 disks - move all disks from peg A to peg C using peg B.

Let's decompose recursively:

Base case: Moving 1 disk
Solution: Simply move it from source to destination

Recursive case: Moving n disks
Solution:
1. Move (n-1) disks from source to auxiliary peg
2. Move the largest disk from source to destination
3. Move (n-1) disks from auxiliary to destination

For 3 disks (A→C using B):

Step 1: Move 2 disks from A to B (using C)
  - Move 1 disk from A to C
  - Move disk from A to B
  - Move 1 disk from C to B

Step 2: Move largest disk from A to C

Step 3: Move 2 disks from B to C (using A)
  - Move 1 disk from B to A
  - Move disk from B to C
  - Move 1 disk from A to C

Total moves: 7 (which equals 2³ - 1)

Sub-Question Decomposition

Break complex questions into simpler questions.

The Pattern

Main Question: [COMPLEX QUESTION]

Let's break this into sub-questions:

Q1: [SIMPLER QUESTION 1]
A1: [ANSWER]

Q2: [SIMPLER QUESTION 2]
A2: [ANSWER]

Q3: [SIMPLER QUESTION 3]
A3: [ANSWER]

Synthesizing answers:
[COMBINE TO ANSWER MAIN QUESTION]

Example: Business Analysis

Main Question: Should our company invest in developing a mobile app?

Let's break this into sub-questions:

Q1: Who is our target audience and do they use mobile apps?
A1: Our target audience is 25-45 year olds, 89% of whom use smartphones daily and spend 
average 3.5 hours on mobile apps.

Q2: What problems would the app solve for our customers?
A2: 
- Easier access to our services on-the-go
- Push notifications for updates
- Offline functionality
- Faster checkout process

Q3: What are the development and maintenance costs?
A3:
- Initial development: $50,000-$100,000
- Annual maintenance: $15,000-$25,000
- Marketing: $20,000 first year

Q4: What is the potential ROI?
A4:
- Expected new customers: 5,000 in year 1
- Average customer value: $200/year
- Revenue potential: $1,000,000
- ROI: ~900% over 3 years

Q5: What are the risks?
A5:
- Technical challenges
- User adoption uncertainty
- Ongoing maintenance commitment
- Competition from existing apps

Synthesizing answers:
Given our mobile-active target audience, clear customer benefits, strong ROI potential 
($1M revenue vs $100K investment), and manageable risks, we should invest in the mobile app. 
The data strongly supports this decision, with the primary risk being user adoption, which 
we can mitigate through targeted marketing.

Planning and Execution Separation

Separate the planning phase from the execution phase.

The Two-Phase Pattern

Phase 1: Planning
- Understand the problem
- Identify sub-tasks
- Determine order of operations
- Allocate resources

Phase 2: Execution
- Execute each sub-task
- Track progress
- Adjust as needed
- Verify completion

Example: Software Development

Problem: Build a user authentication system for a web application.

PHASE 1: PLANNING

Step 1: Define requirements
- User registration with email verification
- Login with email/password
- Password reset functionality
- Session management
- Security: password hashing, rate limiting

Step 2: Break into components
1. Database schema (users table)
2. Registration endpoint
3. Email verification system
4. Login endpoint
5. Password reset flow
6. Session management
7. Security middleware

Step 3: Determine dependencies
- Database schema must be created first
- Email system needed before registration
- Session management needed before login
- Security middleware wraps all endpoints

Step 4: Create implementation order
1. Database schema
2. Email service setup
3. Password hashing utility
4. Registration endpoint + email verification
5. Login endpoint
6. Session management
7. Password reset flow
8. Security middleware (rate limiting)
9. Testing and security audit

PHASE 2: EXECUTION

Task 1: Database Schema ✓
Created users table with: id, email, password_hash, verified, created_at

Task 2: Email Service ✓
Integrated SendGrid API for transactional emails

Task 3: Password Hashing ✓
Implemented bcrypt with salt rounds = 12

Task 4: Registration Endpoint ✓
POST /api/register - creates user, sends verification email

Task 5: Login Endpoint ✓
POST /api/login - validates credentials, creates session

Task 6: Session Management ✓
JWT tokens with 24-hour expiration

Task 7: Password Reset ✓
Implemented reset token generation and validation

Task 8: Security Middleware ✓
Added rate limiting: 5 attempts per 15 minutes

Task 9: Testing ✓
All endpoints tested, security audit passed

Result: Complete authentication system deployed successfully.

When to Use Decomposition

Hierarchical Problems

Use when: The problem has natural sub-components or layersExample: “Design a complete e-commerce checkout flow” (cart → shipping → payment → confirmation)

Multi-Domain Problems

Use when: The problem spans multiple areas of expertiseExample: “Plan a product launch” (marketing + engineering + sales + support)

Sequential Dependencies

Use when: Later steps depend on earlier stepsExample: “Build a house” (foundation → framing → plumbing → electrical → finishing)

Overwhelming Complexity

Use when: The full problem is too complex to hold in working memoryExample: “Optimize a company’s entire supply chain”

Advanced Decomposition Techniques

Parallel Decomposition

Break into independent sub-problems that can be solved simultaneously.

Problem: Analyze customer satisfaction across multiple channels

Decompose into parallel tracks:

Track 1: Email Survey Analysis
- Collect email survey responses
- Calculate satisfaction scores
- Identify common themes

Track 2: Social Media Sentiment
- Scrape social media mentions
- Perform sentiment analysis
- Track trending topics

Track 3: Support Ticket Analysis
- Review support ticket data
- Calculate resolution times
- Identify pain points

Track 4: Product Review Analysis
- Aggregate product reviews
- Calculate star ratings
- Extract feature feedback

Synthesis:
Combine insights from all four tracks to create comprehensive satisfaction report.

Constraint-Based Decomposition

Break down by identifying and addressing constraints.

Problem: Reduce software deployment time from 4 hours to 30 minutes

Identify constraints:
1. Manual testing takes 2 hours
2. Database migrations take 1 hour
3. Build process takes 45 minutes
4. Deployment scripts take 15 minutes

Address each constraint:

Constraint 1: Manual testing (2 hours)
Solution: Implement automated test suite
Expected improvement: 2 hours → 10 minutes

Constraint 2: Database migrations (1 hour)
Solution: Optimize migration scripts, use parallel execution
Expected improvement: 1 hour → 15 minutes

Constraint 3: Build process (45 minutes)
Solution: Implement incremental builds, caching
Expected improvement: 45 minutes → 10 minutes

Constraint 4: Deployment scripts (15 minutes)
Solution: Optimize scripts, parallel deployment
Expected improvement: 15 minutes → 5 minutes

Total new time: 10 + 15 + 10 + 5 = 40 minutes
Result: Reduced from 4 hours to 40 minutes (83% improvement)

Best Practices

Start Simple

Begin with the easiest sub-problem to build confidence

Check Dependencies

Ensure sub-problems are solved in the right order

Verify Each Step

Confirm each sub-solution before moving forward

Synthesize Clearly

Show how sub-solutions combine to solve the main problem

Practice Exercises

Exercise 1: Algorithm Design

Decompose this problem: “Design an algorithm to find the shortest path between two cities on a map.”

Sample Solution

Let's decompose from least to most complex:

Sub-problem 1: How do we represent the map?
Solution: Use a graph where cities are nodes and roads are weighted edges (weight = distance)

Sub-problem 2: How do we find all possible paths?
Solution: Use graph traversal (BFS or DFS) to explore paths

Sub-problem 3: How do we track the shortest path?
Solution: Keep track of the minimum distance to each node

Sub-problem 4: How do we handle the complete algorithm?
Solution: Implement Dijkstra's algorithm:
1. Initialize distances (start = 0, others = infinity)
2. Use priority queue to process nodes by distance
3. For each node, update distances to neighbors
4. Continue until destination is reached

Final algorithm: Dijkstra's shortest path algorithm

Exercise 2: Business Problem

Decompose: “Increase company revenue by 25% in the next year.”

Sample Solution

Main Goal: Increase revenue by 25%

Sub-question 1: What are our current revenue streams?
- Product sales: $2M (50%)
- Services: $1.5M (37.5%)
- Subscriptions: $500K (12.5%)
- Total: $4M

Sub-question 2: What's our target revenue?
- Current: $4M
- Target: $4M × 1.25 = $5M
- Increase needed: $1M

Sub-question 3: How can we increase each stream?
Product sales:
- Launch 2 new products: +$300K
- Improve conversion rate: +$200K

Services:
- Expand to new market: +$250K
- Upsell existing clients: +$150K

Subscriptions:
- New pricing tier: +$100K
- Reduce churn: +$50K

Sub-question 4: What resources are needed?
- Product development: 6 months, $150K
- Marketing: $200K
- Sales team expansion: 2 new hires
- Customer success: 1 new hire

Sub-question 5: What's the implementation timeline?
Q1: Product development, hire sales team
Q2: Launch new products, expand services
Q3: Optimize conversion, reduce churn
Q4: Scale successful initiatives

Expected result: $1.05M increase (105% of goal)

Exercise 3: Technical Problem

Decompose: “Debug why a web application is slow.”

Sample Solution

Problem: Web application is slow

Phase 1: Identify problem areas

Q1: Where is the slowness occurring?
- Frontend load time: 8 seconds
- API response time: 3 seconds
- Database queries: 2 seconds

Q2: What are the specific bottlenecks?
Frontend:
- Large JavaScript bundles (2MB)
- Unoptimized images (5MB total)
- No caching

Backend:
- N+1 query problem
- Missing database indexes
- No query caching

Phase 2: Prioritize by impact

High impact:
1. Database indexes (2s → 0.2s)
2. Fix N+1 queries (1s → 0.1s)
3. Image optimization (3s → 0.5s)

Medium impact:
4. Code splitting (2s → 1s)
5. Enable caching (0.5s → 0.1s)

Phase 3: Implement solutions

Solution 1: Add database indexes
- Index user_id, created_at columns
- Result: Query time 2s → 0.2s

Solution 2: Fix N+1 queries
- Use eager loading
- Result: API time 3s → 2s

Solution 3: Optimize images
- Compress and resize images
- Use WebP format
- Result: Load time 8s → 5s

Solution 4: Code splitting
- Split bundles by route
- Result: Initial load 5s → 4s

Solution 5: Enable caching
- Browser caching + CDN
- Result: Repeat visits 4s → 1s

Final result: 8s → 1s (87.5% improvement)

Real-World Application: Project Planning System

You are a project planning assistant. Help break down complex projects into manageable tasks.

Project: [PROJECT DESCRIPTION]

Step 1: Understand the Goal
What is the ultimate objective?
What defines success?

Step 2: Identify Major Phases
Break the project into 3-5 major phases

Step 3: Decompose Each Phase
For each phase, list:
- Key deliverables
- Required resources
- Dependencies
- Estimated duration

Step 4: Create Task List
Break each phase into specific, actionable tasks

Step 5: Determine Critical Path
Identify which tasks must be completed in sequence

Step 6: Allocate Resources
Assign team members and resources to tasks

Step 7: Create Timeline
Build a realistic schedule with milestones

Output Format:
- Project Overview
- Phase Breakdown
- Detailed Task List
- Timeline with Milestones
- Resource Allocation
- Risk Assessment

Key Takeaways

Use least-to-most prompting for hierarchical problems

Apply recursive decomposition for self-similar problems

Break complex questions into simpler sub-questions

Separate planning from execution for clarity

Verify each sub-solution before proceeding

Synthesize sub-solutions to solve the main problem

Next Steps

You’ve mastered problem decomposition. Now learn how to iteratively improve outputs through self-refinement and critique.

Next: Lesson 3.3 - Self-Refinement & Iteration

Improve outputs through self-critique and iteration

​Introduction

​Why Decomposition Matters

Reduces Complexity

Improves Accuracy

Enables Verification

Handles Hierarchy

​Least-to-Most Prompting

​The Pattern

​Basic Example

​Complex Example: Multi-Step Planning

​Recursive Problem Solving

​The Recursive Pattern

​Example: Factorial Calculation

​Example: Tower of Hanoi

​Sub-Question Decomposition

​The Pattern

​Example: Business Analysis

​Planning and Execution Separation

​The Two-Phase Pattern

​Example: Software Development

​When to Use Decomposition

​Advanced Decomposition Techniques

​Parallel Decomposition

​Constraint-Based Decomposition

​Best Practices

Start Simple

Check Dependencies

Verify Each Step

Synthesize Clearly

​Practice Exercises

​Exercise 1: Algorithm Design

​Exercise 2: Business Problem

​Exercise 3: Technical Problem

​Real-World Application: Project Planning System

​Key Takeaways

​Next Steps

Next: Lesson 3.3 - Self-Refinement & Iteration

Introduction

Why Decomposition Matters

Least-to-Most Prompting

The Pattern

Basic Example

Complex Example: Multi-Step Planning

Recursive Problem Solving

The Recursive Pattern

Example: Factorial Calculation

Example: Tower of Hanoi

Sub-Question Decomposition

The Pattern

Example: Business Analysis

Planning and Execution Separation

The Two-Phase Pattern

Example: Software Development

When to Use Decomposition

Advanced Decomposition Techniques

Parallel Decomposition

Constraint-Based Decomposition

Best Practices

Practice Exercises

Exercise 1: Algorithm Design

Exercise 2: Business Problem

Exercise 3: Technical Problem

Real-World Application: Project Planning System

Key Takeaways

Next Steps