BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

Computational Thinking

BSCS1001 · 10 topics · 12 min read

0/10 revised

Week 1Every paper

The datasets & datatypes

Know these card layouts

Dataset	One card is	Fields you'll filter on
Scores	One student (30 cards, CardNo 0–29)	Name, Gender (M/F), Date of Birth, Town/City, Mathematics, Physics, Chemistry, Total
Words	One word of a paragraph, in order	Word, Part of Speech, Letter count; a sentence ends at a word with a full stop
Shopping Bills	One bill	Shop name, Customer name, items (name, category, quantity, price, cost), bill total
Library, Olympics, others	One book or player record	The question prints the card: read every field name before tracing

Scores
One card is:
One student (30 cards, CardNo 0–29)
Fields you'll filter on:
Name, Gender (M/F), Date of Birth, Town/City, Mathematics, Physics, Chemistry, Total
Words
One card is:
One word of a paragraph, in order
Fields you'll filter on:
Word, Part of Speech, Letter count; a sentence ends at a word with a full stop
Shopping Bills
One card is:
One bill
Fields you'll filter on:
Shop name, Customer name, items (name, category, quantity, price, cost), bill total
Library, Olympics, others
One card is:
One book or player record
Fields you'll filter on:
The question prints the card: read every field name before tracing

Anatomy of a Scores card

Illustrative values. Total is always Mathematics + Physics + Chemistry.

Total = Mathematics + Physics + Chemistry · cost = quantity × price · bill total = sum of item costs · letter count = number of letters in the word.
Sanity of data: every value must be valid for its type. Marks within 0–100, Gender ∈ {M, F}, real dates, totals that add up. A card that breaks these is an error.

Datatypes

Type	Values	Operations that make sense
Boolean	True, False	and, or, not
Integer	…, −1, 0, 1, …	+ − × ÷ mod, comparisons
Character	One letter or symbol	`==`, `!=`, alphabetical order
String	A sequence of characters (names, words)	`==`, joining, length
Subtypes	Marks (integer 0–100), Gender (M/F), Date	Only what the meaning allows: adding two names is invalid

Boolean
Values:
True, False
Operations that make sense:
and, or, not
Integer
Values:
…, −1, 0, 1, …
Operations that make sense:
+ − × ÷ mod, comparisons
Character
Values:
One letter or symbol
Operations that make sense:
==, !=, alphabetical order
String
Values:
A sequence of characters (names, words)
Operations that make sense:
==, joining, length
Subtypes
Values:
Marks (integer 0–100), Gender (M/F), Date
Operations that make sense:
Only what the meaning allows: adding two names is invalid

Week 1Most papers

Variables, iteration & flowcharts

Flowchart symbols

Shape	Meaning
Oval / rounded rectangle	Start or End (terminal)
Rectangle	Process, e.g. count = count + 1
Diamond	Decision: a condition with Yes and No exits
Parallelogram	Input or output
Arrow	Flow of control

The iterator as a flowchart

oval: start / endrectangle: processdiamond: decisionparallelogram: input / output

The same loop as the pseudocode below: the average Maths marks of female students.

Iterator: Pile 1 (unseen) → pick card X → process X → move X to Pile 2 → repeat until Pile 1 is empty.
Initialise every variable before the loop (count = 0, sum = 0).
Filtering: process a card only when a condition holds (a decision box, or an if).
Average = sum ÷ count, computed after the loop ends.

Count + sum in one pass

count = 0
sum = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "F"){
        count = count + 1
        sum = sum + X.Mathematics
    }
    Move X to Table 2
}
avg = sum / count

avg = average Maths marks of female students.

Traps to avoid

Initialising inside the loop resets the variable on every card, so it ends up holding only the last card's value.
A loop that never moves X to Table 2 never ends.

Week 2Every paper

Pseudocode, filtering & AND / OR

Exam-style pseudocode

count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "F" and X.CityTown == "Chennai"){
        count = count + 1
    }
    Move X to Table 2
}

count = number of female students from Chennai.

Operators

Write	Means
`a = b`	Assign: store the value of b in a
`a == b`	Compare: is a equal to b?
`a != b`	Not equal
`and`	True only when both sides are true
`or`	True when at least one side is true
`not`	Flips True and False
`a mod b`	Remainder: 17 mod 5 = 2

Logic you'll use

De Morgan: not (A and B) = (not A) or (not B)
De Morgan: not (A or B) = (not A) and (not B)
Count of A or B: count(A) + count(B) − count(A and B)
Exactly one of A, B: (A and not B) or (B and not A)

Worked example

In Scores, 14 students are female, 12 are from Chennai, and 5 are female and from Chennai. What does an X.Gender == "F" or X.CityTown == "Chennai" filter count?

Show solution

Count(A or B) = 14 + 12 − 5.

Answer: 21 students

and, or, exactly one

A and Bboth: 5

A or Bat least one: 14 + 12 − 5 = 21

Exactly one(A and not B) or (B and not A): 16

14 female students, 12 from Chennai, 5 both.

Brackets change meaning: (A and B) or C ≠ A and (B or C).
Check whether each update sits inside or outside the if. Indentation and braces decide.
A = A + 1 counts cards. A = A + X.Marks adds up a field.

Week 2Every paper

Max, min & 'who has it'

Highest mark and who scored it

max = 0
topper = "None"
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Mathematics > max){
        max = X.Mathematics
        topper = X.Name
    }
    Move X to Table 2
}

Filtered min (PYQ May 2023: lowest Chemistry, male, Vellore)

min = 100
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "M" and X.CityTown == "Vellore"){
        if(X.Chemistry < min){
            min = X.Chemistry
        }
    }
    Move X to Table 2
}

Tracing max over five cards

max so far (starts at 0)Ties: strict > keeps the first card, ≥ keeps the last.

Ties: which card wins?

Comparison	On a tie, keeps
`X.M > max`	the first card with the maximum
`X.M >= max`	the last card with the maximum
`X.M < min`	the first card with the minimum
`X.M <= min`	the last card with the minimum

max = 0 is safe only when every value is ≥ 0. For min, start above the largest possible value (100 for marks) or with the first card's value.
Second highest: if X > max { second = max; max = X } else if X > second { second = X }.

Traps to avoid

min = 0 bug: no mark is below 0, so min never changes. A favourite 'find the mistake' option.
Setting topper outside the if stores the last card's name, not the topper's.
If no card passes the filter, max and min keep their starting values.

Week 3Every paper

Procedures, parameters & return

A procedure

Procedure isVowel(c)
    if(c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'){
        return(True)
    }
    return(False)
End isVowel

What happens on a call

Parameters are the inputs. A call like isVowel(letter) substitutes the argument for c.
return(v) hands v back and exits immediately. Nothing after it runs.
Side effect: the procedure changes something outside itself (moves rows between tables, changes an outside variable). Ask whether the table is the same after the call.
Loop counting: i = 1; while(i <= 20){ i = i * 2 } runs for i = 1, 2, 4, 8, 16: five times.

Standard procedures: learn the trick

Task	Trick
Sum of the two smallest of a, b, c (PYQ Jan 2024)	a + b + c − max(a, b, c)
Largest of three	compare a with b, then the winner with c
Even or odd	`n mod 2 == 0` ⇒ even
Last digit / drop it	`n mod 10` / `floor(n / 10)`
Sum of digits	repeat `s = s + n mod 10`, `n = floor(n / 10)` until n = 0
Reverse a number	repeat `r = r × 10 + n mod 10`, `n = floor(n / 10)`
GCD (Euclid)	`while(b != 0){ t = b; b = a mod b; a = t }` → answer a
Divisible by k	`n mod k == 0`

Trace the GCD loop

Run the Euclid loop with a = 36, b = 24.

Show solution

(36, 24): t = 24, b = 36 mod 24 = 12, a = 24.
(24, 12): t = 12, b = 24 mod 12 = 0, a = 12.
b = 0, so the loop stops.

Answer: 12

Worked example

Sum of digits of 4096 with the mod-10 loop?

Show solution

6 → n = 409
6 + 9 = 15 → n = 40
15 + 0 = 15 → n = 4
15 + 4 = 19 → n = 0

Answer: 19

Week 3Most papers

Slab and bill problems (if / else if)

₹5 for the first 100 units, ₹7 for the next 100, ₹10 after that

if(unit <= 100){
    cost = unit * 5
}
else if(unit <= 200){
    cost = 100 * 5 + (unit - 100) * 7
}
else{
    cost = 100 * 5 + 100 * 7 + (unit - 200) * 10
}

Each rate applies only to the units inside its own slab.
An else-if chain checks top to bottom and stops at the first true condition, so the order of the checks matters.

PYQ pattern (May 2023)

Using the slabs above, what is the bill for 250 units?

Show solution

First 100: 100 × 5 = 500.
Next 100: 100 × 7 = 700.
Last 50: 50 × 10 = 500.

Answer: ₹1700

250 units through the slabs

Each rate applies only to the units inside its own slab.

Traps to avoid

Wrong-option pattern: cost = unit * 10 for unit > 200, which charges every unit at the top rate.
Boundaries: is exactly 100 units in slab 1 (<=) or slab 2 (<)? Check the comparison sign.

Week 3Most papers

Multiple (non-nested) iterations

PYQ (Jan 2024): students above the class average

sum = 0
n = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    sum = sum + X.Total
    n = n + 1
    Move X to Table 2
}
avg = sum / n
Move all rows from Table 2 to Table 1
count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Total > avg){
        count = count + 1
    }
    Move X to Table 2
}

Two passes, in order

1
Pass 1: add up every Total and count the rows
Every card moves from Table 1 to Table 2.
2
avg = sum / n
Only known once pass 1 has finished.
3
Move all rows from Table 2 back to Table 1
Skip this and pass 2 runs zero times.
4
Pass 2: count the rows with X.Total > avg

You can't compare with the average until you know it, so it takes two passes.
Restore Table 1 between passes, or the second loop runs zero times.
Three prizes problem: keep first, second and third in one pass, shifting values down whenever a bigger total arrives.

Week 4Every paper

Nested iterations: comparing pairs

Every pair exactly once

count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    Move X to Table 2
    while(Table 1 has more rows){
        Read the first row Y in Table 1
        if(X.CityTown == Y.CityTown){
            count = count + 1
        }
        Move Y to Table 3
    }
    Move all rows from Table 3 to Table 1
}

count = number of pairs of students from the same city.

Counting pairs on a grid

compared oncesame pair again (double counting)Diagonal: X never meets itself

Six cards A–F. The nested loop only visits the green cells.

Unordered pairs (each once): n(n − 1)2
n = 30 ⇒ 435
Ordered pairs, X ≠ Y: n(n − 1)
Every X with every Y, itself included: n²
Pairs within groups of sizes k₁, k₂, …: Σ k_i(k_i − 1)2
Pairs across two groups: k₁ × k₂

Moving X out before the inner loop means X never meets itself and each pair is met once.
If the inner loop also sees X and the cards before it, each pair is counted twice. Halve it.
Birthday paradox: with just 23 people there's about a 50% chance two share a birthday (about 70% with 30), because the number of pairs grows like n².

Worked example

Scores has 30 cards: 10 from Chennai, 8 from Vellore, 12 from Madurai. How many pairs are from the same city? From different cities?

Show solution

Same city: 45 + 28 + 66 = 139.
All pairs: 30 × 292 = 435.
Different cities: 435 − 139.

Answer: 139 same-city pairs, 296 different-city pairs

Traps to avoid

Read whether the question asks for matching pairs or for comparisons made. Comparisons = n(n − 1)/2, whatever the if says.
'Either same gender or same city, but not both' is exclusive or: (A and not B) or (B and not A).

Week 4Some papers

Binning

Binning: first sort the cards into bins by a field (city, birth month, gender), then compare pairs only inside each bin.
Comparisons drop from n(n − 1)/2 to the sum of k(k − 1)/2 over the bins, plus one pass to fill the bins.

Comparisons with bins: Σ k_i(k_i − 1)2

Worked example

30 cards split evenly into 3 bins. How many comparisons with and without binning?

Show solution

Without: 30 × 292 = 435.
With: 3 × 10 × 92 = 3 × 45.

Answer: 435 without, 135 with

Binning 30 cards into 3 bins

Week 4Every paper

Tracing: 'What does A represent?'

Five-step checklist

Start value: 0 → count or sum; large → min; True/False → flag.
Update: + 1 → count; + X.field → sum; = X.field → max, min or 'last seen'.
Filter: list every condition; note and/or and strict (>) vs non-strict (≥).
Scope: reset inside the outer loop? Then it's per-card, and the final value belongs to the last card.
Dry-run 3–4 cards in a trace table (one column per variable) when unsure.

Spot the pattern

Starts atUpdate inside the loopMeaning

count

A = 0A = A + 1

count

sum

A = 0A = A + X.field

sum

max

A = 0if X.f > A: A = X.f

max

min

A = 100if X.f < A: A = X.f

min

flag: 'at least one'

A = FalseA = True

flag: 'at least one'

Flag pattern

found = False
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Total > 250){
        found = True
    }
    Move X to Table 2
}

found = True if at least one student scored above 250.

Dataset-specific patterns

Words: a word ending in a full stop closes a sentence. Per-sentence counters reset there.
Shopping Bills, 'bought both Bread and Milk' (PYQ Jan 2024): set two flags while scanning a bill's items, then count bills where both are True. A ratio like frac is that count ÷ whatever count the question puts in the denominator.

Traps to avoid

Options often differ only by > vs ≥, and vs or, or first vs last. Check those three first.
A count or sum with no filter is about all cards, not the group the option names.

Exam morning

Last-minute checklist

The 12 things to read on the way to the exam centre.

1Initialise before the loop. No 'Move X to Table 2' means the loop never ends.
2> keeps the first maximum; ≥ keeps the last.
3min starts large (100 for marks), never 0.
4count = count + 1 counts; sum = sum + X.field adds.
5not (A and B) = not A or not B.
6count(A or B) = count(A) + count(B) − count(A and B).
7return exits the procedure immediately.
8Pairs: n(n − 1)/2. 30 cards ⇒ 435 pairs.
9Same-group pairs: Σ k(k − 1)/2.
10Comparing with an average takes two passes; restore Table 1 in between.
11Sum of the two smallest = a + b + c − max(a, b, c).
12Euclid: gcd(a, b) = gcd(b, a mod b).

Now test yourself

Turn these notes into marks

Sit a real paper in the exam portal, then come back to the Traps view for whatever you got wrong.

Previous-year papersThe real papers, official keys PracticeDrill PYQs by topic Full mockAll four courses, timed

Formulas and conventions follow the IIT Madras BS course material for weeks 1–4. “Every paper” and “Most papers” count how often a topic appears in the qualifier papers on BTechi (January 2023 to May 2024). BTechi is not affiliated with IIT Madras.

Computational Thinking

BSCS1001 · 10 topics · 12 min read

0/10 revised

Week 1Every paper

The datasets & datatypes

Know these card layouts

Dataset	One card is	Fields you'll filter on
Scores	One student (30 cards, CardNo 0–29)	Name, Gender (M/F), Date of Birth, Town/City, Mathematics, Physics, Chemistry, Total
Words	One word of a paragraph, in order	Word, Part of Speech, Letter count; a sentence ends at a word with a full stop
Shopping Bills	One bill	Shop name, Customer name, items (name, category, quantity, price, cost), bill total
Library, Olympics, others	One book or player record	The question prints the card: read every field name before tracing

Scores
One card is:
One student (30 cards, CardNo 0–29)
Fields you'll filter on:
Name, Gender (M/F), Date of Birth, Town/City, Mathematics, Physics, Chemistry, Total
Words
One card is:
One word of a paragraph, in order
Fields you'll filter on:
Word, Part of Speech, Letter count; a sentence ends at a word with a full stop
Shopping Bills
One card is:
One bill
Fields you'll filter on:
Shop name, Customer name, items (name, category, quantity, price, cost), bill total
Library, Olympics, others
One card is:
One book or player record
Fields you'll filter on:
The question prints the card: read every field name before tracing

Anatomy of a Scores card

Illustrative values. Total is always Mathematics + Physics + Chemistry.

Total = Mathematics + Physics + Chemistry · cost = quantity × price · bill total = sum of item costs · letter count = number of letters in the word.
Sanity of data: every value must be valid for its type. Marks within 0–100, Gender ∈ {M, F}, real dates, totals that add up. A card that breaks these is an error.

Datatypes

Type	Values	Operations that make sense
Boolean	True, False	and, or, not
Integer	…, −1, 0, 1, …	+ − × ÷ mod, comparisons
Character	One letter or symbol	`==`, `!=`, alphabetical order
String	A sequence of characters (names, words)	`==`, joining, length
Subtypes	Marks (integer 0–100), Gender (M/F), Date	Only what the meaning allows: adding two names is invalid

Boolean
Values:
True, False
Operations that make sense:
and, or, not
Integer
Values:
…, −1, 0, 1, …
Operations that make sense:
+ − × ÷ mod, comparisons
Character
Values:
One letter or symbol
Operations that make sense:
==, !=, alphabetical order
String
Values:
A sequence of characters (names, words)
Operations that make sense:
==, joining, length
Subtypes
Values:
Marks (integer 0–100), Gender (M/F), Date
Operations that make sense:
Only what the meaning allows: adding two names is invalid

Week 1Most papers

Variables, iteration & flowcharts

Flowchart symbols

Shape	Meaning
Oval / rounded rectangle	Start or End (terminal)
Rectangle	Process, e.g. count = count + 1
Diamond	Decision: a condition with Yes and No exits
Parallelogram	Input or output
Arrow	Flow of control

The iterator as a flowchart

oval: start / endrectangle: processdiamond: decisionparallelogram: input / output

The same loop as the pseudocode below: the average Maths marks of female students.

Iterator: Pile 1 (unseen) → pick card X → process X → move X to Pile 2 → repeat until Pile 1 is empty.
Initialise every variable before the loop (count = 0, sum = 0).
Filtering: process a card only when a condition holds (a decision box, or an if).
Average = sum ÷ count, computed after the loop ends.

Count + sum in one pass

count = 0
sum = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "F"){
        count = count + 1
        sum = sum + X.Mathematics
    }
    Move X to Table 2
}
avg = sum / count

avg = average Maths marks of female students.

Traps to avoid

Initialising inside the loop resets the variable on every card, so it ends up holding only the last card's value.
A loop that never moves X to Table 2 never ends.

Week 2Every paper

Pseudocode, filtering & AND / OR

Exam-style pseudocode

count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "F" and X.CityTown == "Chennai"){
        count = count + 1
    }
    Move X to Table 2
}

count = number of female students from Chennai.

Operators

Write	Means
`a = b`	Assign: store the value of b in a
`a == b`	Compare: is a equal to b?
`a != b`	Not equal
`and`	True only when both sides are true
`or`	True when at least one side is true
`not`	Flips True and False
`a mod b`	Remainder: 17 mod 5 = 2

Logic you'll use

De Morgan: not (A and B) = (not A) or (not B)
De Morgan: not (A or B) = (not A) and (not B)
Count of A or B: count(A) + count(B) − count(A and B)
Exactly one of A, B: (A and not B) or (B and not A)

Worked example

In Scores, 14 students are female, 12 are from Chennai, and 5 are female and from Chennai. What does an X.Gender == "F" or X.CityTown == "Chennai" filter count?

Show solution

Count(A or B) = 14 + 12 − 5.

Answer: 21 students

and, or, exactly one

A and Bboth: 5

A or Bat least one: 14 + 12 − 5 = 21

Exactly one(A and not B) or (B and not A): 16

14 female students, 12 from Chennai, 5 both.

Brackets change meaning: (A and B) or C ≠ A and (B or C).
Check whether each update sits inside or outside the if. Indentation and braces decide.
A = A + 1 counts cards. A = A + X.Marks adds up a field.

Week 2Every paper

Max, min & 'who has it'

Highest mark and who scored it

max = 0
topper = "None"
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Mathematics > max){
        max = X.Mathematics
        topper = X.Name
    }
    Move X to Table 2
}

Filtered min (PYQ May 2023: lowest Chemistry, male, Vellore)

min = 100
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Gender == "M" and X.CityTown == "Vellore"){
        if(X.Chemistry < min){
            min = X.Chemistry
        }
    }
    Move X to Table 2
}

Tracing max over five cards

max so far (starts at 0)Ties: strict > keeps the first card, ≥ keeps the last.

Ties: which card wins?

Comparison	On a tie, keeps
`X.M > max`	the first card with the maximum
`X.M >= max`	the last card with the maximum
`X.M < min`	the first card with the minimum
`X.M <= min`	the last card with the minimum

max = 0 is safe only when every value is ≥ 0. For min, start above the largest possible value (100 for marks) or with the first card's value.
Second highest: if X > max { second = max; max = X } else if X > second { second = X }.

Traps to avoid

min = 0 bug: no mark is below 0, so min never changes. A favourite 'find the mistake' option.
Setting topper outside the if stores the last card's name, not the topper's.
If no card passes the filter, max and min keep their starting values.

Week 3Every paper

Procedures, parameters & return

A procedure

Procedure isVowel(c)
    if(c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'){
        return(True)
    }
    return(False)
End isVowel

What happens on a call

Parameters are the inputs. A call like isVowel(letter) substitutes the argument for c.
return(v) hands v back and exits immediately. Nothing after it runs.
Side effect: the procedure changes something outside itself (moves rows between tables, changes an outside variable). Ask whether the table is the same after the call.
Loop counting: i = 1; while(i <= 20){ i = i * 2 } runs for i = 1, 2, 4, 8, 16: five times.

Standard procedures: learn the trick

Task	Trick
Sum of the two smallest of a, b, c (PYQ Jan 2024)	a + b + c − max(a, b, c)
Largest of three	compare a with b, then the winner with c
Even or odd	`n mod 2 == 0` ⇒ even
Last digit / drop it	`n mod 10` / `floor(n / 10)`
Sum of digits	repeat `s = s + n mod 10`, `n = floor(n / 10)` until n = 0
Reverse a number	repeat `r = r × 10 + n mod 10`, `n = floor(n / 10)`
GCD (Euclid)	`while(b != 0){ t = b; b = a mod b; a = t }` → answer a
Divisible by k	`n mod k == 0`

Trace the GCD loop

Run the Euclid loop with a = 36, b = 24.

Show solution

(36, 24): t = 24, b = 36 mod 24 = 12, a = 24.
(24, 12): t = 12, b = 24 mod 12 = 0, a = 12.
b = 0, so the loop stops.

Answer: 12

Worked example

Sum of digits of 4096 with the mod-10 loop?

Show solution

6 → n = 409
6 + 9 = 15 → n = 40
15 + 0 = 15 → n = 4
15 + 4 = 19 → n = 0

Answer: 19

Week 3Most papers

Slab and bill problems (if / else if)

₹5 for the first 100 units, ₹7 for the next 100, ₹10 after that

if(unit <= 100){
    cost = unit * 5
}
else if(unit <= 200){
    cost = 100 * 5 + (unit - 100) * 7
}
else{
    cost = 100 * 5 + 100 * 7 + (unit - 200) * 10
}

Each rate applies only to the units inside its own slab.
An else-if chain checks top to bottom and stops at the first true condition, so the order of the checks matters.

PYQ pattern (May 2023)

Using the slabs above, what is the bill for 250 units?

Show solution

First 100: 100 × 5 = 500.
Next 100: 100 × 7 = 700.
Last 50: 50 × 10 = 500.

Answer: ₹1700

250 units through the slabs

Each rate applies only to the units inside its own slab.

Traps to avoid

Wrong-option pattern: cost = unit * 10 for unit > 200, which charges every unit at the top rate.
Boundaries: is exactly 100 units in slab 1 (<=) or slab 2 (<)? Check the comparison sign.

Week 3Most papers

Multiple (non-nested) iterations

PYQ (Jan 2024): students above the class average

sum = 0
n = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    sum = sum + X.Total
    n = n + 1
    Move X to Table 2
}
avg = sum / n
Move all rows from Table 2 to Table 1
count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Total > avg){
        count = count + 1
    }
    Move X to Table 2
}

Two passes, in order

1
Pass 1: add up every Total and count the rows
Every card moves from Table 1 to Table 2.
2
avg = sum / n
Only known once pass 1 has finished.
3
Move all rows from Table 2 back to Table 1
Skip this and pass 2 runs zero times.
4
Pass 2: count the rows with X.Total > avg

You can't compare with the average until you know it, so it takes two passes.
Restore Table 1 between passes, or the second loop runs zero times.
Three prizes problem: keep first, second and third in one pass, shifting values down whenever a bigger total arrives.

Week 4Every paper

Nested iterations: comparing pairs

Every pair exactly once

count = 0
while(Table 1 has more rows){
    Read the first row X in Table 1
    Move X to Table 2
    while(Table 1 has more rows){
        Read the first row Y in Table 1
        if(X.CityTown == Y.CityTown){
            count = count + 1
        }
        Move Y to Table 3
    }
    Move all rows from Table 3 to Table 1
}

count = number of pairs of students from the same city.

Counting pairs on a grid

compared oncesame pair again (double counting)Diagonal: X never meets itself

Six cards A–F. The nested loop only visits the green cells.

Unordered pairs (each once): n(n − 1)2
n = 30 ⇒ 435
Ordered pairs, X ≠ Y: n(n − 1)
Every X with every Y, itself included: n²
Pairs within groups of sizes k₁, k₂, …: Σ k_i(k_i − 1)2
Pairs across two groups: k₁ × k₂

Moving X out before the inner loop means X never meets itself and each pair is met once.
If the inner loop also sees X and the cards before it, each pair is counted twice. Halve it.
Birthday paradox: with just 23 people there's about a 50% chance two share a birthday (about 70% with 30), because the number of pairs grows like n².

Worked example

Scores has 30 cards: 10 from Chennai, 8 from Vellore, 12 from Madurai. How many pairs are from the same city? From different cities?

Show solution

Same city: 45 + 28 + 66 = 139.
All pairs: 30 × 292 = 435.
Different cities: 435 − 139.

Answer: 139 same-city pairs, 296 different-city pairs

Traps to avoid

Read whether the question asks for matching pairs or for comparisons made. Comparisons = n(n − 1)/2, whatever the if says.
'Either same gender or same city, but not both' is exclusive or: (A and not B) or (B and not A).

Week 4Some papers

Binning

Binning: first sort the cards into bins by a field (city, birth month, gender), then compare pairs only inside each bin.
Comparisons drop from n(n − 1)/2 to the sum of k(k − 1)/2 over the bins, plus one pass to fill the bins.

Comparisons with bins: Σ k_i(k_i − 1)2

Worked example

30 cards split evenly into 3 bins. How many comparisons with and without binning?

Show solution

Without: 30 × 292 = 435.
With: 3 × 10 × 92 = 3 × 45.

Answer: 435 without, 135 with

Binning 30 cards into 3 bins

Week 4Every paper

Tracing: 'What does A represent?'

Five-step checklist

Start value: 0 → count or sum; large → min; True/False → flag.
Update: + 1 → count; + X.field → sum; = X.field → max, min or 'last seen'.
Filter: list every condition; note and/or and strict (>) vs non-strict (≥).
Scope: reset inside the outer loop? Then it's per-card, and the final value belongs to the last card.
Dry-run 3–4 cards in a trace table (one column per variable) when unsure.

Spot the pattern

Starts atUpdate inside the loopMeaning

count

A = 0A = A + 1

count

sum

A = 0A = A + X.field

sum

max

A = 0if X.f > A: A = X.f

max

min

A = 100if X.f < A: A = X.f

min

flag: 'at least one'

A = FalseA = True

flag: 'at least one'

Flag pattern

found = False
while(Table 1 has more rows){
    Read the first row X in Table 1
    if(X.Total > 250){
        found = True
    }
    Move X to Table 2
}

found = True if at least one student scored above 250.

Dataset-specific patterns

Words: a word ending in a full stop closes a sentence. Per-sentence counters reset there.
Shopping Bills, 'bought both Bread and Milk' (PYQ Jan 2024): set two flags while scanning a bill's items, then count bills where both are True. A ratio like frac is that count ÷ whatever count the question puts in the denominator.

Traps to avoid

Options often differ only by > vs ≥, and vs or, or first vs last. Check those three first.
A count or sum with no filter is about all cards, not the group the option names.

Exam morning

Last-minute checklist

The 12 things to read on the way to the exam centre.

1Initialise before the loop. No 'Move X to Table 2' means the loop never ends.
2> keeps the first maximum; ≥ keeps the last.
3min starts large (100 for marks), never 0.
4count = count + 1 counts; sum = sum + X.field adds.
5not (A and B) = not A or not B.
6count(A or B) = count(A) + count(B) − count(A and B).
7return exits the procedure immediately.
8Pairs: n(n − 1)/2. 30 cards ⇒ 435 pairs.
9Same-group pairs: Σ k(k − 1)/2.
10Comparing with an average takes two passes; restore Table 1 in between.
11Sum of the two smallest = a + b + c − max(a, b, c).
12Euclid: gcd(a, b) = gcd(b, a mod b).

Now test yourself

Turn these notes into marks

Sit a real paper in the exam portal, then come back to the Traps view for whatever you got wrong.

Previous-year papersThe real papers, official keys PracticeDrill PYQs by topic Full mockAll four courses, timed