An algorithm is a precise set of instructions to solve a problem or complete a task. Think of it like a recipe. Algorithms are fundamental to all computer programs.
Decomposition & Abstraction
- Decomposition is breaking down a large, complex problem into smaller, more manageable sub-problems. This makes the overall problem easier to solve. For example, programming a full game can be decomposed into sub-problems like "player movement," "scoring," and "displaying graphics."
- Abstraction is the process of removing unnecessary details to focus on the essential parts of a problem. It allows us to create a simplified model. For example, when you use a map, you don't need to know every tree and house; you just need the roads and landmarks.
By using decomposition and abstraction, we can design more efficient and robust algorithms.
Representing Algorithms
There are several ways to represent an algorithm before writing the code:
- Flowcharts: Diagrams using symbols (like rectangles, diamonds) and arrows to show the sequence of steps and decisions.
- Pseudocode: A simple, plain English way of writing out the logic of a program. It's not real code, but it's structured like it.
- Trace Tables: Used to manually step through an algorithm, tracking the value of variables at each stage. This is a crucial skill for debugging and understanding how an algorithm works.
Searching & Sorting Algorithms
Knowing common algorithms is key. Two common types are searching and sorting:
- Linear Search: A simple search that checks each item in a list one by one until it finds the target. It is slow for long lists.
- Binary Search: A much more efficient search that only works on a sorted list. It repeatedly divides the search interval in half.
- Bubble Sort: Compares adjacent items and swaps them if they are in the wrong order. It repeats this process until the list is sorted. It is easy to understand but very inefficient for large lists.
- Merge Sort: Divides the list into smaller sub-lists, sorts each, and then merges them back together. It's a faster, more efficient sorting algorithm.
- Insertion Sort: Builds the final sorted list one item at a time by repeatedly taking the next item and inserting it into its correct position in the sorted part of the list.
Reasoning About Algorithms
When you're asked to trace an algorithm or reason about its correctness, you need to use a trace table or "dry run" the code in your head. This involves tracking the values of variables and checking for edge cases (e.g., empty lists, single-item lists, or data at the very beginning or end of a list).