Algorithms and pseudocode
| English | Chinese | Pinyin |
|---|---|---|
| algorithm | 算法 | suàn fǎ |
| sequence | 顺序 | shùn xù |
| deterministic | 确定性 | què dìng xìng |
| identifier table | 标识符表 | biāo shí fú biǎo |
| variable | 变量 | biàn liàng |
| data type | 数据类型 | shù jù lèi xíng |
| pseudocode | 伪代码 | wěi dài mǎ |
| selection | 选择 | xuǎn zé |
| iteration | 迭代 | dié dài |
| loop | 循环 | xún huán |
| assignment | 赋值 | fù zhí |
| count-controlled loop | 计数循环 | jì shù xún huán |
| pre-condition loop | 前测循环 | qián cè xún huán |
| post-condition loop | 后测循环 | hòu cè xún huán |
| flowchart | 流程图 | liú chéng tú |
| stepwise refinement | 逐步求精 | zhú bù qiú jīng |
The most expensive hyphen in history
- On 22 July 1962 the Mariner 1 rocket, bound for Venus, was blown up 293 seconds after launch.
- The cause was one missing bar over a symbol in the guidance equations. The computer followed the written steps exactly, and the written steps were wrong.
- A computer never fills in what you meant. Every step you give it must have exactly one meaning.
- That is why this lesson is about writing steps a machine can follow: algorithms 算法.
What an algorithm is
- An algorithm is a solution to a problem expressed as a sequence of defined steps.
- Each step is unambiguous (one meaning), deterministic 确定性 (same input → same output), finite (the steps end) and effective (each step can actually be done).
- It says what to do, independent of any programming language, and every one follows input → process → output.
Every algorithm has the same shape: input, process, output
An algorithm is "deterministic". This means:
Deterministic = same input → same output every time. (Finite = the steps end; unambiguous = one meaning per step.)
Worked example: the identifier table
- Before writing code, list every piece of data in an identifier table 标识符表: its variable 变量 name, its data type 数据类型 and a description.
- A shop's stock program stores
"Fruit",20/02/2025,12.67andTRUE. The exam asks for a name and a type for each. Category : STRING(a category of stock),DateSold : DATE(when it was sold),ItemCost : REAL(the cost),InStock : BOOLEAN(is it in stock?).- One mark per row for the name and the type, so write the type exactly as the pseudocode guide does:
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
An identifier table names every piece of data before you write code
In an identifier table, the data type for a value such as 12.67 (a cost) is ____.
A number with a decimal part is a REAL. INTEGER is for whole numbers, STRING for text, BOOLEAN for TRUE/FALSE and DATE for a date.
The three constructs
- Sequence 顺序: steps run one after another. Selection 选择: a condition chooses which steps run (
IF … THEN … ELSE … ENDIF, orCASE OF … ENDCASEfor many options). Iteration 迭代: a block repeats (a loop 循环). - Assignment 赋值 stores a value with an arrow,
Total ← Total + Value;=is for comparison.DIVis whole-number division andMODthe remainder, so17 MOD 5 = 2.
INPUT Age # sequence
IF Age >= 18 THEN # selection
OUTPUT "Adult"
ELSE
OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10 # iteration
OUTPUT Count
NEXT Count
The three building blocks of any algorithm
Selection: follow the IF / ELSE branches
Drag the score and watch which branch runs. Selection tests each condition in turn and takes the FIRST one that is true — that is how IF … ELSE IF … ELSE works.
Match each of the three programming constructs to what it does.
Every algorithm is built from just three constructs — sequence, selection and iteration.
In this pseudocode, which symbol means assignment (store a value)?
Assignment uses ← (e.g. x ← 5); = is reserved for comparison.
What is the value of 17 MOD 5?
MOD gives the remainder: $17 = 3 \times 5 + 2$, so 17 MOD 5 = 2. (17 DIV 5 = 3.)
Which loop?
FOR … NEXTwhen you know how many times: a count-controlled loop 计数循环.WHILE … ENDWHILEtests the condition before each pass, so the body may run zero times: a pre-condition loop 前测循环.REPEAT … UNTILtests after each pass, so the body always runs at least once: a post-condition loop 后测循环. Validating an input is the classic case.- A "describe the iteration construct" answer names the loop, says where the condition is tested, and gives the consequence.
A WHILE loop tests before the body runs; a REPEAT … UNTIL loop tests after it
How does a WHILE loop differ from a REPEAT...UNTIL loop?
WHILE checks first (can run 0 times); REPEAT...UNTIL checks after, so it always runs at least once.
A FOR loop is count-controlled (it repeats a fixed number of times), while a WHILE loop is condition-controlled (it repeats until a condition changes).
Use FOR when you know how many passes; use WHILE/REPEAT when you loop until something becomes true.
Worked example: from words to pseudocode
- Task: input 100 integer values, add up only the positive ones, and output the total.
- Plan the data first:
Count,TotalandNextNumber, allINTEGER. Then the three constructs do the rest.
DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
INPUT NextNumber
IF NextNumber > 0 THEN
Total <- Total + NextNumber
ENDIF
NEXT Count
OUTPUT Total
- The follow-up asks you to identify the constructs: iteration (the
FORloop repeats the input 100 times), selection (theIFdecides whether a value is added) and sequence (the statements run in order).
Spotting constructs in an extract
- A favourite question shows five pseudocode extracts and asks you to tick which of assignment, selection, iteration each one uses.
Result ← CalculateTotal()is an assignment.WHILE IsClosedis iteration.REPEAT … INPUT Value … UNTIL Sales[4] > Valueis iteration and assignment (INPUTstores a value).IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIFis selection and assignment.CASE OF Optionis selection.- Look at every line of the extract, not only the first one. A row may need two ticks.
Which constructs does this extract use? REPEAT … INPUT Value … UNTIL Total > 100. Select all that apply.
REPEAT … UNTIL is iteration, and INPUT Value stores a value, which counts as assignment. There is no IF or CASE, so no selection — the UNTIL condition controls the loop, it does not choose between branches.
Flowcharts
- A flowchart 流程图 documents the same algorithm as a picture. Ovals are
STARTandEND, rectangles are processes, parallelograms areINPUT/OUTPUT, and a diamond is a decision. - A diamond is where selection happens, and a flow line that goes back up the chart is a loop.
- The exam asks both ways: pseudocode from a flowchart, and a flowchart from pseudocode or structured English. Every symbol you draw should map to one line of pseudocode.
Each flowchart symbol maps to one kind of pseudocode statement
In a flowchart, what does a diamond represent?
Diamonds are where selection happens, and a diamond whose flow line goes back up the chart is a loop test. Rectangles are processes, parallelograms input/output, ovals START and END.
Worked example: the guessing game
- The program picks a random integer from 1 to 100, then asks for guesses until the user gets it. The user must guess at least once, so the loop is a
REPEAT … UNTIL.
DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
INPUT Guess
IF Guess < Target THEN
OUTPUT "Too low"
ELSE
IF Guess > Target THEN
OUTPUT "Too high"
ENDIF
ENDIF
UNTIL Guess = Target
OUTPUT "Correct"
- Follow the flowchart: one decision diamond for the loop test, two for the hints, and every flow line ends up back at
INPUT Guessor atEND.
The guessing game as a flowchart: the loop returns to the input until the guess matches
Why is REPEAT … UNTIL the right loop for the guessing game?
A post-condition loop always runs its body once before testing, which matches a game that needs at least one guess. A WHILE loop would need a guess before the loop just to have something to test.
Stepwise refinement
- Stepwise refinement 逐步求精 means starting from an outline and expanding each step into more detailed steps, again and again, until every step can be written directly as pseudocode.
- "Process an order" → "get the items", "calculate the total", "take payment" → "calculate the total" becomes "for each item, add price × quantity; apply any discount".
- Each level is a refinement of the one above, and the finished levels together are the design. "Describe stepwise refinement" wants the outline, the expansion and the stopping rule.
Refine each step until it can be coded directly
Put the stages of stepwise refinement in order.
Outline first, then refine level by level; you stop when a step is one line of pseudocode.
Logic statements
- Parts of a solution are defined by logic statements: conditions built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. - A valid mark:
Mark >= 0 AND Mark <= 100. A discount applies if the customer is a member or spends over 50:IsMember OR Total > 50. NOT (Mark < 40)says the same thing asMark >= 40. Write the statement, then test it with a value on each side of the boundary.
Comparisons joined by AND, OR and NOT build the conditions an algorithm needs
NOT (Mark < 40) is true for exactly the same values of Mark as Mark >= 40.
Negating "less than 40" gives "40 or more". Test the boundary: Mark = 40 makes Mark < 40 false, so NOT of it is true, and 40 >= 40 is also true.
Marks that slip away
←assigns and=compares.IF Total = 0is a test;Total = 0on its own line earns nothing.- Every construct closes:
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. A missing closer breaks the structure mark. - Declare before you use, and initialise a running total to
0. WHILEmay never run,REPEATalways runs once. Choose the loop that matches the task, and say why if asked.
You've got it
- an algorithm's steps are unambiguous, deterministic, finite, effective; plan the data in an identifier table
- three constructs: sequence, selection (
IF/CASE), iteration (FOR/WHILE/REPEAT);WHILEtests before,REPEATafter - a flowchart and pseudocode describe the same algorithm; stepwise refinement expands an outline until it can be coded
- conditions are logic statements: comparisons joined with
AND,OR,NOT