Computational
Thinking 2

Word frequencies, and how to find the maximum frequency in two non-nested passes or in a single pass.

This lecture works on the Words dataset: a paragraph (the opening of R. K. Narayan's Swami and Friends) whose words are kept on cards. We want two things: how many times each word occurs, and the maximum frequency, the count of the most frequent word. We can get the maximum with two iterations run one after the other, or fold both jobs into a single iteration.

1.1The word frequency table

As we walk through the paragraph we build a table with one row per distinct word. Each row has two cells: the word and its count (frequency).

1.2What happens to one word

The same few steps run for every word (on the slides the current word is highlighted in yellow in the paragraph and the table changes beside it).

1. Read the next word W of the paragraph, moving left to right.
2. Look up W in the table.
3. Not found: add a new row for W with count 0.
4. Increment the count in W's row by 1. A new word therefore ends at 1, and a repeated word goes up by one.

1.3Maximum in two iterations

Read the flowchart column by column. The left loop is iteration 1. Its No (False) exit, taken once no words are left, is the only way into the right loop, so iteration 2 always starts on a finished table. The right loop is the familiar max pattern: a decision inside the loop, with an update only on Yes (True).

1.4Maximum in a single iteration

We can avoid the second pass. Keep a Max-frequency box beside the table, starting at 0, and check it every time a count changes.

1. Initialise: the table is empty and Max-frequency = 0.
2. For each word W, update its row exactly as before (add with 0 if new, then increment).
3. Immediately compare the new count of W with Max-frequency.
4. If the count is greater, set Max-frequency to that count; otherwise leave it alone.

The highlighted parts are what changed from iteration 1 of the two-pass method: Max-frequency is initialised along with the table, and a decision is added at the end of the loop body. Its No (False) branch does nothing, so the loop simply continues.

When Max-frequency changes during the pass on the paragraph (the first words and the repeated was and the):

1.5A small example you can check by hand (extra)

Take the nine words the cat saw the dog and the cat ran. Both methods give the table the 3, cat 2, saw 1, dog 1, and 1, ran 1 (6 rows) and Max-frequency = 3. Here is the single-iteration trace:

Max-frequency changed 3 times (to 1, 2 and 3), whenever a count set a new record. The words cat (count 2 while the max was already 2) and the new words with count 1 never changed it.

1.6Going deeper

• Why start at 0. Every count is at least 1, so the very first word already beats Max-frequency = 0.
• Strictly greater. A count equal to the current max does not change the value, so > is enough for the maximum value.
• Which word (extra). To know the word, not just the count, also store it whenever Max-frequency changes. Chapter 2 does exactly this for cards.
• Trade-off. The two-pass method is simpler to reason about; the single pass needs no second scan and always knows the max so far.

1.7Exam tips and common mistakes

Practice questions (graded-assignment style)

Filling in the filtering template to find the maximum, the card that has it, and all cards that tie.

We now draw the maximum as a flowchart on the Scores dataset. Instead of starting from scratch, we take the flowchart for iteration with filtering and fill in its blanks. Then we extend it to remember which card has the maximum, and finally all such cards.

2.1Starting point: iteration with filtering

This is the general shape from Week 1. The outer loop visits every card; inside it a decision Check for ? sends each card down one of two branches. Both branches return to the same place, the check More cards in Pile 1?

2.2Modify the template for the maximum

1. Initialise max to 0. The box becomes max = 0. Marks cannot be negative, so any real mark is at least this value.
2. The check: are the Maths marks of card X greater than max? If so update max; else do nothing.
3. Write the check precisely as CardX.Maths > max?, where CardX.Maths means the Maths marks of card X.
4. Yes (True): max = CardX.Maths.
5. No (False): nothing to do, so the Do something for No box is removed and the No arrow goes straight back to the loop.

2.3Keep track of the card with the maximum

Knowing the maximum value is often not enough; we also want to know whose card it is. We add one more variable.

1. Initialise maxCardId to -1. Card index numbers start at 0, so -1 stands for "no card yet".
2. Update maxCardId at the same moment we update max: maxCardId = CardX.id, where CardX.id is the index number on card X.
3. Both assignments sit in the same Yes (True) box, so max and maxCardId always describe the same card.

2.4The problem: ties for the maximum

What if more than one card has the same maximum marks? The test CardX.Maths > max? is a strict "greater than". A later card with marks equal to max answers No, so it is ignored. Only the first card with the maximum is retained.

2.5Solution: keep a list of cards

Keep a list of ids in maxCardId instead of a single id.

1. On the No (False) branch of CardX.Maths > max?, ask a second question: is card X also at the max marks, CardX.Maths = max?
2. Yes (True): append CardX.id to maxCardId. Appending b to a gives the list a, b.
3. No (False): card X is below the max; nothing to do.
4. The first Yes branch is unchanged: a strictly bigger mark sets max and restarts the list with just CardX.id.

2.6Trace the three versions on a small dataset (extra)

Six cards with ids 0 to 5 and Maths marks 45, 78, 91, 78, 91, 60. We process them in order of id.

The single-id version ends with max = 91, maxCardId = 2: card 4 also has 91 but is ignored. The list version ends with max = 91, maxCardId = [2, 4]. Along the way the list restarts as [1] when 78 beats 45, restarts again as [2] when 91 arrives, ignores the later 78 (below the max), and appends 4 for the later 91 (equal to the max).

2.7Going deeper

• The zero-marks gotcha (extra). With max = 0 and a strict >, a dataset where every mark is 0 never takes the Yes branch, so maxCardId stays -1 even though cards exist. The list version records [0, 1] because the = test catches them.
• Why 0 is safe here. The source relies on marks being non-negative. If marks could be negative, initialise max to the first card's marks instead (extra).
• Strict versus non-strict. Changing > to >= would keep the last maximum card instead of the first (extra).
• Same shape every time. Max, max-with-card and max-with-list all keep the template; only the blanks change.

2.8Exam tips and common mistakes

Practice questions (graded-assignment style)

Why flowcharts need a text companion, and how pseudocode writes assignment and repetition directly.

Flowcharts draw a procedure as a picture. This lecture asks how to write the same procedure as text, keeping what flowcharts do well and fixing what they do badly. The answer is pseudocode.

3.1Flowcharts: a recap

A flowchart is a pictorial representation of a computational process. Our running example is counting the number of cards. It uses three node types joined by arrows that indicate the operation flow.

3.2Pros and cons of flowcharts

3.3From pictures to text

The first idea is simply to describe the process in words, one numbered step per box or arrow of the flowchart.

The numbered badges show the match: boxes become plain steps (0, 1, 4, 5, 6, 8). The decision becomes two steps: Step 2 checks, Step 3 jumps to the End on No. The arrow looping back to the decision becomes Step 7, Go back to Step 2.

3.4Towards a programming language

A programming language is a succinct notation for computational processes. Writing steps in plain words works, but two common patterns read awkwardly and need a better textual representation:

3.5Pseudocode

Pseudocode tunes the notation so these standard features are written directly instead of through jumps.

Start
Count = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    Increment Count
}
End

1. Assign a value to a variable: Count = 0.
2. Repeat steps while a condition holds: while (...).
3. Mark the start and end of the repeated block: { }.

Every process box becomes one line at the same height. The decision and its loop-back arrow together become a single while line plus a pair of braces: the condition Pile 1 has more cards is tested before each repetition, the lines inside the braces are the repeated block, and when the condition fails execution continues after }, at End. No step numbers or "go to" jumps are needed.

3.6Running the numbered steps (extra)

Follow the numbered steps for a Pile 1 that has 2 cards. The steps are visited in this order, and Count ends at 2:

That is 17 steps: 2 to start, then 6 steps (2, 3, 4, 5, 6, 7) for each of the 2 cards, then 3 (2, 3, 8) to finish. The jump back at Step 7 is what the single while line replaces.

3.7Summary

• Flowcharts are easy to read, visual descriptions of procedures, but they are cumbersome, hard to share and edit.
• Writing down steps in text is an alternative.
• Tune the notation to capture standard features: assigning values to variables, conditional execution, repeated execution.

3.8Exam tips and common mistakes

Practice questions (graded-assignment style)

Every flowchart of Weeks 1 and 2 written as pseudocode, with assignment, if/else and ==.

We now write every flowchart from Weeks 1 and 2 as pseudocode. Along the way we meet the assignment statement, conditional execution with if and else, and the difference between == and =. Each pseudocode listing is shown next to its flowchart.

4.1Counting cards

Start
Count = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    Increment Count
}
End

4.2Sum of Maths marks

Sum = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    Sum = Sum + X.Maths
}

Only two lines differ from counting: the variable is Sum, and Increment Count becomes Sum = Sum + X.Maths. Here X.Maths means the Maths marks in card X.

4.3Sum of boys' Maths marks

Sum = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Gender == M) {
        Sum = Sum + X.Maths
    }
}

The filter decision X.Gender == M? becomes if (X.Gender == M) { ... }. The block inside the braces runs only when the condition is True. The No branch has nothing to do, so there is no extra code for it. This is conditional execution, once: the if block runs at most one time each time it is reached. Compare while, which keeps repeating its block as long as the condition holds.

4.4Equality (==) versus assignment (=)

4.5Sum of boys' and girls' Maths marks

BoySum = 0
GirlSum = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Gender == M) {
        BoySum = BoySum + X.Maths
    }
    else {
        GirlSum = GirlSum + X.Maths
    }
}

Now both branches of the decision do work, so we use if (condition) { ... } else { ... }. The if block is the Yes (True) branch and adds to BoySum; the else block is the No (False) branch and adds to GirlSum. Exactly one of the two blocks runs for each card, and then control returns to the while check.

4.6Finding the maximum Maths marks

MaxM = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Maths > MaxM) {
        MaxM = X.Maths
    }
}

This is the flowchart of Lecture 2.8 in text form, with the variable named MaxM. It has the same shape as the boys' sum: an if with no else, because nothing happens when the marks are not bigger.

4.7The card with the maximum Maths marks

MaxM = 0
MaxCard = -1
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Maths > MaxM) {
        MaxM = X.Maths
        MaxCard = X.Id
    }
}

MaxCard starts at -1 (no card yet). Both assignments sit inside the same if block, so they always happen together: whenever a new maximum is found, its card id X.Id is recorded as well.

4.8Run them on a small dataset (extra)

Six cards, ids 0 to 5, genders M F M F M F and Maths marks 45, 78, 91, 78, 91, 60.

Final values: BoySum = 227, GirlSum = 216, and the plain Sum = 443 (their total). The max program gives MaxM = 91 and MaxCard = 2 (card 4 is ignored by the strict >).

4.9Summary

4.10Going deeper

• while tests first. The condition is checked before each repetition, so with an empty pile the block never runs and Sum stays 0 (extra).
• Indentation helps. The braces mark the blocks; indenting the lines inside them makes the nesting easy to see (extra).
• Words as conditions. Pile 1 has more cards is a condition written in plain words; pseudocode is not tied to a real language's syntax (extra).
• Pattern reuse. Every program here is the same while loop with different initialisations and different bodies.

4.11More templates: the minimum, the average, counting with a condition, and compound conditions

Every program in this part is the same while loop with different initial values and a different body. Four more variations are needed so often that they are worth learning as templates. All the traces below use the same six cards as 4.8 (ids 0 to 5, genders M F M F M F, Maths marks 45, 78, 91, 78, 91, 60).

A. The minimum

The minimum is the maximum turned upside down: test with < instead of >. The initial value must be at least as large as any possible mark (for marks out of 100, use 100), because a starting value of 0 could never be beaten by a smaller mark.

MinM = 100
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Maths < MinM) {
        MinM = X.Maths
    }
}

On the six cards, the first card (45) is already the smallest, so MinM = 45 at the end. A better trace uses Maths marks $70, 55, 80, 55, 40$:

To remember which card has the minimum, add MinCard = X.Id inside the same if, exactly as for the maximum.

B. The average

The average needs two accumulators, a sum and a count, and one division after the loop:

Sum = 0
Count = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    Sum = Sum + X.Maths
    Count = Count + 1
}
Avg = Sum / Count

On the six cards: $Sum = 443$, $Count = 6$, $Avg = 443/6 \approx 73.83$. For the average over a filtered group, put both updates inside the same if. For the girls: if (X.Gender == F) { Sum = Sum + X.Maths; Count = Count + 1 } gives $Sum = 216$, $Count = 3$, $Avg = 72$. For the boys $Sum = 227$, $Count = 3$, $Avg \approx 75.67$.

C. Counting with a condition

Counting is the sum template with the update Count = Count + 1 placed inside an if. "How many cards have Maths of at least 80?":

Count = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Maths >= 80) {
        Count = Count + 1
    }
}

On the six cards, the marks $91$ (card 2) and $91$ (card 4) qualify, so Count = 2.

D. Compound conditions: and, or, not

A condition can combine tests. A and B is True only when both are True; A or B is True when at least one is True; not A flips it. A compound condition does the same job as nesting:

Sum = 0
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    if (X.Gender == M and X.Maths > 50) {
        Sum = Sum + X.Maths
    }
}

On the six cards, the boys are cards 0, 2, 4 with marks 45, 91, 91. Only 91 and 91 pass X.Maths > 50, so $Sum = 182$ and a counter beside it would end at 2. With or instead: X.Gender == F or X.Maths > 85 picks the three girls (78, 78, 60) and the two boys with 91, so $Sum = 216 + 182 = 398$. A card that satisfies both parts is still added only once.

E. Where the initialisation goes

• Initialise before the while. Writing Count = 0 inside the loop resets it every round, so it ends at 1 at most (for a non-empty pile).
• Pick the start value so the first update always works: 0 for sums and counts and for a maximum of non-negative marks, a large number for a minimum.
• Updates that need the old value (like Sum = Sum + X.Maths) rely on the initialisation being there. A missing initialisation is the most common reason a trace comes out wrong.

4.12Exam tips and common mistakes

Practice questions (graded-assignment style)

One page to revise all of Week 2: the two ways to find a maximum, the flowchart patterns and the flowchart-to-pseudocode table.

Maximum: two ways

Flowchart patterns on the Scores dataset

Flowchart to pseudocode

Why pseudocode, and notation to remember

Common mistakes