Computational
Thinking 3

Cards as rows of a table, and why a bill with a variable number of items must be split into linked tables.

Data usually arrives on cards: a grade card, a card for a word, a shopping bill. This lecture shows how to lay such data out as a table, and what goes wrong when a card has a variable amount of information, like a bill with any number of items.

1.1Extracting data from cards

• Each card is a unit of information.
• A card has different attributes (also called fields): Card ID, Name, Gender, ..., Total.
• Organise the cards as a table: each attribute is a column and each card is a row.
• All the grade cards go together in a single table.

1.2The same idea for words

Cards can hold anything that has attributes. For the words in a paragraph, each word is a card with an Id, the Word itself, its Type (noun, verb, ...) and its Length.

1.3Shopping bills: a table that is no longer neat

• Variable number of columns? A card cannot have a different number of columns. The table is no longer neat.
• Variable number of rows per card? Give a row to each item and tag the rows with the card (bill) Id.

Doing that gives one big table for the bill:

1.4The fix: multiple tables

Split the bill into two tables. The first holds the columns that are fixed for the bill. The second holds the variable entries as multiple rows. The Bill ID links the two tables.

The same split works for any bill. Bill 1 from SV Stores (customer Srivatsan, total 567) has one row in the first table and many in the second: Carrots, Soap, Tomatoes, ..., Milk.

1.5Going deeper

• Why the link must be unique (extra). If two bills shared Id 5, a lookup of "Id = 5" in the items table would return rows from both, and totals would be wrong.
• Consistency checks. The bill-level Total must equal the sum of the item Costs, and each Cost must equal Qty × Price. A table lets you check both.
• One-to-many. One row in table 1 matches many rows in table 2: that is the shape of every "variable number of entries" problem (extra).

1.6Exam tips and common mistakes

Practice questions (graded-assignment style)

Writing a loop once as a procedure, and filling in its blanks with parameters.

Last week the same loop was written again and again with small changes. A procedure is pseudocode written once as a template that works in different situations, with parameters to say which situation we mean.

2.1Why we need procedures

The sum of the boys' Maths marks uses X.Gender == M. What if we want the girls' Maths marks? Only the value checked against X.Gender changes; the remaining pseudocode is identical.

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
    }
}

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

The flowchart changes in just one box too: the decision becomes X.Gender == F instead of X.Gender == M. Copying the whole loop for every small change is wasteful. A procedure lets us write it once.

2.2A procedure to sum Maths marks

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

Calling the procedure with a parameter: SumMaths(F). The argument variable is assigned the parameter value: the call implicitly starts with gen = F. The procedure returns the value stored in Sum.

2.3Changing the field: SumMarks(gen, fld)

For the Physics marks the only change is the field examined on the card: X.Physics instead of X.Maths. For Chemistry add up X.Chemistry, for the total X.Total. Writing a new procedure for each field is the same problem again, so pass the field name as a parameter too.

Procedure SumMarks(gen,fld)
    Sum = 0
    while (Pile 1 has more cards) {
        Pick a card X from Pile 1
        Move X to Pile 2
        if (X.Gender == gen) {
            Sum = Sum + X.fld
        }
    }
    return(Sum)
end SumMarks

2.4Calling a procedure

Use the procedure name like a maths function, as part of an expression, and assign the return value to a variable.

GirlChemSum = SumMarks(F,Chemistry)
BoyChemSum = SumMarks(M,Chemistry)
if (GirlChemSum ≥ BoyChemSum) {
    "Congratulate the girls"
}
else {
    "Congratulate the boys"
}

A procedure may not return a value. For example, a procedure to correct the marks for one subject on a card, Procedure UpdateMarks(CardId, Subject, Marks) ... end UpdateMarks. Its call is a separate statement, not part of an expression: UpdateMarks(17,Physics,88).

2.5Worked examples on eight cards

These eight cards are used in all the examples this week (example data, not from the lecture):

2.6Going deeper

• Call by copying (extra). The parameter is copied into the argument, so changing gen inside the procedure does not change the caller's value.
• Ignoring the result is a bug. A call like SumMarks(F,Total) on its own line throws the answer away. Assign it.
• Generalising. SumMaths → SumMarks is the pattern: find what changes between copies and turn each change into a parameter.

2.7Local and global variables: what a procedure can see and keep

A procedure uses variables of its own, such as Sum in SumMarks, and it can also see data that belongs to the program that calls it, such as the deck of cards. Knowing which is which explains why a procedure can be called again and again with different arguments and still give a correct answer.

A. Local variables start fresh on every call

The parameters (gen, fld) and every variable that the procedure sets up inside itself (Sum) are local: they exist only while that call is running. Each new call starts with a new Sum = 0. That is why the following two calls are independent:

Procedure SumMarks(gen, fld)
    Sum = 0
    while (Pile 1 has more cards) {
        Pick a card X from Pile 1
        Move X to Pile 2
        if (X.Gender == gen) {
            Sum = Sum + X.fld
        }
    }
    return(Sum)
end SumMarks

• On the eight cards (with the deck restored between the calls), SumMarks(F,Physics) returns $40 + 96 + 82 + 60 = 278$, and SumMarks(M,Physics) returns $93 + 94 + 95 + 70 = 352$. The second answer does not include the first.
• Two different procedures may use the same local name (Sum in SumMarks, Sum in some other procedure) without interfering.
• Changing a parameter inside the procedure (gen = M) changes only the local copy; the caller's value stays as it was.

B. What goes wrong when the total is kept outside

Suppose Sum = 0 is written once, outside the procedure, so Sum is a shared (global) variable that every call updates:

Sum = 0
Procedure SumMarks(gen, fld)
    while (Pile 1 has more cards) {
        Pick a card X from Pile 1
        Move X to Pile 2
        if (X.Gender == gen) {
            Sum = Sum + X.fld
        }
    }
    return(Sum)
end SumMarks

Now the first call SumMarks(F,Physics) returns $278$ and leaves Sum = 278. The second call SumMarks(M,Physics) starts from that leftover: it returns $278 + 352 = 630$, which is wrong. The call that is made first gets the right answer; every later call is contaminated by the earlier ones.

C. Local values versus shared data

This is the same distinction as in "Side Effects of Procedures": a procedure that moves the cards from Pile 1 to Pile 2 leaves Pile 1 empty, so a second call finds no cards unless the caller (or the procedure itself) puts them back.

2.8Exam tips and common mistakes

Practice questions (graded-assignment style)

One Maxmarks procedure for any field, and the analysis of top students built on it.

This lecture uses a procedure to answer questions about the top students. The idea: when the same computation is needed for different fields (Maths, Physics, Chemistry, Total), write it once as a procedure and let a parameter name the field.

3.1Analysis of top students

• Is there a single student who is the best performer across subjects?
• Is the highest overall total the same as the sum of the highest marks in each subject?

Both questions need the maximum for different fields: Maths, Physics, Chemistry and Total. So one procedure Maxmarks(fld), with the field as a parameter, fits.

3.2Finding the maximum in a given field

As usual keep track of the maximum with a variable: initialise it to 0 and update it whenever you see a bigger value. What is new is that the value being compared is not fixed: the parameter fld decides the field of interest.

Procedure Maxmarks(fld)
    Maxval = 0
    while (Pile 1 has more cards) {
        Pick a card X from Pile 1
        Move X to Pile 2
        if (X.fld > Maxval) {
            Maxval = X.fld
        }
    }
    return(Maxval)
end Maxmarks

3.3Using Maxmarks to compare the totals

Call Maxmarks four times, once for each category, with fld set appropriately. Save each return value in its own variable. Then use the saved values to compare the maximum overall total with the sum of the maximum subject marks.

MaxMaths = Maxmarks(Maths)
MaxPhysics = Maxmarks(Physics)
MaxChemistry = Maxmarks(Chemistry)
MaxTotal = Maxmarks(Total)
SubjTotal = MaxMaths + MaxPhysics + MaxChemistry

if (MaxTotal == SubjTotal) {
    SingleTopper = True
}
else {
    SingleTopper = False
}

3.4Going deeper

• Same procedure, four jobs. Using one procedure for four fields avoids describing the same process repeatedly. If we improve the code in the procedure, every call gets the benefit.
• Parameters fix the context, variables keep the outcomes. The parameter says which field; the saved variables hold what came back.
• Ties for the top (extra). MaxTotal == SubjTotal says there is a single top student only in the sense "one card holds all three maxima"; it does not say which card. Use the card-id version of Week 2 for that.

3.5Exam tips and common mistakes

Practice questions (graded-assignment style)

A complex problem broken into procedures: top three marks, subject toppers and the three winners.

This lecture works out a complex problem in full detail: awarding three prizes. The trick is to break it into steps, turn the natural units into procedures, and then plug them together.

4.1The three conditions

1. Basic criterion: total marks. Award prizes to the top 3 students.
2. Must also be in the top three in at least one subject.
3. Must select at least one boy and one girl among the three.

Everything starts from the basic pattern: find the top three marks in a category.

4.2Finding the top three marks, step by step

• The maximum: initialise max to 0, scan the cards, update each time you see a bigger value.
• The top two: maintain max and secondmax. If the current value is bigger than max, copy max to secondmax and update max. If it is between max and secondmax, leave max alone and update secondmax.
• The top three: the same idea with one more slot, thirdmax.

4.3A procedure: top three marks in a subject

Procedure TopThreeMarks(Subj)
    max = 0
    secondmax = 0
    thirdmax = 0
    while (Pile 1 has more cards) {
        Pick a card X from Pile 1
        if (X.Subj > max) {
            thirdmax = secondmax
            secondmax = max
            max = X.Subj
        }
        if (max > X.Subj > secondmax) {
            thirdmax = secondmax
            secondmax = X.Subj
        }
        if (secondmax > X.Subj > thirdmax) {
            thirdmax = X.Subj
        }
    }
    return(thirdmax)
end TopThreeMarks

In the pseudocode these are three separate if statements. Once one has updated the slots, X.Subj equals that slot, so the later tests are False. It is sufficient to return thirdmax, the third highest mark in the subject. (The procedure ought to return all three values as a list; lists come later in the course.)

4.4The three prizes algorithm

The prize winners are the top three totals, but only among students who are in the top three in at least one subject. (The boy and girl requirement is dealt with later.) Again we maintain max, secondmax, thirdmax, now together with the card ids maxid, secondmaxid, thirdmaxid, because at the end we need to know who the winners are.

max = 0
secondmax = 0
thirdmax = 0
maxid = -1
secondmaxid = -1
thirdmaxid = -1

maths3 = TopThreeMarks(Maths)
phys3 = TopThreeMarks(Physics)
chem3 = TopThreeMarks(Chemistry)

while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    if (SubjectTopper(X,maths3,phys3,chem3)) {
        if (X.Total > max) {
            thirdmax = secondmax
            thirdmaxid = secondmaxid
            secondmax = max
            secondmaxid = maxid
            max = X.Total
            maxid = X.Id
        }
        if (max > X.Total > secondmax) {
            thirdmax = secondmax
            thirdmaxid = secondmaxid
            secondmax = X.Total
            secondmaxid = X.Id
        }
        if (secondmax > X.Total > thirdmax) {
            thirdmax = X.Total
            thirdmaxid = X.Id
        }
    }
}

4.5The procedure SubjectTopper

Compare each subject's marks on the card with the third highest mark. The marks are passed explicitly as parameters. One or more comparisons should succeed, which is what the or operator means.

Procedure SubjectTopper(Card,MMark,PMark,CMark)
    if (Card.Maths ≥ MMark or
        Card.Physics ≥ PMark or
        Card.Chemistry ≥ CMark) {
        return(True)
    }
    else {
        return(False)
    }
end SubjectTopper

4.6Boundary conditions

A good solution has to anticipate unexpected situations in the data. The lecture raises two.

4.7When the code gives a wrong answer: ties (extra)

Because every comparison is strict, TopThreeMarks effectively finds the third highest distinct mark. That is fine when marks are all different, but ties can break the idea:

So ties need a deliberate choice of rule (the lecture leaves this open): for example, decide whether equal marks share a place, and change the comparisons (> versus ≥) to match.

4.8Going deeper

• Break big problems into procedures. The prize problem is one loop plus two procedures (TopThreeMarks, SubjectTopper); each is small enough to check on its own.
• Will the exclusion always work? (extra) No: if fewer than three eligible cards remain, or all eligible cards have the same gender, repeating cannot produce a boy and a girl. A real solution must say what to do then.
• Total before subject. Card 6 has the best total but is not eligible: the subject condition filters first, then the total ranks.

4.9Exam tips and common mistakes

Practice questions (graded-assignment style)

What a procedure changes besides its return value, and the contract that says what it promises.

A procedure can do more than return a value: it can change data while it runs. This lecture is about noticing those changes, called side effects, and about writing down what a procedure promises.

5.1Passing the deck of cards

The procedure SumMarks(gen,fld) works for one fixed set of cards, the cards in Pile 1. What about any set of cards? Pass the deck through a third parameter.

Procedure SumMarks(gen,fld,Deck)
    Sum = 0
    while (Deck has more cards) {
        Pick a card X from Deck
        Move X to SeenDeck
        if (X.Gender == gen) {
            Sum = Sum + X.fld
        }
    }
    return(Sum)
end SumMarks

• Third parameter Deck: the loop now runs over the given deck.
• New variable SeenDeck plays the role of the second pile.
• Deck is modified as the procedure executes: cards move from Deck to SeenDeck.
• At the end Deck is empty! The procedure should also restore Deck from SeenDeck.

The version that restores the deck adds one line before the return:

Procedure SumMarks(gen,fld,Deck)
    Sum = 0
    while (Deck has more cards) {
        Pick a card X from Deck
        Move X to SeenDeck
        if (X.Gender == gen) {
            Sum = Sum + X.fld
        }
    }
    Restore Deck from SeenDeck
    return(Sum)
end SumMarks

5.2Side effects

Here the sequence of cards may be disturbed. Does it matter? It depends:

• Not important: adding marks does not depend on how the cards are arranged.
• The side effect is the goal: a procedure to arrange cards in decreasing order of Total Marks exists to change the order.
• Could be undesirable: we pass a deck in decreasing order of Total Marks; afterwards it is randomly rearranged.
• Not tolerated: pronoun matching: FindMatch must leave the words and their positions untouched.

5.3Interface versus implementation

Each procedure comes with a contract.

5.4Side effects in text: pronoun matching

Another task: associating personal pronouns with nouns in a passage of text. Fix a pronoun, search the text before the pronoun backwards, and stop at the nearest name. Write it as a procedure FindMatch(before, pronoun, after): the text before the pronoun, the pronoun, and the text after it.

5.5Going deeper

• Order matters only sometimes. A sum is the same in any order, but a "first match" or a sorted list is not. Ask whether the answer depends on order before you accept a reordering side effect (extra).
• Write the side effect in the contract. "The deck is reversed" is fine if it is promised and predictable.
• Interface changes break callers. Adding a parameter or changing a promised side effect breaks every call that depends on the old contract.

5.6Exam tips and common mistakes

Practice questions (graded-assignment style)

One page to revise all of Week 3: tables, procedures with parameters, using procedures, the three prizes and side effects.

The big picture

Parts of procedures and calls

The procedures of this week

The slot update to remember

if (X.Total > max) {
    thirdmax = secondmax
    thirdmaxid = secondmaxid
    secondmax = max
    secondmaxid = maxid
    max = X.Total
    maxid = X.Id
}

Which tool when?

Common mistakes