Problem Solving: Trace tables

From Wikibooks, open books for an open world
Jump to navigation Jump to search

UNIT 1 - ⇑ Problem Solving ⇑

← Algorithm design Trace tables Pseudo code →


Trace table - a technique used to test algorithms to make sure that no logical errors occur


Hand tracing or 'dry running' allows you to use a trace table to

  • see what code will do before you have to run it
  • find where errors in your code are

Taking a program like the one below we need to keep track (trace) all the variables and outputs.

#include<stdio.h>
 
int main() {
 
    // Read n
    int n;
    printf("Enter number n : ");
    scanf("%d", &n);
 
    // Declare sum to 0 
    // counter variable i to 1
    int sum = 0;
    int i = 1;
 
    // loop to input n numbers
    // loop continues until i<=n
    for(i=1;i<=n;i++){
        // read num
        int num ;
        printf("Enter number %d: ", i);
        scanf("%d", &num);
 
        // update sum to sum + num
        sum = sum + num;
    }
 
    // print sum
    printf("Sum of given numbers is %d", sum);
    return 0;
}

To do this we create a trace table:

y x output
3 1
4 2
6 3
9 4
13 13

The exam will normally ask you to create a trace table of some sort so you need to be very confident with them. The exam will usually give you the headings but just in case, there are several steps in making a trace table, the first one is to note the table headings, this involves the following:

  1. VARIABLES: note all the variables in the piece of code you are looking at (this includes arrays). Note each variable as a heading
  2. OUTPUTS: note if there is an output and put this as a heading
  3. INPUTS: if there are inputs specified, put an inputs column and be prepared to fill it in.

It is very easy to jump right in when filling in trace tables, but you must be careful. The exam will try and trick you, so trying to predict what a trace table will do is not a good idea. In fact, the best idea is to switch your brain off and tackle the problem line by line, exactly as a computer would. Take a look at the following example:

Example: Simple trace table
Dim num() as integer = {10,8,3,5,6,1,2}
Dim sum as integer = 0
Dim avg as decimal
For x = 0 to 5
	sum = sum + num(x)
Loop
avg = sum / (x + 1)
Console.writeline("average =" & avg)
  1. note all the variables: num array / sum / avg / x
  2. note if there is an output: yes
  3. if there are inputs specified: no

So we should construct the following table:

num
0 1 2 3 4 5 6 sum avg x output
10 8 3 5 6 1 2 0
  0

Now looking at the names of the variables you might be tempted to add all the values in the array together to find the sum, and then find the average number from this calculation . However, you'd be wrong, create a trace table and see if you can find the correct answer:

Answer:

num
0 1 2 3 4 5 6 sum avg x output
10 8 3 5 6 1 2 0
10 0
18 1
21 2
26 3
32 4
33 5.5 5 average =5.5

So what went wrong? If you look at the trace table you can see that we never added the number 2 from the num array to the sum, it stopped at element 5. To fix this we would adjust the following line:

For x = 0 to 6
Exercise: Trace tables

Complete the trace table for the following code, where the number input is 39

Dim input As Integer = 78
Dim r As Integer
Console.Write("Input a number:")
input = Console.ReadLine()

Dim op As String = ""

While (input > 0)
	r = input Mod 2
	input = input \ 2
	op = r & op
End While

Console.Write(op)
Console.ReadLine()

Answer:

input r op output
78
39 1 1
19 1 11
9 1 111
4 0 0111
2 0 00111
1 1 100111
0 100111

As always with programming there is a shorter way of performing this task, take a look at:

Dim num As Integer = 239938

Dim ss As String = Convert.ToString(num, 2)
Console.WriteLine(ss)

Do you think you can work out how to output an hex, base 16 number? I bet you can.


What does the above code do?

Answer:

It converts a base10 (denary/decimal) number into its binary equivalent


Complete the trace table for the following code:

Dim nums() = {6,2,8,1,9,2}
Dim n as integer = 0

for i = 0 to 5
  if nums(i) > n
    n = nums(i)
  end if
loop

Answer:

i n nums
0 1 2 3 4 5
0 6 2 8 1 9 2
0 6
1
2 8
3
4 9
5


What function does the above code perform?

Answer:

It finds the highest value in an array of values


UNIT 1 - ⇑ Problem Solving ⇑

← Algorithm design Trace tables Pseudo code →