Tracing a standard algorithm

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Tracing a maximum algorithm on the list 4, 9, 2. Max starts as 4. What is Max after the whole list is traced?

A 2

B 9

2. Which is the best way to check a totalling algorithm using a trace table?

A Use a short list such as 3, 5, 2 and follow Total step by step

B Run it once with a list of 1000 values and only look at the end

3. A trace table for a bubble sort pass on 5, 3, 8 compares 5 and 3. What happens next?

A They are swapped, giving 3, 5, 8

B They are left alone, giving 5, 3, 8

4. A trace of a linear search for the value 7 in the list 2, 7, 9 finishes. What does the trace table show?

A Found stays FALSE because 7 is not the first item

B Found is TRUE after the second item is checked

5. Tracing a linear search for 5 in the list 2, 7, 9. What is the value of Found at the end?

A FALSE, because no item matched

B TRUE, because the loop reached the end

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1Max ← 4, 9, 9, 9 across the rows of a trace table		AThe Total column shows each value instead of adding to the running total
2Found = FALSE in the last row of a search trace		BThe maximum is only replaced when a larger value is found, so it stays at 9
3A bubble sort pass compares neighbours and swaps them if they are in the wrong order		CIF Number > Max THEN Max ← Number
4A trace for a maximum starts with Max set to the first item, then updates it		DThe search value was not in the list, so the whole list was checked without a match
5Trace of a total for 3, 5, 2 shows Total as 3, 5, 2		EThe trace ignores that 7 is found at the second item, so Found should be TRUE
6Trace of a search for 7 in 4, 7, 9 carries on to 9 and ends with Found = FALSE		FIF List[i] > List[i + 1] THEN swap them

Definitions

trace table

Fill in the Blanks

Complete each line of code by filling in the missing parts.

Max ← Num[1] FOR I ← 2 TO 5 IF Num[I] _ Max THEN Max ← Num[I]

I ← 1 Found ← FALSE WHILE I <= 5 ___ Found = FALSE

// Trace: Found never changes to TRUE IF Found = FALSE THEN ______ "Not found"

Temp ← Num[I] Num[I] ← Num[I + 1] Num[I + 1] ← ____

// Num has 5 values: Num[1] to Num[5] FOR I ← 1 TO _ // compare Num[I] with Num[I + 1]

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A Max ← Numbers[2]

B FOR Index ← 2 TO 5

C IF Numbers[Index] > Max THEN

D Max ← Numbers[Index]

E ENDIF

F NEXT Index

Question 2

A Total ← 0

B FOR Index ← 1 TO 5

C Total ← Total + Index

D NEXT Index

E Average ← Total / 5

F OUTPUT Average

Question 3

A Count ← 0

B FOR Index ← 1 TO 5

C IF Mark[Index] >= 50 THEN

D Count ← Mark[Index]

E ENDIF

F NEXT Index

Question 4

A Min ← Numbers[1]

B FOR Index ← 2 TO 5

C IF Numbers[Index] > Min THEN

D Min ← Numbers[Index]

E ENDIF

F NEXT Index

Question 5

A Found ← TRUE

B FOR Index ← 1 TO 5

C IF Item[Index] = Target THEN

D Found ← TRUE

E ENDIF

F NEXT Index

Answer Key

Tracing a standard algorithm

Section A: Quick Questions

B — 9

A — Use a short list such as 3, 5, 2 and follow Total step by step

A — They are swapped, giving 3, 5, 8

B — Found is TRUE after the second item is checked

A — FALSE, because no item matched

Section B: Match the Pairs

Max ← 4, 9, 9, 9 across the rows of a trace table → The maximum is only replaced when a larger value is found, so it stays at 9

Found = FALSE in the last row of a search trace → The search value was not in the list, so the whole list was checked without a match

A bubble sort pass compares neighbours and swaps them if they are in the wrong order → IF List[i] > List[i + 1] THEN swap them

A trace for a maximum starts with Max set to the first item, then updates it → IF Number > Max THEN Max ← Number

Trace of a total for 3, 5, 2 shows Total as 3, 5, 2 → The Total column shows each value instead of adding to the running total

Trace of a search for 7 in 4, 7, 9 carries on to 9 and ends with Found = FALSE → The trace ignores that 7 is found at the second item, so Found should be TRUE

Section C: Definitions

trace table — A table with a column per variable and a row per step. Use it to test an algorithm such as total, maximum, search or bubble sort by following a short list of values by hand.

Section D: Fill in the Blanks

Max ← Num[1]
FOR I ← 2 TO 5
   IF Num[I] > Max THEN Max ← Num[I]

I ← 1
Found ← FALSE
WHILE I <= 5 AND Found = FALSE

// Trace: Found never changes to TRUE
IF Found = FALSE THEN OUTPUT "Not found"

Temp ← Num[I]
Num[I] ← Num[I + 1]
Num[I + 1] ← Temp

// Num has 5 values: Num[1] to Num[5]
FOR I ← 1 TO 4
   // compare Num[I] with Num[I + 1]

Section E: Spot the Error

A — Max must start as the first value, Numbers[1]. Tracing 9, 4, 2, 7, 3 with Max starting as 4 gives 7, not 9. It should be Max ← Numbers[1].

C — The loop adds the counter (1, 2, 3...) instead of the array value. A trace table shows Total as 1, 3, 6... whatever the marks are. It should be Total ← Total + Mark[Index].

D — Count is overwritten with the mark instead of going up by one, so a trace shows Count jumping to mark values. It should be Count ← Count + 1.

C — With > the trace table finds the largest value, not the smallest. To find the minimum the test must be Numbers[Index] < Min.

A — Found must start as FALSE. If it starts TRUE, a trace for a target that is not in the list still ends with Found = TRUE. It should be Found ← FALSE.