Algorithms

Sections:

Documenting/Designing Algorithms using Flowcharts and Pseudocode
Desk Checking & Debugging algorithms using Trace Tables
Standard Algorithms required by the curriculum

Textbook Chapter 9

Documenting Algorithms

Pseudocode and Flowcharts are our two main tools of documenting flow charts.

Although they are both equivalent Flowcharts are easier for non-programmers to read. They are also inherently two-dimensional, so branches (conditionals, if statements) and loops (iterations) are actually represented by a branching or looping of the flowchart.

Pseudocode flattens out the flowchart into a sequence of lines of something like code. The hardest part of the translation from flowchart to pseudocode is the choice loop structure to use, as flowcharts are more flexible in this area.

Algorithms are built out of a sequence of statements to control input and output, assign variables to results, control flow. There are three types of flow in algorithms:

Sequence - is just the idea that code runs "top-to-bottom", one statement after another.
Selection or Branching
1. Binary Selection (IF … THEN … ELSE … ENDIF)
2. Multiway Selection (CASE … OF … OTHERWISE … ENDCASE)
Iteration or Loops
1. Pre-test loop (WHILE … DO … ENDWHILE)
2. Post-test loop (REPEAT … UNTIL ... )
3. Count controlled loop (FOR … TO … NEXT)

For more details, see the Pseudocode & Flowchart resource page.

Trace Tables

AKA Desk Checks or Dry Runs.

This is a method to check an algorithms by running them by hand using test data (how to choose a suitable set of test data is discussed in the next section). If the pseudocode does not produce the expected output for the test then the trace will help you locate the error.

The idea is you track all of the variables and output in a table, working line-by-line through the code and updating the variables when they are assigned a new value.

Here is an animated trace table example from 101computing.net.

Note that their psuedocode uses a slightly different syntax from the IGCSE requirements.

number ← 3

OUTPUT number

FOR count FROM 1 TO 3 STEP 1

      number ← number + 5

      OUTPUT number

NEXT count

OUTPUT "?"

standard Algorithms

There are a number of algorithms that are common patterns that you will need / read many times. Many of these will be revisited and some new ones created using Arrays later in the unit. It is expected that you can recognize the following patterns.

Swap the content of two variables

The following is a variant of a 2003 0420 exam question:

START

  INPUT a, b

  IF a > b THEN

    t ← a

    a ← b

    b ← t

  END IF

  OUTPUT a, b

END

Run the above algorithm twice:

Firstly with the inputs 41, 38
then with inputs 32, 36.

Questions:

What does the algorithm do?
What does the if block (inside the if statement) do?
Why do we need variable t?

Exercises:

Rewrite the algorithm using a flowchart.
Rewrite & test the algorithm in Python
- Do you know a simpler/Pythonic method?

Count Numbers: count = count + 1

Input a sequence of positive numbers, when 9999 is entered, stop the input phase and calculate then print how many numbers, excluding 9999, where entered. Note: 9999 is called a terminal or sentinel value.

Exercise: produce a trace table given the input: 3, 6, 7, 9999

Exercise: Rewrite using pseudocode AND Python - test your code against your trace table

Variation: Given 10 numbers, Count the Positive/Negative/Even/Odd/Square/etc Numbers

Total Numbers: total = total + number

Input a sequence of 10 numbers. Calculate and print their total.

START

  total ← 0

  count ← 1

  WHILE count <= 10 DO

    INPUT number

    total ← total + number

    count ← count + 1

  ENDWHILE

  OUTPUT number

END

Exercise: produce a trace table given the input: 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15

Exercise: Rewrite using a flowchart AND Python -- think about your different choices for loops

Average of Numbers

Input a sequence of numbers until -1 is inputted. Calculate and print their average. This combines counting and totaling the sequence.

Exercise: produce a trace table given the input: 2, 4, 6, 8, 10, 12, 14, -1

Exercise: Rewrite using a pseudocode AND Python

Variation: Input a sequence of positive numbers, when -1 is entered, stop the input phase and calculate then print the average of the positive numbers.

Variation: The numbers are now position on a number line - calculate the average distance of the numbers from zero. (Find the average of them ignoring the sign)

Challenge: We have implemented the Mean of the inputed numbers, can you also find the median and mode?

Min / Max

Input a sequence of positive integers until -1 is inputted. Print the minimum / maximum number in the sequence.

START

  smallest ← 1000000 // A large number

  INPUT number

  WHILE number <> -1 DO

    IF number < smallest THEN

      smallest ← number

    END IF

    INPUT number

  END WHILE

  OUTPUT smallest

END

Exercises:

What are the pros & cons of initialising smallest to a large number?
The first INPUT number is called a priming read for the loop.
Trace using the input 5, 6, 5, 3, 4, -1
Rewrite using a flow chart - can you simplify the logic?

Min / Max Position

Input a sequence of positive integers until -1 is inputted. Print the minimum / maximum number and where it was in the sequence.

Exercise: Modify the pseudocode above to also store and print the position of the minimum number AND complete the same exercises for this modification.

Practice Questions - 0420 Past Papers

0420 2010 Flowchart & Tracetable Questions

Solutions and more on the Connect Archive

Other Common Algorithms Seen on Past Papers

MOD / DIV type questions
- Convert to Binary

E.g., convert the following into a flowchart and into Python. Complete is trace table for num = 19 and for num = 40

BEGIN

  INPUT num

  WHILE num > 0

    OUTPUT num MOD 2

    num ← num DIV 2

  END WHILE

END

Digit Sum

BEGIN

  INPUT num

  digitSum = 0

  WHILE num > 0

    digitSum = digitSum + (num MOD 10)

    num ← num DIV 10

  END WHILE

  OUTPUT digitSum

END

Divisibility: Write a program that uses digit sum to test if a number is divisible by 9

Write an an algorithm to

Calculate / Check a Check Digit
Convert to/from binary or hex or octal ...

Report abuse