Chapter 11 · Computational thinking across units

The World of Algorithms Worksheet

11 questions Ordered procedures and tracing Euclid’s algorithm GCD and LCM Prime testing Remainders and simulations

Try each question before opening its solution.

Name: ________________________   Class: __________   Date: __________

Foundation

Euclid’s algorithm · 1 practice mark

Question 1

Which replacement preserves gcd(a,b) for positive integers a ≥ b?

  1. (a + b,a)
  2. (b, a mod b)
  3. (a − 1,b − 1)
  4. (2a,b)
Show step-wise answer

(b) (b, a mod b)

  1. Write a = qb + r.
  2. An integer divides both a and b exactly when it divides both b and r; replace the pair by (b,r).

Practice

Decimal representations and algorithms · 3 practice marks

Question 2

Convert 0.125 and 0.1666… to fractions. Explain how long division detects an eventually repeating decimal.

Show step-wise answer

0.125 = 1/8; 0.1666… = 1/6.

  1. 125/1000 reduces to 1/8.
  2. For x = 0.1666…, 10x = 1.666… and 100x = 16.666…; subtract to obtain 90x = 15.
  3. In long division record each remainder. A zero remainder terminates; a repeated remainder repeats the subsequent digits.

Decimal representations and algorithms · 3 practice marks

Question 3

Use a remainder-tracking algorithm to generate the decimal expansion of 2/7. Identify the recurring block.

Show step-wise answer

2/7 = 0.285714285714… .

  1. Divide 20 by 7: digit 2, remainder 6. Continue with ten times each remainder.
  2. The subsequent digits/remainders are 8/4, 5/5, 7/1, 1/3, 4/2.
  3. The original remainder 2 returns after six digits; the block 285714 repeats.

Tracing and termination · 3 practice marks

Question 4

Trace Euclid’s algorithm for gcd(252,198). Explain why the process terminates.

Show step-wise answer

gcd(252,198) = 18.

  1. 252 = 1 × 198 + 54; replace the pair by (198,54).
  2. 198 = 3 × 54 + 36; then 54 = 1 × 36 + 18.
  3. 36 = 2 × 18 + 0. The last non-zero remainder is 18.
  4. Successive non-zero remainders are smaller non-negative integers; this strictly decreasing process reaches zero.

GCD and LCM · 3 practice marks

Question 5

Using gcd(36,48) = 12, find their LCM. Check it is a multiple of both numbers.

Show step-wise answer

LCM = 144.

  1. For positive integers, gcd(a,b) × lcm(a,b) = ab.
  2. LCM = 36 × 48/12 = 144.
  3. 144/36 = 4 and 144/48 = 3, verifying both divisibilities.

Challenge

Tower of Hanoi · Explicit and recursive sequence rules · 4 practice marks

Question 6

Explain the recursive Tower of Hanoi algorithm for n disks and derive its minimum-move formula. Calculate it for 5 disks.

Show step-wise answer

T₀ = 0; Tₙ = 2Tₙ₋₁ + 1 = 2ⁿ − 1; 31 moves for 5 disks.

  1. Move the top n − 1 disks to the spare peg using the same rules.
  2. Move the largest disk to the destination; then move the n − 1 disks onto it.
  3. This is necessary as well as sufficient: the largest disk can move only after the smaller disks are cleared, and they must be moved back. Thus Tₙ = 2Tₙ₋₁ + 1.
  4. Tₙ + 1 = 2(Tₙ₋₁ + 1); starting at T₀ + 1 = 1 gives Tₙ = 2ⁿ − 1. T₅ = 31.

Testing collinearity · Testing right-angled triangles · 4 practice marks

Question 7

Describe a systematic algorithm to check if three distinct coordinate points form a triangle, and then whether that triangle is right-angled. Test A(1,1), B(4,1), C(4,5).

Show step-wise answer

The points form a triangle right-angled at B.

  1. First test collinearity, for example whether (xB − xA)(yC − yA) = (yB − yA)(xC − xA). If equal, there is no non-degenerate triangle.
  2. For the given points the products are 12 and 0, so they are not collinear.
  3. Compute the three squared distances: AB² = 9, BC² = 16, AC² = 25.
  4. Sort these values. The two smaller sum to the largest, so the angle at B is right.

Simulation and computational thinking · Experimental/empirical probability · Sample spaces and theoretical probability · 4 practice marks

Question 8

Write a step-by-step simulation of 1000 fair die throws to estimate the probability of an even outcome. State the theoretical target and why a simulation may differ from it.

Show step-wise answer

Choose uniform random integers 1–6; estimated probability = even count/1000; theoretical target 1/2.

  1. Initialise an even-outcome counter to zero.
  2. Repeat 1000 times: sample one of 1,2,3,4,5,6 with equal probability and increment the counter for 2,4 or 6.
  3. Divide the final counter by 1000.
  4. Three of six equally likely outcomes are even, so theoretical probability is 1/2. Random fluctuations mean a finite estimate need not be exactly 0.5.

Simulation and computational thinking · Probability trees and tables · Sample spaces and theoretical probability · 4 practice marks

Question 9

A learner lists sums 2,3,…,12 for two fair dice and assumes all sums are equally likely. Correct the model using a table and describe a simulation for estimating P(sum = 7).

Show step-wise answer

Use 36 equally likely ordered pairs; P(sum = 7) = 6/36 = 1/6.

  1. Make a 6-by-6 table: rows identify the first die and columns the second, giving 36 ordered pairs.
  2. Sum 7 occurs at (1,6), (2,5), (3,4), (4,3), (5,2), (6,1), so its probability is 1/6.
  3. Sums are not equally likely: sum 2 has only one ordered pair, while sum 7 has six.
  4. Simulate independent uniform throws of each die repeatedly, count sums of 7, and divide by total trials. Compare this relative frequency with 1/6.

Prime-testing algorithm · 4 practice marks

Question 10

Write an algorithm to test whether an integer n ≥ 2 is prime. Explain why checking possible divisors only up to √n is enough, and test n = 91.

Show step-wise answer

91 is composite: 91 = 7 × 13.

  1. Check each integer d starting at 2 while d² ≤ n.
  2. If n mod d = 0, report composite. If no such divisor is found, report prime.
  3. In a factor pair ab = n, both factors cannot exceed √n, since their product would exceed n.
  4. For 91, test 2 through 9; divisor 7 is found. Return composite rather than continuing indefinitely.

Valid algorithm inputs · 4 practice marks

Question 11

A decimal-division procedure stores remainders. Explain how it can distinguish termination from recurrence for positive integers p < q, and trace 3/8.

Show step-wise answer

3/8 = 0.375; the zero remainder indicates termination.

  1. Start with remainder p and an empty map of previously encountered remainders.
  2. At each step multiply the remainder by 10, take the quotient digit on division by q, and keep the new remainder.
  3. For 3/8: 30 gives 3 remainder 6; 60 gives 7 remainder 4; 40 gives 5 remainder 0.
  4. Stop on zero. If a non-zero remainder repeats instead, the intervening block repeats. This distinguishes the two outcomes.