Two Views of the Same Process
Suppose we want to add the integers from \(1\) through \(4\).
One pseudocode representation is:
total = 0
FOR i = 1 TO 4
total = total + i
END FORA trace table shows what happens as the algorithm runs:
| Step | \(i\) | total |
|---|---|---|
| start | — | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 3 | 6 |
| 4 | 4 | 10 |
The pseudocode describes the rule. The table records the evolving state.
\[ \boxed{ \text{pseudocode describes execution;} \quad \text{trace tables record execution} } \]Why Use Tables?
Tables organize related information into rows and columns.
In computational thinking, a table can represent:
- input-output pairs,
- successive states of an algorithm,
- condition combinations,
- loop counters and accumulators,
- test cases and expected results.
A table is especially useful when the same variables must be observed across many steps.
What Is Pseudocode?
Pseudocode is a structured way to describe an algorithm using plain language and programming-like notation without requiring the exact syntax of a particular programming language.
For example:
INPUT x
y = 2 * x + 3
OUTPUT yThe same idea could later be implemented in Python, JavaScript, C++, or another language.
Pseudocode focuses on the algorithm rather than language-specific punctuation.
Common Pseudocode Conventions
There is no single universal pseudocode language, but several conventions are widely useful.
INPUT
Receive a value or data structure.
OUTPUT / RETURN
Produce or return a result.
IF / ELSE
Choose among branches.
FOR / WHILE
Repeat operations.
Assignment may be written in several ways:
\[ x\leftarrow x+1 \]or in pseudocode:
x = x + 1In this context, the statement means “replace the current value of \(x\) with the old value plus \(1\).”
Representing Sequential Steps
Straight-line algorithms execute steps in order.
Example
Compute
\[ y=3x-5. \]INPUT x
y = 3 * x
y = y - 5
OUTPUT yEach line changes the current state or produces an output.
The order matters:
\[ 3x-5 \neq 3(x-5). \]Representing Decisions
Pseudocode can make branching structure explicit.
Example: Sign Classification
IF x > 0
OUTPUT "positive"
ELSE IF x < 0
OUTPUT "negative"
ELSE
OUTPUT "zero"
END IFIndentation shows which steps belong to each branch.
Clear indentation is not merely cosmetic; it reveals the algorithm's logical structure.
Representing Repetition
Fixed-Count Loop
FOR i = 1 TO 5
OUTPUT i
END FORCondition-Controlled Loop
WHILE x > 10
x = x / 2
END WHILEThe first states the number or range of repetitions directly.
The second repeats until the condition becomes false.
Named Procedures and Functions
A reusable algorithm can be given a name.
Example
SQUARE(x)
RETURN x * x
ENDThen
SQUARE(5)returns
\[ 25. \]Named procedures make it possible to build larger algorithms from smaller ones.
Trace Tables
A trace table records the values of selected variables as an algorithm executes.
The table may include:
- iteration number,
- input values,
- condition results,
- temporary variables,
- accumulators,
- output values.
Dry Running an Algorithm
A dry run means executing an algorithm manually with chosen inputs.
Suppose:
x = 3
y = 2 * x
x = x + 4
y = y + xTrace it carefully:
| After step | \(x\) | \(y\) |
|---|---|---|
| start | 3 | — |
| \(y=2x\) | 3 | 6 |
| \(x=x+4\) | 7 | 6 |
| \(y=y+x\) | 7 | 13 |
The final state is
\[ \boxed{(x,y)=(7,13)}. \]Dry runs help find logic errors before an algorithm is implemented.
Condition and Decision Tables
Tables are also useful when several conditions interact.
Suppose access requires both a valid password and an active account.
| Password valid? | Account active? | Grant access? |
|---|---|---|
| False | False | No |
| False | True | No |
| True | False | No |
| True | True | Yes |
This table is a practical version of the logical rule
\[ \boxed{ P\land A }. \]Decision tables make it easier to see whether every case has been considered.
Tracing Recursive Procedures
Recursive procedures are often easier to understand when calls and returns are organized in a table.
For factorial:
\[ n!= \begin{cases} 1,&n=0,\\ n(n-1)!,&n>0, \end{cases} \]a trace for \(3!\) can be recorded as:
| Call | Waiting operation | Returned value |
|---|---|---|
| \(\operatorname{fact}(3)\) | \(3\cdot\operatorname{fact}(2)\) | 6 |
| \(\operatorname{fact}(2)\) | \(2\cdot\operatorname{fact}(1)\) | 2 |
| \(\operatorname{fact}(1)\) | \(1\cdot\operatorname{fact}(0)\) | 1 |
| \(\operatorname{fact}(0)\) | base case | 1 |
The table separates the downward calls from the values that eventually return.
Translating among Representations
The same process can appear in many forms.
Natural Language
“Start at \(1\), double the value three times, then report the result.”
Pseudocode
x = 1
REPEAT 3 TIMES
x = 2 * x
END REPEAT
OUTPUT xTrace Table
| Step | \(x\) |
|---|---|
| start | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
Sequence
\[ 1,\ 2,\ 4,\ 8. \]Recursive Rule
\[ a_0=1, \qquad a_{n+1}=2a_n. \]These are different representations of the same repeated structure.
Writing Good Pseudocode
Good pseudocode should be:
- clear — each action is understandable,
- structured — indentation reveals branches and loops,
- consistent — similar actions use similar notation,
- precise — conditions and updates are unambiguous,
- language-independent — unnecessary syntax details are avoided.
Compare:
Poor: “Keep doing stuff until the number looks small.”
Better:
WHILE x >= 10
x = x / 10
END WHILEThe second version can be traced, tested, and implemented.
Practical Applications
Algorithm Design
Pseudocode lets a designer work out logic before worrying about programming syntax.
Debugging
Trace tables reveal exactly where variable values stop matching expectations.
Mathematics
Tables help trace sequences, iterative approximations, recurrence relations, and row-by-row procedures.
Education
Pseudocode exposes the structure of an algorithm without requiring students to learn a full programming language first.
Communication
A table or pseudocode block can make a process easier for another person to review than a long paragraph of prose.
Worked Examples
Example 1: Formula to Pseudocode
Translate
\[ y=4x+1 \]into pseudocode.
INPUT x
y = 4 * x + 1
OUTPUT yExample 2: Trace a Sequence of Assignments
x = 2
y = x + 3
x = y * 2| After step | \(x\) | \(y\) |
|---|---|---|
| \(x=2\) | 2 | — |
| \(y=x+3\) | 2 | 5 |
| \(x=2y\) | 10 | 5 |
Final state:
\[ \boxed{(x,y)=(10,5)}. \]Example 3: Trace a Loop
total = 1
FOR i = 1 TO 3
total = total * 2
END FOR| Iteration | \(i\) | total |
|---|---|---|
| start | — | 1 |
| 1 | 1 | 2 |
| 2 | 2 | 4 |
| 3 | 3 | 8 |
Output:
\[ \boxed8. \]Example 4: Trace a Branch
x = -4
IF x >= 0
y = x
ELSE
y = -x
END IFSince
\[ -4\geq0 \]is false, the else branch runs:
\[ y=-(-4)=4. \] \[ \boxed{y=4} \]Example 5: Decision Table
A user receives free shipping if the order is at least \(\$50\) or the user is a premium member.
| Order ≥ \$50? | Premium? | Free shipping? |
|---|---|---|
| No | No | No |
| No | Yes | Yes |
| Yes | No | Yes |
| Yes | Yes | Yes |
The logical rule is
\[ \boxed{O\lor P}. \]Example 6: Pseudocode to Mathematical Rule
IF x > 0
RETURN x^2
ELSE
RETURN 0
END IFThe equivalent piecewise function is
\[ \boxed{ f(x)= \begin{cases} x^2,&x>0,\\ 0,&x\leq0. \end{cases} } \]Common Errors
1. Writing Programming Syntax Instead of Algorithmic Structure
Pseudocode should emphasize the process, not unnecessary language-specific details.
2. Failing to Update a Trace Table after Every Relevant Step
A skipped state can hide the exact point where an error occurs.
3. Treating Assignment as Ordinary Equality
In
x = x + 1the left side receives a new value. This is not the algebraic equation \(x=x+1\).
4. Losing Track of Variable Values after Reassignment
A trace table should always use the most recent state.
5. Using Poor Indentation
Branches and loops become ambiguous when their bodies are not visually grouped.
6. Recording Only the Final Answer
A trace table is useful precisely because it records intermediate states, not just the final output.
Practice
Trace Assignments
x = 4
y = x + 2
x = y - 1What is the final state?
Check Answer
\[ y=6, \] \[ x=5. \] \[ \boxed{(x,y)=(5,6)}. \]Trace a Loop
total = 0
FOR i = 1 TO 3
total = total + 2
END FORCheck Answer
The totals are
\[ 0,\ 2,\ 4,\ 6. \]Final output:
\[ \boxed6. \]Translate to Pseudocode
Write pseudocode for: “Input \(x\). If \(x<0\), output \(-x\); otherwise output \(x\).”
Check Answer
INPUT x
IF x < 0
OUTPUT -x
ELSE
OUTPUT x
END IFChoose the Better Representation
Which representation is usually better for seeing how a variable changes across ten loop iterations: pseudocode alone or a trace table?
Check Answer
\[ \boxed{\text{trace table}} \]because it records the state at each iteration.
Decision Table
If a rule requires both condition \(P\) and condition \(Q\), for which truth combination should the output be true?
Check Answer
Only when both are true:
\[ \boxed{P=\text{true},\ Q=\text{true}}. \]The Deeper Idea
Pseudocode and tables are complementary representations.
\[ \boxed{ \text{pseudocode} \to \text{rules of transformation} } \] \[ \boxed{ \text{trace table} \to \text{states produced by transformation} } \]This connects directly to earlier ideas:
- algorithms describe processes,
- variables store state,
- iteration produces a sequence of states,
- branching chooses among possible transitions,
- tables organize those transitions so they can be inspected.
A trace table is therefore not merely bookkeeping.
It is a representation of execution.
And pseudocode is not merely simplified code.
It is a representation of algorithmic structure.
Summary
- Tables organize related values, cases, and algorithm states.
- Pseudocode describes algorithms without requiring the exact syntax of a specific programming language.
- Common pseudocode structures include input, output, assignment, branching, loops, and named procedures.
- Indentation makes logical structure visible.
- A trace table records variable values as an algorithm executes.
- A dry run manually executes an algorithm using selected input values.
- Decision tables organize combinations of conditions and resulting actions.
- Recursive procedures can be traced by recording calls, waiting operations, and return values.
- The same algorithm can be represented in natural language, pseudocode, tables, formulas, sequences, flowcharts, or program code.
- Good pseudocode is clear, structured, consistent, precise, and largely language-independent.
- Trace tables are especially useful for finding logic errors and following changing state.
Pseudocode tells us what the algorithm says to do. Tables let us watch what the algorithm actually does to its data. Used together, they provide a powerful bridge between mathematical reasoning, algorithm design, and later computer programming.
Algorithms and Computational Thinking
- Previous: Introductory Recursion
- Algorithms and Computational Thinking — return to the lesson directory.