📘 The Complete Guided Study: CMI M.Sc. Data Science — Programming & Algorithms

A self-contained book for mastering every concept tested in the CMI entrance exam. From absolute zero to exam-ready — with examples, pseudo-code, trace tables, and practice questions.

---

How to Use This Guide

This guide is designed for active learning. Don't just read it — work through it.

1. Read each section slowly. Every concept is built from atomic first principles.
2. Work every example on paper. Draw trace tables, draw trees, write out binary. The physical act of writing cements understanding.
3. Attempt every 🤔 "Think First" question before scrolling to the answer. Cover the answer with your hand or a piece of paper. Struggle for at least 5 minutes.
4. Check your answers at the end of each chapter. If you got it wrong, re-read the section and redo it.
5. Use the Pattern Recognition Cheat-Sheet (Chapter 5) as a quick-reference during revision.

Golden Rule: If you can trace through a piece of pseudo-code on paper and predict the exact output — you will ace this exam.

---

📑 Table of Contents

Chapter 1: Programming Fundamentals & Mechanics

• 1.1 Variables, State, and Operators
  • 1.1.1 What Is a Variable?
  • 1.1.2 Assignment: The = Operator
  • 1.1.3 Arithmetic Operators: +, -, *
  • 1.1.4 Integer Division: //
  • 1.1.5 The Modulo Operator: %
  • 1.1.6 Relational (Comparison) Operators
  • 1.1.7 Combining It All: Digit Extraction & Number Reversal
• 1.2 Control Flow: Branching & Looping
  • 1.2.1 Branching with if / else if / else
  • 1.2.2 The for Loop
  • 1.2.3 The while Loop
  • 1.2.4 Nested Loops
  • 1.2.5 The Trace Table Technique (Introduction)
  • 1.2.6 Off-by-One Errors: The Silent Killer
• 1.3 Bitwise Operations
  • 1.3.1 Binary Number Representation
  • 1.3.2 Bitwise AND (&)
  • 1.3.3 Bitwise OR (|)
  • 1.3.4 Bitwise XOR (^)
  • 1.3.5 Left Shift (<<) and Right Shift (>>)
  • 1.3.6 XOR Properties & Applications
  • 1.3.7 Solved Problem: Find the Element Without a Pair
• Chapter 1 — Answers to "Think First" Questions

Chapter 2: Array & String Algorithms

• 2.1 Arrays — Basics & Linear Search
  • 2.1.1 What Is an Array?
  • 2.1.2 Indexing and Traversal
  • 2.1.3 Linear Search
  • 2.1.4 Time Complexity: Big-O Notation (Gentle Introduction)
• 2.2 Binary Search
  • 2.2.1 The Precondition: Sorted Arrays
  • 2.2.2 The Binary Search Algorithm
  • 2.2.3 Mid-Point Calculation
  • 2.2.4 Full Trace-Table Walkthrough
  • 2.2.5 Counting Iterations
• 2.3 Sorting Algorithms
  • 2.3.1 Why Sorting Matters
  • 2.3.2 Bubble Sort (with Pseudo-Code & Trace)
  • 2.3.3 Selection Sort (with Pseudo-Code & Trace)
  • 2.3.4 Insertion Sort (with Pseudo-Code & Trace)
  • 2.3.5 Merge Sort (Conceptual + Complexity)
  • 2.3.6 Quick Sort (Conceptual + Complexity)
  • 2.3.7 Pattern Recognition: Identifying Sorts from Code
• 2.4 Subarray & Optimization: Kadane's Algorithm
  • 2.4.1 The Maximum Subarray Problem
  • 2.4.2 Brute Force Approach
  • 2.4.3 Prefix Sums
  • 2.4.4 Sliding Window Technique
  • 2.4.5 Kadane's Algorithm — Deep Dive
  • 2.4.6 Full Trace on a 10-Element Array
• Chapter 2 — Answers to "Think First" Questions

Chapter 3: Recursion & Discrete Mathematics

• 3.1 Recursion & Recurrence Relations
  • 3.1.1 What Is Recursion?
  • 3.1.2 Base Case vs Recursive Case
  • 3.1.3 The Call Stack
  • 3.1.4 Drawing Recursion Trees
  • 3.1.5 Classic Examples: Factorial, Fibonacci, Power
  • 3.1.6 Recurrence Relations and Closed-Form Solutions
• 3.2 Combinatorics & Counting
  • 3.2.1 The Fundamental Counting Principle
  • 3.2.2 Permutations
  • 3.2.3 Combinations and the Binomial Coefficient
  • 3.2.4 Catalan Numbers — Formula & Intuition
  • 3.2.5 Application: Counting Binary Trees
• 3.3 Set Theory & Matrix Algebra
  • 3.3.1 Sets and Set Operations
  • 3.3.2 Functions: Injective, Surjective, Bijective
  • 3.3.3 Matrices: Basics and Operations
  • 3.3.4 Transpose, Trace, and Determinant
  • 3.3.5 Symmetric & Triangular Matrices
  • 3.3.6 Pseudo-Code: Checking Matrix Properties
• Chapter 3 — Answers to "Think First" Questions

Chapter 4: Advanced Data Structures (Conceptual)

• 4.1 Binary Trees & Binary Search Trees (BSTs)
  • 4.1.1 Tree Terminology: Root, Leaf, Child, Depth, Height
  • 4.1.2 Binary Trees
  • 4.1.3 Binary Search Tree (BST) Property
  • 4.1.4 Tree Traversals: Pre-order, In-order, Post-order
  • 4.1.5 Building a BST from a Sequence
• 4.2 Stacks & Queues
  • 4.2.1 The Stack (LIFO)
  • 4.2.2 The Queue (FIFO)
  • 4.2.3 Tracing Stack/Queue Operations
  • 4.2.4 Applications
• 4.3 Graphs — Basics
  • 4.3.1 What Is a Graph?
  • 4.3.2 Directed vs Undirected Graphs
  • 4.3.3 Adjacency Matrix Representation
  • 4.3.4 Adjacency List Representation
  • 4.3.5 Graph Traversal Intuition: DFS & BFS
• Chapter 4 — Answers to "Think First" Questions

Chapter 5: Exam Strategy & Practice

• 5.1 What NOT to Study
• 5.2 The Trace Table Technique — Mastery
• 5.3 Pattern Recognition Cheat-Sheet
• 5.4 Final Mixed Practice Set (10 Questions)
• 5.5 Final Practice Answers

---

---

Chapter 1: Programming Fundamentals & Mechanics

Goal: After this chapter, you will be able to read any piece of pseudo-code, track every variable on paper, and predict the exact output.

---

1.1 Variables, State, and Operators

1.1.1 What Is a Variable?

A variable is a named container that holds a value. Think of it as a labeled box.

Box labeled "x" contains: 5
Box labeled "name" contains: "Alice"

At any point during a program, every variable has a current value. The collection of all variable values at a given moment is called the state of the program.

Key Insight: When the exam gives you pseudo-code, your job is to track how the state changes line by line.

---

1.1.2 Assignment: The = Operator

The = sign in code does not mean "equals" like in mathematics. It means "store the value on the right into the variable on the left."

x = 5          // x now holds 5
y = x + 3      // y now holds 8 (x is still 5)
x = x + 1      // x now holds 6 (the OLD value of x was 5, add 1, store back)

⚠️ Common Trap: x = x + 1 is not a mathematical contradiction. It means "take the current value of x, add 1, and store the result back into x."

Example 1: Tracking Assignment

a = 10
b = a
a = 20

Step	a	b
After line 1	10	—
After line 2	10	10
After line 3	20	10

Notice that b is still 10 after line 3. When we wrote b = a, we copied the value of a (which was 10) into b. Changing a later does not affect b.

Example 2: Swapping Two Variables

How do you swap the values of x and y?

x = 3
y = 7

// Wrong way:
x = y      // x is now 7, but we LOST the old value of x (3)!
y = x      // y is now 7 too. Both are 7. Swap failed.

// Correct way — use a temporary variable:
temp = x   // temp = 3
x = y      // x = 7
y = temp   // y = 3     ✓ Swap complete!

---

1.1.3 Arithmetic Operators: +, -, *

These work exactly as in mathematics:

a = 10 + 3     // a = 13
b = 10 - 3     // b = 7
c = 10 * 3     // c = 30

Order of operations follows standard math (PEMDAS/BODMAS):

result = 2 + 3 * 4     // result = 14 (not 20), because * happens before +
result = (2 + 3) * 4   // result = 20, parentheses force addition first

---

1.1.4 Integer Division: //

Integer division divides and then throws away the decimal part (floors the result for positive numbers).

7 // 2 = 3      (not 3.5 — we drop the .5)
10 // 3 = 3     (not 3.33 — we drop the .33)
1 // 5 = 0      (0.2 → drop the .2 → 0)
15 // 5 = 3     (exactly 3, no remainder)

💡 Exam Use: x // 10 removes the last digit of a number.

1234 // 10 = 123
567 // 10 = 56
10 // 10 = 1
5 // 10 = 0

---

1.1.5 The Modulo Operator: %

The modulo operator gives the remainder after division.

7 % 2 = 1       (7 ÷ 2 = 3 remainder 1)
10 % 3 = 1      (10 ÷ 3 = 3 remainder 1)
15 % 5 = 0      (15 ÷ 5 = 3 remainder 0 → perfectly divisible)
4 % 10 = 4      (4 ÷ 10 = 0 remainder 4)

💡 Exam Use: x % 10 extracts the last digit of a number.

1234 % 10 = 4
567 % 10 = 7
10 % 10 = 0

The // and % Duo — Extracting Digits:

Expression	Input x = 4821	Result	Meaning
x % 10	4821	1	Last digit
x // 10	4821	482	Remove last digit
(x // 10) % 10	4821	2	Second-to-last digit
(x // 100) % 10	4821	8	Third-to-last digit

---

1.1.6 Relational (Comparison) Operators

These operators compare two values and produce a boolean result: true or false.

Operator	Meaning	Example	Result
==	Equal to	5 == 5	true
!=	Not equal to	5 != 3	true
<	Less than	3 < 5	true
>	Greater than	5 > 3	true
<=	Less than or equal	5 <= 5	true
>=	Greater than or equal	4 >= 5	false

⚠️ = vs ==: Single = is assignment (store a value). Double == is comparison (check if equal). Confusing them is the #1 beginner mistake.

---

1.1.7 Combining It All: Digit Extraction & Number Reversal

Let's put % and // together to solve a classic exam problem.

Problem: Given a number n, compute the sum of its digits.

function sumOfDigits(n):
    total = 0
    while n > 0:
        digit = n % 10        // extract last digit
        total = total + digit  // add it to running sum
        n = n // 10            // remove last digit
    return total

Trace for n = 4821:

Iteration	n (start)	digit = n % 10	total	n = n // 10
1	4821	1	0 + 1 = 1	482
2	482	2	1 + 2 = 3	48
3	48	8	3 + 8 = 11	4
4	4	4	11 + 4 = 15	0

Loop ends because n = 0, which is not > 0. Answer: 15 ✓ (4 + 8 + 2 + 1 = 15)

Example 2: Reversing a Number

function reverse(n):
    rev = 0
    while n > 0:
        digit = n % 10
        rev = rev * 10 + digit
        n = n // 10
    return rev

Trace for n = 1234:

Iteration	n	digit	rev = rev * 10 + digit	n = n // 10
1	1234	4	0 * 10 + 4 = 4	123
2	123	3	4 * 10 + 3 = 43	12
3	12	2	43 * 10 + 2 = 432	1
4	1	1	432 * 10 + 1 = 4321	0

Answer: 4321 ✓

---

🤔 Think First — Section 1.1 Questions

Q1.1.1: What is the value of result after these lines execute?

a = 5
b = 2
result = a % b + a // b

Q1.1.2: What does the following code print?

x = 100
y = x
x = x + 50
print(y)

Q1.1.3: Trace the sumOfDigits function for n = 907. What is the return value?

Q1.1.4: What does n % 2 tell you about a number? When is it 0? When is it 1?

(Answers at the end of Chapter 1)

---

1.2 Control Flow: Branching & Looping

1.2.1 Branching with if / else if / else

The if statement lets a program make decisions.

if condition:
    // this block runs ONLY if condition is true
else if another_condition:
    // this block runs ONLY if the first condition was false AND this one is true
else:
    // this block runs if ALL above conditions were false

Key Rules:

• Only ONE block ever executes — the first one whose condition is true.
• The else block is a catch-all. It has no condition.
• else if and else are optional.

Example 1: Classifying a Number

function classify(x):
    if x > 0:
        return "positive"
    else if x < 0:
        return "negative"
    else:
        return "zero"

Input x	x > 0?	x < 0?	Output
5	true	—	"positive"
-3	false	true	"negative"
0	false	false	"zero"

Example 2: Finding the Maximum of Three Numbers

function max3(a, b, c):
    if a >= b and a >= c:
        return a
    else if b >= a and b >= c:
        return b
    else:
        return c

Trace for max3(4, 9, 6):

• Is 4 >= 9 and 4 >= 6? → false and true → false. Skip.
• Is 9 >= 4 and 9 >= 6? → true and true → true. Return 9. ✓

---

1.2.2 The for Loop

A for loop repeats a block of code a known number of times.

for i = start to end:
    // body — executes once for each value of i

Example 1: Print numbers 1 to 5

for i = 1 to 5:
    print(i)

Output: 1 2 3 4 5

The variable i is called the loop counter (or iterator). It starts at 1, and after each iteration, it automatically increases by 1 until it exceeds 5.

Example 2: Sum of first N natural numbers

function sumN(N):
    total = 0
    for i = 1 to N:
        total = total + i
    return total

Trace for N = 4:

i	total (before)	total = total + i (after)
1	0	1
2	1	3
3	3	6
4	6	10

Answer: 10 ✓ (1 + 2 + 3 + 4 = 10)

---

1.2.3 The while Loop

A while loop repeats as long as a condition remains true. Use it when you don't know in advance how many iterations you need.

while condition:
    // body — keep executing as long as condition is true

⚠️ Danger: If the condition never becomes false, the loop runs forever (infinite loop).

Example: Counting Digits of a Number

function countDigits(n):
    count = 0
    while n > 0:
        n = n // 10
        count = count + 1
    return count

Trace for n = 3051:

Iteration	n (start)	n = n // 10	count
1	3051	305	1
2	305	30	2
3	30	3	3
4	3	0	4

Now n = 0, so n > 0 is false. Loop stops. Answer: 4 ✓

---

1.2.4 Nested Loops

A loop inside another loop. The inner loop completes all its iterations for each single iteration of the outer loop.

Example: Multiplication Table (3 × 3)

for i = 1 to 3:
    for j = 1 to 3:
        print(i * j, end=" ")
    print(newline)

Trace:

Outer i	Inner j values	Output
1	1, 2, 3	1 2 3
2	1, 2, 3	2 4 6
3	1, 2, 3	3 6 9

Total iterations of the inner body: 3 × 3 = 9.

💡 Key Insight: If the outer loop runs N times and the inner loop runs M times, the body of the inner loop runs N × M times total.

---

1.2.5 The Trace Table Technique (Introduction)

This is the single most important skill for the CMI exam. Here is the method:

1. List all variables as column headers.
2. Write the initial values in the first row.
3. Step through each line of code, updating only the variables that change.
4. Each loop iteration gets its own row.
5. When the loop ends, read the final values.

Full Worked Example:

x = 0
y = 1
for i = 1 to 4:
    temp = y
    y = x + y
    x = temp
print(y)

i	x (start)	y (start)	temp = y	y = x + y	x = temp
1	0	1	1	0 + 1 = 1	1
2	1	1	1	1 + 1 = 2	1
3	1	2	2	1 + 2 = 3	2
4	2	3	3	2 + 3 = 5	3

Output: 5

Wait — do you recognize this? The values of y are: 1, 1, 2, 3, 5 — these are the Fibonacci numbers! This code computes the 5th Fibonacci number. Pattern recognition like this is exactly what the exam tests.

---

1.2.6 Off-by-One Errors: The Silent Killer

The most common mistake in tracing loops is getting the number of iterations wrong by exactly 1.

Example — Spot the Difference:

// Version A: prints 0, 1, 2, 3, 4  (5 numbers)
for i = 0 to 4:
    print(i)

// Version B: prints 1, 2, 3, 4, 5  (5 numbers)
for i = 1 to 5:
    print(i)

// Version C: prints 0, 1, 2, 3  (4 numbers, NOT 5!)
for i = 0 to N-1:    // where N = 4
    print(i)

⚠️ Always ask: Does the loop include the endpoint or not? for i = 0 to 4 — does i take the value 4? In most pseudo-code conventions (and in this exam), yes.

Checklist for Loop Tracing:

• Where does i start?
• Where does i end? (Is the endpoint inclusive or exclusive?)
• How much does i change each step? (Usually +1, but could be +2, *2, etc.)

---

🤔 Think First — Section 1.2 Questions

Q1.2.1: What does this code print?

x = 1
for i = 1 to 5:
    x = x * 2
print(x)

Q1.2.2: How many times does the inner print execute?

for i = 1 to 4:
    for j = 1 to i:
        print("*")

Q1.2.3: What is the value of count after this code?

count = 0
n = 64
while n > 1:
    n = n // 2
    count = count + 1

Q1.2.4: This code is supposed to find the sum of even numbers from 2 to 10. Does it work correctly? If not, what's the bug?

total = 0
for i = 1 to 10:
    if i % 2 == 0:
        total = total + i
print(total)

(Answers at the end of Chapter 1)

---

1.3 Bitwise Operations

1.3.1 Binary Number Representation

Computers store numbers in binary (base 2), using only the digits 0 and 1.

Converting Decimal to Binary:

To convert decimal 13 to binary:

13 ÷ 2 = 6 remainder 1
 6 ÷ 2 = 3 remainder 0
 3 ÷ 2 = 1 remainder 1
 1 ÷ 2 = 0 remainder 1

Read remainders bottom-up: 1101

Verification: 1×8 + 1×4 + 0×2 + 1×1 = 8 + 4 + 0 + 1 = 13 ✓

Common Values to Memorize:

Decimal	Binary	Decimal	Binary
0	0000	8	1000
1	0001	9	1001
2	0010	10	1010
3	0011	11	1011
4	0100	12	1100
5	0101	13	1101
6	0110	14	1110
7	0111	15	1111

---

1.3.2 Bitwise AND (&)

Compares each bit position. The result is 1 only if both bits are 1.

Truth Table:

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example: 13 & 10

  1101   (13)
& 1010   (10)
------
  1000   (8)

Answer: 8

💡 Use Case: n & 1 checks if a number is odd or even. If the result is 1, the number is odd. If 0, even.

---

1.3.3 Bitwise OR (|)

The result is 1 if at least one bit is 1.

Truth Table:

A	B	A | B
0	0	0
0	1	1
1	0	1
1	1	1

Example: 13 | 10

  1101   (13)
| 1010   (10)
------
  1111   (15)

Answer: 15

---

1.3.4 Bitwise XOR (^)

The result is 1 if the bits are different.

Truth Table:

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Example: 13 ^ 10

  1101   (13)
^ 1010   (10)
------
  0111   (7)

Answer: 7

---

1.3.5 Left Shift (<<) and Right Shift (>>)

Left Shift (<<): Shifts all bits to the left by n positions. Equivalent to multiplying by 2ⁿ.

5 << 1:   0101 → 1010 = 10     (5 × 2 = 10)
5 << 2:   0101 → 10100 = 20    (5 × 4 = 20)
3 << 3:   011 → 011000 = 24    (3 × 8 = 24)

Right Shift (>>): Shifts all bits to the right by n positions. Equivalent to integer division by 2ⁿ.

10 >> 1:  1010 → 0101 = 5      (10 // 2 = 5)
20 >> 2:  10100 → 00101 = 5    (20 // 4 = 5)
7 >> 1:   0111 → 0011 = 3      (7 // 2 = 3)

---

1.3.6 XOR Properties & Applications

These properties are critical for exams:

Property	Formula	Explanation
Self-inverse	A ^ A = 0	Any number XOR'd with itself gives 0
Identity	A ^ 0 = A	Any number XOR'd with 0 gives itself
Commutative	A ^ B = B ^ A	Order doesn't matter
Associative	(A ^ B) ^ C = A ^ (B ^ C)	Grouping doesn't matter

Why This Matters: If you XOR a list of numbers where every number appears twice except one, all the pairs cancel out (A ^ A = 0), and you're left with the unique number (X ^ 0 = X).

---

1.3.7 Solved Problem: Find the Element Without a Pair

Problem: Given an array where every element appears exactly twice except one element. Find the unique element.

A = [4, 1, 2, 1, 2]

Algorithm:

function findUnique(A, n):
    result = 0
    for i = 0 to n-1:
        result = result ^ A[i]
    return result

Trace:

i	A[i]	result = result ^ A[i]	Binary
0	4	0 ^ 4 = 4	000 ^ 100 = 100
1	1	4 ^ 1 = 5	100 ^ 001 = 101
2	2	5 ^ 2 = 7	101 ^ 010 = 111
3	1	7 ^ 1 = 6	111 ^ 001 = 110
4	2	6 ^ 2 = 4	110 ^ 010 = 100

Answer: 4 ✓

Why it works: (4 ^ 1 ^ 2 ^ 1 ^ 2) = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

---

🤔 Think First — Section 1.3 Questions

Q1.3.1: Compute 12 & 7 by converting to binary and applying the AND operation.

Q1.3.2: What is 1 << 10? (Don't convert to binary — use the multiplication shortcut.)

Q1.3.3: Given A = [3, 5, 3, 7, 5], trace the findUnique function. What is the result?

Q1.3.4: Can you swap two variables using XOR without a temporary variable? Fill in the blanks:

a = 5, b = 3
a = a ^ b     // a = ?
b = a ^ b     // b = ?
a = a ^ b     // a = ?

(Answers at the end of Chapter 1)

---

Chapter 1 — Answers to "Think First" Questions

Section 1.1 Answers

A1.1.1: result = a % b + a // b = 5 % 2 + 5 // 2 = 1 + 2 = 3

A1.1.2: Prints 100.

• x = 100, then y = x copies the value 100 into y.
• x = x + 50 changes x to 150, but y was already set to 100 and remains unchanged.

A1.1.3: Trace for n = 907:

Iteration	n	digit = n % 10	total	n = n // 10
1	907	7	0 + 7 = 7	90
2	90	0	7 + 0 = 7	9
3	9	9	7 + 9 = 16	0

Answer: 16 (9 + 0 + 7 = 16) ✓

A1.1.4: n % 2 gives the remainder when n is divided by 2.

• If n % 2 == 0: n is even (divisible by 2).
• If n % 2 == 1: n is odd.

---

Section 1.2 Answers

A1.2.1:

i	x (before)	x = x * 2 (after)
1	1	2
2	2	4
3	4	8
4	8	16
5	16	32

Prints: 32 (this computes 2⁵ = 32)

A1.2.2:

Outer i	Inner j runs from 1 to i	Number of print calls
1	1 to 1	1
2	1 to 2	2
3	1 to 3	3
4	1 to 4	4

Total: 1 + 2 + 3 + 4 = 10 times

This prints 10 stars. This pattern is called a triangular number (sum of first N natural numbers = N(N+1)/2 = 4×5/2 = 10).

A1.2.3:

Iteration	n (start)	n = n // 2	count
1	64	32	1
2	32	16	2
3	16	8	3
4	8	4	4
5	4	2	5
6	2	1	6

Now n = 1, so n > 1 is false. count = 6.

This computes log₂(64) = 6. In general, this loop counts how many times you can halve n before reaching 1 — that's the base-2 logarithm.

A1.2.4: Yes, it works correctly!

• It loops i from 1 to 10.
• The if i % 2 == 0 condition filters only even numbers: 2, 4, 6, 8, 10.
• total = 2 + 4 + 6 + 8 + 10 = 30.

The code is correct. Answer: 30.

---

Section 1.3 Answers

A1.3.1: Convert to 4-bit binary:

  1100   (12)
& 0111   (7)
------
  0100   (4)

Answer: 4

A1.3.2: 1 << 10 = 1 × 2¹⁰ = 1024

(Left shift by n is multiplication by 2ⁿ. So 1 << 10 = 2¹⁰ = 1024.)

A1.3.3: Trace for A = [3, 5, 3, 7, 5]:

i	A[i]	result = result ^ A[i]
0	3	0 ^ 3 = 3
1	5	3 ^ 5 = 6
2	3	6 ^ 3 = 5
3	7	5 ^ 7 = 2
4	5	2 ^ 5 = 7

Answer: 7 ✓ (3 and 5 appear twice, 7 is the unique element)

A1.3.4: XOR swap:

a = 5, b = 3      // a = 0101, b = 0011
a = a ^ b          // a = 0101 ^ 0011 = 0110 = 6
b = a ^ b          // b = 0110 ^ 0011 = 0101 = 5   ← b is now the original a!
a = a ^ b          // a = 0110 ^ 0101 = 0011 = 3   ← a is now the original b!

Final: a = 3, b = 5 ✓ (Swapped without a temp variable!)

This works because XOR is its own inverse: (A ^ B) ^ B = A.

---

---

Chapter 2: Array & String Algorithms

Goal: After this chapter, you will be able to search, sort, and optimize over arrays. You will recognize classic algorithms like Binary Search and Kadane's Algorithm from their code patterns.

---

2.1 Arrays — Basics & Linear Search

2.1.1 What Is an Array?

An array is an ordered, fixed-size collection of elements, all of the same type. Think of it as a row of numbered boxes.

Index:   0    1    2    3    4
       +----+----+----+----+----+
A  =   | 10 | 25 | 3  | 47 | 8  |
       +----+----+----+----+----+

Key Facts:

• Arrays are 0-indexed in most conventions (the first element is at index 0).
• A[0] = 10, A[1] = 25, A[4] = 8.
• If the array has n elements, valid indices are 0 to n-1.
• Accessing A[n] or A[-1] is an out-of-bounds error.

---

2.1.2 Indexing and Traversal

Accessing an element: Use A[i] where i is the index.

Traversing means visiting every element, one by one:

// Print every element in array A of size n
for i = 0 to n-1:
    print(A[i])

Example: A = [10, 25, 3, 47, 8], n = 5

i	A[i]	Output
0	10	10
1	25	25
2	3	3
3	47	47
4	8	8

Computing the Sum of an Array:

function arraySum(A, n):
    total = 0
    for i = 0 to n-1:
        total = total + A[i]
    return total

For A = [10, 25, 3, 47, 8]: total = 10 + 25 + 3 + 47 + 8 = 93

Finding the Maximum:

function findMax(A, n):
    max_val = A[0]
    for i = 1 to n-1:
        if A[i] > max_val:
            max_val = A[i]
    return max_val

Trace for A = [10, 25, 3, 47, 8]:

i	A[i]	A[i] > max_val?	max_val
start	—	—	10
1	25	25 > 10? Yes	25
2	3	3 > 25? No	25
3	47	47 > 25? Yes	47
4	8	8 > 47? No	47

Answer: 47 ✓

---

2.1.3 Linear Search

Problem: Given an array A and a target value key, find the index where key is located. Return -1 if not found.

Strategy: Check every element, one by one, from start to end.

function linearSearch(A, n, key):
    for i = 0 to n-1:
        if A[i] == key:
            return i       // Found! Return the index.
    return -1              // Not found.

Example 1: A = [10, 25, 3, 47, 8], key = 47

i	A[i]	A[i] == 47?
0	10	No
1	25	No
2	3	No
3	47	Yes → return 3

Answer: index 3 ✓

Example 2: A = [10, 25, 3, 47, 8], key = 99

• Checks all 5 elements, none match. Returns -1 (not found).

---

2.1.4 Time Complexity: Big-O Notation (Gentle Introduction)

Question: How do we measure how fast an algorithm is?

We use Big-O notation to describe how the number of operations grows as the input size n grows.

Notation	Name	Example
O(1)	Constant	Accessing A[3] — one step regardless of array size
O(log N)	Logarithmic	Binary Search
O(N)	Linear	Linear Search — check each element once
O(N log N)	Log-linear	Merge Sort, Quick Sort (average)
O(N²)	Quadratic	Bubble Sort — nested loops

Linear Search is O(N) because in the worst case (element not found), you check all n elements.

💡 Rule of Thumb: One loop over n elements = O(N). Two nested loops over n elements = O(N²). Halving the problem each step = O(log N).

---

🤔 Think First — Section 2.1 Questions

Q2.1.1: Write pseudo-code to find the minimum value in an array. (Hint: it's very similar to findMax.)

Q2.1.2: What is the time complexity of findMax? Justify.

Q2.1.3: Given A = [5, 3, 8, 1, 9, 2], trace linearSearch(A, 6, 8). How many comparisons does it make?

(Answers at the end of Chapter 2)

---

2.2 Binary Search

2.2.1 The Precondition: Sorted Arrays

Binary Search only works on sorted arrays. If given an unsorted array, you must sort it first (or use Linear Search).

Sorted:     [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]   ✓
Not sorted: [10, 25, 3, 47, 8]                         ✗

---

2.2.2 The Binary Search Algorithm

Idea: Instead of checking every element, check the middle element.

• If it matches, you're done.
• If the target is smaller, search the left half.
• If the target is larger, search the right half.

Each step eliminates half the remaining elements. This is why it's O(log N).

function binarySearch(A, n, key):
    l = 0              // left boundary
    r = n - 1          // right boundary
    c = 0              // iteration counter
    
    while l <= r:
        c = c + 1
        m = l + (r - l) // 2       // mid-point
        
        if A[m] == key:
            print("Found in " + c + " iterations")
            return m
        else if A[m] < key:
            l = m + 1              // search right half
        else:
            r = m - 1              // search left half
    
    print("Not found after " + c + " iterations")
    return -1

---

2.2.3 Mid-Point Calculation

Why m = l + (r - l) // 2 instead of m = (l + r) // 2?

Both give the same mathematical result, but (l + r) can overflow if l and r are very large numbers. The first formula avoids this.

Example:

• l = 2, r = 8: m = 2 + (8 - 2) // 2 = 2 + 3 = 5
• l = 0, r = 9: m = 0 + (9 - 0) // 2 = 0 + 4 = 4
• l = 5, r = 7: m = 5 + (7 - 5) // 2 = 5 + 1 = 6

---

2.2.4 Full Trace-Table Walkthrough

Array: A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9), key = 23

Iter c	l	r	m = l + (r-l)//2	A[m]	Comparison	Action
1	0	9	4	16	16 < 23	l = 5
2	5	9	7	56	56 > 23	r = 6
3	5	6	5	23	23 == 23	Found!

Answer: Found key 23 at index 5 in 3 iterations ✓

Compare: Linear search would have taken 6 iterations (checking indices 0, 1, 2, 3, 4, 5).

---

2.2.5 Counting Iterations

How many iterations does Binary Search take in the worst case?

Each iteration halves the search space:

• Start: n elements
• After 1 iteration: n/2
• After 2 iterations: n/4
• After k iterations: n/2ᵏ

The loop stops when n/2ᵏ = 1, i.e., k = log₂(n).

Array size n	Max iterations
8	3
16	4
64	6
1024	10
1,000,000	~20

💡 Binary Search on a million elements takes at most 20 steps! Linear Search would take up to 1,000,000 steps. This is the power of O(log N).

---

🤔 Think First — Section 2.2 Questions

Q2.2.1: Trace binary search on A = [3, 7, 11, 15, 19, 23, 27] for key = 11. Show each iteration.

Q2.2.2: Trace binary search on the same array for key = 20. What happens? How many iterations?

Q2.2.3: An array has 128 elements. What is the maximum number of iterations binary search will need?

(Answers at the end of Chapter 2)

---

2.3 Sorting Algorithms

2.3.1 Why Sorting Matters

Sorting arranges elements in order (usually ascending: smallest first). Many algorithms (like Binary Search) require sorted input. Sorting also makes it easy to find duplicates, medians, and more.

---

2.3.2 Bubble Sort (with Pseudo-Code & Trace)

Idea: Repeatedly compare adjacent elements and swap them if they're in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position.

function bubbleSort(A, n):
    for i = 0 to n-2:
        for j = 0 to n-2-i:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])

Trace for A = [5, 3, 8, 1]:

Pass 1 (i = 0): Compare adjacent pairs, largest element (8) bubbles to end.

j	Compare	Swap?	Array after
0	A[0]=5 > A[1]=3? Yes	swap	[3, 5, 8, 1]
1	A[1]=5 > A[2]=8? No	—	[3, 5, 8, 1]
2	A[2]=8 > A[3]=1? Yes	swap	[3, 5, 1, 8]

After pass 1: [3, 5, 1, 8] — 8 is in its correct position.

Pass 2 (i = 1): j goes 0 to 1 (no need to check index 3)

j	Compare	Swap?	Array after
0	3 > 5? No	—	[3, 5, 1, 8]
1	5 > 1? Yes	swap	[3, 1, 5, 8]

After pass 2: [3, 1, 5, 8] — 5 is in position.

Pass 3 (i = 2): j goes 0 to 0

j	Compare	Swap?	Array after
0	3 > 1? Yes	swap	[1, 3, 5, 8]

Final: [1, 3, 5, 8] ✓

Time Complexity: O(N²) — two nested loops.

---

2.3.3 Selection Sort (with Pseudo-Code & Trace)

Idea: Find the minimum element in the unsorted portion and swap it into the correct position.

function selectionSort(A, n):
    for i = 0 to n-2:
        min_idx = i
        for j = i+1 to n-1:
            if A[j] < A[min_idx]:
                min_idx = j
        swap(A[i], A[min_idx])

Trace for A = [29, 10, 14, 37, 13]:

Pass i	Unsorted portion	Min value (index)	Swap	Array after
0	[29, 10, 14, 37, 13]	10 (idx 1)	swap A[0]↔A[1]	[10, 29, 14, 37, 13]
1	[29, 14, 37, 13]	13 (idx 4)	swap A[1]↔A[4]	[10, 13, 14, 37, 29]
2	[14, 37, 29]	14 (idx 2)	swap A[2]↔A[2] (no-op)	[10, 13, 14, 37, 29]
3	[37, 29]	29 (idx 4)	swap A[3]↔A[4]	[10, 13, 14, 29, 37]

Final: [10, 13, 14, 29, 37] ✓

Time Complexity: O(N²)

---

2.3.4 Insertion Sort (with Pseudo-Code & Trace)

Idea: Build a sorted section from left to right. Take the next unsorted element and insert it into its correct position in the sorted section.

function insertionSort(A, n):
    for i = 1 to n-1:
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]       // shift element right
            j = j - 1
        A[j+1] = key            // insert key in correct position

Trace for A = [5, 2, 4, 6, 1, 3]:

Pass i	key = A[i]	Sorted portion (before)	Shifts	Array after
1	2	[5]	5 shifts right	[2, 5, 4, 6, 1, 3]
2	4	[2, 5]	5 shifts right	[2, 4, 5, 6, 1, 3]
3	6	[2, 4, 5]	no shifts needed	[2, 4, 5, 6, 1, 3]
4	1	[2, 4, 5, 6]	6,5,4,2 all shift right	[1, 2, 4, 5, 6, 3]
5	3	[1, 2, 4, 5, 6]	6,5,4 shift right	[1, 2, 3, 4, 5, 6]

Final: [1, 2, 3, 4, 5, 6] ✓

Time Complexity: O(N²) worst case, but O(N) for already-sorted arrays (best case).

---

2.3.5 Merge Sort (Conceptual + Complexity)

Idea: Divide and Conquer.

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into one sorted array.

function mergeSort(A, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)         // sort left half
        mergeSort(A, mid+1, right)      // sort right half
        merge(A, left, mid, right)      // merge them

function merge(A, left, mid, right):
    // Create temp arrays for left and right halves
    // Compare elements one by one from both halves
    // Place the smaller element into A
    // Copy any remaining elements

Visual Example:

[38, 27, 43, 3, 9, 82, 10]
          /              \
   [38, 27, 43, 3]    [9, 82, 10]
      /       \          /      \
  [38, 27]  [43, 3]   [9, 82]  [10]
   /   \     /   \     /   \      |
 [38] [27] [43]  [3] [9]  [82]  [10]
   \   /     \   /     \   /      |
  [27, 38]  [3, 43]  [9, 82]   [10]
      \       /          \      /
   [3, 27, 38, 43]    [9, 10, 82]
          \              /
   [3, 9, 10, 27, 38, 43, 82]

Time Complexity: O(N log N) — always, regardless of input.

---

2.3.6 Quick Sort (Conceptual + Complexity)

Idea:

1. Pick a pivot element.
2. Partition the array so that all elements ≤ pivot are on the left, all elements > pivot are on the right.
3. Recursively sort the left and right partitions.

function quickSort(A, low, high):
    if low < high:
        pivot_idx = partition(A, low, high)
        quickSort(A, low, pivot_idx - 1)
        quickSort(A, pivot_idx + 1, high)

Example Partition (pivot = last element):

A = [10, 80, 30, 90, 40, 50, 70]    pivot = 70

After partition:
[10, 30, 40, 50, 70, 90, 80]
                 ^
            pivot in place
Everything ≤ 70 is left, everything > 70 is right.

Time Complexity: O(N log N) average, O(N²) worst case (rare with good pivot selection).

---

2.3.7 Pattern Recognition: Identifying Sorts from Code

This is a critical exam skill. When you see pseudo-code, recognize the sorting algorithm:

Code Pattern	Algorithm
Two nested loops, comparing A[j] and A[j+1], swapping adjacent elements	Bubble Sort
Outer loop picks position, inner loop finds minimum in remaining, one swap per pass	Selection Sort
Outer loop picks next element, inner loop shifts elements right to make room	Insertion Sort
Recursive, splits array in half, has a merge step	Merge Sort
Recursive, has a partition step around a pivot	Quick Sort

---

🤔 Think First — Section 2.3 Questions

Q2.3.1: Trace Bubble Sort on A = [4, 2, 7, 1]. Show the array after each complete pass.

Q2.3.2: You see this code. What sorting algorithm is it?

for i = 0 to n-2:
    min_idx = i
    for j = i+1 to n-1:
        if A[j] < A[min_idx]:
            min_idx = j
    swap(A[i], A[min_idx])

Q2.3.3: Which sorting algorithm has the best time complexity? What is it?

(Answers at the end of Chapter 2)

---

2.4 Subarray & Optimization: Kadane's Algorithm

2.4.1 The Maximum Subarray Problem

Problem: Given an array of integers (possibly negative), find the contiguous subarray with the largest sum.

A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

All possible contiguous subarrays include:
[-2]                 → sum = -2
[-2, 1]              → sum = -1
[1, -3, 4, -1]       → sum = 1
[4, -1, 2, 1]        → sum = 6  ← MAXIMUM!
[-5, 4]              → sum = -1
...and many more

Answer: 6 (from subarray [4, -1, 2, 1])

---

2.4.2 Brute Force Approach

Check every possible subarray — try every start index i and every end index j ≥ i:

function maxSubarrayBrute(A, n):
    max_sum = A[0]
    for i = 0 to n-1:
        current_sum = 0
        for j = i to n-1:
            current_sum = current_sum + A[j]
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

Time Complexity: O(N²) — too slow for large arrays.

---

2.4.3 Prefix Sums

A prefix sum array stores the cumulative sum up to each index:

A      = [3,  1,  4,  1,  5]
P[0]   = 3
P[1]   = 3 + 1 = 4
P[2]   = 3 + 1 + 4 = 8
P[3]   = 3 + 1 + 4 + 1 = 9
P[4]   = 3 + 1 + 4 + 1 + 5 = 14

Prefix = [3,  4,  8,  9,  14]

Why useful? The sum of any subarray A[i..j] = P[j] - P[i-1] (with P[-1] = 0).

Example: Sum of A[2..4] = P[4] - P[1] = 14 - 4 = 10 ✓ (4 + 1 + 5 = 10)

---

2.4.4 Sliding Window Technique

For problems involving fixed-size subarrays, use sliding window:

Problem: Find the maximum sum of any subarray of exactly size k.

function maxSumWindow(A, n, k):
    // Compute sum of first window
    window_sum = 0
    for i = 0 to k-1:
        window_sum = window_sum + A[i]
    
    max_sum = window_sum
    
    // Slide the window: add next element, remove first element
    for i = k to n-1:
        window_sum = window_sum + A[i] - A[i-k]
        if window_sum > max_sum:
            max_sum = window_sum
    
    return max_sum

Example: A = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4

Window	Elements	Sum
[0..3]	1, 4, 2, 10	17
[1..4]	4, 2, 10, 23	39 ← max
[2..5]	2, 10, 23, 3	38
[3..6]	10, 23, 3, 1	37
[4..7]	23, 3, 1, 0	27
[5..8]	3, 1, 0, 20	24

Answer: 39

Time Complexity: O(N) — much better than O(N × k) brute force.

---

2.4.5 Kadane's Algorithm — Deep Dive

For the variable-size maximum subarray problem, Kadane's Algorithm solves it in O(N).

Core Idea: At each position, decide: should I extend the current subarray, or start fresh from here?

If adding the current element to the running sum makes it larger than the element alone, extend. Otherwise, start a new subarray.

function kadane(A, n):
    current_sum = A[0]     // sum of current subarray
    max_sum = A[0]         // best sum seen so far
    
    for i = 1 to n-1:
        // Either extend the current subarray or start a new one
        if current_sum + A[i] > A[i]:
            current_sum = current_sum + A[i]
        else:
            current_sum = A[i]
        
        // Update the overall maximum
        if current_sum > max_sum:
            max_sum = current_sum
    
    return max_sum

Equivalent, more compact version (common in exams):

function kadane(A, n):
    x = A[0]      // current_sum
    m = A[0]      // max_sum
    
    for i = 1 to n-1:
        x = max(x + A[i], A[i])
        m = max(m, x)
    
    return m

💡 Exam Pattern Recognition: If you see code with x = x + A[i] followed by a comparison like if (m < x): m = x, that's Kadane's Algorithm.

---

2.4.6 Full Trace on a 10-Element Array

Array: A = [-2, 1, -3, 4, -1, 2, 1, -5, 4, 3]

Using the compact version:

i	A[i]	x + A[i]	A[i] alone	x = max(...)	m = max(m, x)
start	—	—	—	x = -2	m = -2
1	1	-2+1 = -1	1	max(-1, 1) = 1	max(-2, 1) = 1
2	-3	1+(-3) = -2	-3	max(-2, -3) = -2	max(1, -2) = 1
3	4	-2+4 = 2	4	max(2, 4) = 4	max(1, 4) = 4
4	-1	4+(-1) = 3	-1	max(3, -1) = 3	max(4, 3) = 4
5	2	3+2 = 5	2	max(5, 2) = 5	max(4, 5) = 5
6	1	5+1 = 6	1	max(6, 1) = 6	max(5, 6) = 6
7	-5	6+(-5) = 1	-5	max(1, -5) = 1	max(6, 1) = 6
8	4	1+4 = 5	4	max(5, 4) = 5	max(6, 5) = 6
9	3	5+3 = 8	3	max(8, 3) = 8	max(6, 8) = 8

Answer: 8 (the subarray [4, -1, 2, 1, -5, 4, 3] has sum 8)

Wait — let's verify: 4 + (-1) + 2 + 1 + (-5) + 4 + 3 = 8 ✓

---

🤔 Think First — Section 2.4 Questions

Q2.4.1: Trace Kadane's Algorithm on A = [2, -1, 2, 3, -9, 4]. What is the maximum subarray sum?

Q2.4.2: Compute the prefix sum array for A = [1, 2, 3, 4, 5]. Then use it to find the sum of A[2..4].

Q2.4.3: Can Kadane's Algorithm work if all elements are negative? Trace it on A = [-3, -5, -2, -8].

(Answers at the end of Chapter 2)

---

Chapter 2 — Answers to "Think First" Questions

Section 2.1 Answers

A2.1.1: Find the minimum:

function findMin(A, n):
    min_val = A[0]
    for i = 1 to n-1:
        if A[i] < min_val:     // changed > to <
            min_val = A[i]
    return min_val

A2.1.2: O(N). The function has a single loop that iterates through all n elements exactly once. No nested loops.

A2.1.3: Trace for linearSearch([5, 3, 8, 1, 9, 2], 6, 8):

i	A[i]	A[i] == 8?
0	5	No
1	3	No
2	8	Yes → return 2

3 comparisons (checks index 0, 1, 2).

---

Section 2.2 Answers

A2.2.1: A = [3, 7, 11, 15, 19, 23, 27] (indices 0–6), key = 11:

Iter	l	r	m	A[m]	Action
1	0	6	3	15	15 > 11 → r = 2
2	0	2	1	7	7 < 11 → l = 2
3	2	2	2	11	11 == 11 → Found at index 2!

3 iterations.

A2.2.2: Same array, key = 20:

Iter	l	r	m	A[m]	Action
1	0	6	3	15	15 < 20 → l = 4
2	4	6	5	23	23 > 20 → r = 4
3	4	4	4	19	19 < 20 → l = 5

Now l = 5 > r = 4, so the while loop condition l <= r is false. Loop ends. Not found. 3 iterations.

A2.2.3: log₂(128) = 7. Maximum 7 iterations (since 2⁷ = 128).

---

Section 2.3 Answers

A2.3.1: Bubble Sort on A = [4, 2, 7, 1]:

Pass 1: Compare (4,2)→swap→[2,4,7,1], (4,7)→no→[2,4,7,1], (7,1)→swap→[2,4,1,7] After pass 1: [2, 4, 1, 7]

Pass 2: Compare (2,4)→no, (4,1)→swap→[2,1,4,7] After pass 2: [2, 1, 4, 7]

Pass 3: Compare (2,1)→swap→[1,2,4,7] After pass 3: [1, 2, 4, 7] ✓

A2.3.2: This is Selection Sort. Clue: outer loop + inner loop finding min_idx + one swap per pass.

A2.3.3: Merge Sort — always O(N log N). Quick Sort is also O(N log N) on average, but O(N²) in the worst case.

---

Section 2.4 Answers

A2.4.1: A = [2, -1, 2, 3, -9, 4]:

i	A[i]	x + A[i]	A[i]	x = max(...)	m = max(m, x)
start	—	—	—	2	2
1	-1	1	-1	1	2
2	2	3	2	3	3
3	3	6	3	6	6
4	-9	-3	-9	-3	6
5	4	1	4	4	6

Answer: 6 (subarray [2, -1, 2, 3])

A2.4.2: Prefix sum:

• P = [1, 3, 6, 10, 15]
• Sum of A[2..4] = P[4] - P[1] = 15 - 3 = 12 ✓ (3 + 4 + 5 = 12)

A2.4.3: Trace on A = [-3, -5, -2, -8]:

i	A[i]	x + A[i]	A[i]	x	m
start	—	—	—	-3	-3
1	-5	-8	-5	-5	-3
2	-2	-7	-2	-2	-2
3	-8	-10	-8	-8	-2

Answer: -2 (the "maximum" subarray is just [-2], the least negative element.)

Yes, Kadane's works correctly even with all-negative arrays. It returns the single element closest to zero.

---

---

Chapter 3: Recursion & Discrete Mathematics

Goal: After this chapter, you will be able to trace recursive functions, draw recursion trees, apply counting principles, and work with matrices — the mathematical backbone of the CMI exam.

---

3.1 Recursion & Recurrence Relations

3.1.1 What Is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem.

Think of it like Russian nesting dolls — to open the biggest doll, you open it and find a smaller one inside. You keep opening until you reach the smallest doll (this is the base case).

function countdown(n):
    if n == 0:            // base case — stop!
        print("Go!")
        return
    print(n)
    countdown(n - 1)       // recursive call — smaller problem

Trace for countdown(3):

countdown(3) → prints 3, calls countdown(2)
  countdown(2) → prints 2, calls countdown(1)
    countdown(1) → prints 1, calls countdown(0)
      countdown(0) → prints "Go!", returns

Output: 3 2 1 Go!

---

3.1.2 Base Case vs Recursive Case

Every recursive function must have:

1. Base Case: The condition that stops the recursion. Without it, the function calls itself forever (stack overflow!).
2. Recursive Case: The function calls itself with a smaller/simpler input, moving toward the base case.

function mystery(n):
    if n <= 0:        // ← BASE CASE
        return 0
    return n + mystery(n - 1)   // ← RECURSIVE CASE

⚠️ Common Error: Forgetting the base case, or making the recursive call with the same (not smaller) input.

---

3.1.3 The Call Stack

When a function calls itself, the computer remembers where it left off using a call stack. Each call creates a new "frame" on the stack.

Example: mystery(3)

Call Stack growth:

mystery(3) → needs mystery(2)         [mystery(3) waits]
  mystery(2) → needs mystery(1)       [mystery(2) waits]
    mystery(1) → needs mystery(0)     [mystery(1) waits]
      mystery(0) → returns 0          [base case!]
    mystery(1) → returns 1 + 0 = 1    [resumes]
  mystery(2) → returns 2 + 1 = 3      [resumes]
mystery(3) → returns 3 + 3 = 6        [resumes]

Answer: 6 (which is 3 + 2 + 1 + 0 = 6, or equivalently, 3! / 1 = the sum of 1 to 3)

---

3.1.4 Drawing Recursion Trees

For functions with multiple recursive calls (like Fibonacci), draw a tree where each node is a function call and its children are the calls it makes.

Example: Fibonacci

function fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Recursion Tree for fib(5):

                    fib(5)
                   /      \
              fib(4)       fib(3)
             /     \       /     \
         fib(3)   fib(2) fib(2)  fib(1)
         /   \    /   \   /   \     |
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) → 1
      / \     |     |      |      |
  fib(1) fib(0) → 1  → 1    → 0    → 1
    |      |
    → 1    → 0

Computing bottom-up:

• fib(0) = 0, fib(1) = 1
• fib(2) = fib(1) + fib(0) = 1 + 0 = 1
• fib(3) = fib(2) + fib(1) = 1 + 1 = 2
• fib(4) = fib(3) + fib(2) = 2 + 1 = 3
• fib(5) = fib(4) + fib(3) = 3 + 2 = **5**

💡 Exam Tip: When given a recursive function, don't try to think about it abstractly. Draw the tree, compute the leaf values, and work your way up.

---

3.1.5 Classic Examples: Factorial, Fibonacci, Power

Factorial: n!

function factorial(n):
    if n == 0:           // base case: 0! = 1
        return 1
    return n * factorial(n - 1)

Trace for factorial(5):

Call	Returns
factorial(5)	5 × factorial(4) = 5 × 24 = 120
factorial(4)	4 × factorial(3) = 4 × 6 = 24
factorial(3)	3 × factorial(2) = 3 × 2 = 6
factorial(2)	2 × factorial(1) = 2 × 1 = 2
factorial(1)	1 × factorial(0) = 1 × 1 = 1
factorial(0)	1 (base case)

5! = 120 ✓

Power: aⁿ (Naive)

function power(a, n):
    if n == 0:
        return 1
    return a * power(a, n - 1)

Trace for power(2, 4):

• power(2, 4) = 2 × power(2, 3) = 2 × 8 = 16
• power(2, 3) = 2 × power(2, 2) = 2 × 4 = 8
• power(2, 2) = 2 × power(2, 1) = 2 × 2 = 4
• power(2, 1) = 2 × power(2, 0) = 2 × 1 = 2
• power(2, 0) = 1 (base case)

2⁴ = 16 ✓

Fast Power: aⁿ in O(log n)

function fastPower(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:                   // n is even
        half = fastPower(a, n // 2)
        return half * half
    else:                            // n is odd
        return a * fastPower(a, n - 1)

Trace for fastPower(2, 10):

• fastPower(2, 10) → even: half = fastPower(2, 5) = 32, return 32 × 32 = 1024
• fastPower(2, 5) → odd: return 2 × fastPower(2, 4) = 2 × 16 = 32
• fastPower(2, 4) → even: half = fastPower(2, 2) = 4, return 4 × 4 = 16
• fastPower(2, 2) → even: half = fastPower(2, 1) = 2, return 2 × 2 = 4
• fastPower(2, 1) → odd: return 2 × fastPower(2, 0) = 2 × 1 = 2
• fastPower(2, 0) → return 1

Only 6 calls instead of 10. For n = 1000, this takes ~10 calls instead of 1000!

---

3.1.6 Recurrence Relations and Closed-Form Solutions

A recurrence relation defines a sequence where each term depends on previous terms.

Sequence	Recurrence	Base Case(s)	Closed Form
Sum 1..n	T(n) = T(n-1) + n	T(0) = 0	n(n+1)/2
Factorial	T(n) = n × T(n-1)	T(0) = 1	n!
Fibonacci	T(n) = T(n-1) + T(n-2)	T(0)=0, T(1)=1	(complex formula)
Power of 2	T(n) = 2 × T(n-1)	T(0) = 1	2ⁿ

How to solve a simple recurrence (unwinding):

Given: T(n) = T(n-1) + n, T(0) = 0

T(n) = T(n-1) + n
     = [T(n-2) + (n-1)] + n
     = T(n-2) + (n-1) + n
     = [T(n-3) + (n-2)] + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(0) + 1 + 2 + ... + n
     = 0 + n(n+1)/2
     = n(n+1)/2

---

🤔 Think First — Section 3.1 Questions

Q3.1.1: Trace the following recursive function for f(4). What is the return value?

function f(n):
    if n == 1:
        return 1
    return f(n - 1) + 2 * n - 1

Q3.1.2: How many times is fib called (total, including all recursive calls) when computing fib(5)? Count from the tree.

Q3.1.3: What happens if you write this function and call broken(5)?

function broken(n):
    return broken(n - 1) + 1

Q3.1.4: Solve the recurrence: T(n) = 2 × T(n-1), T(0) = 3. Find T(4).

(Answers at the end of Chapter 3)

---

3.2 Combinatorics & Counting

3.2.1 The Fundamental Counting Principle

If you have m ways to do one thing and n ways to do another, you have m × n ways to do both.

Example 1: You have 3 shirts and 4 pants. How many outfits? 3 × 4 = 12

Example 2: A license plate has 2 letters followed by 3 digits. How many possible plates?

• Letters: 26 choices each → 26 × 26 = 676
• Digits: 10 choices each → 10 × 10 × 10 = 1000
• Total: 676 × 1000 = 676,000

Example 3: How many 4-bit binary strings are there?

• Each bit has 2 choices (0 or 1): 2 × 2 × 2 × 2 = 2⁴ = 16

---

3.2.2 Permutations

A permutation is an arrangement where order matters.

Formula: The number of ways to arrange r items out of n distinct items:

$$P(n, r) = \frac{n!}{(n-r)!}$$

Example 1: How many ways can 3 people sit in 5 chairs? $$P(5, 3) = \frac{5!}{2!} = \frac{120}{2} = 60$$

Example 2: How many ways to arrange all letters of "CAT"? $$P(3, 3) = 3! = 6$$ The arrangements: CAT, CTA, ACT, ATC, TCA, TAC ✓

Special Case: All n items → n! arrangements.

---

3.2.3 Combinations and the Binomial Coefficient

A combination is a selection where order does NOT matter.

Formula:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Example 1: Choose 2 fruits from {Apple, Banana, Cherry}: $$\binom{3}{2} = \frac{3!}{2! \times 1!} = \frac{6}{2} = 3$$ The selections: {A,B}, {A,C}, {B,C} ✓

Example 2: Choose 3 students from a class of 10: $$\binom{10}{3} = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$$

Key Properties of Binomial Coefficients:

Property	Formula
Symmetry	$\binom{n}{r} = \binom{n}{n-r}$
Choose none	$\binom{n}{0} = 1$
Choose all	$\binom{n}{n} = 1$
Pascal's Rule	$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Pascal's Triangle (each entry = sum of two entries above it):

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1

Row n, column r gives $\binom{n}{r}$.

---

3.2.4 Catalan Numbers — Formula & Intuition

Catalan numbers appear in many counting problems in computer science. The nth Catalan number is:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)! \times n!}$$

First few values:

n	0	1	2	3	4	5	6
Cₙ	1	1	2	5	14	42	132

Where Catalan Numbers Appear:

1. Number of structurally different binary trees with n nodes
2. Number of ways to parenthesize n+1 factors: e.g., ((ab)(cd)) vs (a((bc)d))
3. Number of valid combinations of n pairs of balanced parentheses: e.g., for n=3: ((())), (()()), (())(), ()(()), ()()()
4. Number of paths on an n×n grid from top-left to bottom-right that don't cross the diagonal

Computing Example: How many structurally different binary trees with 4 nodes?

$$C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \times \frac{8!}{4! \times 4!} = \frac{1}{5} \times 70 = 14$$

---

3.2.5 Application: Counting Binary Trees

Problem (CMI Exam Style): How many structurally distinct binary trees can be formed with 3 nodes?

Answer: $C_3 = 5$

Here are all 5 trees (with nodes labeled ○):

Tree 1:      Tree 2:      Tree 3:      Tree 4:      Tree 5:
    ○            ○            ○            ○            ○
   /            /              \            \          / \
  ○            ○                ○            ○        ○   ○
 /              \              /              \
○                ○            ○                ○

Verification using the recurrence relation:

Catalan numbers can also be computed recursively: $$C_n = \sum_{i=0}^{n-1} C_i \times C_{n-1-i}$$

For C₃: $$C_3 = C_0 \times C_2 + C_1 \times C_1 + C_2 \times C_0$$ $$= 1 \times 2 + 1 \times 1 + 2 \times 1 = 2 + 1 + 2 = 5$$ ✓

Intuition: To build a tree with 3 nodes, pick one node as root. Then distribute the remaining 2 nodes between left and right subtrees: (0,2), (1,1), or (2,0). Each distribution multiplies the Catalan numbers for left and right.

---

🤔 Think First — Section 3.2 Questions

Q3.2.1: How many 3-letter "words" can be made from the letters {A, B, C, D, E} if repetition is allowed?

Q3.2.2: Compute $\binom{6}{2}$.

Q3.2.3: How many structurally distinct binary trees can be formed with 5 nodes? (Use the Catalan number formula.)

Q3.2.4: Using Pascal's rule, show that $\binom{5}{2} = \binom{4}{1} + \binom{4}{2}$.

(Answers at the end of Chapter 3)

---

3.3 Set Theory & Matrix Algebra

3.3.1 Sets and Set Operations

A set is an unordered collection of distinct elements.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

Operation	Symbol	Result	Meaning
Union	A ∪ B	{1, 2, 3, 4, 5, 6}	Elements in either set
Intersection	A ∩ B	{3, 4}	Elements in both sets
Difference	A − B	{1, 2}	Elements in A but not in B
Complement	A'	Everything not in A	Depends on universal set
Cardinality	|A|	4	Number of elements

Example: If U = {1, 2, 3, 4, 5, 6, 7}, A = {1, 3, 5, 7}, B = {2, 3, 5}:

• A ∪ B = {1, 2, 3, 5, 7}
• A ∩ B = {3, 5}
• A − B = {1, 7}
• B − A = {2}

---

3.3.2 Functions: Injective, Surjective, Bijective

A function f: A → B maps each element of set A to exactly one element of set B.

Type	Definition	Picture	Condition
Injective (One-to-one)	No two inputs map to the same output	Each output has ≤ 1 arrow in	f(a) = f(b) → a = b
Surjective (Onto)	Every element in B is mapped to by some element in A	Each output has ≥ 1 arrow in	For every b ∈ B, ∃ a ∈ A: f(a) = b
Bijective	Both injective AND surjective	Each output has exactly 1 arrow in	One-to-one correspondence

Example 1: f: {1,2,3} → {a,b,c,d}, f(1)=a, f(2)=b, f(3)=c

• Injective? Yes (no two inputs share an output)
• Surjective? No (d is not mapped to)
• Bijective? No

Example 2: f: {1,2,3} → {a,b,c}, f(1)=a, f(2)=b, f(3)=c

• Injective? Yes
• Surjective? Yes (every element of {a,b,c} is hit)
• Bijective? Yes ✓

Example 3: f: {1,2,3} → {a,b}, f(1)=a, f(2)=a, f(3)=b

• Injective? No (1 and 2 both map to a)
• Surjective? Yes (both a and b are mapped to)
• Bijective? No

💡 Key Insight: If |A| = |B| and f is injective, then f must also be surjective (and hence bijective).

---

3.3.3 Matrices: Basics and Operations

A matrix is a rectangular grid of numbers with rows and columns.

        Column 1  Column 2  Column 3
Row 1 [    1         2         3    ]
Row 2 [    4         5         6    ]

This is a 2 × 3 matrix (2 rows, 3 columns). We call element at row i, column j as M[i][j].

M[1][2] = 2, M[2][3] = 6 (using 1-based indexing)

Matrix Addition: Add corresponding elements (matrices must be same size).

[1  2]     [5  6]     [1+5  2+6]     [6   8]
[3  4]  +  [7  8]  =  [3+7  4+8]  =  [10  12]

Matrix Multiplication: For A (m×n) × B (n×p) = C (m×p):

$$C[i][j] = \sum_{k=1}^{n} A[i][k] \times B[k][j]$$

Example:

[1  2]     [5  6]     [1×5+2×7  1×6+2×8]     [19  22]
[3  4]  ×  [7  8]  =  [3×5+4×7  3×6+4×8]  =  [43  50]

Detail for C[1][1]: 1×5 + 2×7 = 5 + 14 = 19 ✓

Pseudo-code for Matrix Multiplication:

function matMul(A, B, n):
    // Assume A and B are n×n square matrices
    C = new n×n matrix filled with 0
    for i = 1 to n:
        for j = 1 to n:
            for k = 1 to n:
                C[i][j] = C[i][j] + A[i][k] * B[k][j]
    return C

Time Complexity: O(N³) — three nested loops.

---

3.3.4 Transpose, Trace, and Determinant

Transpose

The transpose of matrix A (written Aᵀ) swaps rows and columns: Aᵀ[i][j] = A[j][i].

A = [1  2  3]        Aᵀ = [1  4]
    [4  5  6]              [2  5]
                           [3  6]

Pseudo-code:

function transpose(A, rows, cols):
    T = new cols×rows matrix
    for i = 1 to rows:
        for j = 1 to cols:
            T[j][i] = A[i][j]
    return T

Trace

The trace of a square matrix is the sum of its diagonal elements.

A = [1  2  3]
    [4  5  6]        trace(A) = 1 + 5 + 9 = 15
    [7  8  9]

Pseudo-code:

function trace(A, n):
    total = 0
    for i = 1 to n:
        total = total + A[i][i]
    return total

Determinant (2×2 Matrix)

For a 2×2 matrix:

$$det\begin{pmatrix} a & b \ c & d \end{pmatrix} = ad - bc$$

Example: $$det\begin{pmatrix} 3 & 8 \ 4 & 6 \end{pmatrix} = 3 \times 6 - 8 \times 4 = 18 - 32 = -14$$

Determinant (3×3 Matrix)

Expand along the first row:

$$det\begin{pmatrix} a & b & c \ d & e & f \ g & h & i \end{pmatrix} = a(ei - fh) - b(di - fg) + c(dh - eg)$$

Example:

$$det\begin{pmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{pmatrix} = 1(45-48) - 2(36-42) + 3(32-35) = 1(-3) - 2(-6) + 3(-3) = -3 + 12 - 9 = 0$$

---

3.3.5 Symmetric & Triangular Matrices

Symmetric Matrix

A square matrix A is symmetric if A[i][j] == A[j][i] for all i, j. Equivalently, A = Aᵀ.

Symmetric:              NOT Symmetric:
[1  2  3]               [1  2  3]
[2  5  6]               [4  5  6]
[3  6  9]               [7  8  9]

In the left matrix: A[1][2]=2=A[2][1]✓, A[1][3]=3=A[3][1]✓, A[2][3]=6=A[3][2]✓

Upper Triangular Matrix

All elements below the main diagonal are zero.

[1  2  3]
[0  5  6]        A[i][j] = 0 for all i > j
[0  0  9]

Lower Triangular Matrix

All elements above the main diagonal are zero.

[1  0  0]
[4  5  0]        A[i][j] = 0 for all i < j
[7  8  9]

---

3.3.6 Pseudo-Code: Checking Matrix Properties

Check if Symmetric:

function isSymmetric(A, n):
    for i = 1 to n:
        for j = 1 to n:
            if A[i][j] != A[j][i]:
                return false
    return true

💡 Optimization: Only need to check j > i (upper triangle):

function isSymmetric(A, n):
    for i = 1 to n:
        for j = i+1 to n:
            if A[i][j] != A[j][i]:
                return false
    return true

Check if Upper Triangular:

function isUpperTriangular(A, n):
    for i = 2 to n:               // start from row 2
        for j = 1 to i-1:         // check below diagonal
            if A[i][j] != 0:
                return false
    return true

Check if Identity Matrix:

function isIdentity(A, n):
    for i = 1 to n:
        for j = 1 to n:
            if i == j and A[i][j] != 1:
                return false
            if i != j and A[i][j] != 0:
                return false
    return true

Trace Example: Is this matrix symmetric?

M = [1  7  3]
    [7  4  5]
    [3  5  6]

Check: M[1][2]=7, M[2][1]=7 ✓ | M[1][3]=3, M[3][1]=3 ✓ | M[2][3]=5, M[3][2]=5 ✓

Yes, M is symmetric. ✓

---

🤔 Think First — Section 3.3 Questions

Q3.3.1: Is the function f: {1,2,3,4} → {a,b,c,d}, defined as f(1)=b, f(2)=d, f(3)=a, f(4)=c, bijective? Why or why not?

Q3.3.2: Compute the product of these matrices:

[2  0]     [1  3]
[1  4]  ×  [5  2]

Q3.3.3: What is the trace of this matrix?

[10   3   1]
[ 6   7   2]
[ 8   4   5]

Q3.3.4: Write pseudo-code to check if a given square matrix is a lower triangular matrix.

(Answers at the end of Chapter 3)

---

Chapter 3 — Answers to "Think First" Questions

Section 3.1 Answers

A3.1.1: Trace f(4):

Call	Returns
f(4)	f(3) + 2×4 - 1 = 9 + 7 = 16
f(3)	f(2) + 2×3 - 1 = 4 + 5 = 9
f(2)	f(1) + 2×2 - 1 = 1 + 3 = 4
f(1)	1 (base case)

Answer: 16

Notice the pattern: f(1)=1, f(2)=4, f(3)=9, f(4)=16 → f(n) = n²! The function computes perfect squares using the identity: n² = 1 + 3 + 5 + ... + (2n-1).

A3.1.2: Count all nodes in the fib(5) tree:

• fib(5): 1
• fib(4): 1, fib(3): 1
• fib(3): 1, fib(2): 1, fib(2): 1, fib(1): 1
• fib(2): 1, fib(1): 1, fib(1): 1, fib(0): 1, fib(1): 1, fib(0): 1
• fib(1): 1, fib(0): 1

Total: 15 calls. This explosive growth is why naive Fibonacci recursion is O(2ⁿ) — very slow!

A3.1.3: This function has no base case. It will call broken(4), which calls broken(3), which calls broken(2), ... broken(0), broken(-1), broken(-2), ... forever. This causes a stack overflow error — the call stack runs out of memory.

A3.1.4: T(n) = 2 × T(n-1), T(0) = 3.

Unwind: T(n) = 2 × T(n-1) = 2 × 2 × T(n-2) = 2² × T(n-2) = ... = 2ⁿ × T(0) = 3 × 2ⁿ

So T(4) = 3 × 2⁴ = 3 × 16 = 48.

---

Section 3.2 Answers

A3.2.1: Repetition allowed, choosing 3 from 5 letters: 5 × 5 × 5 = 5³ = 125 words.

A3.2.2: $\binom{6}{2} = \frac{6!}{2! \times 4!} = \frac{6 \times 5}{2 \times 1} = \frac{30}{2} = \mathbf{15}$

A3.2.3: C₅ (Catalan number for n=5):

$$C_5 = \frac{1}{6}\binom{10}{5} = \frac{1}{6} \times \frac{10!}{5! \times 5!} = \frac{1}{6} \times 252 = \mathbf{42}$$

There are 42 structurally distinct binary trees with 5 nodes.

A3.2.4: Pascal's Rule check:

• $\binom{5}{2} = \frac{5!}{2! \times 3!} = \frac{120}{2 \times 6} = 10$
• $\binom{4}{1} = 4$
• $\binom{4}{2} = \frac{4!}{2! \times 2!} = \frac{24}{4} = 6$
• $\binom{4}{1} + \binom{4}{2} = 4 + 6 = 10 = \binom{5}{2}$ ✓

---

Section 3.3 Answers

A3.3.1: Check:

• Injective? f(1)=b, f(2)=d, f(3)=a, f(4)=c — all outputs are different. Yes.
• Surjective? The range {b, d, a, c} = {a, b, c, d} — every element of the codomain is hit. Yes.
• Bijective? Both injective and surjective → Yes, it is bijective. ✓

A3.3.2:

[2  0]     [1  3]     [2×1+0×5   2×3+0×2]     [2   6]
[1  4]  ×  [5  2]  =  [1×1+4×5   1×3+4×2]  =  [21  11]

A3.3.3: Trace = sum of diagonal elements = 10 + 7 + 5 = 22

A3.3.4: Check lower triangular:

function isLowerTriangular(A, n):
    for i = 1 to n:
        for j = i+1 to n:         // check ABOVE diagonal
            if A[i][j] != 0:
                return false
    return true

(This is the mirror image of isUpperTriangular — we check above the diagonal instead of below.)

---

---

Chapter 4: Advanced Data Structures (Conceptual)

Goal: After this chapter, you will understand trees, stacks, queues, and graphs — how they work conceptually, how to traverse them, and how to represent them in code.

---

4.1 Binary Trees & Binary Search Trees (BSTs)

4.1.1 Tree Terminology: Root, Leaf, Child, Depth, Height

A tree is a hierarchical data structure made of nodes connected by edges.

         A          ← Root (topmost node)
        / \
       B   C        ← B and C are CHILDREN of A
      / \    \
     D   E    F     ← D and E are children of B; F is child of C
    /
   G                ← G is a child of D

Term	Definition	Example
Root	The topmost node (no parent)	A
Leaf	A node with no children	E, F, G
Child	A node directly below another	B is a child of A
Parent	A node directly above another	A is the parent of B
Sibling	Nodes sharing the same parent	B and C are siblings
Depth	Distance (edges) from root to node	depth(A)=0, depth(B)=1, depth(G)=3
Height	Longest path (edges) from node to a leaf	height(A)=3, height(B)=2, height(F)=0
Height of tree	Height of the root node	3

---

4.1.2 Binary Trees

A binary tree is a tree where each node has at most 2 children: a left child and a right child.

      1
     / \
    2   3
   / \
  4   5

This is a binary tree with 5 nodes. Node 1 is the root. Nodes 3, 4, and 5 are leaves.

Types of Binary Trees:

Type	Definition
Full Binary Tree	Every node has 0 or 2 children (no node has exactly 1 child)
Complete Binary Tree	All levels are fully filled except possibly the last, which is filled left to right
Perfect Binary Tree	All internal nodes have 2 children AND all leaves are at the same depth

---

4.1.3 Binary Search Tree (BST) Property

A Binary Search Tree has the property:

• For every node X:
  • All values in the left subtree < X
  • All values in the right subtree > X

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Verify: Is this a valid BST?

• Node 8: left subtree values {1,3,4,6,7} < 8 ✓, right subtree values {10,13,14} > 8 ✓
• Node 3: left {1} < 3 ✓, right {4,6,7} > 3 ✓
• Node 10: no left child, right {13,14} > 10 ✓
• All other nodes check out. Yes, valid BST ✓

💡 Key Insight for Exams: An in-order traversal of a BST produces elements in sorted order.

---

4.1.4 Tree Traversals: Pre-order, In-order, Post-order

Traversal = visiting every node in a specific order. There are three standard ways:

Traversal	Order	Mnemonic
Pre-order	Root → Left → Right	Root first
In-order	Left → Root → Right	Root in the middle
Post-order	Left → Right → Root	Root last

Pseudo-code:

function preorder(node):
    if node == null: return
    print(node.value)        // process root FIRST
    preorder(node.left)
    preorder(node.right)

function inorder(node):
    if node == null: return
    inorder(node.left)
    print(node.value)        // process root in MIDDLE
    inorder(node.right)

function postorder(node):
    if node == null: return
    postorder(node.left)
    postorder(node.right)
    print(node.value)        // process root LAST

Example Tree:

        1
       / \
      2   3
     / \
    4   5

Traversal	Order	Result
Pre-order	Root→L→R	1, 2, 4, 5, 3
In-order	L→Root→R	4, 2, 5, 1, 3
Post-order	L→R→Root	4, 5, 2, 3, 1

Detailed Pre-order trace:

1. Visit 1 → print 1
2. Go left to 2 → print 2
3. Go left to 4 → print 4
4. 4 has no children, backtrack to 2
5. Go right to 5 → print 5
6. 5 has no children, backtrack to 2, then to 1
7. Go right to 3 → print 3
8. 3 has no children. Done.

Result: 1, 2, 4, 5, 3

In-order on BST example:

        8
       / \
      3   10
     / \    \
    1   6    14

In-order: 1, 3, 6, 8, 10, 14 — Sorted! ✓

---

4.1.5 Building a BST from a Sequence

Insert algorithm: Starting from the root, compare the new value:

• If smaller, go left.
• If larger, go right.
• When you hit a null spot, insert there.

Example: Insert sequence [5, 3, 7, 1, 4, 6, 8]

Insert 5:       Insert 3:       Insert 7:       Insert 1:
    5               5               5               5
                   /               / \             / \
                  3               3   7           3   7
                                                 /
                                                1

Insert 4:       Insert 6:       Insert 8:
    5               5               5
   / \             / \             / \
  3   7           3   7           3   7
 / \             / \ /           / \ / \
1   4           1  4 6          1  4 6  8

Final BST: Verify in-order: 1, 3, 4, 5, 6, 7, 8 ✓ (sorted)

---

🤔 Think First — Section 4.1 Questions

Q4.1.1: Given this tree, what are the Pre-order, In-order, and Post-order traversals?

        10
       /  \
      5    15
     / \     \
    3   7     20

Q4.1.2: Build a BST by inserting elements in this order: [4, 2, 6, 1, 3, 5, 7]. Draw the final tree.

Q4.1.3: Is this a valid BST? Why or why not?

      5
     / \
    3   8
   / \
  2   6

(Answers at the end of Chapter 4)

---

4.2 Stacks & Queues

4.2.1 The Stack (LIFO)

A stack is a data structure that follows Last In, First Out (LIFO).

Think of a stack of plates — you can only add or remove from the top.

Operations:

• push(x) — add element x to the top
• pop() — remove and return the top element
• top() / peek() — view the top element without removing it
• isEmpty() — check if stack is empty

Operations:          Stack state (top → bottom):

push(10)             [10]
push(20)             [20, 10]
push(30)             [30, 20, 10]
pop()  → returns 30  [20, 10]
pop()  → returns 20  [10]
push(40)             [40, 10]
pop()  → returns 40  [10]
pop()  → returns 10  []

💡 Key Insight: If you push [1, 2, 3] and then pop all, you get 3, 2, 1 — reversed order.

---

4.2.2 The Queue (FIFO)

A queue is a data structure that follows First In, First Out (FIFO).

Think of a line at a ticket counter — first person in line is first to be served.

Operations:

• enqueue(x) — add element x to the back
• dequeue() — remove and return from the front
• front() — view the front element
• isEmpty() — check if queue is empty

Operations:            Queue state (front → back):

enqueue(10)            [10]
enqueue(20)            [10, 20]
enqueue(30)            [10, 20, 30]
dequeue() → returns 10 [20, 30]
dequeue() → returns 20 [30]
enqueue(40)            [30, 40]
dequeue() → returns 30 [40]

💡 Key Insight: Elements come out in the same order they went in.

---

4.2.3 Tracing Stack/Queue Operations

Stack Example — Bracket Matching:

A classic stack application: check if parentheses are balanced.

function isBalanced(s):
    stack = empty stack
    for each char c in s:
        if c == '(' or c == '[' or c == '{':
            stack.push(c)
        else:                           // c is ')', ']', or '}'
            if stack.isEmpty():
                return false            // no matching opener
            top = stack.pop()
            if not matches(top, c):
                return false            // wrong type of bracket
    return stack.isEmpty()              // true if all matched

Trace for s = "({[]})":

Char	Action	Stack
(	push	[(]
{	push	[(, {]
[	push	[(, {, []
]	pop [, matches ✓	[(, {]
}	pop {, matches ✓	[(]
)	pop (, matches ✓	[]

Stack is empty → Balanced! ✓

Trace for s = "([)]":

Char	Action	Stack
(	push	[(]
[	push	[(, []
)	pop [, does ) match [? No!	Not Balanced ✗

---

4.2.4 Applications

Data Structure	Common Applications
Stack	Bracket matching, undo operations, function call stack, expression evaluation, DFS
Queue	BFS (Breadth-First Search), task scheduling, print queue, message buffers

---

🤔 Think First — Section 4.2 Questions

Q4.2.1: You push elements 5, 10, 15, 20 onto a stack, then pop twice. What values are popped? What remains on the stack?

Q4.2.2: You enqueue elements A, B, C, D into a queue, then dequeue twice. What values are dequeued? What remains?

Q4.2.3: Is the string "(())()" balanced? Trace using a stack.

(Answers at the end of Chapter 4)

---

4.3 Graphs — Basics

4.3.1 What Is a Graph?

A graph is a collection of nodes (or vertices) connected by edges.

    A --- B
    |   / |
    |  /  |
    C --- D

This graph has:

• Vertices: {A, B, C, D}
• Edges: {(A,B), (A,C), (B,C), (B,D), (C,D)}

Graphs model relationships: social networks (people=nodes, friendships=edges), road maps (cities=nodes, roads=edges), web pages (pages=nodes, links=edges).

---

4.3.2 Directed vs Undirected Graphs

Type	Edges	Example
Undirected	Two-way: A — B means you can go A→B and B→A	Friendships
Directed	One-way: A → B means you can go from A to B only	Twitter follows, web links

Directed Graph Example:

    A → B
    ↓   ↓
    C → D

Here A→B is an edge, but B→A is NOT (unless explicitly shown).

---

4.3.3 Adjacency Matrix Representation

Store a graph as a 2D matrix. M[i][j] = 1 if there's an edge from node i to node j, else 0.

Undirected Graph:

    A --- B
    |     |
    C --- D

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

💡 For undirected graphs, the adjacency matrix is always symmetric (M[i][j] = M[j][i]).

Directed Graph:

    A → B
    ↓     
    C → D

	A	B	C	D
A	0	1	1	0
B	0	0	0	0
C	0	0	0	1
D	0	0	0	0

This matrix is NOT symmetric — correctly reflecting the one-way edges.

Pseudo-code to count edges from a node:

function countEdgesFrom(M, n, node):
    count = 0
    for j = 0 to n-1:
        if M[node][j] == 1:
            count = count + 1
    return count

---

4.3.4 Adjacency List Representation

Instead of a matrix, store for each node a list of its neighbors.

    A --- B
    |     |
    C --- D

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Comparison:

Feature	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Check if edge exists	O(1)	O(degree of node)
List all neighbors	O(V)	O(degree of node)
Best for	Dense graphs	Sparse graphs

Where V = number of vertices, E = number of edges.

---

4.3.5 Graph Traversal Intuition: DFS & BFS

DFS (Depth-First Search): Go as deep as possible before backtracking. Uses a stack (or recursion).

Start at A:
A → B → D (dead end) → backtrack → B (done) → backtrack → A → C → D (already visited) → done

DFS order: A, B, D, C

BFS (Breadth-First Search): Visit all neighbors before going deeper. Uses a queue.

Start at A:
Visit A. Enqueue neighbors: B, C
Visit B (dequeue). Enqueue neighbor: D
Visit C (dequeue). D already queued.
Visit D (dequeue).

BFS order: A, B, C, D

Comparison:

Property	DFS	BFS
Data structure	Stack / recursion	Queue
Explores	Depth first (goes deep)	Breadth first (goes wide)
Finds shortest path?	No	Yes (in unweighted graphs)

---

🤔 Think First — Section 4.3 Questions

Q4.3.1: Draw the adjacency matrix for this directed graph:

    1 → 2
    ↑   ↓
    4 ← 3

Q4.3.2: For an undirected graph with 5 nodes and the following adjacency list, how many edges does the graph have?

0: [1, 2]
1: [0, 2, 3]
2: [0, 1]
3: [1, 4]
4: [3]

Q4.3.3: Is the adjacency matrix of an undirected graph always symmetric? What about a directed graph?

(Answers at the end of Chapter 4)

---

Chapter 4 — Answers to "Think First" Questions

Section 4.1 Answers

A4.1.1: Tree:

        10
       /  \
      5    15
     / \     \
    3   7     20

• Pre-order (Root→L→R): 10, 5, 3, 7, 15, 20
• In-order (L→Root→R): 3, 5, 7, 10, 15, 20 ← Sorted! (It's a BST)
• Post-order (L→R→Root): 3, 7, 5, 20, 15, 10

A4.1.2: Insert [4, 2, 6, 1, 3, 5, 7]:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

This is a perfect binary tree! In-order: 1, 2, 3, 4, 5, 6, 7 ✓

A4.1.3: NOT a valid BST.

      5
     / \
    3   8
   / \
  2   6     ← 6 is in the LEFT subtree of 5, but 6 > 5!

Node 6 is a right child of node 3 (valid: 6 > 3), but it's in the left subtree of node 5. The BST property requires ALL values in the left subtree of 5 to be < 5. Since 6 > 5, this violates the BST property. Invalid.

---

Section 4.2 Answers

A4.2.1:

• Push 5, 10, 15, 20 → Stack: [20, 15, 10, 5] (20 on top)
• Pop → 20. Stack: [15, 10, 5]
• Pop → 15. Stack: [10, 5]

Popped values: 20, 15. Remaining: [10, 5] (10 on top).

A4.2.2:

• Enqueue A, B, C, D → Queue: [A, B, C, D] (A at front)
• Dequeue → A. Queue: [B, C, D]
• Dequeue → B. Queue: [C, D]

Dequeued values: A, B. Remaining: [C, D] (C at front).

A4.2.3: Trace for "(())()":

Char	Action	Stack
(	push	[(]
(	push	[(, (]
)	pop ( ✓	[(]
)	pop ( ✓	[]
(	push	[(]
)	pop ( ✓	[]

Stack empty at end → Yes, balanced! ✓

---

Section 4.3 Answers

A4.3.1: Directed graph:

    1 → 2
    ↑   ↓
    4 ← 3

	1	2	3	4
1	0	1	0	0
2	0	0	1	0
3	0	0	0	1
4	1	0	0	0

A4.3.2: In an undirected graph, each edge appears twice in the adjacency list (once for each endpoint).

Total entries in all lists: 2 + 3 + 2 + 2 + 1 = 10

Number of edges = 10 / 2 = 5 edges.

A4.3.3:

• Undirected: Yes, always symmetric. If there's an edge between A and B, then M[A][B] = 1 AND M[B][A] = 1.
• Directed: Not necessarily symmetric. A→B doesn't imply B→A.

---

---

Chapter 5: Exam Strategy & Practice

Goal: Consolidate everything you've learned, learn exam techniques, and test yourself with a comprehensive practice set.

---

5.1 What NOT to Study

Save your time. These topics are not tested on the CMI M.Sc. Data Science entrance (Programming & Algorithms section):

Topic	Why it's NOT relevant
Language-Specific Syntax (Python's pandas/numpy, C++ STL)	The exam uses pseudo-code, not real programming languages
Object-Oriented Programming (classes, inheritance, polymorphism)	No class design questions
Advanced Data Structures (AVL trees, Red-Black trees, Trie, Segment trees)	These are for competitive programming
Complex Graph Algorithms (Dijkstra's, Kruskal's, Prim's, Bellman-Ford)	Too advanced for this exam format
Software Engineering (web dev, databases, SQL, APIs, system design)	Completely out of scope
Machine Learning / Statistics	Tested in a separate section, not programming

---

5.2 The Trace Table Technique — Mastery

This is the #1 exam skill. Here is the complete method, refined:

Step-by-Step Method

1. Read the entire pseudo-code once without tracing. Understand the structure (how many loops, any conditions).
2. Identify all variables. Create one column per variable in your trace table.
3. Write initial values in the first row.
4. Execute line by line. For each line:
   • If it's an assignment: update the variable in your table.
   • If it's a condition (if): evaluate to true/false and note which branch executes.
   • If it's a loop start: note the iterator's initial value.
5. Each iteration gets its own row. Clearly mark when a loop iteration ends.
6. When the loop ends, read the final values to determine the output.

Full Worked Example

Problem: What does this code print?

function mystery(A, n):
    x = 0
    y = 0
    for i = 0 to n-1:
        if A[i] > 0:
            x = x + A[i]
        else:
            y = y + A[i]
    print(x + y)

Input: A = [3, -1, 4, -2, 5], n = 5

Trace Table:

i	A[i]	A[i] > 0?	x	y
(init)	—	—	0	0
0	3	Yes	3	0
1	-1	No	3	-1
2	4	Yes	7	-1
3	-2	No	7	-3
4	5	Yes	12	-3

Output: x + y = 12 + (-3) = 9

But wait — pattern recognition! The function adds all positive numbers to x and all negative numbers to y. So x + y is just the sum of all elements! (3 + (-1) + 4 + (-2) + 5 = 9 ✓)

---

5.3 Pattern Recognition Cheat-Sheet

When you see pseudo-code on the exam, match it to one of these known patterns:

Code Pattern	What It Does	Algorithm
x % 10 and x // 10 in a loop	Extracts digits one by one	Digit manipulation (sum digits, reverse number)
x = x + A[i], then if m < x: m = x	Tracks running sum and best-so-far	Kadane's Algorithm (max subarray)
result = result ^ A[i] in a loop	XOR all elements	Find unique element (unpaired)
l, r, m with halving	Binary search pattern	Binary Search
Nested loops comparing A[j] vs A[j+1], swapping	Adjacent comparison + swap	Bubble Sort
min_idx updated in inner loop, one swap at end	Find minimum, place in position	Selection Sort
key = A[i], shift elements right	Insert into sorted portion	Insertion Sort
Function calls itself with n-1 or n//2	Reduce problem size	Recursion
Triple nested loop over matrices	Matrix operation	Matrix multiplication
Compare A[i][j] with A[j][i]	Check symmetry	Symmetric matrix check
n & 1 or n % 2	Check odd/even	Parity check
1 << k	Compute 2^k	Power of 2 via bit shift

---

5.4 Final Mixed Practice Set (10 Questions)

Test yourself across all chapters. Attempt each question on paper before checking the answers.

---

Q1 (Variables & Operators): What is the output?

a = 17
b = a % 5
c = a // 5
print(b * c)

---

Q2 (Loops & Tracing): What value is printed?

s = 0
for i = 1 to 100:
    if i % 3 == 0 and i % 5 == 0:
        s = s + 1
print(s)

---

Q3 (Bitwise): Compute 25 ^ 30 (XOR). Show the binary work.

---

Q4 (Binary Search): How many iterations does binary search take to find key = 5 inA = [1, 3, 5, 7, 9, 11, 13]? Show the trace.

---

Q5 (Sorting): After 2 complete passes of Bubble Sort on A = [6, 3, 8, 2, 5], what is the array?

---

Q6 (Kadane's): Trace Kadane's on A = [1, -2, 3, 4, -1, 2]. What is the maximum subarray sum?

---

Q7 (Recursion): What does g(5) return?

function g(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return g(n-1) + g(n-2)

---

Q8 (Combinatorics): How many structurally distinct binary trees can be formed with 4 nodes?

---

Q9 (BST): Insert the sequence [10, 5, 15, 3, 7, 12, 20] into a BST. What is the in-order traversal?

---

Q10 (Graphs & Matrices): Given this adjacency matrix, draw the graph and state whether it is directed or undirected.

    A  B  C  D
A [ 0  1  0  1 ]
B [ 1  0  1  0 ]
C [ 0  1  0  1 ]
D [ 1  0  1  0 ]

---

5.5 Final Practice Answers

A1:

• b = 17 % 5 = 2 (remainder of 17 ÷ 5)
• c = 17 // 5 = 3 (integer division)
• print(b * c) = print(2 * 3) = 6

---

A2: We need to count numbers from 1 to 100 that are divisible by both 3 and 5. A number divisible by both 3 and 5 is divisible by 15.

Multiples of 15 in [1, 100]: 15, 30, 45, 60, 75, 90 → s = 6

---

A3: Convert to binary:

  11001   (25)
^ 11110   (30)
-------
  00111   (7)

Answer: 7

Verification: 25 = 16+8+1, 30 = 16+8+4+2

• Bit 4 (16): 1^1 = 0
• Bit 3 (8): 1^1 = 0
• Bit 2 (4): 0^1 = 1
• Bit 1 (2): 0^1 = 1
• Bit 0 (1): 1^0 = 1 Result: 4+2+1 = 7 ✓

---

A4: A = [1, 3, 5, 7, 9, 11, 13] (indices 0–6), key = 5:

Iter	l	r	m	A[m]	Action
1	0	6	3	7	7 > 5 → r = 2
2	0	2	1	3	3 < 5 → l = 2
3	2	2	2	5	5 == 5 → Found!

3 iterations.

---

A5: Bubble Sort on A = [6, 3, 8, 2, 5]:

Pass 1: (6,3)→swap→[3,6,8,2,5], (6,8)→no, (8,2)→swap→[3,6,2,8,5], (8,5)→swap→[3,6,2,5,8]

Pass 2: (3,6)→no, (6,2)→swap→[3,2,6,5,8], (6,5)→swap→[3,2,5,6,8]

After 2 passes: [3, 2, 5, 6, 8]

---

A6: A = [1, -2, 3, 4, -1, 2]:

i	A[i]	x + A[i]	A[i]	x	m
start	—	—	—	1	1
1	-2	-1	-2	-1	1
2	3	1	3	3	3
3	4	7	4	7	7
4	-1	6	-1	6	7
5	2	8	2	8	8

Maximum subarray sum: 8 (subarray [3, 4, -1, 2])

Verify: 3 + 4 + (-1) + 2 = 8 ✓

---

A7: This is the Fibonacci function!

• g(0) = 0
• g(1) = 1
• g(2) = g(1) + g(0) = 1
• g(3) = g(2) + g(1) = 2
• g(4) = g(3) + g(2) = 3
• g(5) = g(4) + g(3) = 5

---

A8: Use Catalan number formula:

$$C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \times 70 = \mathbf{14}$$

14 structurally distinct binary trees with 4 nodes.

---

A9: Insert [10, 5, 15, 3, 7, 12, 20]:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

In-order traversal: 3, 5, 7, 10, 12, 15, 20 ← Sorted! ✓

---

A10: The matrix is symmetric (M[i][j] = M[j][i] for all i,j), so the graph is undirected.

    A --- B
    |     |
    D --- C

Edges: (A,B), (A,D), (B,C), (C,D) — a 4-node cycle.

---

---

🎯 You've Completed the Guided Study!

Congratulations. If you've worked through every example and every question in this guide, you have covered the full scope of what the CMI M.Sc. Data Science entrance exam tests in Programming & Algorithms.

Your next steps:

1. Re-attempt any questions you got wrong without looking at the answer.
2. Practice past papers using the Trace Table Technique.
3. Use the Pattern Recognition Cheat-Sheet (Section 5.3) during revision.
4. Time yourself — aim to solve tracing questions in under 5 minutes each.

Remember: The exam doesn't test coding ability. It tests logical patience, mathematical maturity, and the ability to mentally execute algorithms. You have all the tools now. 💪