🧠 IIT Madras Notes

Theory

8 min read

CT: The Master Encyclopedia (Theory)

IMPORTANT

This document is the V5 Mastermind Standard for Computational Thinking. It covers every concept, algorithm, and pattern from Week 1 to Week 11 with “Goated” detail, including step-by-step traces, edge cases, and axiomatic derivations of logic.

đź“… Week 1: Foundations of Algorithms & Data

1.1 The Computational Metaphor

Computational Thinking in this course is built on a physical metaphor of data processing:

  • The Pile (Dataset): Data is often visualized as a “pile” of cards. Processing means iterating through this pile one card at a time.
  • The Card (Record): A single unit of data (e.g., a Student’s marks, a Shopping Bill).
  • Fields (Attributes): Properties on the card (e.g., Name, Physics Marks, Total Bill).

1.2 Flowchart Primitives

The visual language of logic.

  • Start/Stop: Ovals.
  • Process (Action): Rectangles (e.g., A = A + 1, Move card to Pile 2).
  • Decision (Branching): Diamonds (e.g., Is A > B?).
    • Yes: Path 1
    • No: Path 2

1.3 Variables & State

A variable is a container for a value.

  • Initialization: Setting a starting value (e.g., Sum = 0, Count = 0).
  • Update: Changing the value based on current state (e.g., Sum = Sum + X.Marks).
  • State: The snapshot of all variable values at a specific step in the algorithm.

1.4 Basic Algorithms (The “Iteration” Pattern)

Most Week 1 algorithms follow this “Single Pass” structure:

  1. Initialize variables (Aggregators).
  2. While pile has cards: 3. Read top card X. 4. Process X (Update variables based on X.Field). 5. Move X to discard pile.
  3. Return result.

Example: Counting Students from “Chennai”

Count = 0
While (Pile 1 has more cards) {
    Read top card X from Pile 1
    If (X.City == "Chennai") {
        Count = Count + 1
    }
    Move X to Pile 2
}
Return Count

đź“… Week 2: Variables, Types & Scope

2.1 Data Types

  • Integer: Whole numbers (e.g., 5, -10). Used for counters, indices.
  • Float/Real: Decimals (e.g., 3.14). Used for averages.
  • String: Text (e.g., "Hello"). Used for Names, Cities.
  • Boolean: Truth values (True, False). Used for flags.
  • List: Ordered collection (e.g., [1, 2, 3]).

2.2 Re-assignment vs. Modification

  • A = 5 sets A to 5.
  • A = A + 1 reads the current value of A, adds 1, and saves it back to A.
  • Common Trap: A = B copies the value. Changing B afterwards does not change A (pass-by-value semantics for primitives).

2.3 Multiple Variables (Parallel Updates)

Handling multiple counters simultaneously.

  • Example: Finding Max and Second Max.
    • Update Max and shift old Max to SecondMax.
    • Order of updates matters critically!

2.4 The “Flag” Pattern

A Boolean variable used to signal a condition found during iteration.

  • “Exists” Check: Initialize Found = False. If condition met, set Found = True.
  • “For All” Check: Initialize AllValid = True. If violation found, set AllValid = False.

đź“… Week 3: Iteration Logic & Nested Loops

3.1 Conditional Logic (Boolean Algebra)

  • AND (A and B): True only if BOTH are True.
  • OR (A or B): True if AT LEAST ONE is True.
  • NOT (not A): Inverts value.

3.2 Nested Iteration (The “Pile within a Pile”)

Processing subsets or comparing elements.

  • Structure: 
    While (Pile 1 has cards) {
    Read X
    // Inner Loop (often implied or explicit)
    While (Inner Condition) {
        ...
    }
    Move X
}
  • Use Cases:
    • Comparing every student with every other student (O(N^2)).
    • Processing a list inside a card (e.g., X.ShoppingList).

3.3 Termination Conditions

  • While Loops: Continue as long as condition is True.
  • Infinite Loops: Occur if the loop condition never becomes False (e.g., forgetting to move the card or increment counter).

đź“… Week 4: Procedural Abstraction & Pattern Matching

4.1 Procedures (Functions)

Encapsulating logic for reuse.

  • Definition: Procedure Name(Parameters) ... End Name
  • Parameters: Inputs to the procedure.
  • Return: Output value.
  • Side Effects: Changes to state outside the procedure (not ideal in pure functional thinking, but common in imperative pseudocode).

4.2 String Manipulation

  • Concatenation: A ++ B or A + B (joining strings).
  • Substring: Extracting parts.
  • Pattern Matching:
    • Starts with, Ends with.
    • Letter Count, Vowel Count.

4.3 The “Filter-Map-Reduce” Paradigm (Implicit)

  • Filter: If (Condition) ...
  • Map: Y = f(X) (Transform data).

4.4 The “State” Metaphor in Procedures

  • Local State: Variables inside a procedure (e.g., i, count). Reset every call.
  • Global State: Variables passed in or accessible globally (e.g., The Dataset).

đź“… Week 5: Lists & Sequences

5.1 The List Primitive

An ordered collection of elements.

  • Syntax: L = [10, 20, 30]
  • Indexing: L[i] (usually 0-indexed or 1-indexed depending on context; in CT pseudocode, often access via first/rest).

5.2 Fundamental List Operations

  • first(L): Returns the first element (Head).
  • rest(L): Returns the list without the first element (Tail).
  • last(L): Returns the last element.
  • init(L): Returns the list without the last element.
  • length(L): Returns number of elements.
  • member(L, x): Returns True if x is in L.

5.3 Pattern: Iterating a List

Using first and rest to traverse.

While (length(L) > 0) {
    X = first(L)
    // Process X
    L = rest(L)
}

5.4 Accumulation Pattern (Lists)

Building a new list M from L.

  • Append: M = M ++ [X] (Adds X to end).
  • Prepend: M = [X] ++ M (Adds X to start - reverses order!).

đź“… Week 6: Advanced List Logic & Sorting

6.1 Sorting Algorithms (Conceptual)

  • Idea: Reordering elements based on a key (e.g., Marks, Name).
  • Strategy: Finding the “Best” element and moving it to a new list.
    1. Find Min/Max in L.
    2. Add to SortedList.
    3. Remove from L.
    4. Repeat.

6.2 Filtering Complex Conditions

  • Multi-Criteria: If (A > 50 AND B < 20).
  • Subset Selection: Creating a list S containing only elements from L that satisfy condition P(x).

6.3 List of Lists (2D Structures)

  • Representation of Matrices or Tables.
  • Access: M[i][j] (Row i, Column j).
  • Traversal: Nested iteration (Outer loop rows, Inner loop columns).

đź“… Week 7: Dictionary (Key-Value Maps)

7.1 The Dictionary Primitive

Unordered collection of Key-Value pairs. Keys must be unique.

  • Syntax: D = { Key1: Value1, Key2: Value2 }
  • Access: D[Key] returns Value.
  • Update: D[Key] = NewValue.
  • Insert: D[NewKey] = Value.

7.2 Core Patterns

  • Frequency Count (Histogram): 
    If (isKey(D, Word)) {
    D[Word] = D[Word] + 1
} Else {
    D[Word] = 1
}
  • Lookup Table: Storing metadata (e.g., ISBN -> Book Title).

7.3 Keys vs. Values

  • keys(D): Returns list of all keys.
  • values(D): Returns list of all values.
  • Iteration: Usually over keys. Foreach k in keys(D).

đź“… Week 8: Advanced Dictionaries & File I/O

8.1 Nested Dictionaries

Values can be dictionaries themselves.

  • Structure: D = { "Section A": { "Pass": 10, "Fail": 2 }, "Section B": ... }
  • Access: D["Section A"]["Pass"].

8.2 The “Group By” Pattern

Grouping data by a CATEGORY.

  • Goal: Organizing a list of student records by “City”.
  • Algorithm: 
    Groups = {}
Foreach Student in List {
    City = Student.City
    If (not isKey(Groups, City)) {
        Groups[City] = []
    }
    Groups[City] = Groups[City] ++ [Student]
}

8.3 Inverting a Dictionary

Swapping Keys and Values (only possible if values are unique, or logic handles collisions).

đź“… Week 9: Graph Theory I (Structure)

9.1 Graph Primitives

  • Node (Vertex): An entity (e.g., City, Person).
  • Edge (Link): A relationship (e.g., Road, Friendship).
  • Directed vs. Undirected: One-way vs. Two-way connection.
  • Weighted vs. Unweighted: Edge has a cost/value vs. just exists.

9.2 Representations

  • Adjacency List: Dictionary where Key = Node, Value = List of Neighbors.
  • Adjacency Matrix: 2D Array M[i][j].
    • M[i][j] = 1 (or weight) if edge exists.
    • M[i][j] = 0 otherwise.

9.3 Degree of a Node

  • Degree: Number of connections.
    • In-Degree: Edges coming IN.
    • Out-Degree: Edges going OUT.
    • Sum of Degrees: 2 * Number of Edges (Handshaking Lemma).

đź“… Week 10: Graph Algorithms

10.1 Path Finding

  • Path: Sequence of connected nodes.
  • Cycle: Path handling A -> ... -> A.
  • Connectivity: Can we get from A to B?

10.2 Neighbor Logic (Triadic Closure)

  • Common Neighbor: If A knows B, and B knows C, do A and C satisfy a condition?
  • Friend of Friend: Length 2 paths. M^2 (Matrix multiplication conceptually).

10.3 The “Good Set” / Clique

  • Clique: Subset of nodes where EVERY pair is connected.
  • Independent Set: Subset where NO pair is connected.

đź“… Week 11: Recursion

11.1 The Recursive Leap of Faith

Defining a problem in terms of a smaller version of itself.

  • Base Case: The simplest version (Stop condition). E.g., Length(L) == 0.
  • Recursive Step: Reducing the problem towards the Base Case.

11.2 Standard Recursive Patterns

  • Sum of List: 
    Procedure Sum(L)
    If (L is empty) Return 0
    Else Return first(L) + Sum(rest(L))
End
  • Reverse List: Reverse(rest(L)) ++ [first(L)].
  • Member Check: (first(L) == X) OR member(rest(L), X).

11.3 Recursion vs. Loop

Anything loop can do, recursion can do (and vice versa, often). Recursion is often cleaner for:

  • Tree traversals.
  • Graph explorations (DFS).
  • Inductive definitions.

Graph View

Recent Features