2.11 Algorithm Dry Run

Introduction

An algorithm dry run means manually checking the execution of an algorithm by providing it with a specific set of inputs. This helps not only to verify the algorithm's correctness but also to understand the algorithm's behavior on certain inputs and conditions. By doing this, we are also able to identify logical errors, if any.

Definition

Algorithm Dry Run is the process of manually tracing through an algorithm step by step with sample inputs to verify that it produces the correct output and to understand how it works.

Main Idea

Before writing actual code, a programmer can test the logic of an algorithm by "running" it by hand on paper. This is called a dry run. It helps catch mistakes early and ensures the algorithm works as intended.

Core Concept

Steps of Dry Run

1. Choose an Input: To test an algorithm, the first step is the selection of a specific set of input values.

2. Simulate Execution: To test algorithm working, each step of the algorithm is manually performed by using the chosen inputs. However, it also needs to keep track of variable states, that may change on performing specific operation.

3. Observe Output: After performing all the required steps of an algorithm, its final output is observed.

4. Compare with Expected Result: The final output of the algorithm is crosschecked with the expected result. If it matches, then it means the algorithm is correct; otherwise, we review each step to identify if something has gone wrong.

Detailed Explanation

Example: Performing dry run of algorithm that finds largest number from a list of numbers

Algorithm:

• Take a variable `max` and initialize with the first element of the list.
• Iterate through all the remaining elements of the list.
• Compare each element with the variable `max`.
• If the compared element is greater than the variable `max`, update `max` variable with the compared element.
• Now `max` variable contains the largest number; return it.

Example Input List: [3, 1, 4, 1, 5, 9, 2, 6]

Dry Run:

1. Initialization: - `max = 3` (First element in the list)

Iteration (take element other than first in each iteration):

• Compare 1 with 3: 1 is less than 3, so `max` will not change.
• Compare 4 with 3: 4 is greater than 3, update value of `max` to 4.
• Compare 1 with 4: 1 is less than 4, so `max` will not change.
• Compare 5 with 4: 5 is greater than 4, update value of `max` to 5.
• Compare 9 with 5: 9 is greater than 5, update value of `max` to 9.
• Compare 2 with 9: 2 is less than 9, so `max` will not change.
• Compare 6 with 9: 6 is less than 9, so `max` will not change.

Result: - `max` contains 9, return this value.

If you visually see your input list, 9 is the largest number, and our dry run of the algorithm has also correctly identified 9 as the maximum number. This shows that the algorithm steps are working as intended. The dry runs are powerful tools that can be used to validate the algorithm logic before writing the code.

Trace Table

A trace table is also used to verify the algorithm's correctness. While tracing the algorithm, the trace table records the values of variables and their respective changes at each of the algorithm steps. The final values of the variables are considered the final output of the algorithm.

In the above table at:

• Step 0: Initialize `max` to the first element (3).
• Step 1: Compare 1 with 3. Since 1 is not greater than 3, `max` remains 3.
• Step 2: Compare 4 with 3. Since 4 is greater than 3, update `max` to 4.
• Step 3: Compare 1 with 4. Since 1 is not greater than 4, `max` remains 4.
• Step 4: Compare 5 with 4. Since 5 is greater than 4, update `max` to 5.
• Step 5: Compare 9 with 5. Since 9 is greater than 5, update `max` to 9.
• Step 6: Compare 2 with 9. Since 2 is not greater than 9, `max` remains 9.
• Step 7: Compare 6 with 9. Since 6 is not greater than 9, `max` remains 9.
• End: The final maximum value is 9.

This trace table shows how the algorithm processes each element of the list and how the `max` value is updated accordingly.

Intermediate Level

At the intermediate level, you should understand the benefits and limitations of dry runs.

• Helps find logical errors before coding.
• Helps understand how the algorithm works.
• Saves time by catching mistakes early.
• Improves confidence in the algorithm's correctness.

• Only tests a few inputs, not all possible inputs.
• Can be time-consuming for large algorithms.
• Does not catch syntax errors (those are caught by the compiler).
• Does not test performance (time and space complexity).

Important Points

• - Dry run = manually executing an algorithm step by step.
• - Steps: Choose input, Simulate execution, Observe output, Compare with expected.
• - Trace tables record variable values at each step.
• - Helps find logical errors before coding.
• - Only tests specific inputs, not all.
• - Powerful tool for validating algorithm logic.

Remember

• - Dry run = manual execution.
• - Steps: Choose input, Simulate, Observe, Compare.
• - Trace table = record variable values.
• - Finds logical errors.
• - Tests specific inputs.
• - Validates algorithm logic.

Common Mistakes

• - Skipping the dry run and going straight to coding.
• - Not keeping track of variable values correctly.
• - Testing only one input and assuming the algorithm is correct.
• - Confusing dry run with actual execution (dry run is manual).
• - Forgetting to compare the output with the expected result.
• - Not using a trace table for complex algorithms.

Quick Revision

• Dry run: manually checking algorithm execution with specific inputs.
• Steps: Choose input, Simulate execution, Observe output, Compare with expected.
• Trace table records variable values at each step.
• Helps find logical errors before coding.
• Only tests specific inputs.
• Powerful tool for validating algorithm logic.

60-Second Revision

• Dry run = manual execution.
• Steps: Choose input, Simulate, Observe, Compare.
• Trace table = record variable values.
• Finds logical errors.
• Validates algorithm logic.
• Warning: Dry run only tests specific inputs; it does not prove correctness for all inputs.