Introduction to Problems and Problem Solving

TL;DR

Understanding algorithms starts with clearly defining a problem and figuring out what its solution should look like. Problem-solving in computer science is about breaking down complex tasks into smaller, manageable steps. This structured approach helps you design efficient algorithms to achieve specific goals.

1. The Mental Model

Think of problem-solving like baking a cake. First, you need to know what cake you want (the problem). Then, you need a recipe (the algorithm) to go from ingredients (input) to a delicious cake (output).

2. The Core Material

At its heart, an algorithm is just a step-by-step set of instructions to solve a problem. Before you can write an algorithm, you need to fully understand the problem you're trying to solve.

Defining a Problem

Photo by Ann H on Pexels

A well-defined problem has clear inputs and desired outputs.

• Input: This is the information or data you start with. What does your algorithm receive?
• Output: This is the result or answer you want to get. What should your algorithm produce?
• Constraints: These are any rules or limitations. For example, "the input numbers will always be positive" or "the output must be sorted in ascending order."

Steps to Problem Solving

Photo by Vanessa Garcia on Pexels

Solving a problem algorithmically usually follows a structured path:

1. Understand the Problem: Read it carefully. What's given? What's expected? Are there any tricky parts?
2. Plan the Solution: Don't jump straight into code! Think about how you'd solve it manually. Break it down. What steps would you take?
3. Design the Algorithm: Translate your plan into a series of clear, unambiguous steps. This is often done using pseudocode or flowcharts.
4. Implement the Algorithm: Write the actual code based on your design.
5. Test and Debug: Check if your code works correctly for various inputs, especially edge cases. Fix any errors.

Here's a simple flowchart illustrating this process:

graph TD
    A["Understand the Problem"] --> B["Plan the Solution (High-Level Steps)"];
    B --> C["Design the Algorithm (Detailed Steps/Pseudocode)"];
    C --> D["Implement the Algorithm (Code)"];
    D --> E{"Test and Debug?"};
    E -- "No (Errors)" --> D;
    E -- "Yes (Works)" --> F["Problem Solved!"];

Problem Decomposition

Photo by Ann H on Pexels

Complex problems are hard to tackle all at once. Problem decomposition is the technique of breaking a large problem into smaller, more manageable sub-problems. Solving each sub-problem individually makes the overall task easier. For example, building a house involves many smaller tasks: laying the foundation, framing walls, adding plumbing, etc.

3. Worked Example

Let's define a simple problem and sketch a solution:

Problem: Given a list of positive numbers, find the largest number in the list.

1. Understand the Problem:

   • Input: A list (or array) of positive numbers, e.g., [3, 1, 7, 4, 9, 2].
   • Output: The single largest number from that list, e.g., 9.
   • Constraints: All numbers in the list are positive. The list will not be empty.

2. Plan the Solution:

   • I need to look at each number in the list.
   • I need a way to remember the biggest number I've seen so far.
   • If I see a number larger than my current "biggest so far," I'll update my "biggest so far."
   • After checking all numbers, whatever I have as "biggest so far" will be the answer.

3. Design the Algorithm (Pseudocode):

   ```
   function findLargestNumber(list_of_numbers):
   // Assume the first number is the largest initially
   largest_so_far = list_of_numbers[0]

   // Loop through the rest of the numbers in the list
   for each number in list_of_numbers (starting from the second number):
       if number > largest_so_far:
           largest_so_far = number
   
   // After checking all numbers, return the largest one found
   return largest_so_far
   

   ```

4. Key Takeaways

• An algorithm is a clear, step-by-step procedure to solve a problem.
• Before writing code, thoroughly understand the problem's inputs, outputs, and constraints.
• Break down big problems into smaller, more manageable parts (decomposition).
• Planning with pseudocode or flowcharts helps organize your thoughts before coding.
• Testing is crucial to ensure your algorithm works correctly for all valid scenarios.

Common Mistakes to Avoid

Photo by KATRIN BOLOVTSOVA on Pexels

• Jumping straight to coding: Resist the urge to code before you have a clear plan.
• Not defining the problem clearly: Vague inputs or outputs lead to buggy or incorrect solutions.
• Ignoring edge cases: What if the input list has only one item? What if numbers are very large or very small?
• Overcomplicating the solution: Sometimes the simplest approach is the best; don't add unnecessary steps.

5. Now Try It

Exercise: Design an algorithm (using pseudocode or steps) to solve the following problem:
Given a list of words, count how many times the word "apple" appears in the list.

What to do:
1. Clearly define the input, output, and any constraints.
2. Outline the steps you would take to manually solve this problem.
3. Write out your algorithm in pseudocode or as a numbered list of instructions.

What success looks like:
You have a clear set of instructions that, if followed, would correctly count the occurrences of "apple" in any given list of words.