Week 4: Nested Iterations

BSCS1001 — IIT Madras BS Degree Prerequisite: Week 2 (Single Iteration), Week 3 (Procedures) Cross-links: BSCS1002-Python (Week 6 — Nested Loops), BSCS2002-PDSA (Week 4 — Complexity)

1. Motivation: Beyond Single Pass

Problems That Need Pairwise Comparison

💡 Key Insight: Single-pass iteration relates each card to an aggregate (sum, max, count). Nested iteration relates each card to every other card.

2. What are Nested Iterations?

Visual Pattern

pseudo
Outer loop: For each card X in the deck
    Inner loop: For each card Y in the deck
        Compare X and Y

Pseudocode Structure

sql
Initialize results
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    // Inner iteration
    while (Pile 2 has cards before X) {   // or process all other cards
        Pick a card Y
        Compare X with Y
    }
}

A Concrete Example

sql
// Find all pairs of students (X, Y) such that X != Y
Pairs = []
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    // Compare X with every card in Pile 2 (already processed cards)
    while (Pile 2 has more cards before X) {
        Pick a card Y from Pile 2 (not X)
        Pairs = Pairs ++ [(X.Id, Y.Id)]
    }
}

3. The Birthday Paradox Problem

Problem

Naive Approach (Without Binning)

sql
shared = []
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    // Compare X's birthday with all remaining cards
    for each card Y in Pile 1 {
        if (X.Dob == Y.Dob) {
            shared = shared ++ [(X.Id, Y.Id)]
        }
    }
}

Tracing the Birthday Paradox

Why not count C-A? Because A-C was already counted when X=A. Counting C-A would double-count. By only comparing X with cards still in Pile 1 (after X), we count each pair exactly once.

4. Naive Approach: Comparing All Pairs

pseudo
for each card X in the deck {
    for each card Y in the deck {
        if (X != Y) {
            Compare X and Y
        }
    }
}

Visualizing All Pairs

pseudo
Comparisons:
A with A (self) — skip
A with B, A with C, A with D, A with E  (4 comparisons)
B with A, B with B (self), B with C, B with D, B with E  (4 comparisons, but B-A is duplicate)
C with A, C with B, C with C (self), C with D, C with E  (4 comparisons, duplicates)
D with A, D with B, D with C, D with D (self), D with E  (4 comparisons, duplicates)
E with A, E with B, E with C, E with D, E with E (self)  (4 comparisons, duplicates)

Optimized: Avoid Self-Comparison and Duplicates

sql
// Only compare each pair ONCE
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2
    // Compare X only with cards REMAINING in Pile 1
    for each card Y in Pile 1 {
        Compare X and Y
    }
}

5. Sequential vs Nested Iterations

Sequential (Non-Nested) Iterations

pseudo
// First iteration: Compute average
Sum = 0, Count = 0
for each card X {
    Sum = Sum + X.Marks
    Count = Count + 1
}
Average = Sum / Count
// Second iteration: Find below-average students
BelowAvg = []
for each card X {
    if (X.Marks < Average) {
        BelowAvg = BelowAvg ++ [X.Id]
    }
}

When to Use Each

6. Counting Comparisons

Without Optimization (All Pairs)

pseudo
Total comparisons = N × N = N²

With Self-Comparison Removed

pseudo
Total comparisons = N × N - N = N × (N - 1)

With Duplicate Pairs Removed (Each Pair Once)

pseudo
Total comparisons = N × (N - 1) / 2

Step-by-Step Derivation

Visualization for N = 5

7. The Comparison Formula

The General Formula

Growth Table

Why This Matters

Derivation from First Principles

1. Total possible ordered pairs: N × N
2. Remove pairs with self: N × N - N = N × (N-1)
3. Each unordered pair counted twice: N × (N-1) / 2

Alternative Derivation

• First element compares with N-1 others
• Second element compares with N-2 others (already compared with first)
• Third element compares with N-3 others
• ...
• Last element compares with 0 others Sum: (N-1) + (N-2) + (N-3) + ... + 1 + 0 = N × (N-1) / 2

8. Practice Questions

Basic Questions

Show Answer

A nested iteration is a loop inside another loop. For each iteration of the outer loop, the inner loop runs completely. It's used to compare every pair of elements. Q2. How many comparisons are needed to compare all pairs of 8 elements (each pair once)? Show Answer

$\frac{8 \times (8-1)}{2} = \frac{8 \times 7}{2} = \frac{56}{2} = 28$

Answer: 28 comparisons Q3. Compare sequential iterations vs nested iterations in terms of what relationship they establish. Show Answer

• Sequential iterations: Establish relationship between an element and the aggregate (e.g., comparing a student's mark to the class average)
• Nested iterations: Establish relationship between element and element (e.g., comparing two students' birthdays) Q4. For N=10, how many pairwise comparisons are saved by avoiding self-comparison and duplicates? Show Answer

Saved: 100 - 45 = 55 comparisons

Intermediate Questions

• A: DOB=50, B: DOB=50, C: DOB=120, D: DOB=200, E: DOB=50 How many matches are found?

Show Answer

Result: 3 matching pairs: (A,B), (A,E), (B,E) Q6. Write pseudocode to find all pairs of students whose total marks differ by less than 10. Show Answer

sql
ClosePairs = []
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2

    for each card Y in Pile 1 {
        diff = X.Total - Y.Total
        if (diff < 0) {
            diff = -diff    // Absolute value
        }
        if (diff < 10) {
            ClosePairs = ClosePairs ++ [(X.Id, Y.Id)]
        }
    }
}

Show Answer

Cards in Pile 2 have already been processed as X in a previous outer iteration. For example, when X=A compared with B, we recorded pair (A,B). Later, when X=B, if we also compared with A (in Pile 2), we'd record (B,A) — which is the same pair. By only comparing with cards remaining in Pile 1, we count each pair exactly once. Q8. If N=100, how many comparisons does the naive nested approach (including self and duplicates) make, compared to the optimized approach? Show Answer

The optimized approach makes less than half the comparisons (avoids self and halves for duplicates).

Advanced Questions

Show Answer

sql
// Find all triples with same birthday
Triples = []
while (Pile 1 has more cards) {
    Pick a card X from Pile 1
    Move X to Pile 2

    while (Pile 1 has cards before current position) { ... }
    // Actually, we'd need THREE nested loops for triples:

    for each card Y where Y is after X {
        for each card Z where Z is after Y {
            if (X.Dob == Y.Dob AND Y.Dob == Z.Dob) {
                Triples = Triples ++ [(X.Id, Y.Id, Z.Id)]
            }
        }
    }
}

Number of triples: C(N,3) = N(N-1)(N-2)/6

For N=10: 10×9×8/6 = 120 triples to check. Q10. Explain why nested iterations are called "costly" and when you should consider alternatives. Show Answer

Nested iterations are costly because they require O(N²) comparisons. For a dataset of 1 million students, comparing all pairs would require ~500 billion operations — completely impractical.

Alternatives to consider:

1. Binning (Topic 08) — Group items first, compare only within groups
2. Sorting — Sort first, then adjacent items tell you what you need
3. Using dictionaries — Key-value lookups can replace pairwise comparisons
4. Sampling — If exact answer isn't needed, approximate with samples

Rule of thumb: If you see nested loops over the same dataset, ask: "Can I avoid this?" Q11. Trace the execution for finding duplicates (same value) in [7, 2, 7, 4, 2] using the optimized nested approach. Show Answer

Duplicate pairs found: (1,3) and (2,5) — both 7s and both 2s. Q12. Compare the number of comparisons for sequential vs nested approaches to find the average AND the most similar pair of students. Show Answer

For N=100 students:

Takeaway: Finding the average is 50× faster than finding the most similar pair for N=100. For N=1000, the gap is ~500×. Always prefer sequential when possible!

📚 Cross-References

Next Topic: 08 — Binning & Complexity Introduction

Quiz Tip: Know the formula N(N-1)/2 cold — you'll need it for Quiz 2! Join Discord PreviousSide Effects of ProceduresNextBinning & Complexity Introduction