Session 5 Binary and Hex; Sorting - selection and insertion

Published

June 16, 2026

Discuss the decision trees for guessing the alphabet. See how the yes/no decisions at each series of nodes leading to each letter can be represented using binary numbers.

Introduce the concept of sorting and the problem of sorting using the resources available at https://www.csfieldguide.org.nz/en/chapters/algorithms/sorting/

Summing Natural Numbers and the Gaussian Formula

The session begins with a method for summing numbers from 1 to 100, noting it is an arithmetic progression. The technique involves writing the numbers in forward order (1, 2, 3… 100) and then in reverse order (100, 99… 1) beneath them. Adding each pair results in 101. Since there are 100 such pairs, the total sum for both rows is \(101 \times 100\), and dividing by two gives the sum for a single sequence. This leads to the general formula for the sum of the first \(n\) natural numbers: \(n(n + 1) / 2\). This method was famously devised by the mathematician Gauss when he was in the fourth grade.

Binary Representation and Computer Science

The discussion then transitions to decision trees for guessing an alphabet, where each decision (yes or no) can be represented by 1 or 0. This binary search allows every letter or decision to have a unique representation in ones and zeros. This is fundamentally why binary is critical in computer science; everything from pixels on a screen to lines in space can be boiled down to these two states. Systems like ASCII use specific binary codes for every letter.

Base Systems (Number Bases)

The session explores different numerical bases:

  • Base 2 (Binary): Uses only 0 and 1.
  • Base 8 (Octal): Uses digits 0 to 7; the number 8 is represented as “10”.
  • Base 5: Uses digits 0 to 4; for example, the number 25 is written as “100”. To represent 72 in base 5, it is calculated as “242” (\(2 \times 25 + 4 \times 5 + 2 \times 1\)).
  • Base 16 (Hexadecimal): Uses digits 0 to 9 and letters A to F to represent 10 to 15. Place values increase from right to left (1, 16, 256…). For instance, “02F” in hexadecimal is 47 (\(2 \times 16 + 15\)).
  • Base 12: Historically used for time (24 hours, 60 minutes) and circles (360 degrees). This system was used by the Sumerians and Acadians roughly 4,000 years ago.

Algorithmic Sorting and Comparisons

The lecture concludes with an interactive sorting problem using boxes of different weights. Because computers typically perform one operation at a time, the goal is to sort the items using the least number of comparisons.

  • Selection Sort (Simple Search): This involves comparing every item against every other item, which is less efficient.
  • Insertion Sort: This involves taking a new item and inserting it into its correct relative position among already sorted items.
    • Best Case: If the items are already in order, it takes \(n - 1\) comparisons.
    • Worst Case: If items are in perfect reverse order, it follows the sum of natural numbers sequence, resulting in \(n(n - 1) / 2\) comparisons.
    • For eight boxes, the lowest bound is 7 comparisons and the highest is 28.