Determinism, State, and Tracing: Predicting What an Algorithm Will Do

Determinism: Same Input, Same Output

An algorithm is deterministic when it produces the same output every time it is run with the same input. Determinism is not about being “simple”; it is about being predictable. If you can trace the steps and know exactly what will happen, the procedure is deterministic.

Determinism depends on two things:

• Unambiguous steps: each instruction has only one possible interpretation.
• Controlled influences: the result depends only on the provided inputs and the defined internal values, not on outside factors like the current time or random numbers (unless those are treated as explicit inputs).

Deterministic procedure example

Procedure: “Given a number n, compute n^2 + 2.”

If the input is n = 3, the output is always 11. There is no choice point that depends on anything external, and every step is fully specified.

State: The Values That Change While Running

During execution, an algorithm typically maintains state: the current values of variables (or named storage locations) that can change over time. Even if the input is fixed, the algorithm moves through a sequence of states until it produces an output.

Continue in our app.

You can listen to the audiobook with the screen off, receive a free certificate for this course, and also have access to 5,000 other free online courses.

Or continue reading below...

Download the app

To predict what an algorithm will do, you track:

• Variables (the names you track)
• Initial state (starting values)
• State transitions (how each step updates values)

Two common tools for this are tracing tables and state diagrams.

Tracing Tables: Recording State Step by Step

A tracing table is a structured way to simulate an algorithm by hand. Each row represents a moment in time (often one step), and each column is a variable or an output.

How to build a tracing table

• List all relevant variables (state) as columns.
• Add a column for the step number (or step description).
• Write the initial values.
• Apply one step at a time, updating only what changes.
• Record the new state after each step.

Example 1: Running total

Procedure: “Given a list of numbers, compute the sum.”

Inputs: numbers = [4, 1, 3]  (a fixed list is part of the input)Step 1: total := 0Step 2: for each x in numbers: total := total + xStep 3: output total

Trace it:

This is deterministic because the list order is part of the input and every update is defined.

Example 2: Swapping and updating state

Procedure: “Given a and b, swap them, then add 10 to a.”

Inputs: a, bStep 1: temp := aStep 2: a := bStep 3: b := tempStep 4: a := a + 10Step 5: output a, b

Trace for input a = 2, b = 7:

The trace makes it hard to “lose track” of values, especially when variables are reassigned.

State Diagrams: Visualizing Transitions

A state diagram represents execution as movement between states. Each state is a snapshot of variable values; each arrow is a step that transforms one state into the next.

Example: Countdown with a counter

Input: nStep 1: count := nStep 2: repeat: count := count - 1 until count = 0Step 3: output "done"

For n = 3, the state transitions for count look like:

(count=3) --decrement--> (count=2) --decrement--> (count=1) --decrement--> (count=0) --stop--> output

State diagrams are especially helpful when you want to reason about “where you can be” during execution and what transitions are allowed.

Where Determinism Breaks: External Factors and Hidden Inputs

Some processes appear deterministic until you notice they depend on information that is not part of the stated input. When that happens, the same “input” can lead to different outputs because there are hidden inputs.

Common sources of non-determinism (unless controlled)

• Time: “Use the current time” changes between runs.
• Randomness: “Pick a random number” varies unless the random source is fixed.
• External environment: sensor readings, network responses, file contents that may change.
• Unspecified choice: “Pick any item” without a rule for which one.

Example: Time-dependent behavior

Procedure: “If it is morning, output A; otherwise output B.”

If the only declared input is “none,” then the same input can produce different outputs depending on the time. To restore determinism, you can make time an explicit input:

Input: hour (0..23)If hour < 12 output A else output B

Now the output is determined by the input hour.

Example: Randomness as a hidden input

Procedure: “Pick a random number from 1 to 6.”

This is not deterministic if the only declared input is “none.” To make it deterministic for tracing and testing, you can treat the random source as an input:

Input: roll_value (an integer 1..6)Output roll_value

Or, if you want a procedure that generates a value but remains reproducible, you can use a fixed seed as an explicit input (conceptually):

Input: seedUse seed to generate a reproducible sequenceOutput the next value

The key idea: determinism is about whether the algorithm’s behavior is fully determined by its stated inputs and rules.

Tracing to Verify Determinism

Tracing is not only for computing outputs; it is also a way to audit an algorithm for determinism. If, while tracing, you reach a step where you cannot uniquely decide the next state, you have found ambiguity or a hidden input.

Checklist while tracing

• Do all variables have defined values before they are used?
• Does every step specify exactly what to do (no “somehow,” “as needed,” “choose”)?
• When selecting among multiple options, is the tie-breaking rule explicit?
• Are any external factors influencing the result without being listed as inputs?

Drills: Find the Ambiguity, Restore Predictability

For each drill: (1) identify the step that breaks determinism, (2) explain why tracing cannot proceed uniquely, (3) rewrite the step(s) to make the procedure deterministic.

Drill 1: Unspecified choice

Input: list of namesStep 1: Choose a name from the listStep 2: Output the chosen name

Task: Rewrite Step 1 so that the same list always produces the same chosen name.

Drill 2: Tie without a rule

Input: numbersStep 1: Find the largest numberStep 2: Output its position in the list

Task: What if the largest number appears multiple times? Add a rule and update the steps so the output position is uniquely determined.

Drill 3: Hidden input (time)

Input: temperatureStep 1: If it is weekend, subtract 2 from temperatureStep 2: Output temperature

Task: Make the “weekend” condition deterministic by changing the inputs and/or steps.

Drill 4: Randomness

Input: user_idStep 1: Generate a random discount between 5 and 25Step 2: Output the discount

Task: Propose a deterministic alternative that still varies by user, and write the revised steps (hint: derive the discount from the input using a fully specified rule).

Drill 5: Undefined variable (state not initialized)

Input: nStep 1: total := total + nStep 2: Output total

Task: Explain why tracing fails at Step 1 and fix the procedure by defining the initial state.

Drill 6: Ambiguous update

Input: scoreStep 1: If score is high, add a bonusStep 2: Output score

Task: Replace “high” and “a bonus” with precise, testable rules so that the state transition is uniquely determined.

Drill 7: Trace and detect the break

Procedure:

Input: items (a list)Step 1: best := first item in itemsStep 2: For each item in items: if item is better than best, best := itemStep 3: Output best

Task: This looks deterministic, but it may not be. Identify what must be specified about “better than” to ensure determinism, especially when two items are equally good. Write a rule that resolves ties and then trace a small example where a tie occurs.

Drill 8: Build a tracing table

Trace the following procedure using a table with columns step, i, value, result:

Input: nStep 1: result := 1Step 2: i := 1Step 3: Repeat while i ≤ n: result := result * 2; i := i + 1Step 4: Output result

Task: Fill the table for n = 4. Then answer: which variables are state, and which step(s) cause state transitions?