🧠 Topic 7: Algorithm Design and Problem-Solving 💡
Hello future computer scientists! This chapter is one of the most important in the entire course. Why? Because programming isn't just about typing code; it's about *thinking logically* to solve problems.
We are going to learn the step-by-step process used by professionals to turn a vague idea into a working computer program. Think of this as learning the recipe before you start cooking!
1. The Program Development Life Cycle (PDLC) (7.1)
When you build a computer system, you can't just jump straight into writing code. You need a structured plan. This plan is called the Program Development Life Cycle (PDLC). It has four main stages:
Stage 1: Analysis (What is the problem?)
This is the stage where you figure out exactly what the system needs to do. If you misidentify the problem here, the entire program will be wrong!
- Identification of the Problem and Requirements: What data will be used? Who is the user? What must the system achieve?
- Abstraction: This means hiding unnecessary details and showing only the essential information.
Example: When you look at a city map, you see main roads and landmarks, not every single tree or pothole. That’s abstraction—focusing on the important stuff (routes). - Decomposition: Taking a large, complex problem and breaking it down into smaller, manageable parts (sub-systems).
Example: Building a robotic arm is too big. Decompose it into: 1. Hand movement control, 2. Wrist rotation, 3. Base stability.
Stage 2: Design (How will we solve the problem?)
In this stage, you plan the step-by-step solution before writing any code. You use tools like flowcharts and pseudocode.
- Decomposition: (Used again here!) We break the system down into modules (sub-systems) which helps us design each part separately.
- Structure Diagrams: Show how the main system is divided into modules and sub-modules.
- Flowcharts: A graphical way to show the flow of logic using standard symbols (Process, Input/Output, Decision, etc.).
- Pseudocode: Structured English used to describe an algorithm. It uses programming keywords but isn't tied to a specific language.
💡 Key Concept: IPOS Structure (7.2)
When designing any module, always think about the IPOS structure:
Stage 3: Coding (Writing the solution)
This is where the plan (pseudocode/flowchart) is translated into actual program code using a high-level language (like Python or Java). This stage also includes iterative testing—testing small parts of the code as you write them.
Stage 4: Testing (Did we solve the problem correctly?)
You run the program using various types of test data to ensure it works according to the requirements and handles unexpected situations gracefully.
Key Takeaway: The PDLC ensures you fully understand the problem before you start programming, which saves huge amounts of time later on. Analysis and Design are essential for good coding!
2. Standard Methods of Solution (Algorithms) (7.4)
Certain tasks are so common in programming that they have standard, well-known solutions. You must understand and be able to describe these:
1. Totalling and Counting
These are the simplest algorithms.
- Counting: Used to track how many times an event occurs. You need a counter variable, which starts at 0 and increases by 1 each time the event happens. (e.g., Counting the number of students who scored over 80%.)
- Totalling: Used to accumulate a sum of values. You need a total variable (accumulator), which starts at 0 and adds the new value in each loop iteration. (e.g., Calculating the total cost of items in a shopping cart.)
2. Finding Maximum, Minimum, and Average Values
To find the max/min, you usually assume the first value entered is the maximum (or minimum) and then compare every subsequent value to it, updating your max/min variable if a larger/smaller value is found.
- Average: \( \text{Average} = \frac{\text{Total}}{\text{Count}} \)
3. Linear Search (Sequential Search)
Used to find a specific item in a list (array) by checking each item one by one, from start to finish.
- How it works: Start at position 1. Compare the search value to the item in the list. If they match, stop. If not, move to the next position. Continue until found or the end of the list is reached.
- Did you know? This is simple but slow for very long lists.
4. Bubble Sort
Used to put a list of items into order (ascending or descending). It gets its name because the largest (or smallest) values "bubble up" to their correct positions.
- How it works: It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed in an entire pass, meaning the list is sorted.
- Analogy: Imagine actual bubbles in a glass of soda. The largest, lightest bubbles rise to the top over time through repeated movements.
Key Takeaway: These standard algorithms are the building blocks of most programs. Make sure you can write the pseudocode for a Bubble Sort or a Linear Search!
3. Data Integrity: Validation and Verification (7.5 & 7.6)
Data integrity means ensuring that data is accurate and reasonable. We use two main methods for this: Validation and Verification.
3.1 Data Validation (7.5)
Validation checks if the data entered is reasonable and sensible, but it doesn't check if it's 100% correct.
- Range Check: Checks if the input is within a predefined maximum and minimum acceptable range.
Example: A test score must be between 0 and 100. - Length Check: Checks if the data contains the required number of characters.
Example: A password must be 8 characters long. - Type Check: Checks if the data entered is of the correct data type.
Example: A Quantity field must contain an INTEGER (a whole number), not text. - Presence Check: Checks if data has actually been entered into a field (i.e., the field is not left blank).
Example: The Name field cannot be empty. - Format Check: Checks if the data conforms to a specific pattern or structure.
Example: A UK postcode must be in the format 'LLNN NLL' (e.g., SW1A 0AA). - Check Digit: An extra digit calculated from the other digits in a number (like an ISBN or barcode). It ensures that data entry errors (like typos) are detected.
🧠 Memory Trick: Validation is Reasonable!
Think of V.A.L.I.D.A.T.I.O.N. to remember that the checks ensure the data is Reasonable, not necessarily correct.
3.2 Data Verification (7.6)
Verification checks if the data entered into the system matches the original source data. It ensures accuracy during data transfer or input.
- Visual Check: The user compares the data they entered on the screen directly against the original data source (e.g., checking a form).
- Double Entry Check: The data is entered twice, perhaps by two different people or via the same person entering it twice. The computer compares the two entries. If they match, the data is accepted.
Key Takeaway: Validation checks if the input is *possible* (e.g., is 99 a possible test score?). Verification checks if the input is *accurate* (e.g., did I type 99 when the paper said 96?).
4. Testing and Debugging (7.7 & 7.8)
Good programs must be thoroughly tested. We need to use specific types of test data to ensure the program can handle all situations.
4.1 Types of Test Data (7.7)
- Normal Data: Data that is expected, valid, and falls within the acceptable range.
Example: If the valid range is 1 to 100, normal data is 50. - Boundary Data (or Extreme Data): Data that is at the limits of the acceptable range, and the smallest/largest unacceptable values.
Example: If 1 to 100 is valid, test with 1, 100 (acceptable boundaries) and 0, 101 (unacceptable boundaries/extreme). - Abnormal Data: Data that is completely invalid and outside the expected type or range.
Example: Entering the word "potato" when expecting a number between 1 and 100.
4.2 Trace Tables (Dry Runs) (7.8)
A trace table is a crucial tool used to manually check the logic of an algorithm (a process known as a dry run).
- You create columns for every variable used in the algorithm, plus columns for any Output and User Prompts.
- You process the algorithm step-by-step, updating the variable values in the columns as they change.
- This helps you spot logical errors (bugs) in your design before you write the actual code.
Don't worry if this seems tricky at first; practice with simple loops and selection statements will make trace tables much easier!
4.3 Explaining Algorithm Purpose (7.3)
In the exam, you may be asked to explain what an algorithm does. Your answer must cover two parts:
- Stating the Purpose: Clearly define the goal (e.g., "The algorithm finds the largest value entered by the user.")
- Describing the Processes: Explain *how* it achieves that goal (e.g., "It uses a loop to take 10 inputs, comparing each input to a variable called MaxValue, updating MaxValue if the new input is larger.")
Key Takeaway: Testing requires deliberate effort using different types of data. Trace tables are your manual method for finding logic errors.