Mini-Lesson

Problem solving & programming

This mini-lesson covers OCR 2.2 — Problem solving and programming: the techniques you write code with, the computational methods that make hard problems solvable, and the three paradigms OCR examines.

Constructs, recursion, scope and modularity
Parameter passing — by value and by reference
Computational methods — backtracking, heuristics, data mining, pipelining
Assembly language — the Little Man Computer
Object-oriented programming

Work through each screen, answer the questions as you go (some are recall, some are calculations you must actually work out) and collect ⭐ stars. Press Start when you're ready.

2.2.1 · Techniques

Constructs, modularity and scope

Three constructs express any computable algorithm: sequence, selection (IF, CASE) and iteration — definite (FOR: a known number of repeats) or indefinite (WHILE, REPEAT).

Modularity means building the program from subroutines:

a procedure performs an action and returns no value;
a function returns exactly one value.

Scope: a local variable is created when its subroutine is called and destroyed when it returns — it cannot be seen outside. A global is visible everywhere for the whole run.

Prefer locals. Any subroutine can silently modify a global, so a bug can originate anywhere in the program. Locals keep subroutines self-contained, which is what makes them independently testable and reusable.

An IDE earns its keep through: syntax highlighting and auto-complete, breakpoints and single-stepping, a watch window showing variable values as the program runs, an integrated translator, and refactoring tools. Debugging by inserting print statements is what you do when you have not learned the debugger.

2.2.1 · Parameters

Parameter passing and recursion

By value	By reference
A copy of the value is passed	The memory address is passed
Changes inside the subroutine are lost on return	Changes persist in the caller
Safe; expensive for large data	Efficient for large arrays; risks unintended side effects

A recursive subroutine calls itself. It needs a base case, a general case, and arguments that move towards the base case — or you get infinite recursion and a stack overflow.

FUNCTION factorial(n) IF n = 0 THEN RETURN 1 // base case ELSE RETURN n * factorial(n-1) // general case ENDIF ENDFUNCTION

Each call pushes a stack frame holding the return address, parameters and locals; the frames unwind in reverse as each call returns.

The trade-off: recursion is elegant for naturally recursive problems (tree traversal, quicksort, Towers of Hanoi) but uses more memory and is slower than iteration. Any recursive routine can be rewritten iteratively, using an explicit stack if necessary.

Calculate

Your turn — trace the recursion

1Using the factorial function above, what is the value of factorial(5)?

Hint: Unwind it: 5 × factorial(4), and so on down to factorial(0), which returns 1.

2.2.2 · Methods

Computational methods

OCR expects you to name and explain these:

Problem recognition — is this problem actually solvable by a computer at all, and in a usable time?
Divide and conquer — split the problem in half, solve each half, combine. Binary search and merge sort both do this.
Backtracking — explore a route; on hitting a dead end, return to the last decision point and try a different branch. This is how maze solvers, Sudoku solvers and the eight-queens problem work.
Heuristics — a rule of thumb giving a good enough answer quickly where an exact one is impractical. The estimate inside A* is a heuristic; so is nearest-neighbour for the travelling salesman.
Data mining — search very large data sets for patterns and correlations that were not anticipated.
Performance modelling — simulate a system's behaviour under load rather than building and testing it for real.
Pipelining — begin the next stage before the previous one has finished, so stages overlap and throughput rises.
Visualisation — present the data so a human can see the pattern that no summary statistic reveals.

Why heuristics are not cheating: for an intractable problem the exact algorithm is worse than useless — it may run for longer than the age of the universe. A heuristic that gets within 5% of optimal in a second is not a compromise; it is the only answer that exists.

Quick check

Computational methods

?A Sudoku solver places a digit, continues, finds a contradiction, and returns to the last cell where it had a choice to try a different digit. Which computational method is this?

2.2.3 · Assembly

The Little Man Computer

LMC is a teaching model of a von Neumann machine: 100 mailboxes (memory), one accumulator, a program counter, and this instruction set:

Instruction	Effect
INP	Read a value into the accumulator
OUT	Output the accumulator
LDA x	Load the contents of mailbox x into the accumulator
STA x	Store the accumulator into mailbox x
ADD x / SUB x	Add / subtract the contents of mailbox x
BRA x	Branch always to x
BRZ x / BRP x	Branch if the accumulator is zero / is positive
HLT / DAT	Stop / declare a data location

INP STA FIRST INP ADD FIRST SUB TEN OUT HLT FIRST DAT TEN DAT 10

Note LDA and STA carefully. LDA copies memory into the accumulator; STA copies the accumulator into memory. Getting them the wrong way round is the single commonest LMC mistake, and it destroys the trace.

Calculate

Your turn — trace the LMC program

2Trace the LMC program above with the inputs 7 and then 12. What value does OUT print?

Hint: The first input is stored in FIRST. The second stays in the accumulator, then FIRST is added to it, then 10 is subtracted.

2.2.3 · OOP

Object-oriented programming

A class is a blueprint defining attributes (data) and methods (behaviour). An object is an instance of it, created by instantiation — the constructor runs and sets the initial state.

Encapsulation — attributes are private; access is only through public getters and setters, so validation cannot be bypassed and the object can never enter an invalid state.
Inheritance — a subclass derives from a superclass, gaining its attributes and methods. It models an is-a relationship.
Polymorphism — the same call runs different code depending on the object's actual class, via method overriding.

CLASS Shape PUBLIC FUNCTION Area() ENDCLASS CLASS Circle INHERITS Shape PUBLIC FUNCTION Area() // overrides RETURN 3.14159 * r * r ENDCLASS FOR EACH s IN shapes OUTPUT s.Area() // polymorphic: the right Area() runs ENDFOR

Favour composition over inheritance. A Car has an Engine (composition); a Circle is a Shape (inheritance). Deep inheritance hierarchies are brittle — a change near the top breaks everything below it. Ask "is-a or has-a?" before you inherit.

Quick check

Encapsulation

?A BankAccount class holds balance as a private attribute, with a public Deposit() method that rejects negative amounts. What does making it private achieve?

Quick check

Parameter passing

?A subroutine is passed a large array and must sort it in place, with the caller seeing the sorted result. Which passing method is needed?

Sort it

Which method is it?

Tap the description, then tap the computational method.

↩️ Backtracking

💡 Heuristic

⛏️ Data mining

Match it

Match the OOP term

Tap an item on the left, then its partner on the right.

Meaning

Term

Recap

The big ideas to know

Techniques: sequence, selection, iteration · procedure vs function · locals over globals · IDE breakpoints and watches

Parameters: by value = copy, changes lost · by reference = address, changes persist

Recursion: base case + general case + progress towards it · stack frames · slower and hungrier than iteration

Methods: divide and conquer · backtracking · heuristics · data mining · performance modelling · pipelining · visualisation

LMC: INP, OUT, LDA, STA, ADD, SUB, BRA, BRZ, BRP, HLT, DAT — LDA loads from memory, STA stores to it

OOP: class, object, instantiation · encapsulation · inheritance (is-a) · polymorphism via overriding · favour composition

That is the whole of OCR 2.2. Press Finish to see your score.

🏆

Mini-lesson complete!

⭐⭐⭐

You've worked through Problem solving & programming for OCR A-level Computer Science (H446). 🎉

Your stars: 0 / 0

Next: test yourself in the Evaluate stage Confidence Quiz, then lock it in with Verify.

📣 Smashed it? Share your score

Challenge a mate to beat your stars, or show a parent how you got on.

→ Back to all subjects