Core Idea: This week, we master the powerful but complex pattern of nested loops. This is the fundamental structure used to solve any problem that requires comparing every item in a dataset with every other item. We’ll learn how to properly structure these loops and use them to find pairs, duplicates, and complex relationships.
The “All-Pairs” pattern is the canonical use for nested loops. Its purpose is to generate every possible pair of items from a dataset so they can be compared.
The Problem: How do you find the two students with the closest exam scores? You must compare student 1 with student 2, student 1 with student 3, …, student 2 with student 3, student 2 with student 4, and so on.
The Pseudocode Structure: This requires three piles.
Pile 1: The main pile of cards to be processed.
Pile 2: A temporary holding pile for cards from the outer loop.
Pile 3: A temporary discard pile for the inner loop.
// Main setupArrange all cards in Pile 1Initialize Pile 2 and Pile 3 as emptyInitialize variable Count to 0// Outer LoopWhile Pile 1 is not empty: Read card X from the top of Pile 1 // Inner Loop: Compare X with every card already processed While Pile 2 is not empty: Read card Y from the top of Pile 2 // The CORE LOGIC happens here If X and Y form a pair that meets the condition then Increment Count Move card Y to Pile 3 // Reset for the next outer loop iteration Move all cards from Pile 3 back to Pile 2 // Move X to the processed pile Move card X from Pile 1 to Pile 2
🧠1.2 Distinguishing Nested Loops from Simple Loops
The key difference is the comparison target.
Simple Loop: Compares each card to a fixed value or an aggregate statistic.
Example: “Find all students whose score is above the class average.” (Each student vs. one number).
Nested Loop: Compares each card to every other card.
Example: “Find all pairs of students from the same country.” (Each student vs. every other student).
⚙️ 1.3 Nested Logic within a Single Iteration
Sometimes, complex logic doesn’t require nested loops over the dataset, but rather nested loops over the attributes of a single card.
The “Consecutive Letters” Analogy:
To check if a word has consecutive consonants, you don’t need to compare it with other words (no outer loop on the deck).
You need a loop that iterates through the letters of that single word.
For each letter, you look at the next letter. This is a nested logic concept.
Pseudocode Structure:
While Pile 1 is not empty: Read card X (contains a word) // Loop through the letters of the word on card X For i from 1 to (Letter Count - 1): Let L1 be the i-th letter Let L2 be the (i+1)-th letter If L1 is a consonant AND L2 is a consonant then // Condition met ...
2. Question Pattern Analysis
From the Week_4_Graded_Assignment, the main patterns are:
Pattern #
Pattern Name
Frequency
Difficulty
Core Skill
4.1
All-Pairs Comparison (Nested Loops)
High
Hard
Recognizing and interpreting the three-pile structure for comparing all pairs.
4.2
Nested Logic on a Single Card
High
Medium
Understanding loops that iterate over the attributes of a single card (e.g., letters in a word).
4.3
Distinguishing Single vs. Nested Loops
High
Medium
Identifying if a problem requires comparing against an aggregate or comparing all pairs.
4.4
Bug Identification in Nested Logic
Medium
Medium
Finding errors in the setup, comparison logic, or reset steps of a nested loop.
3. Detailed Solutions by Pattern
Pattern 4.1: All-Pairs Comparison (Nested Loops)
Core Skill: Correctly interpreting the While Pile 2 is not empty block as the inner loop that compares the current card X with all previously seen cards Y.
Example Problem:
The following pseudocode is executed using the “Olympics” dataset. What will E represent at the end of the execution? (Assume no player won more than one medal).
// (Standard 3-pile nested loop setup as described in 1.1)// The CORE LOGIC is:If X.Country is equal to Y.Country AND X.Medal is not equal to Y.Medal then Increment E
TAA in Action:
Triage: I see the three-pile structure with an outer While Pile 1... loop and an inner While Pile 2... loop. This is an All-Pairs Comparison.
Abstract: The procedure is building up pairs (X, Y) where X is the current card and Y is any card seen before it. The variable E is a counter. It gets incremented only if the pair meets a specific condition.
Act:
Analyze the Condition:X.Country is equal to Y.Country means the two players in the pair must be from the same country.
Analyze the Second Condition:X.Medal is not equal to Y.Medal means the two players must have won different medals.
Combine the Logic: The procedure is counting pairs of players who are from the same country but have won different medals (e.g., one has Gold, the other has Silver).
Final Answer:E represents the number of pairs of players from the same country with different medals.
Pattern 4.2: Nested Logic on a Single Card
Core Skill: Recognizing that the loops are iterating over components of a single data point (like letters in a word), not over the entire dataset multiple times.
Example Problem:
The following pseudocode is executed using the “Words” dataset. What will count represent at the end?
Initialize count to 0While Pile 1 is not empty: Read card X Initialize flag to False // Loop through letters of the word on card X For i from 1 to (Letter Count of X - 1): L1 = i-th letter of X.Word L2 = (i+1)-th letter of X.Word If L1 is a consonant AND L2 is a consonant then Set flag = True If flag is True then Increment count
TAA in Action:
Triage: I see an outer loop processing cards and an inner For loop iterating from 1 to Letter Count. This inner loop is processing the letters of a single word.
Abstract:
The inner loop’s purpose is to check for a specific property within the word.
The condition L1 is a consonant AND L2 is a consonant checks for two consecutive consonants.
The flag is set to True if at least one such pair is found anywhere in the word.
The outer count is incremented only if the flag was flipped to True for that word.
Act: The procedure counts the number of words that contain at least one pair of consecutive consonants. This is different from counting the total number of pairs, which would involve incrementing count inside the inner loop.
Final Answer: Number of words with at least one pair of consecutive consonants. (Note: The assignment answer says “pairs of words”, which seems to be a typo in the question’s options. The logic counts words, not pairs of words).
Memory Palace: Week 4 Concepts
Nested Loops (The Social Network):
Imagine you want to find all pairs of “friends” in a group.
Outer Loop (Card X): You are Person X.
Pile 2: This is the “party room” where people you’ve already processed are waiting.
Inner Loop (Card Y): You walk into the party room and compare yourself to every Person Y already there. You ask each one, “Are we friends?”
Pile 3: A temporary “waiting area” so you don’t talk to the same person twice in one inner loop.
After you’ve talked to everyone in the party room, they all come back from the waiting area, and you join them in the party room, waiting for the next person from the main pile.
Single Loop vs. Nested Loop:
Single Loop Question: “Who in this class is taller than 6 feet?” (Comparing everyone to a fixed standard).
Nested Loop Question: “Who in this class is taller than everyone else?” (Comparing everyone to everyone else).
Nested Logic on One Card (The Word Detective):
You are a detective looking at a single word, like STRENGTH. You don’t care about any other words in the dictionary right now.
Your job is to find consecutive consonants. You take out your magnifying glass (the inner loop).
You look at S and T. Yes! A pair. You can write down “found a pair” (flag=True) and your job is done for this word. You don’t need to check N and G or G and T and H. You’ve already proven the word has what you’re looking for.