🧠 IIT Madras Notes

Patterns

3 min read

CT: The Master Encyclopedia (Patterns & Traps)

IMPORTANT

A “Pattern” is a reusable template for solving a specific type of problem. A “Trap” is a common mistake designed to lose you marks. Master these.

🧩 Type 1: The “Pile Iteration” Patterns

1️⃣ The Filter-Count Pattern

Goal: Count how many cards meet a condition. Recipe:

  1. Initialize Count = 0.
  2. Inside Loop: If (Condition) { Count = Count + 1 }.
  3. Trap: Forgetting to initialize Count (often defaults to Garbage or Error if specific language, but in pseudocode usually 0).
  4. Trap: Updating Count OUTSIDE the If block (counts everything).

2️⃣ The “Max/Min” Pattern

Goal: Find the student with the highest marks. Recipe:

  1. Initialize Max = 0 (or -Infinity).
  2. Inside Loop: If (X.Marks > Max) { Max = X.Marks, BestStudent = X.Name }.
  3. Trap: Initializing Max to 0 if data can be negative (use first(Pile).Marks instead).
  4. Trap: Only updating Max but forgetting BestStudent (if question asks “Who?”, not “How much?“).

3️⃣ The “Flag” Pattern (Found / All)

Goal: Check if at least one element meets condition (Exists) OR all elements meet condition (For All). Recipe (Exists):

  1. Found = False
  2. If (Condition) { Found = True, Break (Optional but Efficient) } Recipe (For All):
  3. AllValid = True
  4. If (NOT Condition) { AllValid = False, Break }

🧩 Type 2: List Logic Patterns

1️⃣ The “First Checks” Pattern

Goal: Logic involving first(L) inside a loop. Recipe:

While (L has elements) {
    X = first(L)
    // Do something
    L = rest(L) // CRITICAL STEP
}

Trap: Forgetting L = rest(L) leads to Infinite Loop (processing same element forever).

2️⃣ The “Nested Pair” Pattern (O(N^2))

Goal: Find pairs (e.g., “Two students from same city”). Recipe:

  1. Loop 1 (Iterator i or X).
  2. Loop 2 (Iterator j or Y).
  3. Condition: X.id != Y.id (Exclude Self-Comparison!) AND X.City == Y.City.
  4. Optimization: If order doesn’t matter, ensure X.id < Y.id to avoid double counting (A, B) and (B, A).

🧩 Type 3: Dictionary Patterns

1️⃣ The “Histogram” (Frequency Count)

Goal: Count occurrences of each word/category. Recipe:

If (isKey(D, Item)) {
    D[Item] = D[Item] + 1
} Else {
    D[Item] = 1
}

Trap: Accessing D[Item] before checking isKey. Error!

2️⃣ The “Nested Key” Access

Goal: D[Student][Subject] = Marks. Recipe:

  1. Check if Student key exists. If not, D[Student] = {}.
  2. Then assign D[Student][Subject] = Marks. Trap: Trying D[Student][Subject] = X when D[Student] is undefined.

🧩 Type 4: Graph & Matrix Patterns

1️⃣ The “Triadic Closure” (Friend of Friend)

Goal: Find people who share a mutual friend but are not friends directly. Recipe (Matrix M):

  1. Check M[i][j] == 0 (Not friends).
  2. Iterate k (The mutual friend).
  3. Check M[i][k] == 1 AND M[k][j] == 1.
  4. If logic holds for any k, they are candidates.

2️⃣ The “Degree” Calculation

Goal: Who has most friends? Recipe:

  1. Sum the Row i (Sum = Sum + M[i][j]).
  2. Max Row Sum = Node with highest Out-Degree (or Degree if undirected).

🧩 Type 5: Recursive Patterns

1️⃣ The “Base Case” Check

Goal: Ensure recursion stops. Rule: ALWAYS check Base Case FIRST. Trap: Recursion inside the Base Case If block (Infinite Recursion).

2️⃣ The “Accumulator” (Tail Recursion)

Goal: Passing state down. Recipe: Proc(L, Count).

  • Call: Proc(rest(L), Count + 1).
  • Base Case: Return Count.

3️⃣ The “Build Up” (Head Recursion)

Goal: Building result on way back. Recipe: return [first(L)] ++ Proc(rest(L)).

  • Result is built as stack unwinds.

Graph View

Recent Features