Use logic statements to define parts of an algorithm solution

9.2 Algorithms – Using Logic Statements to Define Parts of an Algorithm

Learning Objective

By the end of this lesson you will be able to:

• Express the input, processing and output sections of an algorithm using logical statements (AND, OR, NOT, IF‑THEN, IFF, CASE).
• Write clear pre‑conditions and post‑conditions that remove ambiguity.
• Refine a high‑level description into detailed pseudocode, identify loop invariants and evaluate correctness and efficiency (AO2/AO3).
• Relate algorithmic ideas to the broader Cambridge AS & A‑Level Computer Science syllabus (information representation, hardware, networking, security, databases, etc.).

Why Logic Matters in Algorithms

• Logic provides a precise language for decisions and repetitions.
• It removes ambiguity – essential for implementation, testing and exam marking.
• Logical expressions map directly onto the three control structures required by the Cambridge specification:

  • IF … THEN … [ELSE …]
  • CASE … OF … END CASE
  • WHILE … DO … END WHILE or REPEAT … UNTIL …

Logical Operators in Cambridge Pseudocode

Three‑Part Structure of an Algorithm

1. Input Section

   • List every datum required.
   • State any pre‑conditions using logical operators.
   • Example: PRE‑CONDITION: n > 0

2. Processing Section

   • Control flow is expressed with IF … THEN … [ELSE …], CASE … OF … END CASE or loops.
   • Combine conditions with AND, OR and NOT as required.
   • Identify a loop invariant – a condition that remains true each iteration.

3. Output Section

   • State the post‑condition that must hold when the algorithm terminates.
   • Example: POST‑CONDITION: f = n! ∧ f > 0

Step‑wise Refinement (Example – Euclidean GCD)

Find the greatest common divisor of two positive integers a and b.

1. Check that a > 0 AND b > 0.
2. REPEAT
temp ← b
b ← a MOD b
a ← temp
UNTIL b = 0
3. OUTPUT a

INPUT a, b
IF NOT (a > 0 AND b > 0) THEN
OUTPUT "Invalid input"
STOP
END IF
WHILE b ≠ 0 DO
temp ← b
b ← a MOD b
a ← temp
END WHILE
OUTPUT a          // a now holds GCD

Algorithm Analysis Box (AO2 & AO3)

Decomposition & Use of Sub‑Procedures

Abstraction is encouraged. The GCD algorithm can be split into two reusable procedures:

PROCEDURE MODULUS(x, y) RETURNS r
r ← x MOD y
RETURN r
END PROCEDURE
PROCEDURE SWAP(x, y) RETURNS (x', y')
x' ← y
y' ← x
RETURN (x', y')
END PROCEDURE

The main algorithm then calls these procedures, which can be shown in a simple structure chart.

CASE Construct Example – Triangle Type

INPUT a, b, c
IF a + b ≤ c OR a + c ≤ b OR b + c ≤ a THEN
OUTPUT "Not a triangle"
STOP
END IF
CASE
WHEN a = b AND b = c THEN
OUTPUT "Equilateral"
WHEN a = b OR b = c OR a = c THEN
OUTPUT "Isosceles"
OTHERWISE
OUTPUT "Scalene"
END CASE

Worked Example – Leap‑Year Test (Using Logical Statements)

INPUT y
IF y ≤ 0 THEN
OUTPUT "Invalid year"
STOP
END IF
/* Leap year rule:
Leap ↔ (y MOD 4 = 0) AND ((y MOD 100 ≠ 0) OR (y MOD 400 = 0))
*/
IF (y MOD 4 = 0) AND ((y MOD 100 ≠ 0) OR (y MOD 400 = 0)) THEN
OUTPUT "Leap year"
ELSE
OUTPUT "Common year"
END IF

Formal logical expression

\[

\text{Leap} \leftrightarrow (y \bmod 4 = 0) \;\land\; \bigl[(y \bmod 100 \neq 0) \;\lor\; (y \bmod 400 = 0)\bigr]

\]

Linking Algorithmic Logic to the Rest of the Cambridge Syllabus

1 Information Representation

Mini‑activity: Convert 101101₂ to decimal, then to hexadecimal, and interpret it as a signed two’s‑complement integer.

2 Communication (Networking)

3 Hardware

• Von Neumann architecture – CPU, main memory, I/O, bus system.
• CPU components: ALU, control unit, registers (PC, IR, ACC, MAR, MDR).
• Fetch‑execute cycle – illustrated with a simple diagram (fetch, decode, execute, store).
• Interrupts – hardware vs software, priority handling.

4 Processor Fundamentals

5 System Software

6 Security, Privacy & Data Integrity

• Confidentiality – encryption, passwords, access control.
• Integrity – checksums, hash functions, validation of input (range checks, type checks).
• Authentication – passwords, biometrics, two‑factor.
• Data protection legislation – GDPR basics, why it matters for software design.

7 Ethics & Ownership

Case‑study prompt (exam style): A school wants to develop a mobile app. Should they use an open‑source library (GPL) or a commercial SDK (proprietary)? Discuss licensing implications, professional codes of conduct and the impact on future maintenance.

8 Databases

9 Data Types & Structures

• Primitive types: integer, real, Boolean, character, string.
• Composite types:

  • Arrays – fixed size, index range, example of iterating with FOR i ← 1 TO n DO … END FOR.
  • Records (structures) – grouping related fields; example of a Student record.
  • Files – sequential and random access; basic operations OPEN, READ, WRITE, CLOSE.

• Abstract Data Types (ADTs) – stack, queue, list; emphasise the need to define operations (push, pop, enqueue, dequeue).

Worked Example – Using an Array (Maximum of a List)

PROCEDURE MAXIMUM(arr[1..n]) RETURNS max
max ← arr[1]
FOR i ← 2 TO n DO
IF arr[i] > max THEN
max ← arr[i]
END IF
END FOR
RETURN max
END PROCEDURE

Practice Exercise – Perfect‑Square Test

Task: Write a complete algorithm that determines whether a given integer n is a perfect square. Use logical statements for the input, processing (including a CASE to report “Yes” or “No”), and output sections. Include a pre‑condition and a post‑condition.

Guidelines

1. Input: n (integer).
2. Pre‑condition: n ≥ 0.
3. Processing: Compute root ← FLOOR(√n) (you may use a loop that repeatedly increments i until i*i > n).
4. CASE construct:

   CASE
   WHEN root * root = n THEN OUTPUT "Yes"
   OTHERWISE               OUTPUT "No"
   END CASE
   

5. Post‑condition: (output = "Yes") ↔ (∃k ∈ ℕ, k² = n).

Sample Solution (Cambridge style)

INPUT n
PRE‑CONDITION: n ≥ 0
/* Find integer square root */
root ← 0
WHILE (root + 1) * (root + 1) ≤ n DO
root ← root + 1
END WHILE
CASE
WHEN root * root = n THEN
OUTPUT "Yes"
OTHERWISE
OUTPUT "No"
END CASE
POST‑CONDITION: (output = "Yes") ↔ (∃k ∈ ℕ, k² = n)

Summary Checklist (AO1)

• Identify all required inputs and express any pre‑conditions with AND, OR, NOT.
• Translate decision points into IF … THEN … [ELSE …] or CASE … OF … END CASE using the correct Cambridge symbols.
• Use WHILE … DO … END WHILE or REPEAT … UNTIL … with a clear logical termination condition; state a loop invariant if asked.
• State a post‑condition that describes the expected output in logical form.
• Optionally add a brief correctness proof, loop invariant, and time‑/space‑complexity (AO2/AO3).
• Consider decomposition into sub‑procedures where it improves readability or re‑use.
• Recall related syllabus topics (representation, hardware, networking, security, databases, data structures) – they may appear in integrated questions.