🧠 IIT Madras Notes

CT Week 2 - Advanced Procedural Thinking

8 min read

Computational Thinking - Week 2: Advanced Procedural Thinking

  • Core Idea: This week, we build on the fundamentals by introducing more complex logic. We’ll learn how to find the “best” card in a dataset (min/max), use multiple conditions to answer sophisticated questions, and understand how the order of our instructions can completely change the outcome of a procedure.

đź“š Table of Contents

  1. Fundamental Concepts
  2. Question Pattern Analysis
  3. Detailed Solutions by Pattern
  4. Practice Exercises
  5. Visual Learning: Mermaid Diagrams
  6. Common Pitfalls & Traps
  7. Quick Refresher Handbook

1. Fundamental Concepts

🎯 1.1 Finding Minimum and Maximum Values

This is one of the most common and important algorithmic patterns. The core idea is to maintain a “champion” variable and compare every card against it, updating the champion if a new, better card is found.

  • The “King of the Hill” Analogy:

    • You pick one person (the first card) and declare them the “King” (the current maximum).
    • Every other person in line challenges the King.
    • If the challenger is stronger (has a greater value), they become the new King.
    • After everyone has had a chance, the last person remaining as King is the strongest (the true maximum).

  • The Algorithm for Finding a Maximum:

    1. Initialize Max_Value to a very small number (or the value from the first card). Initialize Max_Value to 0 is common if all values are known to be positive.
    2. In the loop, for each card X:
    3. If X.Value > Max_Value then
    4. Set Max_Value = X.Value

  • The Algorithm for Finding a Minimum:

    1. Initialize Min_Value to a very large number. This is crucial. If you initialize it to 0, you’ll never find a minimum greater than 0. Initialize Min_Value to 1000 is a safe bet if scores are 0-100.
    2. In the loop, for each card X:
    3. If X.Value < Min_Value then
    4. Set Min_Value = X.Value

⚙️ 1.2 Complex Conditionals and Logic

This week, we move beyond simple If statements to combine them in powerful ways.

  • Nested Conditionals: An If statement inside another If statement. This allows for more specific filtering.

    If Gender is 'M' then
    If City is 'Chennai' then
        Increment Count

    This is equivalent to a single compound AND condition: If Gender is 'M' AND City is 'Chennai' then...

  • Updating Variables Conditionally: The logic depends on how and when variables are updated.

    • Example 1: Counting “A AND B” If Condition A is true AND Condition B is true then increment Count
    • Example 2: Calculating “(Total A) - (Total A that are also B)” Initialize A to 0, B to 0 If Condition A is true then increment A If Condition A is true AND Condition B is true then increment B Result = A - B (This gives the count of A that are not B).

🔄 1.3 State and Re-initialization

  • State: The values of all your variables at any given moment.
  • Re-initialization: Resetting a variable’s value, often inside a loop. This is a powerful but tricky concept. It’s often used for tasks that involve grouping, like finding the length of each sentence in a paragraph.
    • Example: Finding the length of the shortest sentence. You need one variable for the “champion” (Shortest_Length) and another for the “current challenger” (Current_Sentence_Length). 
      Initialize Shortest_Length to 1000
Initialize Current_Sentence_Length to 0
Loop through cards:
    Add Letter Count to Current_Sentence_Length
    If the word ends with a full stop then
        If Current_Sentence_Length < Shortest_Length then
            Set Shortest_Length = Current_Sentence_Length
        Re-initialize Current_Sentence_Length to 0  // Get ready for the next sentence
    The re-initialization is the key step that separates one sentence from the next.

2. Question Pattern Analysis

From the Week_2_Graded_Assignment, these patterns are central.

Pattern #Pattern NameFrequencyDifficultyCore Skill
2.1Finding Minimum/MaximumHighEasyIdentifying the logic for finding the smallest or largest value in a dataset.
2.2Interpreting Compound ConditionsHighMediumDetermining what a final count represents based on complex AND/OR logic.
2.3Procedure Tracing with Complex LogicMediumMediumManually executing a procedure with multiple variables and conditional updates.
2.4Identifying Bugs in LogicMediumEasy-MediumSpotting errors in initialization or conditional statements.
2.5State Management & Re-initializationLowHardUnderstanding procedures that reset variables inside a loop to handle groups.

3. Detailed Solutions by Pattern

Pattern 2.1: Finding Minimum/Maximum

  • Core Skill: Recognizing the “champion” variable and its update condition.

Example Problem:

What do A and B represent at the end of this procedure on the “Scores” dataset?

Step 1: Arrange all cards in Pile 1
Step 2: Initialize A to 101 and B to 0
Step 3: If Pile 1 is empty then stop
Step 4: Read the top card
Step 5: If A > Chemistry marks, then store Chemistry marks in A
Step 6: If B < Mathematics marks, then store Mathematics marks in B
Step 7: Move card to Pile 2 and repeat from Step 3

TAA in Action:

  1. Triage: Keywords “A > … store in A”, “B < … store in B”. This is a min/max problem.
  2. Abstract:
    • Variable A is initialized to a large number (101, which is > max possible score). It is only updated if the current Chemistry marks are smaller than the current A. This is the algorithm for finding the minimum.
    • Variable B is initialized to a small number (0). It is only updated if the current Mathematics marks are larger than the current B. This is the algorithm for finding the maximum.
  3. Act: Apply the logic. A finds the minimum Chemistry marks, and B finds the maximum Mathematics marks.

Final Answer: A = Lowest marks in Chemistry, B = Highest marks in Mathematics.

Pattern 2.2: Interpreting Compound Conditions

  • Core Skill: Translating pseudocode logic into a plain English sentence.

Example Problem:

What does (A–B) represent after this procedure on the “Shopping Bills” dataset?

Step 1: ...
Step 2: Initialize A and B to 0
Step 3: ...
Step 4: Read card
Step 5: If the bill contains "Bananas" then add 1 to A
Step 6: If Total < 600 AND the bill contains "Bananas" then add 1 to B
Step 7: ...

TAA in Action:

  1. Triage: This asks for the meaning of A-B. I need to define A and B in English first.
  2. Abstract:
    • A = The total count of bills containing “Bananas”.
    • B = The count of bills that contain “Bananas” AND have a total less than 600.
    • Therefore, A - B = (Total “Bananas” bills) - (“Bananas” bills with Total < 600).
  3. Act:
    • The result of the subtraction is the count of “Bananas” bills that are not in group B.
    • The opposite of Total < 600 is Total >= 600.
    • So, A - B represents the number of bills that contain “Bananas” and have a total greater than or equal to 600.

Final Answer: Number of bills that contain the item “Bananas” and total is more than or equal to 600.

Pattern 2.5: State Management & Re-initialization

  • Core Skill: Recognizing that re-initializing a variable marks the end of one “group” and the start of the next.

Example Problem:

What does A represent at the end of this procedure on the “Words” dataset?

Step 1: ...
Step 2: Initialize A to 1000 and B to 0
Step 3: ...
Step 4: Read card
Step 5: Add Letter Count to B
Step 6: If Word does not end with a full stop then go to Step 9
Step 7: If Word ends with a full stop AND B < A then store B in A
Step 8: Re-initialize B to 0
Step 9: ...

TAA in Action:

  1. Triage: I see a variable B being reset (Re-initialize B to 0). This is a grouping pattern. The trigger for the reset is a “full stop”. This procedure is processing sentences.
  2. Abstract:
    • B is an accumulator. It’s summing Letter Count for each word.
    • When a full stop is found, the procedure checks if the current sum (B) is the smallest one seen so far (by comparing with A, which is a “min” variable).
    • Then, B is reset to 0 to start counting the letters of the next sentence.
    • Therefore, the procedure is finding the length of the shortest sentence.
  3. Act: The variable A is the “champion” (minimum-holder), and it holds the total number of letters.

Final Answer: Length of the shortest sentence based on the number of letters.

Memory Palace: Week 2 Concepts

  • Finding Minimum (The Limbo Dance):

    • You set the bar very high initially (Initialize Min_Value to 1000).
    • Each person (card) tries to go under the bar.
    • If a person is shorter (X.Value < Min_Value), you lower the bar to their height (Set Min_Value = X.Value).
    • At the end, the bar’s height is the height of the shortest person (the minimum value).

  • Re-initialization (The Grocery Bagger):

    • Imagine you are bagging groceries (B is your current bag’s weight).
    • You keep adding items (letters) to the bag (Add Letter Count to B).
    • When you see a special item (a “full stop”), you know the order is complete. You weigh the bag and see if it’s the lightest one yet (If B < A).
    • Then you get a new, empty bag (Re-initialize B to 0) for the next customer’s order.

Graph View

Recent Features

    Backlinks