Computational Thinking: Complete Theory Notes

IIT Madras BS DS - Foundational Level All 12 Weeks Covered

Week 1-2: Introduction to Data & Algorithms

1.1 What is Computational Thinking?

A problem-solving approach that involves:

Decomposition: Breaking problems into smaller parts
Pattern Recognition: Finding similarities
Abstraction: Focusing on relevant information
Algorithm Design: Creating step-by-step solutions

1.2 Standard Datasets

Words Dataset

Column	Data Type	Description
Card Number	Integer	Unique ID
Word	Text	The actual word
Part of Speech	Text	Noun, Verb, Adjective, Adverb
Letter Count	Integer	Number of letters

Scores Dataset

Column	Data Type	Description
Name	Text	Student name
Subject	Text	Math, Physics, Chemistry
Marks	Integer	Score in subject
Gender	Text	Male/Female
City	Text	Hometown
DOB	Date	Date of birth

Shopping Bills Dataset

Column	Data Type	Description
Shop Name	Text	Store name
Customer Name	Text	Buyer name
Item	Text	Product purchased
Price	Number	Cost of item
Category	Text	Product category

Library Dataset

Column	Data Type	Description
Book	Text	Book title
Author	Text	Author name
Genre	Text	Fiction, Non-fiction, etc.
Year	Integer	Publication year
Language	Text	English, Hindi, etc.

1.3 Data Types & Sanity Checks

Type	Valid Examples	Invalid Examples
Integer	1, 42, -5	”One”, 3.14, ""
Positive Integer	1, 42	0, -5, 3.14
Text	”Hello”, “123”	(Usually any text is valid)

Common Errors:

Negative letter count
Non-integer card number
Future dates for historical data

Week 2-3: Pseudocode & Flowcharts

2.1 Standard Pseudocode Structure

Step 1: Arrange all cards in Pile 1
Step 2: Initialize variables (A = 0, B = 0)
Step 3: If Pile 1 is empty, go to Step 7
Step 4: Read top card from Pile 1
Step 5: If <condition> then <action>
Step 6: Move card to Pile 2, repeat from Step 3
Step 7: Output result

2.2 Flowchart Symbols

Symbol	Shape	Meaning
Terminal	Oval	Start/End
Process	Rectangle	Action/Calculation
Decision	Diamond	Yes/No Question
Input/Output	Parallelogram	Read/Print
Arrow	Arrow	Flow direction

2.3 Variables

Declaration: A = 0

Update:

Counter: A = A + 1
Accumulator: A = A + Value
Flag: A = 1 (sets to true)

Week 3-4: Logical Operators

3.1 Boolean Operators

Operator	True When	Example
`and`	Both conditions true	`x > 0 and x < 10`
`or`	At least one true	`x < 0 or x > 10`
`not`	Condition is false	`not(x == 0)`

3.2 Truth Tables

AND

A	B	A and B
T	T	T
T	F	F
F	T	F
F	F	F

OR

A	B	A or B
T	T	T
T	F	T
F	T	T
F	F	F

NOT

A	not A
T	F
F	T

3.3 De Morgan’s Laws

$\neg (A \land B) \equiv \neg A \lor \neg B$ $\neg (A \lor B) \equiv \neg A \land \neg B$

In English:

NOT (A and B) = (NOT A) or (NOT B)
NOT (A or B) = (NOT A) and (NOT B)

Week 4-5: Common Patterns

4.1 Counting Pattern

count = 0
for each card X:
    if <condition>:
        count = count + 1

Result: Number of items satisfying condition

4.2 Summing Pattern

sum = 0
for each card X:
    sum = sum + X.Value

Result: Total of all values

4.3 Average Pattern

sum = 0
count = 0
for each card X:
    if <condition>:
        sum = sum + X.Value
        count = count + 1
Average = sum / count

4.4 Maximum/Minimum Pattern

max = 0  (or first value)
for each card X:
    if X.Value > max:
        max = X.Value

4.5 Distinct Counting (Flag Pattern)

A = 0, B = 0, C = 0
for each card X:
    if X.Type == "A": A = 1
    if X.Type == "B": B = 1
    if X.Type == "C": C = 1
Result = A + B + C

Key: Use = 1, not = A + 1

Week 5-6: Procedures & Functions

5.1 Procedure Definition

procedure doSomething(X, Y):
    <steps>
    return result

5.2 Calling Procedures

result = doSomething(card1, card2)

5.3 Return Values

procedure compare(A, B):
    if A > B:
        return -1
    else:
        return 1

Week 6-8: Pair Comparisons

6.1 Double Loop Pattern

for each X in Table 1:
    for each Y in Table 1:
        if X != Y:
            if <condition on X and Y>:
                count = count + 1

Note: This counts (A,B) and (B,A) as separate pairs!

6.2 Common Pair Conditions

Same Author: X.Author == Y.Author
Same Year: X.Year == Y.Year
Different Genre: X.Genre != Y.Genre

6.3 Avoiding Double Counting

To count unordered pairs once:

if X.CardNumber < Y.CardNumber:
    if <condition>:
        count = count + 1

Week 8-10: Algorithms

8.1 Searching

Linear Search

Check each element one by one
Time: $O (n)$

Binary Search

Requires sorted data
Divide and conquer
Time: $O (lo g n)$

8.2 Sorting

Bubble Sort

Compare adjacent pairs
Swap if out of order
Repeat until sorted
Time: $O (n^{2})$

Selection Sort

Find minimum in unsorted portion
Swap to front
Time: $O (n^{2})$

Insertion Sort

Insert each element into correct position in sorted portion
Time: $O (n^{2})$

Week 10-12: Data Structures

10.1 Stack (LIFO)

Push: Add to top
Pop: Remove from top
Use: Backtracking, undo operations

10.2 Queue (FIFO)

Enqueue: Add to back
Dequeue: Remove from front
Use: Task scheduling, BFS

10.3 Arrays

Fixed size collection
Access by index: A[0], A[1], etc.

Common Traps & Debugging

The Reset Bug

Buggy:

Step 2: count = 0
...
Step 6: Repeat from Step 2

Fixed:

Step 6: Repeat from Step 3

Problem: Repeating from initialization resets variables!

Expression Evaluation

Expression	Result
`2 == 2 or 2 > 3`	True
`2 = 2 and 2 > 3`	Error (assignment in condition)
`not(2 > 2)`	True
`2 + '2'`	Error (type mismatch)

Nested IF = AND

if A:
    if B:
        action

Is equivalent to:

if A and B:
    action

End of CT Theory. Good luck!

🧠 IIT Madras Notes

Explorer

Theory_Consolidated