Tracing an algorithm

Objectives

• to identify where inputs, processing and outputs are taking place within an algorithm
• know how, and be able to, construct a trace table to illustrate how the value of variables are changing during the execution of an algorithm

Often, when writing and implementing our algorithms using code, we do not get the results we are expecting. We get an error. There may be different types of errors.

Types of error

Syntax Errors

Syntax errors are related to the structure or grammar of the code and occur when the programmer violates the rules of the programming language. They are picked up by the compiler or interpreter during the compilation phase. Typically these might include missing semicolons, mismatched parentheses, or typos in keywords. The program won't run until all syntax errors are fixed.

Logic Errors

Logic errors occur when the program's logic is flawed, leading to incorrect results or unexpected behavior. The code may run without producing any error messages, but the output is not what was intended. Logic errors are usually discovered during testing and debugging phases and may involve tracing the code and analyzing the output to identify discrepancies. The program runs, but it does not produce the expected or desired results.

Runtime Errors

Runtime errors occur during the execution of a program, they are not detected by the compiler but emerge when the program is running. They are usually identified by error messages displayed during program execution and typically might include division by zero, accessing an out-of-bounds array element, or using an undefined variable. When that happens the execution of the program is interrupted or terminated.

Tracing an algorithm

Tracing an algorithm can help track down i.e. debug logic errors, and runtime errors. Let's first look at the process and principles then use the technique on code that does have a logic error that needs to be corrected.

Note

A trace table can also be used to determine the purpose of the algorithm

We'll start with the binary search algorithm from the previous section:

def binary_search(items, target):
    low = 0
    high = len(items) - 1

    while low <= high:
        mid = (low + high) // 2  # Calculate the middle index

        if items[mid] == target:
            return mid  # Element found, return its index
        elif items[mid] < target:
            low = mid + 1  # Discard the left half
        else:
            high = mid - 1  # Discard the right half

    return -1  # Element not found

Our list of items will be: sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], and our target will be \(7\).

When tracing we play the role of the computer keeping a record of the variables and how they are being changed during the execution of the function. Proceed cautiously, do not try to second guess what you think might be happening, do not look forward just take it line by line. It can help to cover up any lines of code not being considered, analyse that one line, note the variables and any change of state, before moving on to the next line.

Our function has a number of important variables. Make these the columns of a table:

target	low	high	mid	items[mid]	output

We know our target is 7 and lines 2-3 of our function can be entered quite easily into our table:

target	low	high	mid	items[mid]	output
7	0	9

Moving down our code, line 5 is True as 0 is less than 9, so we proceed to the next line and note the value iof mid, then check the value at items[mid]:

target	low	high	mid	items[mid]	output
7	0	9	4	5

Line 8, we've not found the target value in this position, the value is less than our target so we need to adjust the low value:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5

Note

You do not need to repeat the values for target, high, mid etc.. It is assumed these have not changed - which, of course, they haven't.

We return to the top of the loop and repeat.

Line 5 is still True and we can progress to work out the value for mid (line 6) and then get the value for items[mid]:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5		7	8

It's not our target value, but it is higher than our target so we use line 13 to adjust the value if high:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5		7	8
		6

Returning to the top of the loop again, low <= high is still True so we update the value if mid and get the value of items[mid] as before:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5		7	8
		6
			5	6

It's still not our target value so we continue. The value is less than the target so we update the value of low:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5		7	8
		6
			5	6
	6

Returning to the top of the loop again, it evaluates to True and we proceed as before to the next line to get the value of mid and the corresponding item in the list:

target	low	high	mid	items[mid]	output
7	0	9	4	5
	5		7	8
		6
			5	6
	6
			6	7

Now the target is the same as items[mid] and on line 9 we can return the value iof mid from our function and we are done.

Questions

1. What will be the value of 'x' after executing the following pseudocode?

x = 5
y = 3
while y > 0:
    x = x + y
    y = y - 1

8

9

10

11

Initially, x is 5 and y is 3. The loop adds y to x and decreases y. The final values are x = 5 + 3 + 2 + 1 = 11 and y = 0.

Submit

2. What will be the output of the following pseudocode?

for i = 1 to 3:
    for j = 1 to i:
        print(i, j)

1 1 2 1 2 2 3 1 3 2 3 3

1 1 2 1 2 3 1 2 3

1 2 3 2 1 3 3 1 2

1 1 2 2 3 3

The outer loop runs from 1 to 3. For each iteration of i, the inner loop prints pairs of (i, j) where j ranges from 1 to i.

Submit

3. Which of the following algorithms is used to find the shortest path in a weighted graph with positive weights?

Bubble Sort

Selection Sort

Dijkstra's Algorithm

Merge Sort

Dijkstra's Algorithm is designed to find the shortest paths from a source vertex to all other vertices in a weighted graph with positive weights.

Submit

4. What is the time complexity of the binary search algorithm in the worst case?

$O(n)$

$O(n log n)$

$O(log n)$

$O(1)$

Binary search has a time complexity of $O(log n)$ in the worst case, as it repeatedly divides the search interval in half.

Submit

5. What will the value of the variable 'sum' be after executing the following pseudocode?

sum = 0
i = 1
while i <= 4:
    sum = sum + i
    i = i + 1

6

7

8

9

The loop adds values 1 through 4 to sum, resulting in sum = 1 + 2 + 3 + 4 = 10.

Submit

6. Which sorting algorithm is best suited for small datasets due to its simplicity and low overhead?

Quick Sort

Merge Sort

Insertion Sort

Heap Sort

Insertion Sort is often preferred for small datasets due to its simplicity and efficiency with a small number of elements.

Submit

7. What is the key feature of a stable sorting algorithm?

It sorts elements in place.

It guarantees the order of equal elements remains unchanged.

It has the best possible time complexity.

It requires additional memory for sorting.

A stable sorting algorithm preserves the relative order of elements with equal keys.

Submit

8. In a trace table for a sorting algorithm, what information is typically recorded?

Values of variables at each step and changes made during the algorithm's execution.

The final sorted list only.

The time complexity of the algorithm.

The original unsorted list.

A trace table records the values of variables and changes made during each step of the algorithm's execution to understand its behavior.

Submit

9. What is the best-case time complexity of the Bubble Sort algorithm?

O(n^2)

O(n log n)

O(n)

O(log n)

Bubble Sort has a best-case time complexity of O(n) when the array is already sorted and no swaps are needed.

Submit

10. Which algorithm is characterized by dividing the list into two halves, recursively sorting each half, and then merging them back together?

Insertion Sort

Merge Sort

Selection Sort

Heap Sort

Merge Sort divides the list into halves, recursively sorts each half, and merges them to produce a sorted list.

Submit

11. What will be the output of the following pseudocode?

n = 5
for i = 1 to n:
    for j = 1 to i:
        print(i, j)

1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5

1 1 2 1 2 3 3 1 2 3 4 4 5 5

1 1 1 2 2 2 3 3 3 4 4 5

1 2 3 4 5

The nested loop prints pairs of (i, j) where i ranges from 1 to n and j ranges from 1 to i, resulting in increasing sequences of printed pairs.

Submit