Welcome to the World of Algorithms!
Hi there! Today we are diving into one of the most important parts of Computer Science: Algorithms. Don't let the name scare you—an algorithm is simply a set of step-by-step instructions to solve a problem or complete a task. Whether you’re following a recipe to bake a cake or giving a friend directions to your house, you’re already using algorithms in real life!
In this section, we will learn how to design these instructions so that a computer can understand them, how to spot mistakes, and how to make our solutions as fast as possible.
1.1 The Building Blocks: Decomposition and Abstraction
Before we write an algorithm, we need to think like a computer scientist. We do this using Computational Thinking. Two of the most important tools are Decomposition and Abstraction.
Decomposition
Decomposition means breaking a complex problem down into smaller, more manageable parts.
Example: If you want to create a video game, you don't just "write the game." You break it down into: 1. Character movement, 2. Scoring system, 3. Graphics, and 4. Sound effects. It is much easier to solve four small problems than one giant one!
Abstraction
Abstraction means removing unnecessary details to focus on the important parts.
Example: Look at a map of the London Underground. It doesn't show every street or building; it only shows the stations and the lines. By abstracting the extra details, the map becomes easier to use.
Subprograms
A subprogram is a small section of code used to perform a specific task that can be "called" whenever needed.
Benefits of subprograms:
• You don't have to write the same code over and over again.
• It makes the program easier to read and test.
• Different people can work on different subprograms at the same time.
Quick Review: Decomposition = Breaking down. Abstraction = Simplifying. Subprograms = Reusable chunks.
1.2 Representing Algorithms
There are two main ways we "draw" or "write" algorithms before we start typing them into a computer: Flowcharts and Pseudocode.
Flowcharts
Flowcharts use different shapes to show the path a program takes. Here are the shapes you must know:
• Oval (Terminator): Used for "Start" and "Stop".
• Parallelogram: Used for Input (e.g., asking for a name) and Output (e.g., printing a result).
• Rectangle: Used for Process (e.g., a calculation like \(x = y + 2\)).
• Diamond: Used for a Decision (e.g., "Is the score > 50?"). This shape always has two arrows coming out: one for "Yes/True" and one for "No/False".
Pseudocode
Pseudocode is a way of writing instructions that looks like a programming language but uses plain English. There are no strict "grammar" rules, so you don't have to worry about missing a semicolon!
Example:
OUTPUT "What is your age?"
INPUT userAge
IF userAge >= 18 THEN OUTPUT "You can vote!"
1.3 Programming Constructs
Every algorithm in the world is built using three basic structures:
1. Sequence: Completing instructions in a specific order, one after the other.
2. Selection: Making a choice using IF, THEN, and ELSE.
3. Iteration (Repetition): Looping through instructions more than once. There are two types:
• Count-controlled: Use this when you know exactly how many times to repeat (e.g., a FOR loop).
• Condition-controlled: Use this when you want to repeat until something changes (e.g., a WHILE loop).
Key Takeaway: Every program is just a mix of steps (sequence), choices (selection), and loops (iteration).
1.4 Operators and Data
To make calculations and decisions, we use Operators. Think of these as the "verbs" of your algorithm.
Arithmetic Operators
These are used for math:
• Addition: \(+\)
• Subtraction: \(-\)
• Multiplication: \(*\)
• Division: \(/\)
• Integer Division (DIV): Tells you how many times a number goes into another, ignoring the remainder (e.g., \(7 \text{ DIV } 2 = 3\)).
• Modulus (MOD): Only tells you the remainder (e.g., \(7 \text{ MOD } 2 = 1\)).
• Exponentiation: \(^\) (e.g., \(2 ^ 3 = 8\)).
Relational and Logical Operators
These help the computer make decisions:
• Relational: == (equal to), != (not equal to), < (less than), > (greater than).
• Logical: AND (both must be true), OR (at least one must be true), NOT (flips the result).
Common Mistake: Don't confuse = with ==. In many languages, a single = sets a value (assignment), while == asks "are these equal?" (comparison).
1.5 Finding and Fixing Errors
Even the best programmers make mistakes! There are three types of errors you need to know:
1. Syntax Error: A "grammar" mistake in the code (e.g., spelling PRINT as PRUNT). The program won't even start.
2. Logic Error: The program runs, but it gives the wrong answer. For example, if you wanted to add two numbers but accidentally typed a minus sign.
3. Runtime Error: An error that happens while the program is running, causing it to crash (e.g., asking the computer to divide a number by zero).
Trace Tables
A Trace Table is a tool used to track the values of variables as you follow an algorithm line by line. It helps you find logic errors.
How to do it: Create a column for each variable and a column for the output. Update the values every time the code changes them.
1.6 Standard Algorithms: Searching and Sorting
You need to understand how these four classic algorithms work. Imagine you have a pile of shuffled exam papers and you need to find a specific student or put them in alphabetical order.
Searching Algorithms
1. Linear Search: You look at every item in the list, one by one, from start to finish. It works on any list, but it's slow for large groups.
2. Binary Search: Much faster! You go to the middle of the list. If the item you want is smaller, you throw away the right half. If it's larger, you throw away the left half. Repeat until you find it.
Important: Binary search ONLY works if the list is already sorted.
Sorting Algorithms
1. Bubble Sort: You compare two items next to each other and swap them if they are in the wrong order. You keep doing "passes" through the list until no more swaps are needed.
2. Merge Sort: A "divide and conquer" algorithm. You split the list into individual items, then merge them back together in the correct order. It is very fast for large lists!
Memory Aid: "Linear" is like a line. "Binary" is like bi-secting (cutting in half).
1.7 Algorithm Efficiency
How do we know if an algorithm is "good"? We evaluate its efficiency based on:
• Time: How many comparisons or passes does it take?
• Space: How much memory does it use?
Example: A Binary Search is more efficient than a Linear Search because it usually takes fewer steps to find an answer.
Key Takeaway: Don't just find a solution—find the fastest and neatest solution!