Welcome to the World of Algorithm Design!
Ever wondered how a computer "thinks"? It doesn't actually have a brain like ours; instead, it follows a very specific set of instructions called an algorithm. Think of an algorithm as a recipe: if you follow the steps exactly, you get a delicious cake. If you miss a step, things might get messy!
In this chapter, we aren't just learning how to write code; we are learning how to design solutions. We will look at common "recipes" every programmer needs and learn smart ways to break down big, scary problems into small, easy ones. Don't worry if this seems tricky at first—by the end of these notes, you'll be thinking like a pro-coder!
1. Building Your Own Logic: Core Algorithms
In Python, there are built-in shortcuts like min() or sum(). However, to be a great computer scientist, you need to know how these work "under the hood." Let’s look at how to build these from scratch!
A. Finding the Highest (Maximum) or Lowest (Minimum)
The Analogy: Imagine you have a stack of 100 cards with numbers on them. You can only look at one card at a time. How do you find the biggest one? You’d probably keep the biggest one you've seen so far in your left hand and compare it to every new card you pick up with your right hand.
The Step-by-Step:
1. Pick the first item in the list and call it your current_max.
2. Go through the rest of the list one by one.
3. For each item, ask: "Is this item bigger than my current_max?"
4. If yes, update current_max to be this new item.
5. If no, just move to the next item.
6. Once you reach the end, your current_max is the winner!
Common Mistake: Don't start your current_max at 0 if your list might contain negative numbers! It is always safer to start with the first item in the list.
B. Calculating Sum and Average
The "Running Total" Trick: To find a sum, imagine a piggy bank. Every time you see a number in the list, you drop that amount into the piggy bank.
The Formula:
To find the average, you use this simple math: \( Average = \frac{Total Sum}{Number of Items} \)
Quick Review: To get the Number of Items without a shortcut, you can create a "counter" variable that starts at 0 and adds 1 for every item you look at.
C. Searching for an Item
Linear Search: This is like looking for a specific friend in a long queue. You start at the very front and ask each person, "Are you Charlie?" until you find them or reach the end.
The Logic: You use a loop to check each item. If you find a match, you record its position (index) and stop. If you reach the end and haven't found it, you can tell the user the item isn't there.
D. Extracting Items Based on Criteria
Sometimes you only want specific items—like "all numbers greater than 50" or "all names starting with A."
The Logic: Create a new, empty list. Loop through your original list, and for every item, check if it meets your criteria. If it does, "append" (add) it to your new list.
E. Splitting a String Manually
Imagine you have a sentence: "I-love-computing" and you want to separate the words every time you see a dash (-).
The Logic: Create an empty "word" string and an empty list. Look at every character. If the character is not the dash, add it to your "word." If it is the dash, it means the word is finished! Add the "word" to your list and reset your "word" string to empty.
Section Summary: Most basic algorithms follow a pattern: Initialize a variable (like a max or a sum), Loop through the data, and Update the variable based on a condition.
2. Smart Strategies for Big Problems
When you face a complex project, don't try to code it all at once. Use these four professional strategies:
A. The Modular Approach (Decomposition)
The Analogy: Think of a LEGO set. You don't build the whole castle as one giant block. You build the towers, the walls, and the gate separately, then snap them together. In computing, we break a program into small modules or functions.
Why do it? It's easier to fix a broken tower than to fix a whole broken castle!
B. The Incremental Approach
The Concept: Start with the simplest version of your program. Get it working perfectly. Then, slowly add one new feature at a time.
Example: If you are building a calculator, start by making it add. Once that works, add subtraction. Don't try to build add, subtract, multiply, and divide all at the same time!
C. Solving Manually First
Did you know? You should often step away from the computer to solve a problem! If you can't solve a small version of the problem on paper with a pencil, you won't be able to tell the computer how to do it.
The Trick: Solve 3 or 4 small examples by hand. Notice the generic steps you take. Those steps become your algorithm!
D. Pattern Recognition
The Strategy: Ask yourself, "Have I seen something like this before?"
If you know how to find the Maximum number in a list, you already know how to find the Minimum (just flip the "greater than" sign to "less than"). If you can search for a Number, you can search for a String. Don't reinvent the wheel!
3. Quick Review & Tips
Key Terms to Remember:
Algorithm: A set of step-by-step instructions.
Criteria: The rules or conditions used to pick specific data.
Delimiter: The character (like a comma or space) used to separate items in a string.
Iteration: Another word for looping or repeating steps.
Memory Aid: "I.L.U."
Most algorithms follow I.L.U.:
1. Initialize (set your variables first).
2. Loop (go through the data).
3. Update (change your variables if needed).
Final Encouragement: Algorithm design is a skill, like playing an instrument or a sport. The more you practice "manual" versions of these tasks, the more natural it will feel. You've got this!