Algorithms: what they are, algorithms in text, and the middle item of a list

Highlights only0 highlighted

Decision Mathematics 1 is examined on its own paper, WDM11/01, and algorithms is the topic it opens with: in the last three series about a fifth of the paper's 75 marks came from it, and the first question was a bin-packing question every time, usually with a sort or a search attached.

This section is about algorithms in general: what makes a set of instructions an algorithm, how one is written in words, how to run one by hand with a trace table, and the single rule for the "middle" of a list that the rest of the unit leans on.

How the marks work

(D1)

M1 is a method mark: the algorithm attempted in a recognisable form, to a stated depth (for example, the first five items packed, or a full first pass of a sort). dM1 depends on the M mark before it and is rare on D1.

A1 needs its M mark and checks a further stage of the same process; one M mark usually opens a run of two to four A marks, and the last is often cso (correct solution only). A1ft follows through from your own earlier stage.

B1 stands alone: a stated fact, a reason, a conclusion. B1ft follows through from your earlier value.

awrt means "anything which rounds to"; isw means correct work is not undone by later work; a misread that keeps the question's character costs two A or B marks.

In this unit a correct final answer with no visible process earns little or nothing: a sort with no passes, a search with no pivots, or a bound with no division.

The idea: a recipe a machine could follow

An algorithm is a finite sequence of precise instructions which, followed exactly, solves a problem.

You have used algorithms for years without the name: column addition, long division and the steps for solving a quadratic by the formula are all algorithms.

What makes them algorithms is not that they are mathematical but that they need no judgement.

Anyone, or any machine, that carries out the steps correctly gets the same answer from the same input.

That gives four properties to look for:

1. Input. The algorithm starts from stated data (two numbers, a list, a network).

2. Precise steps. Every instruction has exactly one meaning. "Add a few" or "choose a suitable value" is not an instruction a machine can carry out.

3. It stops. After a finite number of steps the algorithm reaches a stop instruction, for every allowed input.

4. Output. It ends with a result: a number, a sorted list, a route.

Decision mathematics is the study of algorithms that make decisions: how to pack items into as few bins as possible, how to sort a list, how to find the shortest route through a network, how to schedule a project, how to share out limited resources.

You need "the general ideas of algorithms and the implementation of an algorithm given by a flow chart or text".

You must be able to carry out an algorithm you are given, in either form, and say what it does.

You are not asked how fast an algorithm is: One limit is worth knowing from the start: "The order of an algorithm is not expected."

Algorithms written in text

An algorithm in text is a numbered list of steps.

Three kinds of instruction appear.

Assignments such as "Let $T = T + B$ ". The right-hand side is worked out with the current values, and the answer becomes the new value of the letter on the left. "Let $T = T + B$ " does not claim that $T$ equals $T + B$ ; it replaces $T$ by $T + B$ .

Conditions such as "If $A$ is odd, ..." The instruction runs only when the condition is true.

Jumps such as "Go to Step 3". This is how an algorithm repeats a block of steps (a loop), and it is also how it stops: some condition sends it to the output step.

Many D1 algorithms use the function INT: $\text{INT}(x)$ is the integer part of $x$ , so $\text{INT}(7.8) = 7$ , $\text{INT}(4) = 4$ and $\text{INT}(0.375) = 0$ .

For the positive numbers used on this paper it simply cuts off everything after the decimal point.

Running an algorithm by hand: the trace table

To run an algorithm by hand you keep a trace table: one column for every variable, one column for each condition tested, and a new row each time you go round the loop.

Write a value only when it changes, read the most recent value in each column when you need it, and finish with the output written clearly.

The examiners give the method mark for the first row of the table complete and the accuracy marks for later rows, so a neat table is worth marks in itself.

Worked example 1: tracing an algorithm written in text

An algorithm is given by these steps.

Step 1: Input $A$ and $B$ , two positive integers.

Step 2: Let $T = 0$ .

Step 3: If $A$ is odd, let $T = T + B$ .

Step 4: Let $A = \text{INT}(A/2)$ and let $B = 2B$ .

Step 5: If $A = 0$ , go to Step 6. Otherwise, go to Step 3.

Step 6: Output $T$ .

(a) Complete a trace table for the algorithm with $A = 37$ and $B = 23$ . (3)

(b) State the relationship between the output and the inputs. (1)

(a) Each row records the values at Step 3, before Step 4 halves $A$ and doubles $B$ .

$A$

$B$

$A$ odd?

$T$

Yes

115

184

115

368

115

736

Yes

851

1. First row complete: $A = 37$ is odd, so $T = 0 + 23 = 23$ . M1

2. Rows two to four: $A$ becomes 18, 9, 4 while $B$ becomes 46, 92, 184; only $A = 9$ adds to $T$ , giving 115. A1

3. Rows five and six: $A = 2$ adds nothing; $A = 1$ is odd, so $T = 115 + 736 = 851$ ; then $A = \text{INT}(1/2) = 0$ and the algorithm goes to Step 6. Output: 851 A1

(b) The output is the product of the inputs: $37 \times 23 = 851$ . B1

Answer: output 851, which is $A \times B$ .

Check: $37 \times 23 = 740 + 111 = 851$ .

Why it works (not examined). Halving $A$ and noting whether it is odd reads off the binary digits of $A$ , from the right: $37 = 32 + 4 + 1$ , and the rows where $A$ is odd are exactly the rows where $B$ has been doubled 0, 2 and 5 times.

So the algorithm adds $23 + 4 \times 23 + 32 \times 23 = 37 \times 23$ .

Each row keeps the quantity $A \times B + T$ unchanged (when $A$ is even, halving $A$ and doubling $B$ keep the product; when $A$ is odd, the half that INT throws away is $B$ , which has just been added to $T$ ), and when $A$ reaches 0 that quantity is $T$ alone.

An unchanging quantity like this is called a loop invariant, and it is how computer scientists prove that an algorithm is correct.

It is also why this method, sometimes called "Russian peasant multiplication", is how a computer multiplies in binary.

The middle item of a list

Three algorithms in this unit (quick sort, binary search, and through them bin packing) keep asking for the middle item of a list or part of a list.

With an odd number of items there is an obvious middle.

With an even number there are two candidates, and if different students chose differently their answers would differ and could not be marked against one scheme.

So the choice is fixed in the D1 glossary, and the rule to follow is: "Whenever finding the middle item of any list, the method defined in the glossary must be used."

The rule: in a list of $N$ items, the middle item has position $\left[\tfrac{1}{2}(N + 1)\right]$ if $N$ is odd and $\left[\tfrac{1}{2}(N + 2)\right]$ if $N$ is even.

For an even list this is the right-hand of the two central items: with 6 items it is the 4th, not the 3rd.

The rule applies to every sublist too.

If the part of the list still in play runs from position $i$ to position $j$ , it holds $N = j - i + 1$ items and its middle is at position $\tfrac{1}{2}(i + j)$ , rounded up when that is not a whole number.

Both ways give the same answer: for positions 6 to 13 there are 8 items, the glossary gives the $\tfrac{1}{2}(8 + 2) = 5$ th of them, which is position $6 + 4 = 10$ ; and $\tfrac{1}{2}(6 + 13) = 9.5$ rounds up to 10.

Worked example 2: middle items

Write down the position of the middle item in a list of (a) 9 items, (b) 8 items, (c) 4 items, (d) 2 items.

(e) A binary search is working on the items in positions 6 to 13 of a list.

Write down the position of the middle item.

(5)

1. (a) $N = 9$ is odd: $\tfrac{1}{2}(9 + 1) = 5$ , the 5th item. B1

2. (b) $N = 8$ is even: $\tfrac{1}{2}(8 + 2) = 5$ , the 5th item (the right-hand of the 4th and 5th). B1

3. (c) $N = 4$ : $\tfrac{1}{2}(4 + 2) = 3$ , the 3rd item. B1

4. (d) $N = 2$ : $\tfrac{1}{2}(2 + 2) = 2$ , the 2nd item. A two-item list still has a middle, and it is the second item. B1

5. (e) $\tfrac{1}{2}(6 + 13) = 9.5$ , rounded up: position 10. B1

Answer: 5th, 5th, 3rd, 2nd, position 10.

Part (d) matters most in practice: in quick sort, a two-item sublist that already looks sorted still takes a pivot, and the pivot is its second item.

Worked example 3: an exam-length trace

An algorithm acts on a list of six numbers $x_1, x_2, \ldots, x_6$ .

Step 1: Let $M = x_1$ , $P = 1$ and $k = 2$ .

Step 2: If $x_k > M$ , let $M = x_k$ and let $P = k$ .

Step 3: Let $k = k + 1$ .

Step 4: If $k \leq 6$ , go to Step 2.

Step 5: Output $M$ and $P$ .

The list is 19, 7, 33, 12, 40, 25.

(a) Complete the trace table for the algorithm, starting with $M = 19$ , $P = 1$ and $k = 2$ . (3)

(b) Explain what the algorithm outputs, in general. (2)

(a)

$k$

$x_k$

$x_k > M$ ?

$M$

$P$

Yes

1. Row $k = 2$ complete: $7 > 19$ is false, so $M$ and $P$ are unchanged. M1

2. Rows $k = 3$ and $k = 4$ : 33 replaces 19 with $P = 3$ ; 12 changes nothing. A1

3. Rows $k = 5$ and $k = 6$ : 40 replaces 33 with $P = 5$ ; 25 changes nothing; then $k = 7$ fails Step 4. Output: $M = 40$ , $P = 5$ A1

(b) $M$ is the largest number in the list B1 and $P$ is its position in the list B1.

Answer: the algorithm outputs 40 and 5: the largest value and where it sits.

The loop invariant here is "after looking at $x_k$ , $M$ is the largest of $x_1, \ldots, x_k$ ", which is why the final $M$ is the largest of all six.

Where this leads

Every later topic in D1 is an algorithm with the same four features: bin packing and sorting in this unit, Prim's, Kruskal's and Dijkstra's algorithms on networks, route inspection and the nearest neighbour algorithm, and the forward and backward passes of critical path analysis.

Computer science studies the same objects with a sharper interest in speed, and Further Mathematics takes decision mathematics further.

The habits you build here (one column per variable, one row per pass, write each new value, state the output) are the habits every later D1 question rewards.

Key terms

Algorithm: a finite sequence of precise instructions which, followed exactly, solves a problem; it has an input, ends after a finite number of steps, and gives an output.

Trace table: a table with a column for each variable (and each condition tested) recording the values as an algorithm runs.

INT(x): the integer part of $x$ ; for positive $x$ , the number with everything after the decimal point removed.

Middle item (D1 glossary): In a list containing N items the 'middle' item has position [½(N + 1)] if N is odd, [½(N + 2)] if N is even, so that if N = 9, the middle item is the 5th and if N = 6 it is the 4th.

Formulae for this unit

The D1 cover lists only the answer book and a calculator; no D1 item needs the formulae booklet. Students are expected to know the D1 glossary.

Learn it: the middle item rule above, and its sublist form "position $\tfrac{1}{2}(i + j)$ , rounded up".

Learn it: the lower bound for the number of bins, $\dfrac{\text{sum of the items}}{\text{capacity of one bin}}$ rounded up (taught later in this unit). It is printed nowhere in the exam.

Exam tip

When a question says "complete the table", fill in every cell of every row the algorithm reaches, and write the output on its own line at the end (on the "Output" line where the answer book prints one).

The first mark is for a complete first row, and the last mark is lost if the output is left only inside the table.

Common mistakes

Overwriting the wrong value. In "Let $A = \text{INT}(A/2)$ and let $B = 2B$ ", both new values come from the old ones. Work out each right-hand side from the current row, then write the new row.

Stopping one row early or late. The test in a "go to" step decides whether the loop runs again. Apply it exactly: " $k \leq 6$ " still runs when $k = 6$ .

Choosing the left-hand middle of an even list. The glossary rule gives the right-hand middle: the 4th of 6, the 5th of 8, the 2nd of 2. Write the calculation $\tfrac{1}{2}(N + 2)$ so the examiner can see it.

Describing what the steps do instead of what the output is. "It halves $A$ and doubles $B$ " earns nothing when the question asks what the algorithm outputs; "the product of $A$ and $B$ " does.

Check your understanding

1. A list contains $N$ items.

(a) Write down the position of the middle item when $N = 15$ . (1)

(b) Write down the position of the middle item when $N = 12$ . (1)

Total: [3]

2. An algorithm is given by these steps.

Step 1: Input $A$ and $B$ , two positive integers.

Step 2: Let $Q = 0$ .

Step 3: If $A < B$ , go to Step 6.

Step 4: Let $A = A - B$ and let $Q = Q + 1$ .

Step 5: Go to Step 3.

Step 6: Output $Q$ and $A$ .

(a) Complete a trace table for the algorithm with $A = 47$ and $B = 9$ . (3)

(b) Explain what the two outputs represent. (2)

Total: [5]

3. A set of instructions for finding a route through a town contains the step "If the traffic looks heavy, choose a quieter road". Explain why this set of instructions is not an algorithm. (1)

Total: [1]

4. A student says that, in a list of 8 items, the middle item is the 4th, "because 8 divided by 2 is 4". Explain why the student is wrong, and state the correct position. (2)

Total: [2]

5. An algorithm is given by these steps.

Step 1: Input $n$ , a positive integer.

Step 2: Let $S = 0$ and let $k = 1$ .

Step 3: Let $S = S + k^2$ .

Step 4: If $S > n$ , go to Step 6.

Step 5: Let $k = k + 1$ and go to Step 3.

Step 6: Output $k$ .

(a) Complete a trace table for the algorithm with $n = 60$ . (3)

(b) Explain what the output represents. (2)

Total: [5]

6. A student claims that two people who carry out the same algorithm correctly on the same input might get different outputs, "because people think differently". Explain whether the student is right. (2)

Total: [2]

Answers

1. (a) $\tfrac{1}{2}(15 + 1) = 8$ : the 8th item B1 (b) $\tfrac{1}{2}(12 + 2) = 7$ : the 7th item B1 (c) $\tfrac{1}{2}(7 + 12) = 9.5$ , rounded up: position 10 (6 items, the 4th of them) B1

2. (a) Trace (values of $A$ and $Q$ after each visit to Step 4): $A$ = 47, 38, 29, 20, 11, 2 and $Q$ = 0, 1, 2, 3, 4, 5; at Step 3, $2 < 9$ sends the algorithm to Step 6. First row with $A = 38$ , $Q = 1$ M1; rows to $A = 20$ , $Q = 3$ A1; final rows and output $Q = 5$ , $A = 2$ A1 (b) $Q$ is the whole-number quotient when 47 is divided by 9 (how many times 9 goes into 47) B1; $A$ is the remainder B1. Check: $5 \times 9 + 2 = 47$ .

3. The instruction needs a judgement ("looks heavy", "quieter"), so it is not precise: two people could carry it out differently B1

4. The glossary rule for an even number of items is $\tfrac{1}{2}(N + 2)$ , which takes the right-hand of the two central items B1; the middle item is the 5th B1

5. (a) $k = 1$ , $S = 1$ , $1 > 60$ ? No M1; $k = 2$ , $S = 5$ , No; $k = 3$ , $S = 14$ , No; $k = 4$ , $S = 30$ , No A1; $k = 5$ , $S = 55$ , No; $k = 6$ , $S = 91$ , Yes. Output: 6 A1 (b) The output is the least number $k$ for which $1^2 + 2^2 + \cdots + k^2$ is greater than $n$ B1, so here the first six squares are needed before their sum passes 60 (the first five sum to 55) B1

6. The student is wrong. Every step of an algorithm is precise and needs no judgement B1, so the same input always produces the same output, whoever (or whatever) carries the algorithm out B1

Algorithms: what they are, algorithms in text, and the middle item of a list

Your course level