IGCSE Computer Science 0478 — 7d Standard Methods of Solution Hangman

The 44 key terms

1algorithm

A set of clear steps, in order, that solves a problem or completes a task, like a recipe or morning routine. Each step must be precise so a person or computer can follow it.

2UPPERCASE keywords

Cambridge pseudocode writes keywords like IF, FOR and WHILE in capitals and indents the lines inside each structure, so the code is easy to read.

3DECLARE Score : INTEGER

Creates a variable called Score with a stated data type. Types: INTEGER, REAL, STRING, CHAR, BOOLEAN. Pick a meaningful name.

4Total ← 0

The ← arrow stores the value on its right in the variable on its left. Total ← 0 sets Total to 0. A new assignment replaces the old value. It is not the same as = used to compare.

5INPUT and OUTPUT

INPUT stores a value from the user in a variable, e.g. INPUT Number. OUTPUT shows a message or value on screen, e.g. OUTPUT "Total is ", Total. Prompt first so users know what to enter.

6+ - * / DIV MOD

Arithmetic operators: + - * / calculate with numbers, and / gives a real result. DIV gives the whole-number quotient and MOD the remainder, so 17 DIV 5 is 3 and 17 MOD 5 is 2.

8AND, OR, NOT

Logic operators that combine or reverse conditions: AND needs both true, OR needs one true, NOT reverses a condition. Range test: Number >= 1 AND Number <= 10

9IF condition THEN ... ENDIF

Runs the indented lines between THEN and ENDIF only when the condition is TRUE. If it is FALSE, those lines are skipped. Every IF must be closed with its own ENDIF.

10ELSE

Starts the lines that run when the IF condition is FALSE. Exactly one branch runs: THEN or ELSE, never both. ELSE has no condition of its own.

11FOR Count ← 1 TO 10

Repeats the lines up to NEXT Count a fixed number of times. Count starts at 1, goes up automatically, and both the start and end values are included. STEP changes the jump.

12WHILE condition DO

A loop that tests the condition first and repeats its body while it is TRUE. The body may run zero times, and it must change the variable or the loop never ends.

13REPEAT ... UNTIL condition

A loop that runs its lines first, then checks the UNTIL condition. It stops when the condition is TRUE, so the body always runs at least once.

14FOR, WHILE, REPEAT

Use FOR when the number of repeats is known. Use WHILE (tests at the start) or REPEAT (tests at the end) when repeating depends on a condition.

15DECLARE Marks : ARRAY[1:10] OF INTEGER

Creates an array called Marks: a named list of 10 items, numbered from lower bound 1 to upper bound 10. Every item must be the same data type, here INTEGER.

16Marks[3]

Refers to one element of the array Marks by its index, here 3. You can read it or assign to it, e.g. Marks[3] ← 55. An index outside the array bounds causes an error.

17FOR Index ← 1 TO 10

A loop whose counter is the array index. Inside it, Marks[Index] picks each element in turn, so the loop visits every item from position 1 to 10 once.

18Trace table

A table that records the value of each variable at every step of an algorithm, used to check its logic by hand.

19standard method

A tried-and-tested algorithm for a common task, such as totalling, counting, max/min, average, linear search or bubble sort, that programmers reuse instead of inventing a new solution.

20Total ← Total + Value

Totalling keeps a running sum. Set Total to 0 before the loop, add each Value to Total inside the loop, then output Total after the loop. Counting adds 1 each time instead of the value.

21Total ← Total + Number

Adds each new Number to the running Total every time the loop repeats. Set Total ← 0 before the loop so the total starts from zero.

23Count ← Count + 1

Counting adds 1 to a counter each time something happens. Start the counter at 0, add 1 (not the item's value), and do it for every item or only for matches.

25IF Mark[i] >= 50 THEN Count ← Count + 1

An IF inside a loop adds 1 to Count only when an item meets the condition, so Count tallies the matching items. A total adds the item's value instead.

27IF Num > Max THEN Max ← Num

Keep the largest value seen so far in Max. Start Max with the first value, then replace it whenever a later value is larger. Starting at 0 can fail if all values are negative.

28IF Marks[Index] > Largest THEN Largest ← Marks[Index] ENDIF

Used inside a loop to compare each mark with Largest. If the mark is bigger, it replaces Largest. When the loop ends, Largest holds the biggest value in the array.

29IF Marks[Index] < Smallest THEN Smallest ← Marks[Index] ENDIF

Inside a loop, this compares each item with Smallest and replaces Smallest when a lower value is found. Start Smallest as Marks[1], not 0, so the minimum is correct.

30IF Number > Largest THEN

In a trace table, Largest only changes on rows where this test is true. If Number is equal or smaller, the Largest cell stays the same as the row above. Smallest uses < instead.

31Average ← Total / Count

The average is the total of the values divided by how many values there are. It needs both a total and a count, can be a REAL, and is not allowed when the count is zero.

33single pass

One loop visits each item once, updating the total, count, maximum and minimum together. The average is worked out after the loop ends, as Total / Count.

34linear search

Checks each item in a list in turn, from the start, until the target is found or the end of the list is reached. It works on unsorted data.

35Found ← FALSE

Sets a BOOLEAN flag to FALSE before a FOR loop. The loop sets Found to TRUE if an element equals the target. After the loop, Found shows whether the target was seen.

36WHILE Found = FALSE AND Index <= 10 DO

Keeps searching while the target has not been found AND the end of the list has not been reached, so the loop stops early as soon as Found becomes TRUE.

37IF Found = TRUE THEN OUTPUT "Found at ", Index ELSE OUTPUT "Not found" ENDIF

After the search loop, check the Found flag: if TRUE, output the position (Index) where the target was found, otherwise output a not-found message. Covers first, last and missing items.

39bubble sort

A sorting method that compares neighbouring items and swaps them if in the wrong order, repeating passes until the list is sorted. The largest value bubbles to the end each pass.

40Temp ← Marks[Index]

Saves the value of Marks[Index] in Temp so it is not lost. Marks[Index] can then be overwritten, and Temp is copied into Marks[Index + 1] to finish the swap.

41IF Marks[Index] > Marks[Index + 1] THEN

One pass: a FOR loop compares each item with its neighbour and swaps them if the first is larger, so the biggest value moves to the end.

42FOR Pass ← 1 TO n - 1

Outer loop of a bubble sort: it runs n - 1 passes. Inside it, an inner FOR loop compares neighbours and swaps them if out of order, so the whole array ends up sorted.

43UNTIL Swapped = FALSE

A BOOLEAN flag set to FALSE before each pass and to TRUE whenever a swap happens. The bubble sort stops when a full pass leaves it FALSE, meaning no swaps were needed and the data is sorted.

44bubble sort trace

Writing out the array after every pass, showing each comparison and swap, plus the Temp and Swapped values, to see how a bubble sort puts the data in order.

45test data

Chosen inputs, each with the output you expect, picked so every path (branch) through an algorithm gets tested. Compare the real result to the expected output.

46logic error

A mistake in an algorithm's steps that lets it run but gives wrong results, e.g. a total not set to 0, a loop going past the array end, or using > instead of <.

47key words

Words in a problem, like add up, how many, highest, average, find or put in order, that show which standard method to use: totalling, counting, max/min, average, search or sort.

48DECLARE, loop, OUTPUT

To solve a described problem, list the inputs, pick the standard method, then write it: DECLARE variables, set start values, loop through the data, and OUTPUT the result.

49complete the algorithm

Fill each missing line or value by asking what the standard method (total, count, max, search, sort) needs at that point: start value, loop bound, condition or closing keyword.

50dry run

Following an algorithm line by line with given data, recording each variable's value in a trace table, to find its output or purpose.