topic badge

12.11 Debugging

Worksheet
Debugging
1

Consider the following list of numbers: 4, \,9, \,8, \,1, \,6

a

Complete the table by writing the output for each step of the selection sort algorithm for the above list of numbers.

Step Number Algorithm StepOutput
1\text{Find the smallest number.} \\ \text{Swap it with the first number.}
2\text{Find the second-smallest number.} \\ \text{Swap it with the second number.}
3\text{Find the third-smallest number.} \\ \text{Swap it with the third number.}
4\text{Find the fourth-smallest number.} \\ \text{Swap it with the fourth number.}
b

The algorithm below contains a bug. Complete the table by writing the output for each step of the algorithm.

Step Number Algorithm StepOutput
1\text{Find the smallest number.} \\ \text{Swap it with the first number.}
2\text{Find the second-smallest number.} \\ \text{Swap it with the first number.}
3\text{Find the third-smallest number.} \\ \text{Swap it with the third number.}
4\text{Find the fourth-smallest number.} \\ \text{Swap it with the fourth number.}
c

Now, which step contains the bug? Explain your answer.

2

Consider the following list of numbers: 5,\, 9, \,7, \,1, \,6

a

Complete the table by writing the output for each step of the selection sort algorithm for the above list of numbers.

Step Number Algorithm StepOutput
1\text{Find the smallest number.} \\ \text{Swap it with the first number.}
2\text{Find the second-smallest number.} \\ \text{Swap it with the second number.}
3\text{Find the third-smallest number.} \\ \text{Swap it with the third number.}
4\text{Find the fourth-smallest number.} \\ \text{Swap it with the fourth number.}
b

The algorithm below contains a bug. Complete the table by writing the output for each step of the algorithm.

Step Number Algorithm StepOutput
1\text{Find the smallest number.} \\ \text{Swap it with the first number.}
2\text{Find the second-smallest number.} \\ \text{Swap it with the second number.}
3\text{Find the third-smallest number.} \\ \text{Swap it with the third number.}
4\text{Find the third-smallest number.} \\ \text{Swap it with the third number.}
c

Now, which step contains the bug? Explain your answer.

3

Consider the following list of numbers: 4, \,9, \,8, \,1, \,7

a

Complete the table by writing the output for each step of the insertion sort algorithm for the above list of numbers.

Step Number Algorithm StepOutput
1\text{Compare the second number with the first number.} \\ \text{If it is less than the first number, insert it before the} \\ \text {first number.}
2\text{Compare the third number with the first two numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 3 \text{ numbers are in ascending order.}
3\text{Compare the fourth number with the first three numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 4 \text{ numbers are in ascending order.}
4\text{Compare the fifth number with the first four numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 5 \text{ numbers are in ascending order.}
b

The algorithm below contains a bug. Complete the table by writing the output for each step of the algorithm.

Step Number Algorithm StepOutput
1\text{Compare the second number with the first number.} \\ \text{If it is less than the first number, insert it after the} \\ \text {first number.}
2\text{Compare the third number with the first two numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 3 \text{ numbers are in ascending order.}
3\text{Compare the fourth number with the first three numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 4 \text{ numbers are in ascending order.}
4\text{Compare the fifth number with the first four numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 5 \text{ numbers are in ascending order.}
c

Now, which step contains the bug? Explain your answer.

4

Consider the following list of numbers: 3, \, 8, \,5,\, 2,\, 4

a

Complete the table by writing the output for each step of the insertion sort algorithm for the above list.

Step Number Algorithm StepOutput
1\text{Compare the second number with the first number.} \\ \text{If it is less than the first number, insert it before the} \\ \text {first number.}
2\text{Compare the third number with the first two numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 3 \text{ numbers are in ascending order.}
3\text{Compare the fourth number with the first three numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 4 \text{ numbers are in ascending order.}
4\text{Compare the fifth number with the first four numbers.} \\ \text{Insert the number in the correct position so that the first} \\ 5 \text{ numbers are in ascending order.}
b

Write a step that could be used as a replacement for Step 1 so that the algorithm still produces the desired result.

5

Consider the following pseudocode:

a

What is the output of this code?

b

Which line contains a bug? Explain your answer.

1\text{START}
2 \text{SET } a=18
3\text{IF } a \, /\, 2 \text{ IS integer}
4\quad \text{THEN PRINT } a \text{ is odd}
5\quad \text{ELSE PRINT }a \text{ is odd}
6\text{END IF}
7\text{END}
6

Consider the following list of numbers: 9, \,4, \,6, \,7, \,3

a

Each step of the linear search algorithm is listed below.

Step NumberAlgorithm Step
1\text{Value}=6
2\text{If first number in list} = \text{Value then print } 1
3\text{If second number in list} = \text{Value then print } 2
4\text{If third number in list} = \text{Value then print } 3
5\text{If fourth number in list} = \text{Value then print } 4
6\text{If fifth number in list} = \text{Value then print } 5
i

Which step of the algorithm produces an output?

ii

What is the output of this algorithm?

b

The algorithm below contains a bug.

Step NumberAlgorithm Step
1\text{Number to be found}=\text{Value}
2\text{If Value}= \text{first number in list then print } 1
3\text{If Value}= \text{second number in list then print } 2
4\text{If Value}= \text{third number in list then print } 3
5\text{If Value}= \text{fourth number in list then print } 4
6\text{If Value}= \text{third number in list then print } 5
i

Which steps of the algorithm produce an output?

ii

What are the outputs of these steps of the algorithm?

c

Now, which step contains the bug?

7

Consider the following pseudocode which is meant to calculate the mean of two numbers:

a

What is the output of the code?

b

Which line contains a bug? Explain your answer.

1\text{START}
2 \text{SET } a=7
3\text{SET } b=6
4\text{SET } m=(a+b)\,/\,4
5\text{PRINT } m
6\text{END}
8

Consider the following pseudocode which is meant to calculate the mean of a set of numbers:

a

What is the final value of \text{sum}?

b

What is the final value of a?

c

What is the final value of n?

d

Now, what is the output of this code?

e

Which line contains a bug? Explain your answer.

1\text{START}
2\text{SET } a =3
3\text{SET sum}=0
4\text{SET } n = 0
5\text{WHILE } a < 10
6\qquad \text{sum} = \text{sum} + a
7\qquad a = a + 1
8\qquad n = n + 1
9\text{END WHILE}
10\text{PRINT sum}\, / \,a
11\text{END}
9

The factorial of a number n is given by \\ n!=n \times (n-1) \times (n-2) \times ... \times 2 \times 1.

So 4! = 4 \times 3 \times 2 \times 1= 24.

Consider the given pseudocode which is meant to calculate the factorial of a number n:

a

What is the output of the code if n = 8?

b

Now, which line contains the bug? Explain your answer.

1\text{START}
2\text{SET } a = 1
3\text{SET } f = 1
4\text{WHILE }a < n
5\qquad f = a * f
6\qquad a = a + 1
7\text{END WHILE}
8\text{PRINT } f
9\text{END}
10

Consider the following pseudocode which is meant to calculate the sum of the first n natural numbers:

a

What is the output of the code if n = 7?

b

Now, which line contains the bug?

1\text{START}
2\text{SET } a = 1
3\text{SET sum } = 0
4\text{WHILE }a <= n
5\qquad \text{sum} = a-\text{sum}
6\qquad a = a + 1
7\text{END WHILE}
8\text{PRINT sum}
9\text{END}
11

Consider the following pseudocode which sorts a list of five numbers from smallest to largest. The outputs of the code are also given.

1\text{START}
2\text{SET list } = [6, \,9, \,8, \,1, \,7]
3\text{SET } a= 0
4\text{FOR } n \text{ FROM } 1 \text{ TO } 4
5 \quad a = \text{list element at position } n
6\quad \text{FOR } m \text{ FROM } (n + 1) \text{ TO } 5
7\qquad \text{IF list element at position } m < a
8\qquad \quad a = \text{list element at position } m
9\qquad \text{END IF}
10\quad \text{END FOR}
11\quad \text{SWAP } a \text{ WITH list element at position } n
12\quad \text{PRINT list}
13\text{END FOR}
14\text{END}
OUTPUTS:
1, \,9,\, 8,\, 6,\, 7
1, \,6, \,8, \,9, \,7
1, \,6, \,7, \,9,\, 8
1, \,6, \,7, \,8, \,9
a

Line 4 is replaced with the following: \text{FOR } n \text{ FROM } 1 \text{ TO } 5.

What is the new set of outputs?

b

Explain why the order of the numbers is the same for the last two outputs.

c

Line 7 is rthen eplaced with the following: \text{IF list element at position } m > a.

What is the new set of outputs?

d

Line 6 is then replaced with the following: \text{FOR } m \text{ FROM } 1 \text{ TO } 5.

What is the new set of outputs?

e

Explain why the replacement Line 7 results in an unsorted list.

12

Consider the following pseudocode which sorts a list of five numbers from smallest to largest:

1\text{START}
2\text{SET list } = [4, \,9,\, 7,\, 3,\, 6]
3\text{SET } a= 0
4\text{FOR } n \text{ FROM } 1 \text{ TO } 4
5 \quad a = \text{list element at position } n
6\quad \text{FOR } m \text{ FROM } (n + 1) \text{ TO } 5
7\qquad \text{IF list element at position } m < a
8\qquad \quad a = \text{list element at position } m
9\qquad \text{END IF}
10\quad \text{END FOR}
11\quad \text{SWAP } a \text{ WITH list element at position } n
12\quad \text{PRINT list}
13\text{END FOR}
14\text{END}
OUTPUT:
3, \,9, \,7, \,4, \,6
3, \,4,\, 7,\, 9,\, 6
3, \,4,\, 6,\, 9,\, 7
3, \,4,\, 6,\, 7,\, 9
a

The pseudocode was changed to give the following outputs:

i

Which line most likely contained the bug?

ii

Write a replacement line that could have resulted in this output.

OUTPUT:
3, \,9,\, 7,\, 3,\, 6
3, \,3,\, 7,\, 3,\, 6
3, \,3, \,3, \,3, \,6
3,\, 3,\, 3,\, 3, \,6
b

The pseudocode was changed to give the following outputs:

i

Which line most likely contains the bug?

ii

Write a replacement line that could have resulted in this output.

OUTPUT:
3, \,9, \,7, \,4, \,6
3, \,4,\, 7,\, 9,\, 6
3, \,4,\, 7,\, 9,\, 6
3, \,4, \,7,\, 9,\, 6
Sign up to access Worksheet
Get full access to our content with a Mathspace account

What is Mathspace

About Mathspace