Lesson 3.2: Problem Decomposition

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

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)

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

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

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)

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]

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.

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

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.

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.

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)

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