Problem Solving and Algorithms

TL;DR

Problem solving is breaking down a complex challenge into smaller, manageable steps, then finding a logical path to a solution. Algorithms are those step-by-step instructions that get you from a problem's start to its end. Understanding common algorithmic patterns helps you design efficient solutions.

1. The Mental Model

Think of problem solving as baking a cake: you start with a goal (the cake), then follow a recipe (algorithm) that tells you exactly what to do, step by step, using specific ingredients (data) to get your delicious result.

2. The Core Material

Problem solving and algorithms are two sides of the same coin. You first solve the problem by figuring out what needs to happen, then you algorithmize that solution by detailing the exact steps.

What is Problem Solving?

Photo by MART PRODUCTION on Pexels

It's the process of identifying a problem, analyzing it, coming up with potential solutions, selecting the best one, and then implementing and evaluating it. It's not just about finding an answer, but often the best answer given constraints (like time or resources).

Key steps in problem solving:
1. Understand the Problem: What are the inputs? What's the desired output? What are the constraints or special conditions? What's actually being asked? Don't jump to coding until you clearly understand the goal.
2. Devise a Plan (Algorithm Design): Brainstorm different ways to solve it. Break down the problem into smaller, simpler sub-problems. Consider known patterns or structures.
3. Execute the Plan (Implementation): Write your code or carry out your steps.
4. Review and Refine (Testing & Debugging): Does your solution work? Does it handle edge cases? Can it be made more efficient or clearer?

What is an Algorithm?

Photo by Syirwan Ainu on Pexels

An algorithm is a finite set of well-defined, unambiguous instructions to solve a specific problem or perform a computation. They're like recipes:
* Input: They take some starting data.
* Output: They produce a result.
* Definite: Each step is precise.
* Effective: Each step can be carried out.
* Finite: They must terminate after a finite number of steps.

Think about how you'd instruct a robot to make a sandwich. You can't just say "make a sandwich." You'd need precise steps: "Open bread bag," "Take out two slices," "Place on plate," etc.

Common Algorithmic Concepts

Photo by Markus Winkler on Pexels

• Sequencing: Steps happen in a specific order. Most algorithms involve this.
• Selection (Conditional Logic): Making decisions based on conditions (if/else statements). "If bread is moldy, discard; else, use bread."
• Iteration (Loops): Repeating a set of steps multiple times (for, while loops). "Spread butter until bread is covered."
• Recursion: A function or process calling itself to solve smaller versions of the same problem. This is a powerful technique for problems that can be broken down into identical sub-problems, like calculating factorials or searching through tree-like structures.

Here's how problem-solving typically flows into an algorithm:

graph TD
    A["Understand the Problem"] --> B["Identify Inputs & Outputs"];
    B --> C["Break Down into Sub-problems"];
    C --> D{"Known Pattern?"};
    D -- "Yes" --> E["Apply/Adapt Pattern"];
    D -- "No" --> F["Design Step-by-Step Logic"];
    E --> G["Formulate Algorithm (Pseudocode/Flowchart)"];
    F --> G;
    G --> H["Test & Refine Algorithm"];
    H --> I["Implement Solution (Code)"];
    I --> J["Evaluate & Optimize"];

Measuring Algorithm Efficiency

Photo by https://kaboompics.com/ on Pexels

It's not enough for an algorithm to just work; it should ideally work well. We measure efficiency primarily using:

• Time Complexity: How the runtime of an algorithm grows with the size of the input. We use Big O notation (e.g., O(n), O(log n), O(n²)) to describe this. O(n) means linear growth (doubling input doubles time), O(log n) is very efficient (growth slows down significantly), O(n²) is less efficient (doubling input quadruples time).
• Space Complexity: How much extra memory an algorithm needs relative to the input size.

Choosing the right algorithm for a task often involves a trade-off between time and space efficiency.

3. Worked Example

Let's say your problem is to "Find the largest number in a list of positive integers."

1. Understand the Problem:

   • Input: A list (or array) of positive integers, e.g., [3, 1, 9, 4, 7].
   • Output: A single integer, which is the largest in the list, e.g., 9.
   • Constraint: Numbers are positive integers. The list won't be empty.

2. Devise a Plan (Algorithm):

   • We need to look at each number.
   • We need to keep track of the biggest number we've seen so far.
   • We can start by assuming the first number in the list is the biggest.
   • Then, we go through the rest of the numbers one by one.
   • If we find a number that's larger than our current "biggest so far," we update our "biggest so far" to that new number.
   • Once we've looked at all numbers, our "biggest so far" will be the overall largest.

3. Execute the Plan (Pseudocode/Python):

   ```python
   def find_largest_number(numbers):
   # 1. Handle edge case: what if the list has only one number?
   # Our plan already covers this: first number is assumed largest.
   # But let's add a check for an empty list, though problem states it won't be empty.
   if not numbers:
   return None # Or raise an error, depending on requirements

   # 2. Assume the first number is the largest found so far
   largest_so_far = numbers[0]
   
   # 3. Iterate through the rest of the numbers
   # (We can start from index 1, as 0 is already handled)
   for i in range(1, len(numbers)):
       current_number = numbers[i]
       # 4. Compare current number with largest_so_far
       if current_number > largest_so_far:
           largest_so_far = current_number # Update if current is larger
   
   # 5. After checking all numbers, return the largest found
   return largest_so_far
   

   Test cases

   list1 = [3, 1, 9, 4, 7]
   print(f"List: {list1}, Largest: {find_largest_number(list1)}") # Expected: 9

   list2 = [10]
   print(f"List: {list2}, Largest: {find_largest_number(list2)}") # Expected: 10

   list3 = [2, 2, 2]
   print(f"List: {list3}, Largest: {find_largest_number(list3)}") # Expected: 2
   ```

4. Review and Refine:

   • Does it work for all test cases? Yes.
   • Is it efficient? We look at each number once. If there are 'n' numbers, we do roughly 'n' comparisons. This is O(n) time complexity, which is generally good for this type of problem.
   • Is there a simpler way? For Python specifically, max(numbers) does this directly, but the purpose of this example was to illustrate the algorithm behind it.

4. Key Takeaways

• Always fully understand the problem's inputs, outputs, and constraints before attempting a solution.
• Break down complex problems into smaller, more manageable sub-problems to simplify the design process.
• Algorithms are precise, step-by-step instructions that guarantee a solution to a problem given valid inputs.
• Common algorithmic patterns like sequencing, selection (if/else), iteration (loops), and recursion are fundamental building blocks.
• Evaluate your algorithms for efficiency, considering both time and space complexity, usually described using Big O notation.

Common Mistakes to Avoid:
- Jumping straight to coding without fully understanding or planning the solution.
- Not considering edge cases (e.g., empty lists, single-element inputs).
- Overlooking potential inefficiencies in your algorithm, leading to slow performance.
- Writing overly complex solutions when a simpler one would suffice.

5. Now Try It

Choose a simple everyday task, like "making a cup of tea" or "tying your shoelaces." Now, write down an algorithm for it, as if you're instructing a very literal robot. Make sure your steps are unambiguous, complete, and in the correct sequence, including any selections (decisions) or iterations (loops).

Success looks like: Your algorithm should be so clear that someone unfamiliar with the task could follow your instructions precisely and achieve the desired outcome without asking clarifying questions.