Cambridge AS & A Level IT (9626) - Chapter 4 - Algorithms & Flowcharts - Part 2

1. Algorithm Refinement and Trace Tables

Algorithms are refined through a process of testing and debugging. A key tool for this is the trace table (also known as a dry run).

1.1 Trace Tables

• Purpose: To manually test an algorithm step-by-step, verifying its logic and identifying errors before programming. It tracks the values of variables and output at each stage of execution.

• Structure: A table with columns for:

  • Step Number: To follow the execution order.

  • Input: Any data provided to the algorithm at that step.

  • Variables: A separate column for each variable used in the algorithm to track its changing value.

  • Condition: For decision points (e.g., IF statements, loops), to evaluate if the condition is true or false.

  • Output: Any data produced by the algorithm at that step.

Example Trace Table Scenario:
An algorithm to calculate simple interest from principal, rate, and time.

ALGORITHM SimpleInterest:
1. INPUT Principal (P)
2. INPUT Rate (R)
3. INPUT Time (T)
4. Interest = (P * R * T) / 100
5. OUTPUT Interest

2. Flowcharts

Flowcharts are graphical representations of algorithms, using standard symbols to depict steps and their sequence.

2.1 Flowchart Symbols

3. Developing Algorithms (Pseudocode & Flowchart Constructs)

Algorithms are constructed using variables, constants, and control structures for input/output, processing, selection, and repetition.

3.1 Variables and Constants

• Variables: Memory locations that store data whose values can change during program execution (e.g., Score, UserName). Declared with a specific data type (e.g., Integer, String, Boolean).

• Constants: Memory locations that store data whose values remain fixed throughout program execution (e.g., PI = 3.14159, TAX_RATE = 0.05).

3.2 Input and Output Operations

• INPUT: To get data from the user or a file (e.g., INPUT UserName).

• OUTPUT / PRINT / DISPLAY: To show results to the user or write to a file (e.g., OUTPUT "Hello, " & UserName).

3.3 Assignment Statements

Used to assign a value to a variable.

• Pseudocode examples: SET Total TO 0, Count <- Count + 1, Average = Sum / Number

3.4 Arithmetic Operations

Standard mathematical operations:

• Addition: +

• Subtraction: -

• Multiplication: *

• Division: /

• Modulus (remainder): MOD (e.g., 10 \text{ MOD } 3 = 1)

• Integer Division (quotient): DIV (e.g., 10 \text{ DIV } 3 = 3)

3.5 Selection (Conditional Statements)

Allows the algorithm to make decisions and execute different blocks of code based on conditions.

• IF...THEN...ENDIF (Single Selection):

  IF Condition THEN
      Statement(s)
  ENDIF

• IF...THEN...ELSE...ENDIF (Dual Selection):

  IF Condition THEN
      Statement(s) for True
  ELSE
      Statement(s) for False
  ENDIF

• CASE OF...OTHERWISE...ENDCASE (Multiple Selection):

  CASE OF Variable
      Value1: Statement(s) for Value1
      Value2: Statement(s) for Value2
      OTHERWISE: Statement(s) for other values
  ENDCASE

3.6 Repetition (Looping Constructs)

Allows a block of code to be executed multiple times.

• FOR...TO...NEXT (Fixed Iteration Loop):
  For when the number of iterations is known in advance.

  FOR Counter FROM Start TO End [STEP StepValue]
      Statement(s)
  NEXT Counter

Example: FOR i FROM 1 TO 10 NEXT i

• WHILE...DO...ENDWHILE (Pre-condition Loop):
  The condition is checked before each iteration. The loop may not execute at all if the condition is initially false.

  WHILE Condition DO
      Statement(s)
  ENDWHILE

Example: WHILE Score < 0 OR Score > 100 DO INPUT Score ENDWHILE

• REPEAT...UNTIL (Post-condition Loop):
  The condition is checked after each iteration. The loop will always execute at least once.

  REPEAT
      Statement(s)
  UNTIL Condition

Example: REPEAT INPUT Number UNTIL Number >= 0

4. Efficiency Considerations

When designing algorithms, it's important to consider efficiency:

• Time Complexity: How quickly the algorithm runs relative to the input size (e.g., processing N items might take N steps, N^2 steps, or \log N steps). Aim for algorithms that complete in a reasonable time, especially for large datasets.

• Space Complexity: The amount of memory (storage) the algorithm requires. Efficient algorithms minimize memory usage.

• Optimisation: Choosing the most efficient control structures and operations to reduce processing time and memory consumption.