Computational
Thinking 4

How many comparisons comparing every pair needs, why that grows so fast, and how binning cuts it.

Some computations seem to need comparing each card with all the other cards in a pile. An example is choosing a study partner for each student. The number of comparisons can be very large. This lecture counts them exactly and shows how binning cuts the count.

1.1Comparing each element with all the others

Take 5 elements A, B, C, D, E. Compare A with every other element, then B with every element not yet compared with B, and so on.

1.2A formula for the number of comparisons

The same formula from first principles:

1. Start: N × N = 5 × 5 = 25 pairs: every card with every card.
2. Remove the self comparisons (A with A): N × N − N = 20, which is N × (N − 1).
3. A with B is the same as B with A. We double counted: halve it.
4. ½ × N × (N − 1) = ½ × 5 × 4 = 10.

1.3The number of comparisons grows really fast

1.4The key idea: binning

If we can organise the cards into bins based on some heuristic (a rule of thumb), then we only need to compare cards within one bin. This seems to reduce the number of comparisons a lot. To find the reduction formally: calculate the comparisons without binning, calculate them with binning, and use both to find the reduction factor.

Take 9 objects A to I. Comparing all pairs needs ½ × 9 × 8 = 36 comparisons. Now suppose the objects can be put into 3 bins of 3 each (ABC, DEF and GHI) and we compare only inside each bin:

1. Comparisons per bin: ½ × 3 × (3 − 1) = ½ × 3 × 2 = 3.
2. Total for all 3 bins: 3 × 3 = 9.
3. The comparisons reduce from 36 to 9: a reduction by a factor of 4.

1.5The calculation for any N and K

For N items put into K bins of equal size:

Check with N = 9 and K = 3: (9 − 1) / (3 − 1) = 8 / 2 = 4, as found above.

1.6Going deeper

• The factor is close to K (extra). For large N, (N − 1)/(N/K − 1) is a little more than K (10.09 for K = 10), so ten bins give about a ten-fold saving.
• K = N breaks the formula (extra). If every bin has one item, N/K − 1 = 0: no comparisons at all, and the factor is undefined (division by zero).
• The heuristic carries the risk (extra). If two items that should be compared land in different bins, the comparison is never made. Binning by month finds people with the same birth month, which is a necessary condition for the same birthday.
• Square growth (extra). Going from 10 to 20 items multiplies the comparisons by 190 / 45 ≈ 4.2.

1.7Exam tips and common mistakes

Practice questions (graded-assignment style)

Iterators, datatypes, filtering, procedures, accumulation and nested iterations, each building on the last.

This lecture revisits the main ideas of Weeks 1 to 4. Each idea builds on the previous one, from a plain iterator up to nested iterations that relate two elements to each other.

2.1Iterators and variables

The iterator is the most commonly used pattern in computational thinking. It represents the procedure of doing some task repeatedly. It needs an initialisation step, the steps for the task that is repeated, and a way to determine when to stop.

Initialise variables
while (Continue with Iteration?) {
    Update values of variables
}

• Variables keep track of intermediate values. They get starting values at the initialisation step and are updated at each repeated step.
• Initialisation and updates are done through assignment statements.
• The flowchart symbols are: terminal (Start, End), process, decision, and arrows that show progress from one step to another.

2.2Going through a set of items

To go systematically through a set of items, the loop picks a card from Pile 1, moves it to Pile 2, and continues while Pile 1 has more cards.

Initialise variables
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    Update values of variables
}

2.3Datatypes, lists and records

The items need well defined values. This leads to datatypes, which clearly identify the values and the allowed operations. The basic datatypes are boolean, integer and character; the string datatype is added to these. Subtypes put more constraints on the values and operations allowed.

2.4Iteration with filtering

Filtering makes a decision at each repeated step whether to process an item or not. This adds a decision step inside the loop.

Initialise variables
while (Continue with Iteration?) {
    ...
    if (condition is satisfied?) {
        Update some variables
    }
    ...
}
Prepare final results from variable values

2.5Procedures and parameters

We sometimes write the same piece of code again and again with small differences. A piece of pseudocode can become a procedure by separating it from the rest of the code. Some variables or constants in it are replaced by a parameter variable. Instead of rewriting the code, we call the procedure with a different parameter value, for example finding the max for each subject.

2.6Accumulation through iteration

The most common use of an iterator is to create an aggregate value (accumulation) from the available values. Simple examples are count, sum and average. We can filter while accumulating, for example the sum of the boys' marks. We can also collect a list of elements, for example the students with the maximum marks in a subject.

2.7Two iterations, one after another

The first iteration does some accumulation. The variables that hold the results are called accumulators. The second iteration does filtering using the accumulator variables, for example finding the above-average students, where the average comes from the first iteration. This establishes a relationship between any element and the aggregate of all elements, for example the more frequently occurring word, or higher-spending customers.

2.8Two iterations, one nested within the other

To go beyond an element and the aggregate, and express a relationship between any two elements, one iteration must run inside another. Example: find out if two students have the same birth day and month. Nested iterations are costly in the number of computations, so wherever possible we reduce the comparisons using binning (Lecture 4.3). How to store such relationships is discussed in the next four weeks.

2.9Going deeper

• Iterator, filter, accumulate, nest. Each idea adds one thing to the last: a repeated step, then a decision inside it, then variables that collect results, then a second loop, then a loop inside a loop.
• Constant versus variable. A constant condition (X.Gender == F) can be tested on any card in any order; a variable condition (X.Maths > Maxval) depends on what was seen so far.
• Why two loops (extra). The average needs all the marks, so no card can be judged until the whole pile has been summed.
• Cost of nesting (extra). The outer loop runs N times and the inner about N times, so the work is about N²; binning is the way to shrink it.

2.10Exam tips and common mistakes

Practice questions (graded-assignment style)

One page to revise all of Week 4: how many comparisons a pile needs, how binning cuts them, and the ideas that lead up to it.

The big picture

Formulas to remember

Concepts from Weeks 1 to 4

Which tool when?

Common mistakes