WA Computer Science ATAR Year 11 — Standard Algorithms Hangman

The 35 key terms

1scores[1]

Accesses the array element at index 1, using square brackets to specify the position.

2for i in range(len(arr)):

Loops i through every index of arr, so arr[i] can be read or changed and you know each element's position. Used for totals, finding the largest value and editing in place.

3FOR i FROM 1 TO n

A loop that repeats its instructions a fixed number of times, counting the variable i from 1 up to n

4WHILE condition DO

A loop that repeats its instructions for as long as the given condition remains true, checked before each repetition

5IF-THEN-ELSE

A selection structure that runs one set of instructions if a condition is true, and a different set if it is false

7standard method

A tried-and-tested algorithm for a common task, such as totalling, counting, max/min, average, linear search or bubble sort, that programmers reuse instead of inventing a new solution.

8count <- count + 1

A counter. It adds 1 to a variable each time a loop repeats. Set it to 0 before the loop. An accumulator works the same way: total <- total + x adds a value each time.

9Total ← Total + Value

Totalling keeps a running sum. Set Total to 0 before the loop, add each Value to Total inside the loop, then output Total after the loop. Counting adds 1 each time instead of the value.

10Total ← Total + Number

In a trace table, this line makes the Total column grow by the new Number on every pass. Total must start at 0 before the loop, and this line must sit inside the loop.

11Count ← Count + 1

Counting adds 1 to a counter each time something happens. Start the counter at 0, add 1 (not the item's value), and do it for every item or only for matches.

12IF Mark[i] >= 50 THEN Count ← Count + 1

An IF inside a loop adds 1 to Count only when an item meets the condition, so Count tallies the matching items. A total adds the item's value instead.

14IF Num > Max THEN Max ← Num

Keep the largest value seen so far in Max. Start Max with the first value, then replace it whenever a later value is larger. Starting at 0 can fail if all values are negative.

15IF Number > Largest THEN

In a trace table, Largest only changes on rows where this test is true. If Number is equal or smaller, the Largest cell stays the same as the row above. Smallest uses < instead.

16Average ← Total / Count

The average is the total of the values divided by how many values there are. It needs both a total and a count, can be a REAL, and is not allowed when the count is zero.

17single pass

One loop visits each item once, updating the total, count, maximum and minimum together. The average is worked out after the loop ends, as Total / Count.

18linear search

Checks each item in a list in turn, from the start, until the target is found or the end of the list is reached. It works on unsorted data.

20Found ← FALSE

Sets a BOOLEAN flag to FALSE before a FOR loop. The loop sets Found to TRUE if an element equals the target. After the loop, Found shows whether the target was seen.

21WHILE Found = FALSE AND Index <= 10 DO

Keeps searching while the target has not been found AND the end of the list has not been reached, so the loop stops early as soon as Found becomes TRUE.

22trace table

A table that records the index, the element compared and the Found flag on each pass of a linear search, so you can follow it step by step.

23Binary Search

An algorithm that repeatedly halves a sorted array to quickly find a target value.

24mid ← (low + high) DIV 2

Each row of a binary search trace table updates low, high and mid. The range halves each step until the target is found or low becomes greater than high.

25while low <= high:

The binary search loop: while low <= high, check the middle item of a sorted list, then move low or high to halve the search range each time.

26bubble sort

A sorting method that compares neighbouring items and swaps them if in the wrong order, repeating passes until the list is sorted. The largest value bubbles to the end each pass.

27Temp ← Marks[Index]

Saves the value of Marks[Index] in Temp so it is not lost. Marks[Index] can then be overwritten, and Temp is copied into Marks[Index + 1] to finish the swap.

28IF Marks[Index] > Marks[Index + 1] THEN

One pass: a FOR loop compares each item with its neighbour and swaps them if the first is larger, so the biggest value moves to the end.

29FOR Pass ← 1 TO n - 1

Outer loop of a bubble sort: it runs n - 1 passes. Inside it, an inner FOR loop compares neighbours and swaps them if out of order, so the whole array ends up sorted.

30UNTIL Swapped = FALSE

A BOOLEAN flag set to FALSE before each pass and to TRUE whenever a swap happens. The bubble sort stops when a full pass leaves it FALSE, meaning no swaps were needed and the data is sorted.

31bubble sort trace

Writing out the array after every pass, showing each comparison and swap, plus the Temp and Swapped values, to see how a bubble sort puts the data in order.

32Selection Sort

An algorithm that repeatedly finds the smallest remaining element and swaps it into its correct position.

35log2 n

Worst-case comparisons for binary search: it halves a sorted range, so 1000 items need about 10 steps. Linear search needs up to n, so 1000 items could need 1000 comparisons.

37algorithm efficiency

How many steps an algorithm takes as data grows, and what it needs (e.g. sorted data for binary search). Compare it to choose between linear or binary search, selection or quick sort.

38key words

Words in a problem, like add up, how many, highest, average, find or put in order, that show which standard method to use: totalling, counting, max/min, average, search or sort.

39algorithm

A step-by-step method for solving a problem, like search or sort. Choose one by matching its input and output to your data, then wrap it in a function to reuse it.

40test data

Chosen inputs, each with the output you expect, picked so every path (branch) through an algorithm gets tested. Compare the real result to the expected output.

41logic error

A mistake in an algorithm's steps that lets it run but gives wrong results, e.g. a total not set to 0, a loop going past the array end, or using > instead of <.