> ## Documentation Index
> Fetch the complete documentation index at: https://prompt.university/llms.txt
> Use this file to discover all available pages before exploring further.
# Lesson 3.2: Problem Decomposition
> Break complex problems into manageable sub-problems using systematic decomposition strategies
**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
Transforms hard problems into easier sub-problems
Each sub-problem is simpler and less error-prone
Easier to verify correctness of smaller pieces
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
Break the main problem into ordered sub-problems
Solve each sub-problem, using previous solutions
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
**Use when:** The problem has natural sub-components or layers
**Example:** "Design a complete e-commerce checkout flow" (cart → shipping → payment → confirmation)
**Use when:** The problem spans multiple areas of expertise
**Example:** "Plan a product launch" (marketing + engineering + sales + support)
**Use when:** Later steps depend on earlier steps
**Example:** "Build a house" (foundation → framing → plumbing → electrical → finishing)
**Use when:** The full problem is too complex to hold in working memory
**Example:** "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
Begin with the easiest sub-problem to build confidence
Ensure sub-problems are solved in the right order
Confirm each sub-solution before moving forward
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."
```
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."
```
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."
```
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.
Improve outputs through self-critique and iteration