Expressing Algorithms Clearly - Learning Module

Loading content...

0/276

Dry Running an Algorithm Step by Step

Becoming a Human Computer

Imagine you've written what you believe is a correct algorithm. You're confident in the logic, the pseudocode looks clean, and you're ready to implement. But how do you know it's correct?

You could implement it, run test cases, and debug failures. But this approach is slow, frustrating, and often reveals problems after you've invested significant coding time. There's a better way.

Dry running is the technique of manually executing your algorithm step by step, tracking variable changes and control flow exactly as a computer would—but using your brain, a pen, and paper instead of a CPU and memory. It's like being a human interpreter for your own code.

This technique is not optional. It's the most reliable way to verify algorithm correctness before you write a single line of implementation code.

What You Will Learn

By the end of this page, you will master the art of dry running. You'll learn how to set up trace tables, track variable states through iterations, verify loop invariants, catch off-by-one errors, and develop the intuition that comes from deeply understanding how algorithms execute.

What Is Dry Running?

Dry running (also called hand tracing, desk checking, or walkthrough) is the process of manually simulating algorithm execution on paper or a whiteboard. You:

Choose a specific input (test case)
Execute each statement in order, exactly as a computer would
Track the values of all variables after each step
Follow branches and loops precisely based on current values
Verify that the final output matches your expectation

The term "dry run" comes from the idea of running through something without the actual execution—like a rehearsal before a performance, or a fire drill without a real fire.

Why Dry Running Is Essential

•Catches logic errors before coding — You find bugs in minutes on paper rather than hours debugging compiled code
•Reveals off-by-one errors — The most common algorithmic mistake becomes visible when you trace exact indices
•Tests edge cases cheaply — You can trace unusual inputs without writing test infrastructure
•Builds deep understanding — You don't just believe the algorithm works; you know because you've watched it work
•Improves explanation skills — After dry running, you can explain the algorithm's behavior step-by-step in interviews
•Develops intuition — Repeated dry runs build pattern recognition for common algorithmic behaviors

The Master's Secret

Expert programmers don't skip dry running—they've just internalized it. When a senior engineer glances at code and says 'there's an off-by-one error in the loop termination,' they're doing a rapid mental dry run. The skill becomes faster with practice, but never obsolete.

Setting Up a Trace Table

The most reliable dry running technique is the trace table (also called a state table or variable trace). A trace table systematically records the value of every variable after each step of execution.

How to construct a trace table:

Columns — Create one column for each variable in the algorithm, plus a 'Step' or 'Line' column, and optionally an 'Action/Notes' column
Rows — Each row represents the state after executing one step (statement, loop iteration, or function call)
Initial row — Record the initial values before the first statement executes
Update on change — When a variable changes, record its new value; if unchanged, either repeat the previous value or use a dash to indicate 'unchanged'

Example: Tracing a simple maximum-finding algorithm

Let's trace the FindMaximum algorithm with input [3, 7, 2, 9, 4]:

Trace Table for FindMaximum([3, 7, 2, 9, 4])
Step	i	array[i]	max	array[i] > max?	Action
Init			3		max ← array[0] = 3
1	1	7	7	Yes (7 > 3)	max ← 7
2	2	2	7	No (2 ≤ 7)	No change
3	3	9	9	Yes (9 > 7)	max ← 9
4	4	4	9	No (4 ≤ 9)	No change
End			9		RETURN 9 ✓

Reading the trace table:

We start with max = 3 (first element)
At i=1, we find 7 > 3, so max becomes 7
At i=2, 2 ≤ 7, so max stays 7
At i=3, we find 9 > 7, so max becomes 9
At i=4, 4 ≤ 9, so max stays 9
We return 9, which is indeed the maximum ✓

The trace table proves the algorithm works for this input. To build confidence, we'd trace additional inputs, especially edge cases.

Column Selection

You don't need columns for every expression—only for variables that change and comparisons that affect control flow. Include enough to follow the logic, but not so much that the table becomes unwieldy.

Tracing Through Loops

Loops are where most algorithmic bugs hide. Off-by-one errors, incorrect termination conditions, and infinite loops all occur in loop constructs. Careful loop tracing catches these errors.

Key elements to verify when tracing loops:

Loop Tracing Checklist

•Initialization — Is the loop variable initialized correctly before the first iteration?
•First iteration — Does the loop process the correct first element? (Often index 0 or 1)
•Last iteration — Does the loop stop at the right element? Watch for < vs <= and length vs length - 1
•Loop body — Does each iteration do the right thing for that iteration's values?
•Termination — Will the loop eventually terminate? Does the condition become false?
•Post-loop state — After the loop ends, what are the final variable values?

Example: Tracing a loop to count occurrences

Trace Table for CountOccurrences([1, 3, 5, 3, 3, 2], 3)
Step	i	array[i]	array[i] = 3?	count
Init				0
1	0	1	No	0
2	1	3	Yes	1
3	2	5	No	1
4	3	3	Yes	2
5	4	3	Yes	3
6	5	2	No	3
End				RETURN 3 ✓

Verifying loop boundaries:

Array indices: 0, 1, 2, 3, 4, 5 (6 elements)
Loop condition: i ← 0 TO length(array) - 1 = i ← 0 TO 5
The loop processes indices 0 through 5 (all 6 elements) ✓
Loop terminates when i would exceed 5 ✓
Final count is 3, which matches manual counting of '3's in the array ✓

The Off-By-One Trap

Off-by-one errors are so common they have a name: 'fencepost errors' (if you need fence posts between sections, you need n+1 posts for n sections). When tracing, always verify: Does the loop start at the right index? Does it end at the right index? Does the range include both endpoints or exclude one?

Tracing Nested Structures

Nested loops, conditionals within loops, and function calls within loops create additional complexity. The trace table approach scales to handle these cases.

Example: Tracing a nested loop (finding pairs)

Trace Table for FindPairs([1, 4, 3, 2], 5)
i	j	array[i]	array[j]	sum	= 5?	pairs
0	1	1	4	5	Yes	[[0,1]]
0	2	1	3	4	No	[[0,1]]
0	3	1	2	3	No	[[0,1]]
1	2	4	3	7	No	[[0,1]]
1	3	4	2	6	No	[[0,1]]
2	3	3	2	5	Yes	[[0,1], [2,3]]

Observations from the trace:

Outer loop runs for i = 0, 1, 2 (stops before length-1 = 3)
Inner loop starts at j = i+1, ensuring we don't compare an element with itself or duplicate pairs
We find two pairs that sum to 5: indices [0,1] (values 1+4) and [2,3] (values 3+2) ✓

Verifying loop boundaries:

Outer loop: i ← 0 TO length-2 = i ← 0 TO 2 (3 iterations for i = 0, 1, 2)
Inner loop with i=0: j ← 1 TO 3 (j = 1, 2, 3)
Inner loop with i=1: j ← 2 TO 3 (j = 2, 3)
Inner loop with i=2: j ← 3 TO 3 (j = 3 only)

Total comparisons: 3 + 2 + 1 = 6, which matches our 6 rows ✓

Compact Nested Loop Traces

For nested loops, you can either show each inner iteration as a row (comprehensive) or summarize the inner loop's effect in one row per outer iteration (compact). Choose based on complexity—if bugs hide in the inner loop, trace it fully.

Tracing Recursive Algorithms

Recursive algorithms require a different tracing approach. Each recursive call creates a new context with its own parameter values. The key is to trace the call stack—the sequence of active function calls.

Techniques for tracing recursion:

Call tree — Draw a tree where each node is a function call, with children representing recursive calls
Indented trace — Indent each level of recursion to show the stack depth
Stack table — Maintain a table of stacked frames, pushing on calls and popping on returns

Example: Tracing binary search (recursive)

Recursion Unwinding

Recursion has two phases: the 'winding' phase where calls stack up, and the 'unwinding' phase where returns propagate back. For algorithms that compute on the way down (like binary search), the result is found during winding. For algorithms that accumulate (like factorial), results combine during unwinding.

Tracing Algorithms with Data Structures

When algorithms use stacks, queues, or other data structures, your trace must show the state of these structures at each step.

Example: Tracing a stack-based parenthesis validator

Trace Table for IsValid("(()(()))")
Step	char	Action	stack (bottom→top)
Init		Create empty stack	[]
1	(	Push	['(']
2	(	Push	['(', '(']
3	)	Pop	['(']
4	(	Push	['(', '(']
5	(	Push	['(', '(', '(']
6	)	Pop	['(', '(']
7	)	Pop	['(']
8	)	Pop	[]
End		isEmpty(stack)?	Yes → RETURN true ✓

Visualizing the stack:

It often helps to draw the stack graphically:

Step 5 (maximum depth):
   ┌───┐
   │ ( │  ← top
   ├───┤
   │ ( │
   ├───┤
   │ ( │  ← bottom
   └───┘

Drawing the data structure helps you see whether operations are correct and catch issues like underflow (popping from empty) or overflow (if size is bounded).

Data Structure State is Key

When tracing algorithms that use complex data structures (trees, graphs, priority queues), sketch the structure's state at critical points—especially before and after the operations that modify it. This visual trace often reveals bugs invisible in a pure variable trace.

Choosing Test Cases for Dry Runs

Dry running one case proves the algorithm works for that input. But algorithms can fail on specific edge cases while working on typical inputs. Strategic test case selection maximizes bug-finding efficiency.

Essential Test Case Categories

•Typical case — A normal, representative input that exercises the main logic path
•Empty input — Empty array, empty string, zero. Tests initialization and base cases
•Single element — One item in array, one-character string. Tests minimum non-empty case
•Two elements — Often reveals issues with comparison/swap logic
•All same — Array of identical elements. Tests handling of duplicates
•Sorted (ascending) — Already in expected order. Tests if algorithm handles no-work-needed cases
•Sorted (descending) — Reverse order. Often the worst case for sorting algorithms
•Boundary values — Maximum/minimum integers, values at array boundaries (first, last element)
•Target not found — For search algorithms, ensure no-match is handled correctly
•Negative numbers — If algorithm should handle them, test explicitly

Prioritizing test cases for time-constrained dry runs:

You often don't have time to trace every case. Prioritize:

One typical case — Verify the happy path works
One edge case most likely to fail — Empty input, single element, or the case your algorithm's structure makes riskiest
Boundary case if relevant — First/last element handling, loop termination

If all three pass, you have reasonable confidence. If time permits, add more edge cases.

Example Test Case Selection for FindMaximum
Test Case	Input	Expected	Why Include
Typical	[3, 7, 2, 9, 4]	9	Normal case with max in middle
Single element	[5]	5	Tests if loop handles n=1
Max at start	[9, 3, 2, 1]	9	Tests if initialization is correct
Max at end	[1, 2, 3, 9]	9	Tests if loop reaches last element
All equal	[5, 5, 5, 5]	5	Tests handling of no updates
Negatives	[-3, -1, -7]	-1	Tests if comparison works for negatives

Edge Cases Break Algorithms

In interviews and production, most bugs occur in edge cases, not happy paths. An algorithm that works for [3, 7, 2, 9, 4] but crashes on [] or returns wrong for [5] is broken. Always trace at least one edge case.

Common Bugs Revealed by Dry Running

Experienced programmers know the usual suspects. When dry running, watch specifically for these common error patterns:

Common Algorithm Bugs

•Off-by-one in loop bounds — < length vs <= length, starting at 0 vs 1
•Incorrect initialization — Setting max to 0 instead of array[0], or count to 1 instead of 0
•Missing base case — Recursion without termination condition
•Wrong base case — Factorial(0) should be 1, not 0
•Wrong operator — Using < when <= was intended, or = vs ≠
•Integer division truncation — (5/2) is 2, not 2.5; affects midpoint calculations
•Updating in wrong order — Updating an index before using it, or vice versa
•Variable shadowing — Accidentally using a loop variable named like an outer variable
•Not handling empty input — Algorithm crashes or returns wrong value for edge case
•Early return skips cleanup — Returning before updating a result variable

Dry Running Caught It

This bug would crash at runtime with an index error. But our trace caught it before we wrote any code. We traced to i=3, asked 'what is array[3]?', and realized the array only has indices 0, 1, 2. Five minutes of tracing saved debugging time.

Summary: The Power of Systematic Tracing

Dry running is not busywork—it's the most efficient way to verify algorithm correctness. The time invested in tracing pays dividends in reduced debugging and increased confidence.

Key Takeaways

•Trace tables are your primary tool — Columns for variables, rows for steps, systematic updates for each statement.
•Loops need careful attention — Verify initialization, termination, and boundary handling. Off-by-one errors are the most common bugs.
•Recursion uses call trees or indented traces — Track the winding phase (calls going deeper) and unwinding phase (returns propagating up).
•Data structure state matters — Draw stacks, queues, and other structures at key steps to visualize their evolution.
•Choose test cases strategically — Include typical cases, edge cases (empty, single element), and boundary cases.
•Know common bug patterns — Off-by-one errors, wrong operators, missing base cases. Watch for these specifically.
•Trace before you implement — Finding bugs on paper takes minutes; debugging compiled code takes hours.

What's next:

Now that you can trace algorithm execution, the next skill is tracing complexity—understanding how time and space requirements evolve as you step through the algorithm. This combines dry running techniques with the complexity analysis we've learned earlier in this chapter.

Page Complete

You now have the tools to systematically verify any algorithm's correctness through dry running. This skill sets you apart from programmers who rely solely on trial-and-error debugging. Next, we'll extend this technique to trace time and space complexity during dry runs.

Dry Running an Algorithm Step by Step

Becoming a Human Computer

Imagine you've written what you believe is a correct algorithm. You're confident in the logic, the pseudocode looks clean, and you're ready to implement. But how do you know it's correct?

You could implement it, run test cases, and debug failures. But this approach is slow, frustrating, and often reveals problems after you've invested significant coding time. There's a better way.

This technique is not optional. It's the most reliable way to verify algorithm correctness before you write a single line of implementation code.

What You Will Learn

What Is Dry Running?

Dry running (also called hand tracing, desk checking, or walkthrough) is the process of manually simulating algorithm execution on paper or a whiteboard. You:

Choose a specific input (test case)
Execute each statement in order, exactly as a computer would
Track the values of all variables after each step
Follow branches and loops precisely based on current values
Verify that the final output matches your expectation

The term "dry run" comes from the idea of running through something without the actual execution—like a rehearsal before a performance, or a fire drill without a real fire.

Why Dry Running Is Essential

•Catches logic errors before coding — You find bugs in minutes on paper rather than hours debugging compiled code
•Reveals off-by-one errors — The most common algorithmic mistake becomes visible when you trace exact indices
•Tests edge cases cheaply — You can trace unusual inputs without writing test infrastructure
•Builds deep understanding — You don't just believe the algorithm works; you know because you've watched it work
•Improves explanation skills — After dry running, you can explain the algorithm's behavior step-by-step in interviews
•Develops intuition — Repeated dry runs build pattern recognition for common algorithmic behaviors

The Master's Secret

Setting Up a Trace Table

How to construct a trace table:

Columns — Create one column for each variable in the algorithm, plus a 'Step' or 'Line' column, and optionally an 'Action/Notes' column
Rows — Each row represents the state after executing one step (statement, loop iteration, or function call)
Initial row — Record the initial values before the first statement executes
Update on change — When a variable changes, record its new value; if unchanged, either repeat the previous value or use a dash to indicate 'unchanged'

Example: Tracing a simple maximum-finding algorithm

Let's trace the FindMaximum algorithm with input [3, 7, 2, 9, 4]:

Trace Table for FindMaximum([3, 7, 2, 9, 4])
Step	i	array[i]	max	array[i] > max?	Action
Init			3		max ← array[0] = 3
1	1	7	7	Yes (7 > 3)	max ← 7
2	2	2	7	No (2 ≤ 7)	No change
3	3	9	9	Yes (9 > 7)	max ← 9
4	4	4	9	No (4 ≤ 9)	No change
End			9		RETURN 9 ✓

Reading the trace table:

We start with max = 3 (first element)
At i=1, we find 7 > 3, so max becomes 7
At i=2, 2 ≤ 7, so max stays 7
At i=3, we find 9 > 7, so max becomes 9
At i=4, 4 ≤ 9, so max stays 9
We return 9, which is indeed the maximum ✓

The trace table proves the algorithm works for this input. To build confidence, we'd trace additional inputs, especially edge cases.

Column Selection

Tracing Through Loops

Loops are where most algorithmic bugs hide. Off-by-one errors, incorrect termination conditions, and infinite loops all occur in loop constructs. Careful loop tracing catches these errors.

Key elements to verify when tracing loops:

Loop Tracing Checklist

•Initialization — Is the loop variable initialized correctly before the first iteration?
•First iteration — Does the loop process the correct first element? (Often index 0 or 1)
•Last iteration — Does the loop stop at the right element? Watch for < vs <= and length vs length - 1
•Loop body — Does each iteration do the right thing for that iteration's values?
•Termination — Will the loop eventually terminate? Does the condition become false?
•Post-loop state — After the loop ends, what are the final variable values?

Example: Tracing a loop to count occurrences

Trace Table for CountOccurrences([1, 3, 5, 3, 3, 2], 3)
Step	i	array[i]	array[i] = 3?	count
Init				0
1	0	1	No	0
2	1	3	Yes	1
3	2	5	No	1
4	3	3	Yes	2
5	4	3	Yes	3
6	5	2	No	3
End				RETURN 3 ✓

Verifying loop boundaries:

Array indices: 0, 1, 2, 3, 4, 5 (6 elements)
Loop condition: i ← 0 TO length(array) - 1 = i ← 0 TO 5
The loop processes indices 0 through 5 (all 6 elements) ✓
Loop terminates when i would exceed 5 ✓
Final count is 3, which matches manual counting of '3's in the array ✓

The Off-By-One Trap

Tracing Nested Structures

Nested loops, conditionals within loops, and function calls within loops create additional complexity. The trace table approach scales to handle these cases.

Example: Tracing a nested loop (finding pairs)

Trace Table for FindPairs([1, 4, 3, 2], 5)
i	j	array[i]	array[j]	sum	= 5?	pairs
0	1	1	4	5	Yes	[[0,1]]
0	2	1	3	4	No	[[0,1]]
0	3	1	2	3	No	[[0,1]]
1	2	4	3	7	No	[[0,1]]
1	3	4	2	6	No	[[0,1]]
2	3	3	2	5	Yes	[[0,1], [2,3]]

Observations from the trace:

Outer loop runs for i = 0, 1, 2 (stops before length-1 = 3)
Inner loop starts at j = i+1, ensuring we don't compare an element with itself or duplicate pairs
We find two pairs that sum to 5: indices [0,1] (values 1+4) and [2,3] (values 3+2) ✓

Verifying loop boundaries:

Outer loop: i ← 0 TO length-2 = i ← 0 TO 2 (3 iterations for i = 0, 1, 2)
Inner loop with i=0: j ← 1 TO 3 (j = 1, 2, 3)
Inner loop with i=1: j ← 2 TO 3 (j = 2, 3)
Inner loop with i=2: j ← 3 TO 3 (j = 3 only)

Total comparisons: 3 + 2 + 1 = 6, which matches our 6 rows ✓

Compact Nested Loop Traces

Tracing Recursive Algorithms

Techniques for tracing recursion:

Call tree — Draw a tree where each node is a function call, with children representing recursive calls
Indented trace — Indent each level of recursion to show the stack depth
Stack table — Maintain a table of stacked frames, pushing on calls and popping on returns

Example: Tracing binary search (recursive)

Recursion Unwinding

Tracing Algorithms with Data Structures

When algorithms use stacks, queues, or other data structures, your trace must show the state of these structures at each step.

Example: Tracing a stack-based parenthesis validator

Trace Table for IsValid("(()(()))")
Step	char	Action	stack (bottom→top)
Init		Create empty stack	[]
1	(	Push	['(']
2	(	Push	['(', '(']
3	)	Pop	['(']
4	(	Push	['(', '(']
5	(	Push	['(', '(', '(']
6	)	Pop	['(', '(']
7	)	Pop	['(']
8	)	Pop	[]
End		isEmpty(stack)?	Yes → RETURN true ✓

Visualizing the stack:

It often helps to draw the stack graphically:

Step 5 (maximum depth):
   ┌───┐
   │ ( │  ← top
   ├───┤
   │ ( │
   ├───┤
   │ ( │  ← bottom
   └───┘

Drawing the data structure helps you see whether operations are correct and catch issues like underflow (popping from empty) or overflow (if size is bounded).

Data Structure State is Key

Choosing Test Cases for Dry Runs

Essential Test Case Categories

•Typical case — A normal, representative input that exercises the main logic path
•Empty input — Empty array, empty string, zero. Tests initialization and base cases
•Single element — One item in array, one-character string. Tests minimum non-empty case
•Two elements — Often reveals issues with comparison/swap logic
•All same — Array of identical elements. Tests handling of duplicates
•Sorted (ascending) — Already in expected order. Tests if algorithm handles no-work-needed cases
•Sorted (descending) — Reverse order. Often the worst case for sorting algorithms
•Boundary values — Maximum/minimum integers, values at array boundaries (first, last element)
•Target not found — For search algorithms, ensure no-match is handled correctly
•Negative numbers — If algorithm should handle them, test explicitly

Prioritizing test cases for time-constrained dry runs:

You often don't have time to trace every case. Prioritize:

One typical case — Verify the happy path works
One edge case most likely to fail — Empty input, single element, or the case your algorithm's structure makes riskiest
Boundary case if relevant — First/last element handling, loop termination

If all three pass, you have reasonable confidence. If time permits, add more edge cases.

Example Test Case Selection for FindMaximum
Test Case	Input	Expected	Why Include
Typical	[3, 7, 2, 9, 4]	9	Normal case with max in middle
Single element	[5]	5	Tests if loop handles n=1
Max at start	[9, 3, 2, 1]	9	Tests if initialization is correct
Max at end	[1, 2, 3, 9]	9	Tests if loop reaches last element
All equal	[5, 5, 5, 5]	5	Tests handling of no updates
Negatives	[-3, -1, -7]	-1	Tests if comparison works for negatives

Edge Cases Break Algorithms

Common Bugs Revealed by Dry Running

Experienced programmers know the usual suspects. When dry running, watch specifically for these common error patterns:

Common Algorithm Bugs

•Off-by-one in loop bounds — < length vs <= length, starting at 0 vs 1
•Incorrect initialization — Setting max to 0 instead of array[0], or count to 1 instead of 0
•Missing base case — Recursion without termination condition
•Wrong base case — Factorial(0) should be 1, not 0
•Wrong operator — Using < when <= was intended, or = vs ≠
•Integer division truncation — (5/2) is 2, not 2.5; affects midpoint calculations
•Updating in wrong order — Updating an index before using it, or vice versa
•Variable shadowing — Accidentally using a loop variable named like an outer variable
•Not handling empty input — Algorithm crashes or returns wrong value for edge case
•Early return skips cleanup — Returning before updating a result variable

Dry Running Caught It

Summary: The Power of Systematic Tracing

Dry running is not busywork—it's the most efficient way to verify algorithm correctness. The time invested in tracing pays dividends in reduced debugging and increased confidence.

Key Takeaways

•Trace tables are your primary tool — Columns for variables, rows for steps, systematic updates for each statement.
•Loops need careful attention — Verify initialization, termination, and boundary handling. Off-by-one errors are the most common bugs.
•Recursion uses call trees or indented traces — Track the winding phase (calls going deeper) and unwinding phase (returns propagating up).
•Data structure state matters — Draw stacks, queues, and other structures at key steps to visualize their evolution.
•Choose test cases strategically — Include typical cases, edge cases (empty, single element), and boundary cases.
•Know common bug patterns — Off-by-one errors, wrong operators, missing base cases. Watch for these specifically.
•Trace before you implement — Finding bugs on paper takes minutes; debugging compiled code takes hours.

What's next:

Page Complete