Searching Algorithms: Linear, Binary & Binary Tree | AQA A Level Computer Science 7517 | 20 Workshee

Searching algorithms practice for AQA A Level Computer Science (7517): twenty
different worksheets on linear search, binary search and binary tree search,
each with a complete answer key.

Every sheet runs all three algorithms on the same values, looking for the same
target: the unsorted list, the same list sorted, and the binary search tree
built from it. A student finishes the sheet having counted, say, twelve
comparisons against four and five - and question 4 then asks them to explain
the gap they have just measured, rather than to recite O(n) and O(log n) from
memory.

WHAT YOU GET

• 20 worksheets, 4 pages each, numbered 01 to 20
• 20 matching answer keys
• A contents table giving the number of values, the mark total and the
  comparison counts of every sheet, so you can set one where the contrast is
  stark or one where it is narrower

WHAT IS ON EVERY SHEET

Question 1 traces a linear search of an unsorted list and asks for the number
of comparisons. Question 2 traces a binary search of the same values sorted,
against the pseudocode printed on the sheet, in a table with Bottom, Top,
Midpoint and the value there. Question 3 traces a binary tree search of the
same values. Question 4 asks for the time complexity of all three, for an
explanation of the gap between the first two counts, and for the largest
number of comparisons a binary search could need on a list of several thousand
items.

The first row of every trace table is completed, so there is no doubt about
where a trace begins. Sheets run from 19 to 20 marks.

THE MIDPOINT RULE IS PRINTED ON THE SHEET

On an even number of items there is no middle item, and a trace question that
does not say which way to round has two correct answers. Every worksheet
states the rule in its conventions and again in the pseudocode: Midpoint is
(Bottom + Top) DIV 2, integer division, rounded down. Whatever your department
teaches, the trace the sheet asks for is the one determined by what the
student is looking at.

WRITTEN FOR AQA

The specification asks students to “know and be able to trace and analyse the
complexity of the linear search algorithm”, and the same for binary search and
binary tree search - AQA 7517, section 4.3.4, printed in the header of every
page. Both verbs are on the sheet: three traces, then the complexity of each
with a reason, in the specification’s own terms.

The pseudocode follows AQA’s own written conventions: DIV for integer
division, LEN for the length of an array, arrays indexed from 0, and the not-
equal and less-than-or-equal symbols as AQA writes them.

FORMAT

PDF, A4, print-ready. Twenty genuinely different versions, so you already have
a fresh sheet for every class, every resit and every homework.

Licensed for the purchasing teacher and their own classes.