Dry Running an Algorithm… — Expressing Algorithms… | OneNoughtOne

0/361

Data Structures & AlgorithmsExpressing Algorithms Clearly

Expressing Algorithms Clearly

LevelBeginner

Duration60 mins

TopicExpressing Algorithms Clearly

3 / 5

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] :

FUNCTION FindMaximum(array)
    max ← array[0]
    
    FOR i ← 1 TO length(array) - 1 DO
        IF array[i] > max THEN
            max ← array[i]
        END IF
    END FOR
    
    RETURN max
END FUNCTION
 
Input: array = [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 \leq 7, so max stays 7 At i=3, we find 9 > 7, so max becomes 9 At i=4, 4 \leq 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

FUNCTION CountOccurrences(array, target)
    count ← 0
    
    FOR i ← 0 TO length(array) - 1 DO
        IF array[i] = target THEN
            count ← count + 1
        END IF
    END FOR
    
    RETURN count
END FUNCTION
 
Input: array = [1, 3, 5, 3, 3, 2], target = 3

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 \leftarrow 0 TO length(array) - 1 = i \leftarrow 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)

FUNCTION FindPairs(array, target)
    pairs ← empty list
    
    FOR i ← 0 TO length(array) - 2 DO
        FOR j ← i + 1 TO length(array) - 1 DO
            IF array[i] + array[j] = target THEN
                append(pairs, [i, j])
            END IF
        END FOR
    END FOR
    
    RETURN pairs
END FUNCTION
 
Input: array = [1, 4, 3, 2], target = 5

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 \leftarrow 0 TO length-2 = i \leftarrow 0 TO 2 (3 iterations for i = 0, 1, 2) Inner loop with i=0: j \leftarrow 1 TO 3 (j = 1, 2, 3) Inner loop with i=1: j \leftarrow 2 TO 3 (j = 2, 3) Inner loop with i=2: j \leftarrow 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

FUNCTION Factorial(n)
    IF n ≤ 1 THEN
        RETURN 1
    END IF
    RETURN n × Factorial(n - 1)
END FUNCTION
 
Trace: Factorial(4)

Factorial(4):
    n = 4, not ≤ 1
    need: 4 × Factorial(3)
    
    Factorial(3):
        n = 3, not ≤ 1
        need: 3 × Factorial(2)
        
        Factorial(2):
            n = 2, not ≤ 1
            need: 2 × Factorial(1)
            
            Factorial(1):
                n = 1, is ≤ 1
                RETURN 1                    ← base case reached
            
            returns: 2 × 1 = 2              ← unwind begins
        
        returns: 3 × 2 = 6
    
    returns: 4 × 6 = 24
 
Final result: 24 ✓

Example: Tracing binary search (recursive)

FUNCTION BinarySearch(array, target, low, high)
    IF low > high THEN
        RETURN -1
    END IF
    mid ← (low + high) / 2
    IF array[mid] = target THEN
        RETURN mid
    ELSE IF array[mid] < target THEN
        RETURN BinarySearch(array, target, mid + 1, high)
    ELSE
        RETURN BinarySearch(array, target, low, mid - 1)
    END IF
END FUNCTION
 
Input: array = [1, 3, 5, 7, 9, 11], target = 7
 
Trace:
BinarySearch([1,3,5,7,9,11], 7, 0, 5):
    low=0, high=5, mid=(0+5)/2=2
    array[2]=5, 5 ≠ 7, 5 < 7
    → search right half
    
    BinarySearch([...], 7, 3, 5):
        low=3, high=5, mid=(3+5)/2=4
        array[4]=9, 9 ≠ 7, 9 > 7
        → search left half
        
        BinarySearch([...], 7, 3, 3):
            low=3, high=3, mid=(3+3)/2=3
            array[3]=7, 7 = 7 ✓
            RETURN 3
        
        returns 3
    
    returns 3
 
Final result: 3 (index of value 7) ✓

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

FUNCTION IsValid(s)
    stack ← empty stack
    
    FOR EACH char IN s DO
        IF char is '(' THEN
            push(stack, char)
        ELSE IF char is ')' THEN
            IF isEmpty(stack) THEN
                RETURN false
            END IF
            pop(stack)
        END IF
    END FOR
    
    RETURN isEmpty(stack)
END FUNCTION
 
Input: s = "(()(()))"
(Only considering '(' and ')' for simplicity)

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): ┌───┐ │ ( │ \leftarrow top ├───┤ │ ( │ ├───┤ │ ( │ \leftarrow 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.

Data Structures & AlgorithmsExpressing Algorithms Clearly

Expressing Algorithms Clearly

LevelBeginner

Duration60 mins

TopicExpressing Algorithms Clearly

3 / 5

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] :

FUNCTION FindMaximum(array)
    max ← array[0]
    
    FOR i ← 1 TO length(array) - 1 DO
        IF array[i] > max THEN
            max ← array[i]
        END IF
    END FOR
    
    RETURN max
END FUNCTION
 
Input: array = [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 \leq 7, so max stays 7 At i=3, we find 9 > 7, so max becomes 9 At i=4, 4 \leq 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

FUNCTION CountOccurrences(array, target)
    count ← 0
    
    FOR i ← 0 TO length(array) - 1 DO
        IF array[i] = target THEN
            count ← count + 1
        END IF
    END FOR
    
    RETURN count
END FUNCTION
 
Input: array = [1, 3, 5, 3, 3, 2], target = 3

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 \leftarrow 0 TO length(array) - 1 = i \leftarrow 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)

FUNCTION FindPairs(array, target)
    pairs ← empty list
    
    FOR i ← 0 TO length(array) - 2 DO
        FOR j ← i + 1 TO length(array) - 1 DO
            IF array[i] + array[j] = target THEN
                append(pairs, [i, j])
            END IF
        END FOR
    END FOR
    
    RETURN pairs
END FUNCTION
 
Input: array = [1, 4, 3, 2], target = 5

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 \leftarrow 0 TO length-2 = i \leftarrow 0 TO 2 (3 iterations for i = 0, 1, 2) Inner loop with i=0: j \leftarrow 1 TO 3 (j = 1, 2, 3) Inner loop with i=1: j \leftarrow 2 TO 3 (j = 2, 3) Inner loop with i=2: j \leftarrow 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

FUNCTION Factorial(n)
    IF n ≤ 1 THEN
        RETURN 1
    END IF
    RETURN n × Factorial(n - 1)
END FUNCTION
 
Trace: Factorial(4)

Factorial(4):
    n = 4, not ≤ 1
    need: 4 × Factorial(3)
    
    Factorial(3):
        n = 3, not ≤ 1
        need: 3 × Factorial(2)
        
        Factorial(2):
            n = 2, not ≤ 1
            need: 2 × Factorial(1)
            
            Factorial(1):
                n = 1, is ≤ 1
                RETURN 1                    ← base case reached
            
            returns: 2 × 1 = 2              ← unwind begins
        
        returns: 3 × 2 = 6
    
    returns: 4 × 6 = 24
 
Final result: 24 ✓

Example: Tracing binary search (recursive)

FUNCTION BinarySearch(array, target, low, high)
    IF low > high THEN
        RETURN -1
    END IF
    mid ← (low + high) / 2
    IF array[mid] = target THEN
        RETURN mid
    ELSE IF array[mid] < target THEN
        RETURN BinarySearch(array, target, mid + 1, high)
    ELSE
        RETURN BinarySearch(array, target, low, mid - 1)
    END IF
END FUNCTION
 
Input: array = [1, 3, 5, 7, 9, 11], target = 7
 
Trace:
BinarySearch([1,3,5,7,9,11], 7, 0, 5):
    low=0, high=5, mid=(0+5)/2=2
    array[2]=5, 5 ≠ 7, 5 < 7
    → search right half
    
    BinarySearch([...], 7, 3, 5):
        low=3, high=5, mid=(3+5)/2=4
        array[4]=9, 9 ≠ 7, 9 > 7
        → search left half
        
        BinarySearch([...], 7, 3, 3):
            low=3, high=3, mid=(3+3)/2=3
            array[3]=7, 7 = 7 ✓
            RETURN 3
        
        returns 3
    
    returns 3
 
Final result: 3 (index of value 7) ✓

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

FUNCTION IsValid(s)
    stack ← empty stack
    
    FOR EACH char IN s DO
        IF char is '(' THEN
            push(stack, char)
        ELSE IF char is ')' THEN
            IF isEmpty(stack) THEN
                RETURN false
            END IF
            pop(stack)
        END IF
    END FOR
    
    RETURN isEmpty(stack)
END FUNCTION
 
Input: s = "(()(()))"
(Only considering '(' and ')' for simplicity)

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): ┌───┐ │ ( │ \leftarrow top ├───┤ │ ( │ ├───┤ │ ( │ \leftarrow 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.

Dry Running an Algorithm Step by Step

Becoming a Human Computer

What Is Dry Running?

Setting Up a Trace Table

Tracing Through Loops

Tracing Nested Structures

Tracing Recursive Algorithms

Tracing Algorithms with Data Structures

Choosing Test Cases for Dry Runs

There’s more to understand.

Dry Running an Algorithm Step by Step

Becoming a Human Computer

What Is Dry Running?

Setting Up a Trace Table

Tracing Through Loops

Tracing Nested Structures

Tracing Recursive Algorithms

Tracing Algorithms with Data Structures

Choosing Test Cases for Dry Runs

There’s more to understand.