Reading and Interpreting Pseudocode

Overview

In the dynamic and rapidly evolving field of data science, effective algorithm design and clear communication are paramount. This chapter, "Reading and Interpreting Pseudocode," serves as your foundational guide to mastering pseudocode – a powerful, language-agnostic tool for expressing computational logic. You will learn to decipher and comprehend various pseudocode notations, bridging the gap between abstract algorithmic ideas and their concrete implementation. This skill is not about writing code, but about deeply understanding the how and why behind computational processes.

For your CMI Masters in Data Science, proficiency in pseudocode is not merely beneficial; it is essential. CMI examinations frequently employ pseudocode to assess your understanding of fundamental algorithms, data structures, and computational processes, requiring you to interpret logic without the distraction of specific programming language syntax. Beyond exams, data scientists regularly encounter pseudocode when researching new algorithms, collaborating on model designs, or explaining complex logic to diverse teams. This chapter ensures you can confidently read, understand, and critically evaluate any algorithm presented in pseudocode, equipping you with a crucial skill for both academic success and professional practice in data science.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Core Pseudocode Constructs | Identify variables, loops, conditionals, and functions. |

---

Learning Objectives

---

Now let's begin with Core Pseudocode Constructs...

Part 1: Core Pseudocode Constructs

Introduction

Pseudocode is a fundamental tool in algorithmic thinking, serving as an intermediate step between problem understanding and actual code implementation. For the CMI exam, particularly in a Masters in Data Science context, proficiency in reading, interpreting, and analyzing pseudocode is crucial. It tests your ability to understand complex logic, trace execution, identify algorithmic patterns, and predict outcomes without getting bogged down by the specifics of a particular programming language. This chapter provides a comprehensive guide to core pseudocode constructs, focusing on the structures and techniques frequently encountered in CMI examinations. Mastering these concepts will enable you to dissect any given algorithm, evaluate its behavior, and solve related problems efficiently.

---

Key Concepts

#
## 1. Variables and Basic Operations

Variables are named storage locations used to hold data. Pseudocode typically implies variable declaration upon first assignment or use, without requiring explicit type declarations unless specified (e.g., `int i`). Basic operations include assignment, arithmetic, comparison, and logical operations.

Variable Assignment:
Assigns a value to a variable.
`variable = value` or `variable := value`

Arithmetic Operations:
Standard mathematical operations.
`+` (addition), `-` (subtraction), `*` (multiplication), `/` (division), `//` (integer division), `%` (modulo/remainder).

Comparison Operators:
Used to compare values, resulting in a boolean (`True`/`False`) outcome.
`==` (equal to), `!=` (not equal to), `<` (less than), `>` (greater than), `<=` (less than or equal to), `>=` (greater than or equal to).

Logical Operators:
Combine boolean expressions.
`and`, `or`, `not`.

Worked Example:

Problem: Calculate the result of $(a + b) * c$ where $a=10$, $b=5$, $c=2$, and then check if the result is greater than $20$.

Solution:

Step 1: Initialize variables

Step 2: Perform the arithmetic calculation

Step 3: Evaluate the conditional statement

Answer: $result = 30$, $is\_greater\_than\_20 = \text{True}$

---

#
## 2. Conditional Statements

Conditional statements allow an algorithm to execute different blocks of code based on whether a condition evaluates to `True` or `False`. The most common forms are `if-else` and `if-else if-else`.

Syntax:

```pseudocode
if condition {
// Code to execute if condition is True
} else {
// Code to execute if condition is False
}
```

```pseudocode
if condition1 {
// Code if condition1 is True
} else if condition2 {
// Code if condition1 is False and condition2 is True
} else {
// Code if all preceding conditions are False
}
```

Worked Example:

Problem: Determine if a given integer `num` is positive, negative, or zero.

Solution:

Step 1: Define the input number

Step 2: Check the first condition
```pseudocode
if num > 0 {
// num is positive
} else if num < 0 {
// num is negative
} else {
// num is zero
}
```

Step 3: Trace execution for $num = -7$
The condition $num > 0$ ($-7 > 0$) is \text{False}.
The condition $num < 0$ ($-7 < 0$) is \text{True}.
The code inside the `else if` block will execute.

Answer: `num` is negative.

---

#
## 3. Loop Structures

Loops allow a block of code to be executed repeatedly. Understanding loop bounds, termination conditions, and how variables change within loops is critical.

#
### 3.1. For Loops

`for` loops are used for iterating over a sequence (e.g., a range of numbers, elements in an array).

Syntax:

```pseudocode
for variable from start to end {
// Code to repeat
}
```
(Inclusive of `start` and `end`)

```pseudocode
for variable from start to (end-1) {
// Code to repeat (often used for 0-indexed arrays)
}
```

Worked Example:

Problem: Calculate the sum of all elements in an array $A$ of size $n$, indexed from $0$.

Solution:

Step 1: Initialize array and sum

Step 2: Iterate through the array using a `for` loop
```pseudocode
for i from 0 to (n-1) {
total_sum = total_sum + A[i];
}
```

Step 3: Trace the loop execution
* $i=0$: $total\_sum = 0 + A[0] = 0 + 10 = 10$
* $i=1$: $total\_sum = 10 + A[1] = 10 + 20 = 30$
* $i=2$: $total\_sum = 30 + A[2] = 30 + 30 = 60$
* $i=3$: $total\_sum = 60 + A[3] = 60 + 40 = 100$

Answer: $total\_sum = 100$

---

#
### 3.2. While Loops

`while` loops continue to execute a block of code as long as a specified condition remains `True`. It's crucial to ensure the condition eventually becomes `False` to avoid infinite loops.

Syntax:

```pseudocode
while condition {
// Code to repeat
// Must contain a statement that eventually makes 'condition' False
}
```

Worked Example:

Problem: Count how many times a number $n$ can be divided by $2$ before it becomes $0$ or less.

Solution:

Step 1: Initialize variables

Step 2: Loop while $n$ is greater than $0$
```pseudocode
while n > 0 {
n = n // 2; // Integer division
count = count + 1;
}
```

Step 3: Trace the loop execution
* Initial: $n=25, count=0$
* Iter 1: $n=25 > 0$ is \text{True}. $n = 25 // 2 = 12$. $count = 1$.
* Iter 2: $n=12 > 0$ is \text{True}. $n = 12 // 2 = 6$. $count = 2$.
* Iter 3: $n=6 > 0$ is \text{True}. $n = 6 // 2 = 3$. $count = 3$.
* Iter 4: $n=3 > 0$ is \text{True}. $n = 3 // 2 = 1$. $count = 4$.
* Iter 5: $n=1 > 0$ is \text{True}. $n = 1 // 2 = 0$. $count = 5$.
* Iter 6: $n=0 > 0$ is \text{False}. Loop terminates.

Answer: $count = 5$

---

#
### 3.3. Repeat-Until Loops

A `repeat-until` loop is similar to a `while` loop, but the condition is checked after the loop body executes at least once. The loop continues `until` the condition becomes `True`.

Syntax:

```pseudocode
repeat {
// Code to repeat
// Must contain a statement that eventually makes 'condition' True
} until condition
```

Worked Example:

Problem: Simulate a game where a player rolls a die repeatedly until they roll a $6$. Count the number of rolls. (Assume `roll_die()` is a function that returns a random integer from $1$ to $6$).

Solution:

Step 1: Initialize variables

Step 2: Loop until `die_roll` is $6$
```pseudocode
repeat {
rolls = rolls + 1;
die_roll = roll_die(); // For tracing, let's assume rolls: 4, 1, 5, 6
} until die_roll == 6
```

Step 3: Trace the loop execution (assuming `roll_die()` returns $4$, then $1$, then $5$, then $6$)
* Initial: $rolls=0, die\_roll=0$
* Iter 1: $rolls=1$. $die\_roll=4$. $die\_roll == 6$ is \text{False}.
* Iter 2: $rolls=2$. $die\_roll=1$. $die\_roll == 6$ is \text{False}.
* Iter 3: $rolls=3$. $die\_roll=5$. $die\_roll == 6$ is \text{False}.
* Iter 4: $rolls=4$. $die\_roll=6$. $die\_roll == 6$ is \text{True}. Loop terminates.

Answer: $rolls = 4$

---

#
## 4. Functions and Recursion

Functions are reusable blocks of code that perform a specific task. Recursion is a special case where a function calls itself to solve a problem.

#
### 4.1. Function Definition and Calls

Functions accept input parameters (arguments) and can return a value.

Syntax:

```pseudocode
function functionName(param1, param2) {
// Function body
return result;
}

// Function call
variable = functionName(arg1, arg2);
```

Worked Example:

Problem: Create a function that takes two numbers and returns their product.

Solution:

Step 1: Define the function
```pseudocode
function multiply(a, b) {
product = a * b;
return product;
}
```

Step 2: Call the function

Step 3: Trace execution
* `multiply(7, 8)` is called.
* Inside `multiply`: $a=7, b=8$.
$product = 7$ 8 = 56.
* `return 56`.
* $result$ receives $56$.

Answer: $result = 56$

---

#
### 4.2. Recursion

A recursive function solves a problem by calling itself with smaller instances of the same problem until a base case is reached. A base case is a condition where the function can return a result directly without further recursion.

Worked Example:

Problem: Calculate the factorial of a non-negative integer $n$ using recursion. Recall $n! = n \times (n-1)!$ and $0! = 1$.

Solution:

Step 1: Define the recursive function with a base case
```pseudocode
function factorial(n) {
if n == 0 {
return 1; // Base case
} else {
return n * factorial(n - 1); // Recursive step
}
}
```

Step 2: Call the function

Step 3: Trace the recursive calls
* `factorial(4)`
`return 4 factorial(3)`
* `factorial(3)`
`return 3 factorial(2)`
* `factorial(2)`
`return 2 factorial(1)`
* `factorial(1)`
`return 1 factorial(0)`
* `factorial(0)` returns $1$ (base case)
`return 1 1 = 1`
`return 2 1 = 2`
`return 3 2 = 6`
`return 4 6 = 24`

Answer: $result = 24$

---

#
## 5. Arrays and String Manipulation

Arrays are ordered collections of elements. Strings are sequences of characters. Pseudocode often provides implicit functions for common operations.

#
### 5.1. Array Access and Traversal

Elements in an array are accessed using an index. Traversal involves visiting each element, usually with a loop.

Syntax:
$A[index]$ to access the element at `index`.

Worked Example:

Problem: Find the maximum element in an array $A$ of size $n$, indexed from $0$.

Solution:

Step 1: Initialize array and variables

Step 2: Iterate from the second element to compare with `max_val`
```pseudocode
for i from 1 to (n-1) {
if A[i] > max_val {
max_val = A[i];
}
}
```

Step 3: Trace the loop execution
* Initial: $max\_val = A[0] = 3$
* $i=1$: $A[1]=1$. $1 > 3$ is \text{False}. $max\_val$ remains $3$.
* $i=2$: $A[2]=8$. $8 > 3$ is \text{True}. $max\_val = 8$.
* $i=3$: $A[3]=4$. $4 > 8$ is \text{False}. $max\_val$ remains $8$.
* $i=4$: $A[4]=6$. $6 > 8$ is \text{False}. $max\_val$ remains $8$.

Answer: $max\_val = 8$

---

#
### 5.2. String Operations

Pseudocode often assumes availability of standard string operations like `length()`, `append()`, `trim()`, and `reverse()`.

Common String Functions:
* `length(str)`: Returns the number of characters in `str`.
* `append(str1, str2)`: Concatenates `str1` and `str2`.
* `trim(str)`: Removes leading/trailing whitespace.
* `reverse(str, i, j)`: Reverses the substring of `str` from index $i$ to $j$.
* `str[i]`: Accesses the character at index $i$.

Worked Example:

Problem: Reverse a given string $S$ and then concatenate it with its original form.

Solution:

Step 1: Initialize string

Step 2: Reverse the string
```pseudocode
reversed_S = "";
for i from (length(S)-1) down to 0 {
reversed_S = append(reversed_S, S[i]);
}
```
(Assuming `append` adds character to string, or a direct `reverse(S, 0, length(S)-1)` function exists)

Step 3: Concatenate the original and reversed strings

Step 4: Trace execution
* $S = \text{"hello"}$
* Loop for `reversed_S`:
* $i=4$: `reversed_S = "o"`
* $i=3$: `reversed_S = "ol"`
* $i=2$: `reversed_S = "oll"`
* $i=1$: `reversed_S = "olle"`
* $i=0$: `reversed_S = "olleh"`
* $final\_string = \operatorname{append}(\text{"hello"}, \text{"olleh"}) = \text{"helloolleh"}$

Answer: $final\_string = \text{"helloolleh"}$

---

#
## 6. Mathematical and Bitwise Operations

Beyond basic arithmetic, CMI pseudocode can include specialized mathematical functions and bitwise operations.

#
### 6.1. Integer Division and Modulo

These operations are crucial for digit manipulation, parity checks, and cyclic algorithms.

Worked Example:

Problem: Reverse the digits of a positive integer $num$.

Solution:

Step 1: Initialize variables

Step 2: Use a `while` loop with modulo and integer division
```pseudocode
while num > 0 {
digit = num % 10;
reversed_num = (reversed_num * 10) + digit;
num = num // 10;
}
```

Step 3: Trace the loop execution
* Initial: $num=12345, reversed\_num=0$
Iter 1: $digit=5$. $reversed\_num=(0$10)+5=5. $num=1234$.
Iter 2: $digit=4$. $reversed\_num=(5$10)+4=54. $num=123$.
Iter 3: $digit=3$. $reversed\_num=(54$10)+3=543. $num=12$.
Iter 4: $digit=2$. $reversed\_num=(543$10)+2=5432. $num=1$.
Iter 5: $digit=1$. $reversed\_num=(5432$10)+1=54321. $num=0$.
* Loop terminates.

Answer: $reversed\_num = 54321$

---

#
### 6.2. Absolute Value and Ceiling

Standard mathematical functions:
* `abs(x)`: Returns the absolute value of $x$ (i.e., $|x|$).
* `ceil(x)`: Returns the smallest integer greater than or equal to $x$ (i.e., $\lceil x \rceil$).

Worked Example:

Problem: Find the absolute difference between two numbers, and then round up the average of these two numbers.

Solution:

Step 1: Initialize numbers

Step 2: Calculate absolute difference

Step 3: Calculate average and ceiling

Step 4: Trace execution
* $diff = \operatorname{abs}(15 - 7) = \operatorname{abs}(8) = 8$.
* $average = (15 + 7) / 2 = 22 / 2 = 11$.
* $rounded\_average = \operatorname{ceil}(11) = 11$.

If $a=15, b=6$:
* $diff = \operatorname{abs}(15 - 6) = \operatorname{abs}(9) = 9$.
* $average = (15 + 6) / 2 = 21 / 2 = 10.5$.
* $rounded\_average = \operatorname{ceil}(10.5) = 11$.

Answer: For $a=15, b=7$: $diff=8, rounded\_average=11$.

---

#
### 6.3. Bitwise Exclusive OR

The bitwise Exclusive OR (XOR) operation (`^` or $\oplus$) compares two numbers bit by bit. If corresponding bits are different, the result is $1$; otherwise, it's $0$.

Worked Example:

Problem: Calculate the XOR sum of an array $A = [2, 5, 2, 8, 5]$.

Solution:

Step 1: Initialize array and accumulator

Step 2: Iterate through the array and apply XOR
```pseudocode
for i from 0 to (length(A)-1) {
acc = acc ^ A[i];
}
```

Step 3: Trace the execution
* Initial: $acc = 0$
* $i=0$: $acc = 0 \oplus 2 = 2$
* $i=1$: $acc = 2 \oplus 5 = (010_2 \oplus 101_2) = 111_2 = 7$
* $i=2$: $acc = 7 \oplus 2 = (111_2 \oplus 010_2) = 101_2 = 5$ (Note: $x \oplus x = 0$, so $7 \oplus 2 = (5 \oplus 2) \oplus 2 = 5 \oplus (2 \oplus 2) = 5 \oplus 0 = 5$)
* $i=3$: $acc = 5 \oplus 8 = (0101_2 \oplus 1000_2) = 1101_2 = 13$
* $i=4$: $acc = 13 \oplus 5 = (1101_2 \oplus 0101_2) = 1000_2 = 8$ (Note: $13 \oplus 5 = (8 \oplus 5) \oplus 5 = 8 \oplus (5 \oplus 5) = 8 \oplus 0 = 8$)

Answer: $acc = 8$. The unique element is $8$.

---

#
## 7. Common Algorithmic Patterns

CMI pseudocode problems often combine basic constructs to implement well-known algorithmic patterns.

#
### 7.1. Finding Max/Min/Second Best

This pattern involves iterating through a collection and maintaining variables to track the largest, smallest, or second largest/smallest elements seen so far. Careful handling of edge cases (e.g., small array size, duplicate values) is necessary.

Worked Example:

Problem: Find the second largest distinct element in an array $A$ of size $n$. If no second largest distinct element exists (e.g., all elements are the same), return `None`.

Solution:

Step 1: Handle edge cases for small $n$

```pseudocode
if n < 2 {
return None;
}
```

Step 2: Initialize `first` and `second` with appropriate values. A common robust approach is to initialize `first` to negative infinity and `second` to negative infinity (or the two smallest possible values). Then iterate.

Alternatively, handle the first two elements:
```pseudocode
first = -infinity; // Or a very small number
second = -infinity;

for i from 0 to (n-1) {
if A[i] > first {
second = first;
first = A[i];
} else if (A[i] > second) and (A[i] != first) {
second = A[i];
}
}

if second == -infinity {
return None; // No distinct second largest found
} else {
return second;
}
```

Step 3: Trace execution for $A = [5, 2, 9, 2, 5, 9, 1]$
* Initial: $first = -\infty, second = -\infty$
* $i=0, A[0]=5$: $5 > -\infty$. $second = -\infty, first = 5$.
(Current: $first=5, second=-\infty$)
* $i=1, A[1]=2$: $2 > 5$ is \text{False}. $2 > -\infty$ is \text{True} AND $2 \ne 5$. $second = 2$.
(Current: $first=5, second=2$)
* $i=2, A[2]=9$: $9 > 5$. $second = 5, first = 9$.
(Current: $first=9, second=5$)
* $i=3, A[3]=2$: $2 > 9$ is \text{False}. $2 > 5$ is \text{False}.
(Current: $first=9, second=5$)
* $i=4, A[4]=5$: $5 > 9$ is \text{False}. $5 > 5$ is \text{False}. (Condition $A[i] \ne first$ is important here. If $A[i]=5$ and $first=5$, it shouldn't update `second` to `5` if `second` is already `5`. The $A[i] \ne first$ handles this for distinct values.)
(Current: $first=9, second=5$)
* $i=5, A[5]=9$: $9 > 9$ is \text{False}. $9 > 5$ is \text{True} but $9 \ne 9$ is \text{False}. So no update.
(Current: $first=9, second=5$)
* $i=6, A[6]=1$: $1 > 9$ is \text{False}. $1 > 5$ is \text{False}.
(Current: $first=9, second=5$)

Final check: $second \ne -\infty$. Return $second$.

Answer: $second = 5$

---

#
### 7.2. Counting and Frequency Analysis

This involves using a counter variable or a separate array/data structure to keep track of occurrences or to count elements satisfying certain conditions.

Worked Example:

Problem: Count the number of elements in an array $A$ (indexed from $0$) that are prime numbers. Assume a function `isPrime(num)` exists.

Solution:

Step 1: Initialize array and counter

Step 2: Define `isPrime` function (conceptual)
```pseudocode
function isPrime(num) {
if num <= 1 {
return False;
}
for i from 2 to (sqrt(num)) {
if num % i == 0 {
return False;
}
}
return True;
}
```

Step 3: Iterate through $A$ and check each element
```pseudocode
for i from 0 to (n-1) {
if isPrime(A[i]) == True {
prime_count = prime_count + 1;
}
}
```

Step 4: Trace execution
* Initial: $prime\_count = 0$
* $i=0, A[0]=2$: `isPrime(2)` is \text{True}. $prime\_count = 1$.
* $i=1, A[1]=3$: `isPrime(3)` is \text{True}. $prime\_count = 2$.
* $i=2, A[2]=4$: `isPrime(4)` is \text{False}.
* $i=3, A[3]=5$: `isPrime(5)` is \text{True}. $prime\_count = 3$.
* $i=4, A[4]=6$: `isPrime(6)` is \text{False}.
* $i=5, A[5]=7$: `isPrime(7)` is \text{True}. $prime\_count = 4$.
* $i=6, A[6]=10$: `isPrime(10)` is \text{False}.

Answer: $prime\_count = 4$

---

#
### 7.3. Binary Search

Binary search is an efficient algorithm for finding an element in a sorted array. It repeatedly divides the search interval in half.

Prerequisite: The array must be sorted.

Key Idea:

Find the middle element of the current search interval.

If the middle element is the target, return its index.

If the target is smaller, search in the left half.

If the target is larger, search in the right half.

Worked Example:

Problem: Search for the value `target` in a sorted array $A$ (indexed from $0$) of size $n$ using binary search. Return its index, or $-1$ if not found.

Solution:

Step 1: Initialize array and search parameters

Step 2: Loop while $L \le R$
```pseudocode
function binarySearch(A, n, target) {
L = 0;
R = n - 1;
while L <= R {
m = L + (R - L) // 2; // Calculate middle index using integer division
if A[m] == target {
return m;
} else if A[m] < target {
L = m + 1; // Search right half
} else { // A[m] > target
R = m - 1; // Search left half
}
}
return -1; // Target not found
}
```

Step 3: Trace execution for $target = 50$
* Initial: $L=0, R=6$.
* Iter 1: $L=0, R=6$. $m = 0 + (6-0)//2 = 3$. $A[3]=40$. $40 < 50$. $L = 3+1 = 4$.
(Current: $L=4, R=6$)
* Iter 2: $L=4, R=6$. $m = 4 + (6-4)//2 = 4 + 1 = 5$. $A[5]=60$. $60 > 50$. $R = 5-1 = 4$.
(Current: $L=4, R=4$)
* Iter 3: $L=4, R=4$. $m = 4 + (4-4)//2 = 4$. $A[4]=50$. $50 == 50$. `return 4`.

Answer: Index $4$

---

#
### 7.4. Loop Invariants

A loop invariant is a condition that is true before and after each iteration of a loop. Understanding loop invariants can help you reason about the correctness of an algorithm and predict its state.

Worked Example:

Problem: Consider a loop where $i$ increments, $j$ decrements, and $k$ is supposed to maintain the invariant $k = i + j$. What should be the updates for $k$?

```pseudocode
i = 0;
j = N;
k = 0 + N; // Initial invariant
while i < j {
i = i + 1;
j = j - 1;
// Update k here to maintain k = i + j
}
```

Solution:

Step 1: Initial state

Step 2: Updates to $i$ and $j$

Step 3: What should $k_{new}$ be to maintain the invariant?
We want $k_{new} = i_{new} + j_{new}$.
Substitute the new values:

Since $k_{old} = i_{old} + j_{old}$, we find that $k_{new} = k_{old}$.

This means $k$ does not need to be updated within the loop if its initial value correctly reflects $i+j$.

Answer: No update is needed for $k$ within the loop. The invariant $k = i+j$ is naturally maintained.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the function `calculateValue(p, q)`:\n```pseudocode\nfunction calculateValue(p, q) {\n result = 0;\n while p > 0 {\n if p % 2 == 1 {\n result = result + q;\n }\n p = p // 2;\n q = q 2;\n }\n return result;\n}\n```\nWhat will `calculateValue(13, 5)` return?" options=["35","65","100","130"] answer="65" hint="Trace the values of $p$, $q$, and $result$ through each iteration of the `while` loop, paying attention to integer division and modulo." solution="Let's trace `calculateValue(13, 5)`:\n\nInitial: $p=13, q=5, result=0$\n\nIteration 1:\n- $p > 0$ ($13 > 0$) is \text{True}.\n- $p \% 2 == 1$ ($13 \% 2 == 1$) is \text{True}.\n- $result = result + q$ $\Rightarrow$ $result = 0 + 5 = 5$.\n- $p = p // 2$ $\Rightarrow$ $p = 13 // 2 = 6$.\n- $q = q$ 2 $\Rightarrow$ $q = 5$ 2 = 10q=5∗2=10.\n(Current: $p=6, q=10, result=5$)\n\nIteration 2:\n- $p > 0$ ($6 > 0$) is \text{True}.\n- $p \% 2 == 1$ ($6 \% 2 == 1$) is \text{False}.\n- $p = p // 2$ $\Rightarrow$ $p = 6 // 2 = 3$.\n- $q = q$ 2 $\Rightarrow$ $q = 10$ 2 = 20q=10∗2=20.\n(Current: $p=3, q=20, result=5$)\n\nIteration 3:\n- $p > 0$ ($3 > 0$) is \text{True}.\n- $p \% 2 == 1$ ($3 \% 2 == 1$) is \text{True}.\n- $result = result + q$ $\Rightarrow$ $result = 5 + 20 = 25$.\n- $p = p // 2$ $\Rightarrow$ $p = 3 // 2 = 1$.\n- $q = q$ 2 $\Rightarrow$ $q = 20$ 2 = 40q=20∗2=40.\n(Current: $p=1, q=40, result=25$)\n\nIteration 4:\n- $p > 0$ ($1 > 0$) is \text{True}.\n- $p \% 2 == 1$ ($1 \% 2 == 1$) is \text{True}.\n- $result = result + q$ $\Rightarrow$ $result = 25 + 40 = 65$.\n- $p = p // 2$ $\Rightarrow$ $p = 1 // 2 = 0$.\n- $q = q$ 2 $\Rightarrow$ $q = 40 * 2 = 80$.\n(Current: $p=0, q=80, result=65$)\n\nIteration 5:\n- $p > 0$ ($0 > 0$) is \text{False}. Loop terminates.\n\n`return result` $\Rightarrow$ `return 65`."
:::

:::question type="NAT" question="An array $A$ is indexed from $0$. The function `processArray(A, n)` is defined as:\n```pseudocode\nfunction processArray(A, n) {\n sum_val = 0;\n for i from 0 to (n-1) {\n if A[i] % 2 == 0 {\n sum_val = sum_val + A[i];\n } else {\n sum_val = sum_val - A[i];\n }\n }\n return sum_val;\n}\n```\nIf $A = [1, 4, 3, 8, 5, 2]$ and $n = 6$, what will `processArray(A, 6)` return?" answer="5" hint="Iterate through the array, adding even numbers and subtracting odd numbers from `sum_val`." solution="Let's trace `processArray([1, 4, 3, 8, 5, 2], 6)`:\n\nInitial: $sum\_val = 0$\n\n- $i=0, A[0]=1$: $1 \% 2 == 0$ is \text{False}. $sum\_val = 0 - 1 = -1$.\n- $i=1, A[1]=4$: $4 \% 2 == 0$ is \text{True}. $sum\_val = -1 + 4 = 3$.\n- $i=2, A[2]=3$: $3 \% 2 == 0$ is \text{False}. $sum\_val = 3 - 3 = 0$.\n- $i=3, A[3]=8$: $8 \% 2 == 0$ is \text{True}. $sum\_val = 0 + 8 = 8$.\n- $i=4, A[4]=5$: $5 \% 2 == 0$ is \text{False}. $sum\_val = 8 - 5 = 3$.\n- $i=5, A[5]=2$: $2 \% 2 == 0$ is \text{True}. $sum\_val = 3 + 2 = 5$.\n\nThe loop finishes. `return sum_val` $\Rightarrow$ `return 5`."
:::

:::question type="MSQ" question="Consider the function `modifyArray(A, n)`:\n```pseudocode\nfunction modifyArray(A, n) {\n if n <= 1 {\n return;\n }\n for i from 0 to (n-2) {\n for j from (i+1) to (n-1) {\n if A[i] > A[j] {\n temp = A[i];\n A[i] = A[j];\n A[j] = temp;\n }\n }\n }\n}\n```\nWhich of the following statements are true about `modifyArray`?\n\nA. It sorts the array `A` in ascending order.\nB. It sorts the array `A` in descending order.\nC. After calling `modifyArray([5, 1, 4, 2, 8], 5)`, the array `A` will be `[1, 2, 4, 5, 8]`.\nD. It performs a Bubble Sort algorithm." options=["A","C"] answer="A,C" hint="Analyze the nested loops and the swap condition. What effect does swapping $A[i]$ and $A[j]$ when $A[i] > A[j]$ have over multiple passes?" solution="Let's analyze the `modifyArray` function:\n\n1. Nested Loops: The outer loop runs from $i = 0$ to $n-2$. The inner loop runs from $j = i+1$ to $n-1$. This structure ensures that every pair of elements $(A[i], A[j])$ where $i < j$ is compared exactly once.\n2. Swap Condition: `if A[i] > A[j]` then $A[i]$ and $A[j]$ are swapped. This means that if an element at an earlier index ($i$) is greater than an element at a later index ($j$), they are put in increasing order.\n\nThis is the core logic of Selection Sort or a similar comparison sort that places the smallest element found so far into its correct position. In each outer iteration $i$, the inner loop finds the smallest element in $A[i...n-1]$ and swaps it with $A[i]$. This effectively sorts the array in ascending order.\n\nLet's trace `modifyArray([5, 1, 4, 2, 8], 5)`:\n\nInitial: $A = [5, 1, 4, 2, 8]$\n\n- $i = 0$:\n - $j = 1$: $A[0]=5, A[1]=1$. $5 > 1$ is \text{True}. Swap. $A = [1, 5, 4, 2, 8]$.\n - $j = 2$: $A[0]=1, A[2]=4$. $1 > 4$ is \text{False}.\n - $j = 3$: $A[0]=1, A[3]=2$. $1 > 2$ is \text{False}.\n - $j = 4$: $A[0]=1, A[4]=8$. $1 > 8$ is \text{False}.\n (After $i=0$ loop, $A[0]$ is the smallest element: $A = [1, 5, 4, 2, 8]$)\n\n- $i = 1$:\n - $j = 2$: $A[1]=5, A[2]=4$. $5 > 4$ is \text{True}. Swap. $A = [1, 4, 5, 2, 8]$.\n - $j = 3$: $A[1]=4, A[3]=2$. $4 > 2$ is \text{True}. Swap. $A = [1, 2, 5, 4, 8]$.\n - $j = 4$: $A[1]=2, A[4]=8$. $2 > 8$ is \text{False}.\n (After $i=1$ loop, $A[1]$ is the second smallest element: $A = [1, 2, 5, 4, 8]$)\n\n- $i = 2$:\n - $j = 3$: $A[2]=5, A[3]=4$. $5 > 4$ is \text{True}. Swap. $A = [1, 2, 4, 5, 8]$.\n - $j = 4$: $A[2]=4, A[4]=8$. $4 > 8$ is \text{False}.\n (After $i=2$ loop, $A[2]$ is the third smallest element: $A = [1, 2, 4, 5, 8]$)\n\n- $i = 3$:\n - $j = 4$: $A[3]=5, A[4]=8$. $5 > 8$ is \text{False}.\n (After $i=3$ loop, $A[3]$ is the fourth smallest element: $A = [1, 2, 4, 5, 8]$)\n\nThe outer loop finishes after $i=n-2 = 3$.\n\nFinal array: $[1, 2, 4, 5, 8]$.\n\nTherefore:\n- A. It sorts the array `A` in ascending order. (\text{True})\n- B. It sorts the array `A` in descending order. (\text{False})\n- C. After calling `modifyArray([5, 1, 4, 2, 8], 5)`, the array `A` will be `[1, 2, 4, 5, 8]`. (\text{True})\n- D. It performs a Bubble Sort algorithm. (\text{False} - this is Selection Sort. Bubble Sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.)"
:::

:::question type="SUB" question="Derive the final value of $x$ when `calculateX(8)` is called, where `calculateX(n)` is defined as:\n```pseudocode\nfunction calculateX(n) {\n x = 0;\n while n > 0 {\n if n % 2 == 0 {\n x = x + 1;\n }\n n = n // 2;\n }\n return x;\n}\n```" answer="3" hint="Trace the execution of the `while` loop for $n=8$, updating $n$ and $x$ in each step. The condition $n \% 2 == 0$ checks for even numbers." solution="Let's trace `calculateX(8)`:\n\nInitial: $n=8, x=0$\n\nIteration 1:\n- $n > 0$ ($8 > 0$) is \text{True}.\n- $n \% 2 == 0$ ($8 \% 2 == 0$) is \text{True}.\n- $x = x + 1$ $\Rightarrow$ $x = 0 + 1 = 1$.\n- $n = n // 2$ $\Rightarrow$ $n = 8 // 2 = 4$.\n(Current: $n=4, x=1$)\n\nIteration 2:\n- $n > 0$ ($4 > 0$) is \text{True}.\n- $n \% 2 == 0$ ($4 \% 2 == 0$) is \text{True}.\n- $x = x + 1$ $\Rightarrow$ $x = 1 + 1 = 2$.\n- $n = n // 2$ $\Rightarrow$ $n = 4 // 2 = 2$.\n(Current: $n=2, x=2$)\n\nIteration 3:\n- $n > 0$ ($2 > 0$) is \text{True}.\n- $n \% 2 == 0$ ($2 \% 2 == 0$) is \text{True}.\n- $x = x + 1$ $\Rightarrow$ $x = 2 + 1 = 3$.\n- $n = n // 2$ $\Rightarrow$ $n = 2 // 2 = 1$.\n(Current: $n=1, x=3$)\n\nIteration 4:\n- $n > 0$ ($1 > 0$) is \text{True}.\n- $n \% 2 == 0$ ($1 \% 2 == 0$) is \text{False}.\n- $n = n // 2$ $\Rightarrow$ $n = 1 // 2 = 0$.\n(Current: $n=0, x=3$)\n\nIteration 5:\n- $n > 0$ ($0 > 0$) is \text{False}. Loop terminates.\n\n`return x` $\Rightarrow$ `return 3`.\n\nThe function counts how many times $n$ is even during its repeated integer division by $2$ before it becomes $0$."
:::

:::question type="MCQ" question="What will `mysteryXOR([1, 2, 3, 1, 2], 5)` return?\n```pseudocode\nfunction mysteryXOR(A, n) {\n acc = 0;\n for i from 0 to (n-1) {\n acc = acc ^ A[i];\n }\n return acc;\n}\n```" options=["0","1","2","3","4"] answer="3" hint="Recall the properties of bitwise XOR, especially $x \oplus x = 0$ and $x \oplus 0 = x$. This function effectively finds the single unique element if all others appear an even number of times." solution="Let's trace `mysteryXOR([1, 2, 3, 1, 2], 5)`:\n\nInitial: $acc = 0$\n\n- $i=0, A[0]=1$: $acc = 0 \oplus 1 = 1$.\n- $i=1, A[1]=2$: $acc = 1 \oplus 2 = 3$ (binary $01_2 \oplus 10_2 = 11_2$).\n- $i=2, A[2]=3$: $acc = 3 \oplus 3 = 0$ (binary $11_2 \oplus 11_2 = 00_2$. $x \oplus x = 0$).\n- $i=3, A[3]=1$: $acc = 0 \oplus 1 = 1$.\n- $i=4, A[4]=2$: $acc = 1 \oplus 2 = 3$.\n\nThe loop finishes. `return acc` $\Rightarrow$ `return 3`.\n\nThis function calculates the XOR sum of all elements in the array. Due to the properties of XOR ($x \oplus x = 0$ and $x \oplus 0 = x$), any number that appears an even number of times will effectively cancel itself out in the XOR sum. The result will be the XOR sum of elements that appear an odd number of times.\n\nIn the array `[1, 2, 3, 1, 2]`:\n- $1$ appears twice (even).\n- $2$ appears twice (even).\n- $3$ appears once (odd).\n\nSo, the XOR sum is $1 \oplus 2 \oplus 3 \oplus 1 \oplus 2 = (1 \oplus 1) \oplus (2 \oplus 2) \oplus 3 = 0 \oplus 0 \oplus 3 = 3$."
:::

:::question type="MSQ" question="Consider the function `analyzeArray(A, n)`:\n```pseudocode\nfunction analyzeArray(A, n) {\n if n == 0 {\n return 0;\n }\n max_val = A[0];\n second_max_val = A[0];\n for i from 1 to (n-1) {\n if A[i] > max_val {\n second_max_val = max_val;\n max_val = A[i];\n } else if A[i] > second_max_val {\n second_max_val = A[i];\n }\n }\n return max_val + second_max_val;\n}\n```\nIf $A = [10, 20, 15, 20, 5]$ and $n = 5$, which of the following statements are true?\n\nA. The function `analyzeArray` correctly finds the sum of the largest and second largest distinct elements.\nB. The function `analyzeArray` will return `40` for the given input.\nC. If $A = [7, 7, 7, 7]$, the function will return `14`.\nD. The function assumes all elements are positive." options=["B","C"] answer="B,C" hint="Trace the execution carefully for the given input. Pay attention to how `max_val` and `second_max_val` are updated, especially with duplicate largest values." solution="Let's trace `analyzeArray([10, 20, 15, 20, 5], 5)`:\n\nInitial: $A = [10, 20, 15, 20, 5], n = 5$\n$max\_val = A[0] = 10$\n$second\_max\_val = A[0] = 10$\n\nLoop for $i$ from $1$ to $4$:\n\n- $i = 1, A[1] = 20$:\n - $A[1] > max\_val$ ($20 > 10$) is \text{True}.\n - $second\_max\_val = max\_val$ $\Rightarrow$ $second\_max\_val = 10$.\n - $max\_val = A[1]$ $\Rightarrow$ $max\_val = 20$.\n (Current: $max\_val = 20, second\_max\_val = 10$)\n\n- $i = 2, A[2] = 15$:\n - $A[2] > max\_val$ ($15 > 20$) is \text{False}.\n - $A[2] > second\_max\_val$ ($15 > 10$) is \text{True}.\n - $second\_max\_val = A[2]$ $\Rightarrow$ $second\_max\_val = 15$.\n (Current: $max\_val = 20, second\_max\_val = 15$)\n\n- $i = 3, A[3] = 20$:\n - $A[3] > max\_val$ ($20 > 20$) is \text{False}.\n - $A[3] > second\_max\_val$ ($20 > 15$) is \text{True}.\n - $second\_max\_val = A[3]$ $\Rightarrow$ $second\_max\_val = 20$.\n (Current: $max\_val = 20, second\_max\_val = 20$)\n\n- $i = 4, A[4] = 5$:\n - $A[4] > max\_val$ ($5 > 20$) is \text{False}.\n - $A[4] > second\_max\_val$ ($5 > 20$) is \text{False}.\n (Current: $max\_val = 20, second\_max\_val = 20$)\n\nLoop ends.\n\n`return max_val + second_max_val` $\Rightarrow$ `return 20 + 20 = 40`.\n\nNow evaluate the options:\n\nA. The function `analyzeArray` correctly finds the sum of the largest and second largest distinct elements.\n - For `[10, 20, 15, 20, 5]`, the largest is $20$, the second largest distinct is $15$. The sum should be $20+15=35$. The function returns $40$ ($20+20$). So, it does not correctly find the sum of distinct elements if the largest element appears multiple times. (\text{False})\n\nB. The function `analyzeArray` will return `40` for the given input.\n - As traced above, it returns $40$. (\text{True})\n\nC. If $A = [7, 7, 7, 7]$, the function will return `14`.\n - Initial: $max\_val = 7, second\_max\_val = 7$.\n - Loop for $i$ from $1$ to $3$:\n - $A[i]$ is always $7$.\n - $A[i] > max\_val$ ($7 > 7$) is \text{False}.\n - $A[i] > second\_max\_val$ ($7 > 7$) is \text{False}.\n - $max\_val$ and $second\_max\_val$ remain $7$.\n - `return max_val + second_max_val` $\Rightarrow$ `return 7 + 7 = 14`. (\text{True})\n\nD. The function assumes all elements are positive.\n - The initialization `max_val = A[0]; second_max_val = A[0];` works for negative numbers too. The comparisons `A[i] > max_val` and `A[i] > second_max_val` are valid for any numerical values. So, it does not assume all elements are positive. (\text{False})\n\nTherefore, statements B and C are true."
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the following pseudocode:
```pseudocode
DECLARE x : INTEGER
DECLARE y : INTEGER
x <- 10
y <- 5
IF x > y THEN
FOR i FROM 1 TO y STEP 1
x <- x - 1
ENDFOR
ELSE
WHILE y > 0
x <- x + 1
y <- y - 1
ENDWHILE
ENDIF
PRINT x
```
What is the final value of $x$ printed by the pseudocode?" options=["5","10","15","20"] answer="5" hint="Carefully trace the execution of the FOR loop when the IF condition is met. Keep track of the value of $x$ in each iteration." solution="Initially, $x = 10$ and $y = 5$.
The condition $x > y$ ($10 > 5$) is \text{true}.
The code enters the `IF` block and executes the `FOR` loop.
The `FOR` loop iterates from $i = 1$ to $y$ (which is $5$).
In each iteration, $x$ is decremented by $1$.

• $i=1: x = 10 - 1 = 9$


• $i=2: x = 9 - 1 = 8$


• $i=3: x = 8 - 1 = 7$


• $i=4: x = 7 - 1 = 6$


• $i=5: x = 6 - 1 = 5$

After the loop, the `IF` block finishes, and the `PRINT x` statement is executed.
The final value of $x$ is $5$."
:::

:::question type="NAT" question="Consider the following pseudocode:
```pseudocode
FUNCTION CalculateValue(a : INTEGER, b : INTEGER) RETURNS INTEGER
IF a MOD 2 = 0 THEN
RETURN a * b
ELSE
RETURN a + b
ENDIF
ENDFUNCTION

DECLARE p : INTEGER
DECLARE q : INTEGER
p <- 3
q <- 4
p <- CalculateValue(q, p)
q <- CalculateValue(p, 2)
PRINT q
```
What is the final value of $q$ printed by the pseudocode?" answer="24" hint="Trace the values of $p$ and $q$ carefully through each function call. Remember that the `CalculateValue` function takes two parameters and returns a value based on whether the first parameter is even or odd." solution="Initially, $p = 3$ and $q = 4$.

`p <- CalculateValue(q, p)`:

This calls $\operatorname{CalculateValue}(4, 3)$.
Inside the function: $a = 4$, $b = 3$.
The condition $a \text{ MOD } 2 = 0$ ($4 \text{ MOD } 2 = 0$) is \text{true}.
The function returns $a$ b = 4 3 = 12.
So, $p$ is updated to $12$. Current state: $p = 12$, $q = 4$.

`q <- CalculateValue(p, 2)`:

This calls $\operatorname{CalculateValue}(12, 2)$.
Inside the function: $a = 12$, $b = 2$.
The condition $a \text{ MOD } 2 = 0$ ($12 \text{ MOD } 2 = 0$) is \text{true}.
The function returns $a$ b = 12 2 = 24.
So, $q$ is updated to $24$. Current state: $p = 12$, $q = 24$.

Finally, `PRINT q` will output $24$.
The final value of $q$ is $24$."
:::

:::question type="MCQ" question="Consider the following pseudocode:
```pseudocode
DECLARE numbers : ARRAY[0:3] OF INTEGER
numbers[0] <- 20
numbers[1] <- 20
numbers[2] <- 30
numbers[3] <- 40

DECLARE result : INTEGER
result <- 0
FOR i FROM 0 TO 2 STEP 1
IF numbers[i] MOD 20 = 0 THEN
result <- result + numbers[i+1]
ENDIF
ENDFOR
PRINT result
```
What is the final value of `result` printed by the pseudocode?" options=["20","50","70","90"] answer="50" hint="Pay close attention to the array indexing $numbers[i+1]$ inside the loop and the condition for adding to `result`." solution="Initially, $numbers = [20, 20, 30, 40]$ and $result = 0$.
The `FOR` loop iterates with $i$ from $0$ to $2$.

• $i=0$:

$numbers[0]$ is $20$. The condition $numbers[0] \text{ MOD } 20 = 0$ ($20 \text{ MOD } 20 = 0$) is \text{true}. $result <- result + numbers[0+1]$ which is $result + numbers[1]$. $result <- 0 + 20 = 20$.

• $i=1$:

$numbers[1]$ is $20$. The condition $numbers[1] \text{ MOD } 20 = 0$ ($20 \text{ MOD } 20 = 0$) is \text{true}. $result <- result + numbers[1+1]$ which is $result + numbers[2]$. $result <- 20 + 30 = 50$.

• $i=2$:

$numbers[2]$ is $30$. The condition $numbers[2] \text{ MOD } 20 = 0$ ($30 \text{ MOD } 20 = 10 \neq 0$) is \text{false}. $result$ remains $50$.

The loop finishes. The final value of $result$ printed is $50$."
:::

:::question type="NAT" question="Consider the following pseudocode:
```pseudocode
FUNCTION ProcessString(inputString : STRING) RETURNS STRING
DECLARE processed : STRING
processed <- ""
DECLARE length : INTEGER
length <- LENGTH(inputString)
FOR i FROM 1 TO length STEP 1
DECLARE char : STRING
char <- SUBSTRING(inputString, i, 1)
IF char = 'A' OR char = 'E' OR char = 'I' OR char = 'O' OR char = 'U' THEN
processed <- processed + '*'
ELSE
processed <- processed + char
ENDIF
ENDFOR
RETURN processed
ENDFUNCTION

DECLARE myString : STRING
myString <- 'COMPUTING'
myString <- ProcessString(myString)
PRINT myString
```
How many '*' characters are in the final `myString` printed by the pseudocode?" answer="3" hint="Trace the `ProcessString` function character by character. Remember that `SUBSTRING(string, start_index, length)` extracts a substring. Assume 1-based indexing for `SUBSTRING` as commonly seen in pseudocode contexts." solution="Initially, `myString = 'COMPUTING'`.
The `ProcessString` function is called with `inputString = 'COMPUTING'`.

Inside `ProcessString`:
`processed` is initialized as `""`.
`length` is $\operatorname{LENGTH}('COMPUTING') = 9$.
The `FOR` loop iterates from $i = 1$ to $9$.

• $i=1$: $char = \operatorname{SUBSTRING}('COMPUTING', 1, 1) = \text{'C'}$. Not a vowel. `processed = "C"`.
• $i=2$: $char = \operatorname{SUBSTRING}('COMPUTING', 2, 1) = \text{'O'}$. Is a vowel. `processed = "C*"`.
• $i=3$: $char = \operatorname{SUBSTRING}('COMPUTING', 3, 1) = \text{'M'}$. Not a vowel. `processed = "C*M"`.
• $i=4$: $char = \operatorname{SUBSTRING}('COMPUTING', 4, 1) = \text{'P'}$. Not a vowel. `processed = "C*MP"`.
• $i=5$: $char = \operatorname{SUBSTRING}('COMPUTING', 5, 1) = \text{'U'}$. Is a vowel. `processed = "CMP"`.
• $i=6$: $char = \operatorname{SUBSTRING}('COMPUTING', 6, 1) = \text{'T'}$. Not a vowel. `processed = "CMPT"`.
• $i=7$: $char = \operatorname{SUBSTRING}('COMPUTING', 7, 1) = \text{'I'}$. Is a vowel. `processed = "CMPT*"`.
• $i=8$: $char = \operatorname{SUBSTRING}('COMPUTING', 8, 1) = \text{'N'}$. Not a vowel. `processed = "CMPT*N"`.
• $i=9$: $char = \operatorname{SUBSTRING}('COMPUTING', 9, 1) = \text{'G'}$. Not a vowel. `processed = "CMPT*NG"`.

The function returns `CMPT*NG`. `myString` is updated to `CMPT*NG`. `PRINT myString` will output `CMPT*NG`.

Counting the '' characters in `CMPTNG`, we find there are $3$ asterisks.
The final answer is $3$."
:::

---

What's Next?