What is a Problem?
• Definition: A condition or situation that presents
uncertainty and requires a solution
• Key Components:
• - Initial state
• - Goal state
• - Obstacles or constraints
• Categories:
• - Well-structured problems (clear goals, defined path)
• - Ill-structured problems (ambiguous goals, unclear path)
Solvable Problems
• Characteristics:
– Clear definitions
– Logical pathways to solutions
– Verifiable outcomes
• Examples:
– Arithmetic operations
– Programming tasks with known outputs
– Planning a travel itinerary with given constraints
Unsolvable Problems
• Characteristics:
– No algorithmic solution exists
– Inherently ambiguous or contradictory
– May be undecidable within a formal system
• Examples:
– The Halting Problem
– Gödel’s Incompleteness Theorem
– Squaring the circle using only a compass and
straightedge
Distinguishing Between Problem Types: Decidability in Computer Science
• Why classification matters
• Helps prioritize effort and choose the right tools
• Prevents wasted resources on inherently unsolvable
tasks
• Turing Machines: Used to formalize algorithms
• Decidable Problems: Have an algorithmic solution (e.g.,
sorting a list)
• Undecidable Problems: No general solution exists (e.g.,
Halting Problem)
Implications of Unsolvability
• Limits of computation
• Importance of approximation, heuristics, and simulation in
real-world problems
Overview of Problem-Solving Techniques
• Techniques covered:
– Abstraction, Analogy, Brainstorming, Trial and Error, Hypothesis
Testing
– Reduction, Literal Thinking, Means-End Analysis, Focal Object
Method
– Morphological Analysis, Research, Root Cause Analysis
– Proof, Divide and Conquer
Abstraction and Analogy
Abstraction
• Focus on key elements, ignore irrelevant details
• Application:
– Programming: Class design in OOP
– Mathematics: Using functions instead of numbers
Analogy
• Transfer solutions from familiar problems to new ones
• Example:
– Learning electric circuits by comparing them to water pipes
• Helps reframe unfamiliar concepts
Brainstorming
• Group creativity method to generate many
ideas
• Guidelines:
– Withhold judgment
– Encourage wild ideas
– Combine and improve
• Applications: Product development, marketing
Trial and Error, Hypothesis Testing
Trial and Error
• Testing various options until one works
• Useful in:
– Puzzle solving
– Learning physical skills
• Limitations: Time-consuming and inefficient for complex problems
• Hypothesis Testing
• Scientific approach to validation
• Steps:
– Formulate a hypothesis
– Design an experiment
– Analyze results
• Example: Testing a drug’s efficacy
Reduction and Literal Thinking
• Reduction
• Transform a problem into a simpler or known problem
• Used in:
– Algorithm design
– Legal reasoning (precedents)
Literal Thinking
• Avoid assumptions
• Interpret information at face value
• Helps avoid misinterpretation and miscommunication
Means-End Analysis/Focal Object Method
• Means-End Analysis
• Identify difference between current state and goal
• Break down goal into manageable sub-goals
• Example: Planning a research paper
Focal Object Method
• Combine unrelated ideas to spur innovation
• Example:
– Merging 'chair' with 'clock' may result in a time-tracking
ergonomic seat
• Encourages lateral thinking