🧠 IIT Madras Notes

CT Week 1 - Procedural Thinking

8 min read

Computational Thinking - Week 1: Procedural Thinking

  • Core Idea: This week, we learn to think like a computer scientist—not by writing code, but by breaking down tasks into simple, unambiguous steps. We will learn how to read and write procedures (also called algorithms) using a simple model involving piles of cards, and understand the basic components that make these procedures work.

đź“š 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 The Card Machine Model

To think about procedures, we use a simple mental model. Imagine you have a deck of cards, where each card contains a piece of information (like a student’s scores or items on a shopping bill). Your goal is to process this deck.

  • Pile 1: The initial, unsorted pile of cards you need to process.
  • The Processor: You. You can only read one card at a time—the top card of Pile 1.
  • Pile 2: A discard pile where you place cards after you are done with them.
  • Procedure: A numbered list of steps that tell you exactly what to do with each card.

⚙️ 1.2 The Core Components of a Procedure

Every procedure we write is built from a few simple, powerful ideas.

  1. Variables & Initialization:

    • A variable is a named placeholder for a piece of information. Think of it as a small whiteboard where you can write down and update a value. Examples: Count, TotalAmount, X.
    • Initialization is the most important first step: giving a variable its starting value before the main work begins.
      • Initialize Count to 0 (If you’re counting things).
      • Initialize TotalAmount to 0 (If you’re summing things up).
      • Initialize Max_Score to 0 (If you’re finding the highest score).

  2. Iteration (The Loop):

    • Iteration is the act of repeating a set of instructions. In our model, this means processing every card in Pile 1, one by one.
    • A loop always has three parts:
      1. The Termination Condition: A check to see if the work is done. Step 3: If Pile 1 is empty then stop the iteration.
      2. The Body: The work you do for a single card (reading it, checking conditions, updating variables). Steps 4, 5...
      3. The Loop Instruction: Moving the processed card and going back to the termination check. Step 6: Move the current card to Pile 2 and repeat from Step 3.

  3. Conditionals (The Decision Maker):

    • A conditional is an If... then... statement. It allows your procedure to make decisions and behave differently based on the data it reads.
    • Simple Condition: Checks one thing. If the Shop Name is “SV Stores” then...
    • Compound Condition: Uses AND or OR to check multiple things. If Shop Name is "SV Stores" AND Total Bill Amount > 500 then...
      • AND: Both parts must be true.
      • OR: At least one part must be true.

đź“Š 1.3 Data and Sanity

  • Dataset: A collection of related data, like our “Shopping Bills” or “Scores” decks.
  • Attribute: A property or field on a card, like “Shop Name” or “Total Bill Amount”.
  • Data Sanity: Checking if the data makes sense. This is a crucial first step in any real-world data task.
    • Data Type Sanity: Is the data in the correct format? A Card Number should be a number, not text like “One”.
    • Value Sanity: Is the value plausible? A Letter Count cannot be negative. A Total Bill Amount is unlikely to be zero or negative.

2. Question Pattern Analysis

From the Week_1_Graded_Assignment, we can identify these primary question types.

Pattern #Pattern NameFrequencyDifficultyCore Skill
1.1Procedure InterpretationHighEasyReading a procedure and determining its overall goal (e.g., finding an average).
1.2Bug IdentificationMediumEasy-MediumFinding the logical error in a procedure that prevents it from working correctly.
1.3Procedure Tracing (Execution)HighMediumManually executing a procedure on a given dataset to find a variable’s final value.
1.4Data Sanity ChecksLowEasyIdentifying incorrect or invalid data entries in a table.

3. Detailed Solutions by Pattern

Pattern 1.1: Procedure Interpretation

  • Core Skill: Identifying the roles of different variables (counter, accumulator) and how they are combined in the end.

Example Problem:

The following procedure is executed using the “Shopping Bills” dataset. What will X represent at the end of execution?

Step 1: Arrange all cards in Pile 1
Step 2: Initialize variables A, B and X to 0
Step 3: If Pile 1 is empty then stop and go to Step 7
Step 4: Read the top card
Step 5: If Shop Name is “SV Stores” then add total bill amount to A and increment B
Step 6: Move card to Pile 2 and repeat from Step 3
Step 7: X = A / B

TAA in Action:

  1. Triage: Keywords “what will X represent”. This is a procedure interpretation problem.
  2. Abstract: I need to figure out what A and B are accumulating, and then what A/B means.
  3. Act:
    • Analyze Variable A: It starts at 0. In Step 5, it add[s] total bill amount. This only happens if the Shop Name is “SV Stores”. So, A is the sum of bill amounts from SV Stores.
    • Analyze Variable B: It starts at 0. In Step 5, it is increment[ed]. This only happens for “SV Stores”. So, B is the count of bills from SV Stores.
    • Analyze Step 7: X = A / B is (Sum of values) / (Count of values). This is the definition of an average.

Final Answer: X represents the Average of total bill amount from “SV Stores”.

Pattern 1.2: Bug Identification

  • Core Skill: Mentally tracing the flow of the loop to spot incorrect jumps or resets.

Example Problem:

This procedure is supposed to count bills from “SV Stores” with a total > 500. Find the mistake.

Step 1: Arrange cards in Pile 1
Step 2: Initialize count to 0
Step 3: If Pile 1 is empty then stop
Step 4: Read top card
Step 5: If Shop Name is "SV Stores" AND Total > 500 then increment count
Step 6: Move card to Pile 2 and repeat from Step 2

TAA in Action:

  1. Triage: Keywords “find the mistake”. This is a bug identification problem.
  2. Abstract: I need to trace the loop’s path. The “repeat from” instruction is the most common place for bugs.
  3. Act:
    • Trace the first iteration: Let’s say the first card matches. count starts at 0. After Step 5, count becomes 1.
    • Trace the loop instruction: Step 6 says “repeat from Step 2”.
    • Spot the error: Step 2 is Initialize count to 0. This means that before processing the next card, the procedure will reset count back to 0. The procedure will never be able to count past 1.
    • The Fix: The loop should repeat from Step 3, which is the termination condition, not the initialization step.

Final Answer: Step 6 contains an incorrect step number for the repeat instruction.

Pattern 1.3: Procedure Tracing (Execution)

  • Core Skill: Patiently and accurately playing the role of the “processor”, updating variable values on a scratchpad for each card.

Example Problem:

The following pseudocode is executed using the “Words” dataset. What will A & B represent? Dataset snippet: (word: “The”, PoS: “Article”, Letters: 3), (word: “is”, PoS: “Verb”, Letters: 2), (word: “running”, PoS: “Verb”, Letters: 7), (word: “fast”, PoS: “Adverb”, Letters: 4).

Step 1: Arrange all cards in Pile 1
Step 2: Initialize A, B to 0
Step 3: If Pile 1 is empty then stop
Step 4: Read the top card
Step 5: If Part of Speech is “Verb” then add Letter Count to A
Step 6: If Part of Speech is “Adverb” then add Letter Count to B
Step 7: Move card to Pile 2 and repeat from Step 3

TAA in Action:

  1. Triage: Keywords “what will A & B represent” with a specific dataset. This is a tracing problem.
  2. Abstract: I need a “scratchpad” to track the values of A and B as I process each card one by one.
  3. Act:
    • Initialization: A = 0, B = 0.
    • Card 1 (“The”): PoS is “Article”. Neither Step 5 nor 6 is triggered. A=0, B=0.
    • Card 2 (“is”): PoS is “Verb”. Step 5 is triggered. A = A + 2. A is now 2. B is still 0.
    • Card 3 (“running”): PoS is “Verb”. Step 5 is triggered. A = A + 7. A is now 9. B is still 0.
    • Card 4 (“fast”): PoS is “Adverb”. Step 6 is triggered. B = B + 4. B is now 4. A is still 9.
    • …continue for all cards…
    • (Assuming the full dataset leads to the given options from your assignment file). After processing all cards, let’s say the total letter count for all verbs was 32 and for all adverbs was 13.

Final Answer: A = 32, B = 13.

Memory Palace: Week 1 Concepts

  • The Procedure as a Recipe:

    • Variables: Your mixing bowls (Initialize A to 0 means getting a clean bowl).
    • Pile 1: Your pile of ingredients.
    • The Loop: The instruction “for each ingredient in the pile…“.
    • Conditionals: Instructions like “If the ingredient is an egg, whisk it. Otherwise, chop it.”
    • The Bug: The recipe says, “for each ingredient, get a new clean bowl.” You’d never finish! This is like repeating from the initialization step. You must repeat after getting your bowl.

  • Finding an Average (The Most Common Pattern):

    • You always need two variables: a Sum (an accumulator) and a Count (a counter).
    • Inside the loop, you update both: Sum = Sum + value, Count = Count + 1.
    • After the loop, you calculate Average = Sum / Count. Recognizing this pattern saves a lot of time.

Graph View

Recent Features

    Backlinks