Standard methods of solution

Welcome to Standard Methods of Solution!

In Computer Science, we often face the same types of problems over and over again. Instead of "reinventing the wheel" every time, we use Standard Methods of Solution. Think of these as reliable recipes or templates that you can use to build more complex programs. Mastering these will give you a massive advantage in Paper 2!

1. Totalling and Counting

These are the two most basic building blocks of algorithms. They are often used inside loops to keep track of data as it is processed.

Totalling

Totalling is the process of keeping a running sum of numbers. You start with a variable at zero and add each new value to it.

Example: Adding up the cost of items in a shopping basket.

The Logic:
1. Initialize Total to 0.
2. Inside a loop, use: Total <- Total + NewValue

Counting

Counting is used to track how many times something happens. Instead of adding a variable value, you always add 1.

Example: Counting how many students passed an exam.

The Logic:
1. Initialize Counter to 0.
2. Inside an IF statement or loop, use: Counter <- Counter + 1

Key Takeaway: Totalling adds a variable amount (\( x \)), while counting always adds a fixed amount (\( 1 \)).

2. Finding the Average

To find the Average (specifically the arithmetic mean), you combine the two methods above. You need the total sum of the numbers and the count of how many numbers there were.

The Formula:
\( Average <- Total / Counter \)

Common Mistake: Make sure you only calculate the average after the loop has finished, or you will get a different result every time the loop runs!

3. Maximum and Minimum

These methods find the largest or smallest value in a list (array). Don't worry if this seems tricky; the secret is in how you "initialize" your variables.

Finding the Maximum

1. Set a variable Max to a very small number (or the first item in the list).
2. Compare every other number to Max.
3. If the CurrentValue > Max, then Max becomes the CurrentValue.

Finding the Minimum

1. Set a variable Min to a very large number (or the first item in the list).
2. Compare every other number to Min.
3. If the CurrentValue < Min, then Min becomes the CurrentValue.

Analogy: Imagine you are looking for the tallest student in a line. You look at the first person and say, "You're the tallest so far." You move to the next person; if they are taller, they become your new "tallest so far."

4. Linear Search

A Linear Search is used to find if a specific value exists within a list. It starts at the very beginning and looks at every item one by one until it finds a match or reaches the end.

Step-by-Step:
1. Use a Boolean flag called Found and set it to FALSE.
2. Use a loop to look at each element in the array.
3. If Array[Index] = SearchValue, set Found to TRUE.
4. After the loop, check the flag to tell the user if the item was found.

Did you know? Linear search is simple but can be slow for very large lists because it might have to check every single item!

5. Bubble Sort

The Bubble Sort is a standard way to organize a list into order (e.g., alphabetical or numerical). It is called a "bubble" sort because the largest values gradually "bubble up" to the end of the list.

How it works:
It compares adjacent (side-by-side) items. If they are in the wrong order, it swaps them. It repeats this process until no more swaps are needed.

The "Swap" Trick:
To swap two values, you need a third temporary variable. Imagine you have a glass of Orange Juice and a glass of Apple Juice and you want to swap the liquids. You need an empty Temp glass!
1. Temp <- GlassA
2. GlassA <- GlassB
3. GlassB <- Temp

Bubble Sort Logic (Pseudocode Snippet):
FOR i <- 1 TO (ArrayLength - 1)
  FOR j <- 1 TO (ArrayLength - i)
    IF MyArray[j] > MyArray[j+1] THEN
      Temp <- MyArray[j]
      MyArray[j] <- MyArray[j+1]
      MyArray[j+1] <- Temp
    ENDIF
  NEXT j
NEXT i

Key Takeaway: The Bubble Sort uses nested loops (a loop inside a loop). The inner loop handles the comparisons, while the outer loop ensures the process is repeated enough times to sort the whole list.

Quick Review Box

Note: For more information on how to test these algorithms, see the chapter on "Validation, verification and test data." To see how these variables change step-by-step, refer to the "Trace tables" chapter.