Computational Thinking and Problem-solving

• Linear search checks every item in turn: O(n). Binary search halves a sorted list each step: O(log n).
• Bubble sort and insertion sort are both O(n²) in the worst case; on nearly sorted data they approach O(n).
• ADTs: stack (LIFO), queue (FIFO), linked list, binary tree, dictionary, graph. They are built from arrays, records and pointers, or from other ADTs.
• Write algorithms to find, insert and delete items in these structures.
• Big O describes how time or memory grows with the number of items.
• Recursion: a subroutine that calls itself, with a base case and a general case that moves towards it.
• Each recursive call is pushed on the call stack (parameters, local variables, return address) and the stack unwinds as calls return.

Linear and binary search

A linear search checks each element from the start until the item is found or the list ends. It works on any list, sorted or not.

FUNCTION LinearSearch(SearchItem : INTEGER) RETURNS INTEGER
   DECLARE Index : INTEGER
   Index ← 1
   WHILE Index <= 15
      IF Data[Index] = SearchItem THEN
         RETURN Index
      ENDIF
      Index ← Index + 1
   ENDWHILE
   RETURN -1
ENDFUNCTION

A binary search needs the data to be sorted. It looks at the middle item: if that is the item, stop; if the item is bigger, discard the lower half; if smaller, discard the upper half. Repeat on the half that is left until the item is found or no items remain.

FUNCTION BinarySearch(SearchItem : INTEGER) RETURNS INTEGER
   DECLARE Lower : INTEGER
   DECLARE Upper : INTEGER
   DECLARE Middle : INTEGER
   Lower ← 1
   Upper ← 15
   WHILE Lower <= Upper
      Middle ← (Lower + Upper) DIV 2
      IF Data[Middle] = SearchItem THEN
         RETURN Middle
      ELSE
         IF Data[Middle] < SearchItem THEN
            Lower ← Middle + 1
         ELSE
            Upper ← Middle - 1
         ENDIF
      ENDIF
   ENDWHILE
   RETURN -1
ENDFUNCTION

Performance: every comparison halves the items left, so the maximum number of comparisons for n items is about log₂ n + 1: 4 for 15 items, 10 for 1000, 20 for 1 000 000. A linear search may need n comparisons. Doubling the data adds only one comparison to a binary search but doubles the worst case of a linear search.

Bubble sort and insertion sort

Bubble sort compares each pair of neighbours and swaps them if they are in the wrong order. After each pass the largest remaining item has "bubbled" to the end, so each pass can stop one place earlier. A flag records whether any swap happened; a pass with no swaps means the data is sorted.

Stack, queue, linked list, binary tree, graph, dictionary

abstract data type (ADT) implemented from built-in types other ADTs

Stack (last in, first out)

Time and space complexity

time memory