Computer Science Programming Concepts

B2.1.1 Construct, trace programs with variables (AO3)

B2.1.1_1 Data types: Boolean, char, decimal, integer, string

Example Program

                            # Declare variables with appropriate data types

                            student_name = "Alice"  # String: Stores textual data

                            is_passing = True       # Boolean: True/False for logical conditions

                            grade1 = 85             # Integer: Whole number for grades

                            grade2 = 90

                            weight = 75.5           # Decimal (float): For precise numerical values

                            initial = 'A'           # Char (string of length 1): Single character

                            # Calculate average grade

                            average = (grade1 + grade2) / 2

                            # Output results

                            print(f"Student: {student_name}, Initial: {initial}")

                            print(f"Average Grade: {average}")

                            print(f"Passing: {is_passing}")

              // Declare variables with appropriate data types

              String studentName = "Alice";  // String: textual data

              boolean isPassing = true;       // boolean: true/false

              int grade1 = 85;               // int: whole number

              int grade2 = 90;

              double weight = 75.5;          // double: decimal value

              char initial = 'A';           // char: single character

              // Calculate average grade

              double average = (grade1 + grade2) / 2.0;

              // Output results

              System.out.println("Student: " + studentName + ", Initial: " + initial);

              System.out.println("Average Grade: " + average);

              System.out.println("Passing: " + isPassing);

Tracing the Program

Initialize: student_name = "Alice", is_passing = True, grade1 = 85, grade2 = 90, weight = 75.5, initial = 'A'
Calculate: average = (85 + 90) / 2 = 87.5
Output: Prints "Student: Alice, Initial: A", "Average Grade: 87.5", "Passing: True"

Boolean

Stores True or False for logical conditions
Example: is_passing = grade >= 60

Char

Single character (in Python, a string of length 1)
Example: initial = 'A'

Decimal (Float)

Represents numbers with decimal points
Example: weight = 75.5 for precise measurements

Integer

Whole numbers for counts or discrete values
Example: grade1 = 85

String

Text data for names, descriptions, etc.
Example: student_name = "Alice"

Purpose

Selecting appropriate data types ensures accurate data storage, manipulation, and program functionality
Tracing verifies program logic by tracking variable changes and confirming expected outputs

B2.1.2 Construct programs for substring manipulation (AO3)

B2.1.2_1 Identify, extract, alter, concatenate, replace substrings

Identify

Locate specific substrings using methods like find() or index()
Example: text = "Hello World"; pos = text.find("World") returns 6

Extract

Retrieve a portion using slicing or substring methods
Example: text = "Hello World"; substring = text[6:11] extracts "World"

Alter

Modify parts by creating a new string with changes
Example: text = "hello"; text = text.upper() results in "HELLO"

Concatenate

Combine strings using + operator or join() method
Example: first = "Hello"; last = "World"; full = first + " " + last

Replace

Substitute a substring using replace() method
Example: text = "Hello World"; new_text = text.replace("World", "Python")

Example Program

                            # Program to manipulate a string

                            text = "Welcome to IB Computer Science"

                            # Identify: Find position of substring

                            pos = text.find("Computer")

                            print(f"Position of 'Computer': {pos}")  # Output: 11

                            # Extract: Get substring

                            substring = text[11:19]

                            print(f"Extracted substring: {substring}")  # Output: Computer

                            # Alter: Convert to uppercase

                            upper_text = substring.upper()

                            print(f"Uppercase substring: {upper_text}")  # Output: COMPUTER

                            # Concatenate: Add prefix

                            new_text = "Subject: " + text

                            print(f"Concatenated: {new_text}")  # Output: Subject: Welcome to IB Computer Science

                            # Replace: Change substring

                            replaced_text = text.replace("Computer Science", "Programming")

                            print(f"Replaced text: {replaced_text}")  # Output: Welcome to IB Programming

              // Program to manipulate a string

              String text = "Welcome to IB Computer Science";

              // Identify: Find position of substring

              int pos = text.indexOf("Computer");

              System.out.println("Position of 'Computer': " + pos);  // Output: 14

              // Extract: Get substring

              String substring = text.substring(14, 22);

              System.out.println("Extracted: " + substring);  // Output: Computer

              // Alter: Convert to uppercase

              String upperText = substring.toUpperCase();

              System.out.println("Uppercase: " + upperText);  // Output: COMPUTER

              // Concatenate: Add prefix

              String newText = "Subject: " + text;

              System.out.println("Concatenated: " + newText);

              // Replace: Change substring

              String replacedText = text.replace("Computer Science", "Programming");

              System.out.println("Replaced: " + replacedText);

Construction and Tracing

Construct: Write code to perform substring operations based on requirements
Trace: Step through the code, tracking variable values:
- text = "Welcome to IB Computer Science"
- pos = 14 (from find("Computer"))
- substring = "Computer" (from slicing [14:22])
- upper_text = "COMPUTER" (from upper())
- new_text = "Subject: Welcome to IB Computer Science" (from concatenation)
- replaced_text = "Welcome to IB Programming" (from replace())

Use Case

A program processing email addresses to extract usernames (e.g., user@domain.com → user)
Concatenate with a greeting, and replace domains for standardization
Ensuring correct manipulation through tracing

B2.1.3 Describe exception handling (AO2)

B2.1.3_1 Failure points: unexpected inputs, resource unavailability, logic errors

Unexpected Inputs

Occurs when user data does not match expected format or type
Example: Entering "abc" when expecting an integer
Can cause crashes (e.g., ValueError) or incorrect behavior

Resource Unavailability

Failure due to inaccessible resources (files, databases, network)
Example: Attempting to open a non-existent file
Results in FileNotFoundError, disrupting execution

Logic Errors

Errors in program logic (division by zero, out-of-bounds access)
Example: Dividing by a variable that equals zero
Causes runtime errors or incorrect outputs

B2.1.3_2 Role in program development

Purpose

Exception handling ensures programs gracefully handle errors
Improves robustness and user experience
Prevents crashes by catching and managing errors
Allows programs to recover or fail gracefully

Benefits in Development

Enhances reliability by anticipating and addressing potential failure points
Improves debugging by providing clear error messages and controlled error handling
Supports user-friendly applications by informing users of issues without abrupt termination

Use in Testing

Helps developers identify and handle edge cases during testing
Ensures comprehensive error management
Example: Testing a calculator program for division by zero

B2.1.3_3 Constructs: try/catch (Java), try/except (Python), finally block

Try/Catch (Java)

                                    try {

                                        int result = 10 / 0; // Potential ZeroDivisionError

                                    } catch (ArithmeticException e) {

                                        System.out.println("Error: Division by zero");

                                    }

              try {

                  int result = 10 / 0; // Potential ArithmeticException

              } catch (ArithmeticException e) {

                  System.out.println("Error: Division by zero");

              }

Catches specific exceptions to prevent crashes

Try/Except (Python)

                                    try:

                                        result = 10 / 0  # Potential ZeroDivisionError

                                    except ZeroDivisionError:

                                        print("Error: Division by zero")

              try {

                  int result = 10 / 0;  // Potential ArithmeticException

              } catch (ArithmeticException e) {

                  System.out.println("Error: Division by zero");

              }

Manages runtime errors, allowing program continuation

Finally Block (Java and Python)

                            try:

                                file = open("data.txt", "r")

                                content = file.read()

                            except FileNotFoundError:

                                print("Error: File not found")

                            finally:

                                file.close()  # Ensures file is closed

              import java.io.*;

              BufferedReader reader = null;

              try {

                  reader = new BufferedReader(new FileReader("data.txt"));

                  String content = reader.readLine();

              } catch (FileNotFoundException e) {

                  System.out.println("Error: File not found");

              } finally {

                  if (reader != null) reader.close();  // Ensures reader is closed

              }

Executes code regardless of whether an exception occurs
Often used for cleanup tasks (e.g., closing files)
Ensures resources are properly released, preventing leaks

Use Case

A Python program reading user input for a calculation uses try/except to handle invalid inputs
Finally block logs the operation's completion
Ensures robustness and proper resource management

B2.1.4 Construct, use debugging techniques (AO3)

B2.1.4_1 Techniques: trace tables, breakpoints, print statements, step-by-step execution

Trace Tables

Table tracking variable values at each step
Identifies logic errors or unexpected behavior
Example: For a loop calculating sum:

                                total = 0

                                for i in range(1, 4):

                                    total += i

                                print(total)

              int total = 0;

              for (int i = 1; i <= 3; i++) {

                  total += i;

              }

              System.out.println(total);

Step	i	total
1	1	1
2	2	3
3	3	6

Breakpoints

Pause execution at specific lines to inspect state
Used with debuggers (e.g., Python's pdb, IDEs)
Example: Setting breakpoint at total += i to check values
Pinpoints where errors occur

Print Statements

Insert print() to output variable values
Quick monitoring without debugger
Example:

                                total = 0

                                for i in range(1, 4):

                                    total += i

                                    print(f"i={i}, total={total}")

              int total = 0;

              for (int i = 1; i <= 3; i++) {

                  total += i;

                  System.out.println("i=" + i + ", total=" + total);

              }

Output: i=1, total=1, i=2, total=3, i=3, total=6

Step-by-Step Execution

Execute code line-by-line using debugger
Observe behavior and variable changes in real-time
Tools: pdb, VS Code, PyCharm debuggers
Identifies exact lines where errors occur

Construction and Use

                            # Example: Debug a program to find the maximum number

                            numbers = [4, 7, 2, 9, 1]

                            max_num = numbers[0]

                            for num in numbers:

                                print(f"Checking num={num}, max_num={max_num}")  # Print statement

                                if num > max_num:

                                    max_num = num

                            print(f"Maximum: {max_num}")

              // Debug a program to find the maximum number

              int[] numbers = {4, 7, 2, 9, 1};

              int maxNum = numbers[0];

              for (int num : numbers) {

                  System.out.println("Checking num=" + num + ", maxNum=" + maxNum);  // Print statement

                  if (num > maxNum) {

                      maxNum = num;

                  }

              }

              System.out.println("Maximum: " + maxNum);

Step	num	max_num
1	4	4
2	7	7
3	2	7
4	9	9
5	1	9

B2.2.1 Compare static vs dynamic data structures (AO3)

B2.2.1_1 Memory allocation, resizing mechanisms

Static Data Structures

Memory Allocation

Memory allocated at compile time
Fixed size that cannot change during runtime
Example: numbers = [0] * 5 creates a Python list with 5 elements

Resizing Mechanism

Cannot be resized dynamically
Size is set during declaration
To change size, a new structure must be created and data copied

Dynamic Data Structures

Memory Allocation

Memory allocated at runtime
Flexible size adjustments as needed
Example: numbers = [1, 2, 3]; numbers.append(4) dynamically adds an element

Resizing Mechanism

Automatically resizes when capacity exceeded
Allocates new memory and copies data
Example: Python lists double capacity when full

B2.2.1_2 Pros, cons: speed, memory, flexibility

Aspect	Static Data Structures	Dynamic Data Structures
Speed	Faster access (O(1)) due to contiguous memory and fixed size	Slower due to resizing overhead (O(n) in worst case)
Memory	More efficient, no overhead for resizing	Higher overhead for resizing and extra capacity
Flexibility	Inflexible, fixed size	Highly flexible, grows/shrinks as needed
Use Case	Fixed number of student grades (exactly 10)	Tracking user inputs in a chat application

Static Pros

Faster access due to contiguous memory
Memory-efficient with no overhead

Static Cons

Inflexible size cannot change
Wasted space if not fully utilized

Dynamic Pros

Flexible size adjusts as needed
Easy to use with automatic memory management

Dynamic Cons

Slower due to resizing overhead
Higher memory usage for extra capacity

B2.2.2 Construct programs with arrays, lists (AO3)

B2.2.2_1 1D/2D arrays, ArrayLists (Java)

1D Arrays

Fixed-size, contiguous collection of elements
Accessed by index

                                # 1D array using Python list

                                grades = [85, 90, 78, 92]

                                grades[2] = 80  # Update element

                                print(grades[0])  # Access: 85

              // 1D array

              int[] grades = {85, 90, 78, 92};

              grades[2] = 80;  // Update element

              System.out.println(grades[0]);  // Access: 85

Use: Store sequences like student grades

2D Arrays

Matrix-like structure with rows and columns
Accessed by two indices

                                # 2D array using nested lists

                                matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

                                matrix[1][2] = 10  # Update element

                                print(matrix[0][1])  # Access: 2

              // 2D array

              int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};

              matrix[1][2] = 10;  // Update element

              System.out.println(matrix[0][1]);  // Access: 2

Use: Represent grids, tables, or seating charts

ArrayLists (Java)

Dynamic, resizable list in Java
Part of java.util package

                                import java.util.ArrayList;

                                // Initialize ArrayList

                                ArrayList<Integer> scores = new ArrayList<>();

                                scores.add(85);  // Add element

                                scores.add(90);

                                scores.set(1, 95);  // Update element

                                System.out.println(scores.get(0));  // Access: 85

              import java.util.ArrayList;

              // Initialize ArrayList

              ArrayList<Integer> scores = new ArrayList<>();

              scores.add(85);  // Add element

              scores.add(90);

              scores.set(1, 95);  // Update element

              System.out.println(scores.get(0));  // Access: 85

Use: Store dynamic collections like user inputs

B2.2.2_2 1D/2D lists (Python)

1D Lists

Python's built-in dynamic lists
Resizable and can store mixed data types

                                    # 1D list

                                    names = ["Alice", "Bob", "Charlie"]

                                    names.append("David")  # Add element

                                    names[1] = "Beth"  # Update element

                                    print(names[0])  # Access: Alice

              // 1D list using ArrayList

              ArrayList<String> names = new ArrayList<>();

              names.add("Alice");

              names.add("Bob");

              names.add("Charlie");

              names.add("David");  // Add element

              names.set(1, "Beth");  // Update element

              System.out.println(names.get(0));  // Access: Alice

Use: Store dynamic sequences like customer names

2D Lists

Nested lists representing a grid or table
Dynamic resizing capabilities

                                    # 2D list

                                    grid = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

                                    grid[1][1] = 2  # Update element

                                    print(grid[0][2])  # Access: 0

                                    grid.append([1, 1, 1])  # Add new row

              // 2D list using ArrayList of ArrayLists

              ArrayList<ArrayList<Integer>> grid = new ArrayList<>();

              grid.add(new ArrayList<>(Arrays.asList(0,1,0)));

              grid.add(new ArrayList<>(Arrays.asList(1,0,1)));

              grid.add(new ArrayList<>(Arrays.asList(0,1,0)));

              grid.get(1).set(1, 2);  // Update element

              System.out.println(grid.get(0).get(2));  // Access: 0

              grid.add(new ArrayList<>(Arrays.asList(1,1,1)));  // Add new row

Use: Represent dynamic matrices like game boards

B2.2.2_3 Add, remove, traverse dynamic list elements

Add Elements

Append or insert elements to expand size

                                students = ["Alice", "Bob"]

                                students.append("Charlie")  # Add to end

                                students.insert(1, "Beth")  # Add at index 1

                                print(students)  # ['Alice', 'Beth', 'Bob', 'Charlie']

              ArrayList<String> students = new ArrayList<>(Arrays.asList("Alice", "Bob"));

              students.add("Charlie");  // Add to end

              students.add(1, "Beth");  // Add at index 1

              System.out.println(students);  // [Alice, Beth, Bob, Charlie]

Remove Elements

Remove by value, index, or clear entire list

                                students = ["Alice", "Beth", "Bob", "Charlie"]

                                students.remove("Beth")  # Remove by value

                                students.pop(1)  # Remove by index (Bob)

                                print(students)  # ['Alice', 'Charlie']

              ArrayList<String> students = new ArrayList<>(

                  Arrays.asList("Alice","Beth","Bob","Charlie"));

              students.remove("Beth");  // Remove by value

              students.remove(1);  // Remove by index (Bob)

              System.out.println(students);  // [Alice, Charlie]

Traverse Elements

Iterate through elements to process or analyze

                                scores = [85, 90, 78, 92]

                                for score in scores:

                                    print(f"Score: {score}")

                                # Access by index

                                for i in range(len(scores)):

                                    scores[i] += 5  # Add 5 to each

                                print(scores)  # [90, 95, 83, 97]

              int[] scores = {85, 90, 78, 92};

              for (int score : scores) {

                  System.out.println("Score: " + score);

              }

              // Access by index

              for (int i = 0; i < scores.length; i++) {

                  scores[i] += 5;  // Add 5 to each

              }

              // scores: [90, 95, 83, 97]

Use Case

A program managing a student roster:
- Adds new students (append)
- Removes dropouts (remove)
- Traverses the list to calculate average grades or print names
Ensures dynamic updates and efficient data processing

B2.2.3 Explain stack (LIFO) (AO2)

B2.2.3_1 Operations: push, pop, peek, isEmpty

Push

Adds element to the top of the stack
Example: Adding a plate to a stack of plates

                                stack = []

                                stack.append(5)  # Push 5 onto stack

              Stack<Integer> stack = new Stack<>();

              stack.push(5);  // Push 5 onto stack

Pop

Removes and returns the top element
Example: Taking the top plate off

top = stack.pop() # Removes and returns 5

int top = stack.pop(); // Removes and returns 5

Peek

Returns top element without removing it
Example: Checking the top plate

top = stack[-1] if stack else None # Views top element

int top = stack.isEmpty() ? -1 : stack.peek(); // View top element

isEmpty

Checks if stack is empty
Returns True if no elements remain

is_empty = len(stack) == 0 # Returns True if empty

boolean isEmpty = stack.isEmpty(); // Returns true if empty

B2.2.3_2 Impact on performance, memory

Performance

Push/Pop: O(1) time complexity
Operations occur at the top (constant-time access)
Peek/isEmpty: O(1) time complexity
Only access top element or check length
Example: Fast for function call management

Memory

Uses contiguous or dynamic memory
Minimal overhead for simple operations
Dynamic resizing may cause occasional O(n) operations
Example: Function call stack uses small, fixed space per element

Trade-offs

Efficient for LIFO operations but limited for random access or searching (O(n))
Memory-efficient for sequential data but may waste space if underused

B2.2.3_3 Appropriate stack use

Function Call Stack

Manages function calls and returns
Tracks execution context
Example: Python's call stack in recursion

Undo/Redo Operations

Tracks actions in reverse order
Example: Text editor undo feature

Expression Evaluation

Processes expressions or validates syntax
Example: Checking balanced parentheses

Backtracking Algorithms

Supports algorithms like depth-first search
Example: Solving a maze by storing visited paths

Example

                            # Stack for checking balanced parentheses

                            def is_balanced(expression):

                                stack = []

                                for char in expression:

                                    if char == '(':

                                        stack.append(char)  # Push

                                    elif char == ')':

                                        if len(stack) == 0:  # Check isEmpty

                                            return False

                                        stack.pop()  # Pop

                                return len(stack) == 0

                            print(is_balanced("(a + b)"))  # Output: True

                            print(is_balanced("(a + b))"))  # Output: False

              // Stack for checking balanced parentheses

              public static boolean isBalanced(String expr) {

                  Stack<Character> stack = new Stack<>();

                  for (char ch : expr.toCharArray()) {

                      if (ch == '(') {

                          stack.push(ch);  // Push

                      } else if (ch == ')') {

                          if (stack.isEmpty()) return false;

                          stack.pop();  // Pop

                      }

                  }

                  return stack.isEmpty();

              }

              System.out.println(isBalanced("(a + b)"));   // Output: true

              System.out.println(isBalanced("(a + b))"));  // Output: false

Appropriateness

Ideal for LIFO access, reversing actions, or managing nested operations
Inappropriate for random access or frequent searching

B2.2.4 Explain queue (FIFO) (AO2)

B2.2.4_1 Operations: enqueue, dequeue, front, isEmpty

Enqueue

Adds element to the back of the queue
Example: Adding a customer to a ticket line

                                queue = []

                                queue.append(10)  # Enqueue 10

              Queue<Integer> queue = new LinkedList<>();

              queue.offer(10);  // Enqueue 10

Dequeue

Removes and returns the front element
Example: Serving the first customer

front = queue.pop(0) # Dequeue first element (10)

int front = queue.poll(); // Dequeue first element (10)

Front

Returns the front element without removing
Example: Checking the next customer

front = queue[0] if queue else None # View front element

int front = queue.isEmpty() ? -1 : queue.peek(); // View front element

isEmpty

Checks if queue is empty
Returns True if no elements remain

is_empty = len(queue) == 0 # Returns True if empty

boolean isEmpty = queue.isEmpty(); // Returns true if empty

B2.2.4_2 Impact on performance, memory

Performance

Enqueue: O(1) using dynamic list (append)
Dequeue: O(n) in basic Python list due to shifting
Optimized implementations (collections.deque) achieve O(1)
Front/isEmpty: O(1) time complexity

                                    # Optimized implementation

                                    from collections import deque

                                    queue = deque()

                                    queue.append(10)  # O(1)

                                    queue.popleft()  # O(1)

              // Optimized implementation using ArrayDeque

              Deque<Integer> queue = new ArrayDeque<>();

              queue.offer(10);  // O(1)

              queue.poll();  // O(1)

Memory

Uses contiguous or dynamic memory
Overhead for resizing in dynamic implementations
Efficient for sequential processing
May waste memory if pre-allocated capacity is underused
Example: Print job queue uses minimal space per job

Trade-offs

Fast for FIFO operations but inefficient for random access (O(n))
Optimized implementations like deque improve performance

B2.2.4_3 Appropriate queue use

Task Scheduling

Manages tasks in arrival order
Example: CPU process scheduling

Event Handling

Processes events/messages in order received
Example: Server queueing user requests

Breadth-First Search

Explores nodes level by level
Example: Finding shortest path in a maze

Buffering

Handles data streams
Example: Video player queueing frames

Example

                            from collections import deque

                            # Queue for processing print jobs

                            def process_print_jobs(jobs):

                                queue = deque()

                                for job in jobs:

                                    queue.append(job)  # Enqueue job

                                while len(queue) > 0:  # Check isEmpty

                                    current_job = queue.popleft()  # Dequeue front job

                                    print(f"Processing: {current_job}")

                                return len(queue) == 0

                            print_jobs = ["Doc1.pdf", "Doc2.pdf", "Doc3.pdf"]

                            print(process_print_jobs(print_jobs))  # Processes each job, returns True

              public static boolean processPrintJobs(String[] jobs) {

                  Queue<String> queue = new LinkedList<>();

                  for (String job : jobs) {

                      queue.offer(job);  // Enqueue job

                  }

                  while (!queue.isEmpty()) {

                      String currentJob = queue.poll();  // Dequeue front job

                      System.out.println("Processing: " + currentJob);

                  }

                  return queue.isEmpty();

              }

              String[] printJobs = {"Doc1.pdf","Doc2.pdf","Doc3.pdf"};

              System.out.println(processPrintJobs(printJobs));

Appropriateness

Ideal for FIFO scenarios, processing tasks in order of arrival
Inappropriate for LIFO or random access, where stacks or arrays are better

B2.3.1 Construct programs implementing correct instruction sequence (AO3)

B2.3.1_1 The impact of instruction order on program functionality

Why Order Matters

Programs execute instructions sequentially — each line runs in the order it appears
Changing the order of instructions can produce entirely different (often incorrect) results
Variables must be declared and assigned before they are used
Computations that depend on previous results must appear after those results are computed

Incorrect Order

                                    # ERROR: using average before it is calculated

                                    print(f"Average: {average}")  # NameError!

                                    score1 = 80

                                    score2 = 90

                                    average = (score1 + score2) / 2

              // ERROR: using average before it is declared

              System.out.println("Average: " + average);  // CompilationError!

              int score1 = 80;

              int score2 = 90;

              double average = (score1 + score2) / 2.0;

Causes a NameError: average is not yet defined when printed

Correct Order

                                    # Correct: compute before printing

                                    score1 = 80

                                    score2 = 90

                                    average = (score1 + score2) / 2

                                    print(f"Average: {average}")  # Output: 85.0

              // Correct: compute before printing

              int score1 = 80;

              int score2 = 90;

              double average = (score1 + score2) / 2.0;

              System.out.println("Average: " + average);  // Output: 85.0

Variables are defined before use — program runs correctly

B2.3.1_2 Ways to avoid errors: infinite loops, deadlock, incorrect output

Infinite Loops

A loop that never terminates because the exit condition is never met
Cause: missing update to the loop variable, or logic error in condition
Prevention: ensure the loop variable is modified inside the loop body and the condition will eventually be false

                                # INFINITE — count never changes

                                count = 0

                                while count < 5:

                                    print("Hello")  # count is never incremented!

                                # FIXED

                                count = 0

                                while count < 5:

                                    print("Hello")

                                    count += 1  # Loop variable updated

              // INFINITE — count never changes

              int count = 0;

              while (count < 5) {

                  System.out.println("Hello");  // count is never incremented!

              }

              // FIXED

              count = 0;

              while (count < 5) {

                  System.out.println("Hello");

                  count++;  // Loop variable updated

              }

Deadlock

Two or more processes are each waiting for the other to release a resource — neither can proceed
Common in concurrent / multi-threaded programs
Prevention: use consistent resource-locking order, timeouts, or avoid circular dependencies between processes

                                # Conceptual example (pseudo-code)

                                # Process A holds Lock1, waits for Lock2

                                # Process B holds Lock2, waits for Lock1

                                # → deadlock: neither can continue

                                # Prevention: always acquire locks in the same order

                                # Both processes acquire Lock1 first, then Lock2

              // Conceptual example (pseudo-code)

              // Process A holds Lock1, waits for Lock2

              // Process B holds Lock2, waits for Lock1

              // → deadlock: neither can continue

              // Prevention: always acquire locks in the same order

              // Both processes acquire Lock1 first, then Lock2

Incorrect Output

Program runs without errors but produces wrong results
Caused by logic errors: wrong formula, off-by-one index, incorrect operator
Prevention: trace tables, unit testing, careful code review

                                # Off-by-one error example

                                scores = [70, 80, 90]

                                # WRONG: misses last element

                                for i in range(len(scores) - 1):

                                    print(scores[i])

                                # CORRECT

                                for i in range(len(scores)):

                                    print(scores[i])

              // Off-by-one error example

              int[] scores = {70, 80, 90};

              // WRONG: misses last element

              for (int i = 0; i < scores.length - 1; i++) {

                  System.out.println(scores[i]);

              }

              // CORRECT

              for (int i = 0; i < scores.length; i++) {

                  System.out.println(scores[i]);

              }

General Best Practices

Plan program logic with pseudocode or flowcharts before coding
Use trace tables to step through logic manually
Test with boundary values (e.g., 0, negative numbers, empty lists)
Use meaningful variable names to reduce logic mistakes

B2.3.2 Construct programs with selection structures (AO3)

B2.3.2_1 if, else, elif / else if — conditional execution

What is Selection?

Selection allows a program to choose which block of code to execute based on a condition
Enables programs to respond differently to different inputs or states
Core constructs: if, else, elif (Python) / else if (Java)

Python: if / elif / else

                                    grade = 74

                                    if grade >= 90:

                                        print("A")

                                    elif grade >= 80:

                                        print("B")

                                    elif grade >= 70:

                                        print("C")  # Output: C

                                    else:

                                        print("Fail")

              int grade = 74;

              if (grade >= 90) {

                  System.out.println("A");

              } else if (grade >= 80) {

                  System.out.println("B");

              } else if (grade >= 70) {

                  System.out.println("C");  // Output: C

              } else {

                  System.out.println("Fail");

              }

Java: if / else if / else

                                    int grade = 74;

                                    if (grade >= 90) {

                                        System.out.println("A");

                                    } else if (grade >= 80) {

                                        System.out.println("B");

                                    } else if (grade >= 70) {

                                        System.out.println("C");  // Output: C

                                    } else {

                                        System.out.println("Fail");

                                    }

              int grade = 74;

              if (grade >= 90) {

                  System.out.println("A");

              } else if (grade >= 80) {

                  System.out.println("B");

              } else if (grade >= 70) {

                  System.out.println("C");  // Output: C

              } else {

                  System.out.println("Fail");

              }

B2.3.2_2 Boolean operators (AND, OR, NOT) and relational operators (<, <=, >, >=, ==, !=)

Relational Operators

== equal to != not equal to
< less than <= less than or equal
> greater than >= greater than or equal
Always produce a Boolean result (True or False)

Boolean Operators

AND — both conditions must be True
OR — at least one condition must be True
NOT — inverts a Boolean value
Used to combine multiple conditions in a single if statement

Combined Example

                            age = 17

                            has_permission = True

                            score = 55

                            # AND: both conditions required

                            if age >= 16 and has_permission:

                                print("Access granted")  # Output: Access granted

                            # OR: either condition sufficient

                            if score < 40 or score > 100:

                                print("Invalid score")

                            else:

                                print("Score accepted")  # Output: Score accepted

                            # NOT: invert condition

                            if not has_permission:

                                print("Access denied")

                            else:

                                print("Welcome!")  # Output: Welcome!

              int age = 17;

              boolean hasPermission = true;

              int score = 55;

              // AND: both conditions required

              if (age >= 16 && hasPermission) {

                  System.out.println("Access granted");  // Output: Access granted

              }

              // OR: either condition sufficient

              if (score < 40 || score > 100) {

                  System.out.println("Invalid score");

              } else {

                  System.out.println("Score accepted");  // Output: Score accepted

              }

              // NOT: invert condition

              if (!hasPermission) {

                  System.out.println("Access denied");

              } else {

                  System.out.println("Welcome!");  // Output: Welcome!

              }

Use Case

A login system checks: if username == stored_name and password == stored_pass
A ticket system applies discounts: if age < 12 or age >= 65
A sensor triggers an alert: if temperature > 100 and pressure > 200

B2.3.3 Construct programs with looping structures (AO3)

B2.3.3_1 Counted loops vs conditional loops

Counted Loops (for)

Repeat a known, fixed number of times
Best when the number of iterations is determined before the loop starts
Uses a loop variable that steps through a range or collection

                                    # Print squares of 1 to 5

                                    for i in range(1, 6):

                                        print(f"{i}² = {i**2}")

                                    # Output: 1²=1, 2²=4, 3²=9, 4²=16, 5²=25

                                    # Traverse a list

                                    names = ["Alice", "Bob", "Carol"]

                                    for name in names:

                                        print(f"Hello, {name}")

              // Print squares of 1 to 5

              for (int i = 1; i <= 5; i++) {

                  System.out.println(i + "² = " + (i*i));

              }

              // Output: 1²=1, 2²=4, 3²=9, 4²=16, 5²=25

              // Traverse an array

              String[] names = {"Alice", "Bob", "Carol"};

              for (String name : names) {

                  System.out.println("Hello, " + name);

              }

Conditional Loops (while)

Repeat while a condition remains True
Best when the number of iterations is not known in advance
Loop variable must be updated inside the loop to avoid infinite loops

                                    # Keep asking until valid input

                                    user_input = ""

                                    while user_input != "quit":

                                        user_input = input("Enter command: ")

                                        print(f"You entered: {user_input}")

                                    print("Session ended")

              Scanner sc = new Scanner(System.in);

              // Keep asking until valid input

              String userInput = "";

              while (!userInput.equals("quit")) {

                  userInput = sc.nextLine();

                  System.out.println("You entered: " + userInput);

              }

              System.out.println("Session ended");

B2.3.3_2 Conditional statements within loops using Boolean and relational operators

Example: Filtering and Accumulating

                            # Count and sum only passing grades (>= 50)

                            grades = [72, 45, 88, 33, 91, 60]

                            total = 0

                            count = 0

                            for grade in grades:

                                if grade >= 50:  # Condition inside loop

                                    total += grade

                                    count += 1

                            if count > 0:

                                print(f"Passing average: {total / count:.1f}")  # Output: 77.8

              // Count and sum only passing grades (>= 50)

              int[] grades = {72,45,88,33,91,60};

              int total = 0;

              int count = 0;

              for (int grade : grades) {

                  if (grade >= 50) {  // Condition inside loop

                      total += grade;

                      count++;

                  }

              }

              if (count > 0) {

                  System.out.printf("Passing average: %.1f%n", (double) total / count);  // Output: 77.8

              }

Example: Early Exit with Boolean Operators

                            # Search for first student with grade A (>= 90) who is also enrolled

                            students = [("Alice", 85, True), ("Bob", 92, True), ("Carol", 95, False)]

                            found = False

                            i = 0

                            while i < len(students) and not found:

                                name, grade, enrolled = students[i]

                                if grade >= 90 and enrolled:

                                    print(f"Top student: {name} ({grade})")  # Output: Bob (92)

                                    found = True

                                i += 1

              // Search for first student with grade A (>= 90) who is enrolled

              String[] names = {"Alice","Bob","Carol"};

              int[] grades = {85,92,95};

              boolean[] enrolled = {true,true,false};

              boolean found = false;

              int i = 0;

              while (i < names.length && !found) {

                  if (grades[i] >= 90 && enrolled[i]) {

                      System.out.println("Top student: "+names[i]+" ("+grades[i]+")");

                      found = true;

                  }

                  i++;

              }

Trace Table for Filtering Example

grade	grade >= 50	total	count
72	True	72	1
45	False	72	1
88	True	160	2
33	False	160	2
91	True	251	3
60	True	311	4

Final average: 311 / 4 = 77.75

B2.3.4 Construct functions and modularization (AO3)

B2.3.4_1 Functions — reusable blocks with different inputs

What is a Function?

A named block of code that performs a specific task and can be called multiple times
Accepts parameters (inputs) and optionally returns a value
Eliminates repeated code — define once, call many times with different arguments

Python Functions

                                    def calculate_average(scores):

                                        # Returns the average of a list

                                        if len(scores) == 0:

                                            return 0

                                        return sum(scores) / len(scores)

                                    def letter_grade(average):

                                        # Returns a letter grade string

                                        if average >= 90: return "A"

                                        elif average >= 75: return "B"

                                        elif average >= 60: return "C"

                                        else: return "Fail"

                                    # Call with different inputs

                                    class_a = [88, 76, 95]

                                    class_b = [55, 62, 48]

                                    avg_a = calculate_average(class_a)  # 86.3

                                    avg_b = calculate_average(class_b)  # 55.0

                                    print(letter_grade(avg_a))  # B

                                    print(letter_grade(avg_b))  # Fail

              public static double calculateAverage(int[] scores) {

                  if (scores.length == 0) return 0;

                  int sum = 0;

                  for (int s : scores) sum += s;

                  return (double) sum / scores.length;

              }

              public static String letterGrade(double avg) {

                  if (avg >= 90) return "A";

                  else if (avg >= 75) return "B";

                  else if (avg >= 60) return "C";

                  else return "Fail";

              }

              // Call with different inputs

              int[] classA = {88,76,95};

              int[] classB = {55,62,48};

              System.out.println(letterGrade(calculateAverage(classA)));  // B

              System.out.println(letterGrade(calculateAverage(classB)));  // Fail

Java Methods (Functions)

                                    public static double calculateAverage(int[] scores) {

                                        if (scores.length == 0) return 0;

                                        int total = 0;

                                        for (int s : scores) total += s;

                                        return (double) total / scores.length;

                                    }

                                    public static String letterGrade(double avg) {

                                        if (avg >= 90) return "A";

                                        else if (avg >= 75) return "B";

                                        else if (avg >= 60) return "C";

                                        else return "Fail";

                                    }

              public static double calculateAverage(int[] scores) {

                  if (scores.length == 0) return 0;

                  int total = 0;

                  for (int s : scores) total += s;

                  return (double) total / scores.length;

              }

              public static String letterGrade(double avg) {

                  if (avg >= 90) return "A";

                  else if (avg >= 75) return "B";

                  else if (avg >= 60) return "C";

                  else return "Fail";

              }

B2.3.4_2 Modularization to create well-structured, reusable and maintainable code

Modularization

Breaking a program into smaller, self-contained modules (functions, classes, files)
Each module has a single, clear responsibility
Modules can be reused across different programs
Makes code easier to read, test, maintain, and extend

Benefits of Modularization

Reusability: write once, use in many places
Maintainability: change one function without affecting others
Testability: test each function in isolation
Readability: meaningful function names make code self-documenting
Collaboration: team members can work on separate modules

Modularized Program Example

                            # Modularized student grade report program

                            def get_grades():

                                # Module 1: data input

                                return [88, 72, 95, 64, 80]

                            def calculate_average(grades):

                                # Module 2: calculation

                                return sum(grades) / len(grades)

                            def generate_report(grades, average):

                                # Module 3: output

                                print(f"Grades: {grades}")

                                print(f"Average: {average:.1f}")

                                print(f"Result: {'Pass' if average >= 60 else 'Fail'}")

                            # Main program — calls each module in sequence

                            grades = get_grades()

                            avg = calculate_average(grades)

                            generate_report(grades, avg)

                            # Output: Grades: [88,72,95,64,80]  Average: 79.8  Result: Pass

              // Modularized student grade report program

              public static int[] getGrades() {

                  return new int[]{88,72,95,64,80};

              }

              public static double calculateAverage(int[] grades) {

                  int sum = 0;

                  for (int g : grades) sum += g;

                  return (double) sum / grades.length;

              }

              public static void generateReport(int[] grades, double avg) {

                  System.out.println("Average: " + String.format("%.1f", avg));

                  System.out.println("Result: " + (avg >= 60 ? "Pass" : "Fail"));

              }

              // Main: calls each module in sequence

              int[] grades = getGrades();

              double avg = calculateAverage(grades);

              generateReport(grades, avg);

              // Output: Average: 79.8  Result: Pass

B2.3.4_3 Principles of scope (local versus global)

Local Scope

Variables declared inside a function exist only for that function's duration
Cannot be accessed from outside the function
Prevents unintended modification from other parts of the program

	                                def greet():

	                                    message = "Hello"  # local

	                                    print(message)

	                                greet()

	                                # print(message)  → NameError!

              public static void greet() {

                  String message = "Hello";  // local variable

                  System.out.println(message);

              }

              greet();

              // System.out.println(message);  → CompilationError!

Global Scope

Variables declared outside all functions are accessible everywhere
Should be used sparingly because global state makes programs harder to debug
In Python, use the global keyword to modify a global variable inside a function

	                                total = 0  # global variable

	                                def add_score(score):

	                                    global total

	                                    total += score

	                                add_score(85)

	                                add_score(90)

	                                print(total)  # Output: 175

              static int total = 0;  // static (class-level) variable

              public static void addScore(int score) {

                  total += score;

              }

              addScore(85);

              addScore(90);

              System.out.println(total);  // Output: 175

B2.3.4_4 Benefits of modularization in programming scenarios

Input Validation

A validation function can be reused in menus, forms, and file imports
Changing one function improves every place that calls it

File Processing

Separate functions for opening, reading, processing, and saving files reduce errors
Each function can be tested independently before combining the program

Game Logic

Movement, scoring, collision checks, and display updates can be separate modules
This makes the program easier to extend without rewriting unrelated code

B2.4.1 Describe algorithm efficiency using Big O notation (AO2)

B2.4.1_1 Time and space complexity

Time Complexity

Measures how execution time grows as the input size (n) increases
Describes the worst-case number of operations
Not the actual time in seconds — it describes the rate of growth
Example: an algorithm that checks every item in a list of n items takes time proportional to n

Space Complexity

Measures how memory usage grows as input size increases
Includes variables, data structures, and call stack
A sorting algorithm that creates a copy of the input uses O(n) extra space
An in-place algorithm that uses only a few variables uses O(1) extra space

B2.4.1_2 Calculating Big O — common complexities

What is Big O?

Big O notation expresses the upper bound of an algorithm's growth rate
Constants and lower-order terms are dropped: 3n + 5 → O(n)
Focus is on how the algorithm scales as n becomes very large

Big O	Name	Description	Example
O(1)	Constant	Same time regardless of input size	Access list[0]
O(log n)	Logarithmic	Halves the problem each step	Binary search
O(n)	Linear	One operation per element	Linear search
O(n log n)	Linearithmic	Efficient sorting	Merge sort, quicksort
O(n²)	Quadratic	Nested loops over entire input	Bubble sort, selection sort
O(2ⁿ)	Exponential	Doubles with each added element	Brute-force subset enumeration

O(1) — Constant

	                                def get_first(lst):

	                                    return lst[0]  # Always 1 operation

              public static int getFirst(int[] arr) {

                  return arr[0];  // Always 1 operation

              }

Derivation: no loop over n items, so growth is constant

O(n) — Linear

                                def find_max(lst):

                                    max_val = lst[0]

                                    for x in lst:  # n iterations

                                        if x > max_val: max_val = x

	                                    return max_val

              public static int findMax(int[] arr) {

                  int maxVal = arr[0];

                  for (int x : arr) {  // n iterations

                      if (x > maxVal) maxVal = x;

                  }

                  return maxVal;

              }

Derivation: one loop over n items gives O(n)

O(n²) — Quadratic

                                def all_pairs(lst):

                                    for i in range(len(lst)):      # n

                                        for j in range(len(lst)):  # × n

	                                            print(lst[i], lst[j])

              public static void allPairs(int[] arr) {

                  for (int i = 0; i < arr.length; i++) {      // n

                      for (int j = 0; j < arr.length; j++) {  // × n

                          System.out.println(arr[i] + " " + arr[j]);

                      }

                  }

              }

Derivation: n outer iterations × n inner iterations gives O(n²)

O(log n) — Logarithmic

                                def binary_search(lst, target):

                                    low, high = 0, len(lst) - 1

                                    while low <= high:  # halves each time

                                        mid = (low + high) // 2

                                        if lst[mid] == target: return mid

                                        elif lst[mid] < target: low = mid + 1

	                                        else: high = mid - 1

              public static int binarySearch(int[] arr, int target) {

                  int low = 0, high = arr.length - 1;

                  while (low <= high) {  // halves each time

                      int mid = (low + high) / 2;

                      if (arr[mid] == target) return mid;

                      else if (arr[mid] < target) low = mid + 1;

                      else high = mid - 1;

                  }

                  return -1;

              }

Derivation: the search space halves each step, so growth is O(log n)

B2.4.1_3 Algorithm choice based on scalability

Choosing the Right Algorithm

For small datasets, a simple O(n²) algorithm is acceptable and often easier to implement
For large datasets, an O(n log n) or O(log n) algorithm is essential — an O(n²) algorithm on 1,000,000 items would require 10¹² operations
Always consider both time and space — a faster algorithm may use significantly more memory

n	O(log n)	O(n)	O(n log n)	O(n²)
10	3	10	33	100
100	7	100	664	10,000
1,000	10	1,000	10,000	1,000,000
1,000,000	20	1,000,000	20,000,000	10¹²

B2.4.2 Construct and trace linear and binary search (AO3)

B2.4.2_1 Linear Search — O(n)

How it Works

Checks each element one by one from start to end
Works on unsorted or sorted data
Best case: target is first element — O(1)
Worst case: target is last or not present — O(n)

Implementation

                                    def linear_search(lst, target):

                                        for i in range(len(lst)):

                                            if lst[i] == target:

                                                return i  # Found: return index

                                        return -1  # Not found

                                    phones = ["Alice", "Bob", "Carol", "David"]

                                    print(linear_search(phones, "Carol"))  # 2

                                    print(linear_search(phones, "Eve"))    # -1

              public static int linearSearch(String[] arr, String target) {

                  for (int i = 0; i < arr.length; i++) {

                      if (arr[i].equals(target)) {

                          return i;  // Found: return index

                      }

                  }

                  return -1;  // Not found

              }

              String[] phones = {"Alice","Bob","Carol","David"};

              System.out.println(linearSearch(phones, "Carol"));  // 2

              System.out.println(linearSearch(phones, "Eve"));    // -1

Trace for linear_search(["Alice","Bob","Carol","David"], "Carol")

i	lst[i]	== "Carol"?	Action
0	"Alice"	False	Continue
1	"Bob"	False	Continue
2	"Carol"	True	Return 2

B2.4.2_2 Binary Search — O(log n)

How it Works

Requires a sorted list
Compares target to the middle element
If target is smaller → search the left half
If target is larger → search the right half
Halves the search space each step → O(log n)

Implementation

                                    def binary_search(lst, target):

                                        low = 0

                                        high = len(lst) - 1

                                        while low <= high:

                                            mid = (low + high) // 2

                                            if lst[mid] == target:

                                                return mid

                                            elif lst[mid] < target:

                                                low = mid + 1

                                            else:

                                                high = mid - 1

                                        return -1

              public static int binarySearch(int[] arr, int target) {

                  int low = 0;

                  int high = arr.length - 1;

                  while (low <= high) {

                      int mid = (low + high) / 2;

                      if (arr[mid] == target) {

                          return mid;

                      } else if (arr[mid] < target) {

                          low = mid + 1;

                      } else {

                          high = mid - 1;

                      }

                  }

                  return -1;

              }

Trace for binary_search([10, 23, 37, 45, 58, 72, 89], 58)

Step	low	high	mid	lst[mid]	Action
1	0	6	3	45	45 < 58 → low = 4
2	4	6	5	72	72 > 58 → high = 4
3	4	4	4	58	Found! Return 4

Only 3 comparisons to find the target in 7 elements — vs up to 7 for linear search

B2.4.2_3 Comparing search efficiency and use cases

Aspect	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Requires Sorted Data?	No	Yes
Best Case	O(1) — target is first element	O(1) — target is middle element
Worst Case	O(n) — target not present	O(log n) — target not present
Use Case	Unsorted list; small datasets; searching by phone number to find a name	Large sorted dataset; searching a sorted/indexed name list to find a phone number

B2.4.3 Construct and trace bubble sort and selection sort (AO3)

B2.4.3_1 Bubble Sort

How it Works

Repeatedly compares adjacent pairs and swaps them if out of order
Each pass "bubbles" the largest unsorted element to its correct position
Continues until no swaps are made in a full pass (sorted)
Time: O(n²) worst/average; O(n) best (already sorted with optimisation)
Space: O(1) — in-place, only needs one temporary variable

Implementation

                                    def bubble_sort(lst):

                                        n = len(lst)

                                        for i in range(n):

                                            swapped = False

                                            for j in range(0, n - i - 1):

                                                if lst[j] > lst[j + 1]:

                                                    lst[j], lst[j+1] = lst[j+1], lst[j]

                                                    swapped = True

                                            if not swapped: break  # Early exit if sorted

                                        return lst

                                    data = [64, 25, 12, 22, 11]

                                    print(bubble_sort(data))  # [11,12,22,25,64]

              public static void bubbleSort(int[] arr) {

                  int n = arr.length;

                  for (int i = 0; i < n; i++) {

                      boolean swapped = false;

                      for (int j = 0; j < n - i - 1; j++) {

                          if (arr[j] > arr[j+1]) {

                              int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;

                              swapped = true;

                          }

                      }

                      if (!swapped) break;  // Early exit if sorted

                  }

              }

              int[] data = {64,25,12,22,11};

              bubbleSort(data);

              System.out.println(Arrays.toString(data));  // [11,12,22,25,64]

Trace for [64, 25, 12, 22, 11]

Pass	After Pass	Swaps?
1	[25, 12, 22, 11, 64]	Yes
2	[12, 22, 11, 25, 64]	Yes
3	[12, 11, 22, 25, 64]	Yes
4	[11, 12, 22, 25, 64]	Yes
5	[11, 12, 22, 25, 64]	No → stop

Bold = element placed in final sorted position that pass

B2.4.3_2 Selection Sort

How it Works

Divides list into a sorted left portion and an unsorted right portion
Each pass finds the minimum in the unsorted portion and swaps it to the end of the sorted portion
Time: always O(n²) — no early exit like bubble sort
Space: O(1) — in-place
Makes fewer swaps than bubble sort (at most n−1 swaps)

Implementation

                                    def selection_sort(lst):

                                        n = len(lst)

                                        for i in range(n):

                                            # Find minimum in unsorted portion

                                            min_idx = i

                                            for j in range(i + 1, n):

                                                if lst[j] < lst[min_idx]:

                                                    min_idx = j

                                            # Swap minimum into sorted position

                                            lst[i], lst[min_idx] = lst[min_idx], lst[i]

                                        return lst

                                    data = [64, 25, 12, 22, 11]

                                    print(selection_sort(data))  # [11,12,22,25,64]

              public static void selectionSort(int[] arr) {

                  int n = arr.length;

                  for (int i = 0; i < n; i++) {

                      // Find minimum in unsorted portion

                      int minIdx = i;

                      for (int j = i + 1; j < n; j++) {

                          if (arr[j] < arr[minIdx]) minIdx = j;

                      }

                      // Swap minimum into sorted position

                      int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;

                  }

              }

              int[] data = {64,25,12,22,11};

              selectionSort(data);

              System.out.println(Arrays.toString(data));  // [11,12,22,25,64]

Trace for [64, 25, 12, 22, 11]

Pass (i)	Min Found	Swap	After Pass
0	11 (idx 4)	64 ↔ 11	[11, 25, 12, 22, 64]
1	12 (idx 2)	25 ↔ 12	[11, 12, 25, 22, 64]
2	22 (idx 3)	25 ↔ 22	[11, 12, 22, 25, 64]
3	25 (idx 3)	No swap	[11, 12, 22, 25, 64]
4	64 (idx 4)	No swap	[11, 12, 22, 25, 64]

Bold = element confirmed in its final sorted position

B2.4.3_3 Comparing bubble sort and selection sort

Aspect	Bubble Sort	Selection Sort
Time (worst/avg)	O(n²)	O(n²)
Time (best)	O(n) with optimisation (already sorted)	O(n²) — always scans full unsorted portion
Space	O(1)	O(1)
Number of Swaps	Can be high — many adjacent swaps	At most n−1 — one swap per pass
Stable?	Yes — equal elements preserve order	No — swaps can change relative order
Best Used When	Data is nearly sorted; small datasets	Minimising writes/swaps is important; small datasets

Summary

Both algorithms are simple to implement but inefficient for large datasets — O(n²) becomes impractical for n > 10,000
These algorithms are valuable for learning and understanding how sorting works at a low level

B2.4.4 Explain recursion and its applications (AO2) HL

B2.4.4_1 Fundamentals — advantages and limitations

What is Recursion?

A function that calls itself to solve a smaller version of the same problem
Every recursive solution has two essential components:
- Base case: a condition that stops the recursion (returns a direct answer)
- Recursive case: reduces the problem towards the base case and calls the function again
Each call is placed on the call stack and resolved when the base case is reached

Advantages

Elegant and concise — recursive solutions are often far shorter than iterative equivalents
Natural fit for problems with a recursive structure (trees, fractals, divide-and-conquer)
Improves code readability when the problem itself is recursive in nature
Simplifies complex algorithms like quicksort and tree traversal

Limitations

Memory usage: each recursive call adds a stack frame — deep recursion can cause a stack overflow
Performance: function call overhead makes recursion slower than iteration for simple repetitions
Complexity: tracing and debugging recursive code can be harder to follow
Risk of infinite recursion if base case is missing or unreachable

B2.4.4_2 Applications — problems suited to recursion

B2.4.4_3 Recursive Algorithms

Quicksort

Selects a pivot element and partitions the list into elements smaller and larger than the pivot
Recursively sorts each partition
Average time: O(n log n); worst case O(n²)

                                def quicksort(lst):

                                    if len(lst) <= 1: return lst  # Base case

                                    pivot = lst[len(lst) // 2]

                                    left  = [x for x in lst if x < pivot]

                                    mid   = [x for x in lst if x == pivot]

                                    right = [x for x in lst if x > pivot]

                                    return quicksort(left) + mid + quicksort(right)

              public static void quickSort(int[] arr, int low, int high) {

                  if (low >= high) return;  // Base case

                  int pivot = arr[(low + high) / 2];

                  int i = low, j = high;

                  while (i <= j) {

                      while (arr[i] < pivot) i++;

                      while (arr[j] > pivot) j--;

                      if (i <= j) {

                          int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;

                          i++; j--;

                      }

                  }

                  quickSort(arr, low, j);   // Sort left partition

                  quickSort(arr, i, high);  // Sort right partition

              }

Binary Tree Traversal

Trees are naturally recursive: each node has left and right subtrees
In-order traversal visits left → root → right to produce sorted output
Recursion visits every node exactly once: O(n)

                                def inorder(node):

                                    if node is None: return  # Base case

                                    inorder(node.left)   # Visit left subtree

                                    print(node.value)   # Visit root

                                    inorder(node.right)  # Visit right subtree

              public static void inorder(TreeNode node) {

                  if (node == null) return;  // Base case

                  inorder(node.left);   // Visit left subtree

                  System.out.println(node.value);   // Visit root

                  inorder(node.right);  // Visit right subtree

              }

Fractal Image Creation

Fractals are shapes that contain smaller copies of themselves
Each recursive call draws a smaller version of the same pattern
Example: The Sierpiński triangle — a triangle made of three smaller triangles, each containing three smaller triangles, and so on
Recursion depth controls level of detail

When to Choose Recursion

Use recursion when the problem naturally decomposes into identical sub-problems (trees, divide-and-conquer, fractals)
Avoid recursion when depth could be large (risk of stack overflow) or when a simple loop will do
Use memoisation (caching results) to avoid recalculating the same sub-problems in recursive algorithms

B2.4.4_4 Limitations — complexity and memory usage

Stack Overflow Example

                            def countdown(n):

                                # Missing base case → infinite recursion → RecursionError

                                print(n)

                                return countdown(n - 1)  # Never stops

                            def countdown_fixed(n):

                                if n < 0: return  # Base case prevents overflow

                                print(n)

                                countdown_fixed(n - 1)

              public static void countdown(int n) {

                  // Missing base case → infinite recursion → StackOverflowError

                  System.out.println(n);

                  countdown(n - 1);  // Never stops

              }

              public static void countdownFixed(int n) {

                  if (n < 0) return;  // Base case prevents overflow

                  System.out.println(n);

                  countdownFixed(n - 1);

              }

Enrichment — beyond exam scope: Memoisation is not listed as examinable content in the IB CS 2027 curriculum for this objective. It is included here as useful context for understanding recursive performance.

Naive Recursion vs Memoisation

                            # Naive Fibonacci: O(2ⁿ) — recalculates the same values repeatedly

                            def fib(n):

                                if n <= 1: return n

                                return fib(n - 1) + fib(n - 2)  # Exponential time!

                            # With memoisation: O(n) — each value computed only once

                            memo = {}

                            def fib_memo(n):

                                if n <= 1: return n

                                if n in memo: return memo[n]  # Use cached result

                                memo[n] = fib_memo(n-1) + fib_memo(n-2)

                                return memo[n]

              // Naive Fibonacci: O(2ⁿ) — recalculates same values repeatedly

              public static int fib(int n) {

                  if (n <= 1) return n;

                  return fib(n-1) + fib(n-2);  // Exponential time!

              }

              // With memoisation: O(n) — each value computed only once

              static HashMap<Integer,Integer> memo = new HashMap<>();

              public static int fibMemo(int n) {

                  if (n <= 1) return n;

                  if (memo.containsKey(n)) return memo.get(n);  // Use cached result

                  memo.put(n, fibMemo(n-1) + fibMemo(n-2));

                  return memo.get(n);

              }

fib(50) with naive recursion: over 10¹⁰ calls; with memoisation: just 50 unique calls

B2.4.4_5 Situations that best suit recursion

Best-Fit Problems

Fractal image creation: each recursive call draws a smaller version of the same shape
Traversing binary trees: each node can be processed using the same logic for left and right subtrees
Sorting algorithms: divide-and-conquer sorts such as quicksort split a list into smaller lists
Avoid recursion when a simple loop is clearer or when recursion depth may become very large

B2.4.5 Construct, trace recursive algorithms (AO3) HL

B2.4.5_1 Simple, non-branching recursive algorithms

Constructing Recursive Algorithms

Solve problems by calling themselves with smaller inputs
Consist of:
- Base case: Terminates recursion
- Recursive case: Reduces problem size
Non-branching: Makes a single recursive call per iteration

Factorial Example

                            def factorial(n):

                                # Base case

                                if n == 0 or n == 1:

                                    return 1

                                # Recursive case

                                return n * factorial(n - 1)

                            # Computes n! (e.g., 5! = 5 × 4 × 3 × 2 × 1 = 120)

              public static int factorial(int n) {

                  // Base case

                  if (n == 0 || n == 1) {

                      return 1;

                  }

                  // Recursive case

                  return n * factorial(n - 1);

              }

              // Computes n! (e.g., 5! = 5×4×3×2×1 = 120)

Tracing Recursive Algorithms

Follow each recursive call, tracking values until base case
Then compute final output by unwinding the call stack

Trace for factorial(4):

Call 1: factorial(4) → 4 × factorial(3)
Call 2: factorial(3) → 3 × factorial(2)
Call 3: factorial(2) → 2 × factorial(1)
Call 4: factorial(1) → Base case, returns 1
Unwind:
- factorial(2) → 2 × 1 = 2
- factorial(3) → 3 × 2 = 6
- factorial(4) → 4 × 6 = 24
Result: factorial(4) returns 24

Sum of Numbers Example

                            def sum_to_n(n):

                                # Base case

                                if n <= 1:

                                    return n

                                # Recursive case

                                return n + sum_to_n(n - 1)

                            # Computes sum from 1 to n (e.g., sum_to_n(4) = 1+2+3+4 = 10)

              public static int sumToN(int n) {

                  // Base case

                  if (n <= 1) {

                      return n;

                  }

                  // Recursive case

                  return n + sumToN(n - 1);

              }

              // Computes sum 1 to n (e.g., sumToN(4)=1+2+3+4=10)

Trace for sum_to_n(4):

Call 1: sum_to_n(4) → 4 + sum_to_n(3)
Call 2: sum_to_n(3) → 3 + sum_to_n(2)
Call 3: sum_to_n(2) → 2 + sum_to_n(1)
Call 4: sum_to_n(1) → Base case, returns 1
Unwind:
- sum_to_n(2) → 2 + 1 = 3
- sum_to_n(3) → 3 + 3 = 6
- sum_to_n(4) → 4 + 6 = 10
Result: sum_to_n(4) returns 10

Key Considerations

Ensure a clear base case to prevent infinite recursion
Non-branching algorithms are simpler to trace and construct
Example Use Case: Calculating power of a number (x^n)

                            def power(x, n):

                                if n == 0:  # Base case

                                    return 1

                                return x * power(x, n - 1)  # Recursive case

                            # Trace for power(2, 3):

                            # power(2, 3) → 2 * power(2, 2)

                            # power(2, 2) → 2 * power(2, 1)

                            # power(2, 1) → 2 * power(2, 0)

                            # power(2, 0) → 1

                            # Unwind: 2 * 1 = 2, 2 * 2 = 4, 2 * 4 = 8

                            # Result: 8

              public static int power(int x, int n) {

                  if (n == 0) {  // Base case

                      return 1;

                  }

                  return x * power(x, n - 1);  // Recursive case

              }

              // Trace for power(2, 3):

              // power(2,3) → 2 * power(2,2)

              // power(2,2) → 2 * power(2,1)

              // power(2,1) → 2 * power(2,0)

              // power(2,0) → 1

              // Unwind: 2*1=2, 2*2=4, 2*4=8  Result: 8

B2.5.1 Construct file-processing code (AO3)

B2.5.1_1 Manipulate text files

Description

Writing code to read from, write to, or modify text files
Enables data persistence and processing
Purpose: Store, retrieve, or update data for tasks like logging, configuration, or analysis
Example: Reading student names from a file, updating grades, and saving results

B2.5.1_2 Open files in read, write, append modes

Read Mode ('r')

Opens file for reading
Raises error if file doesn't exist
Example: Reading student grades from text file

Write Mode ('w')

Opens file for writing
Overwrites if exists or creates new file
Example: Writing processed data to a file

Append Mode ('a')

Opens file to add data at the end
Preserves existing content
Example: Adding new log entries without overwriting

Code Example

                            # Example: Manipulating a text file with different modes

                            # Write mode: Create or overwrite a file

                            with open('students.txt', 'w') as file:

                                file.write("Alice,85\nBob,90\n")  # Write initial data

                            # Append mode: Add new data

                            with open('students.txt', 'a') as file:

                                file.write("Charlie,78\n")  # Append new student

                            # Read mode: Read and print file contents

                            with open('students.txt', 'r') as file:

                                content = file.read()

                                print("File Contents:", content)

              // Write mode: Create or overwrite a file

              FileWriter writer = new FileWriter("students.txt");

              writer.write("Alice,85\nBob,90\n");  // Write initial data

              writer.close();

              // Append mode: Add new data

              FileWriter appender = new FileWriter("students.txt", true);

              appender.write("Charlie,78\n");  // Append new student

              appender.close();

              // Read mode: Read and print file contents

              Scanner scanner = new Scanner(new File("students.txt"));

              while (scanner.hasNextLine()) {

                  System.out.println(scanner.nextLine());

              }

              scanner.close();

B2.5.1_3 Read, write, append, close files

Read

Retrieves data using methods like read(), readline(), or readlines()
Example: file.read() reads entire file as string
file.readlines() reads lines into a list

Write

Writes data to file in 'w' mode
Overwrites existing content
Example: file.write("data") writes a string

Append

Adds data to end in 'a' mode
Preserves existing content
Example: file.write("new data\n") appends a line

Close

Closes file to free system resources
Automatically handled using 'with' statement
Example: with open('file.txt', 'r') as file: ensures closure

Code Example

                            # Read, write, append example

                            # Write initial data

                            with open('grades.txt', 'w') as file:

                                file.write("Alice: 85\n")

                            # Append additional data

                            with open('grades.txt', 'a') as file:

                                file.write("Bob: 90\n")

                            # Read and process file

                            with open('grades.txt', 'r') as file:

                                lines = file.readlines()  # Read all lines into a list

                                for line in lines:

                                    name, grade = line.strip().split(': ')

                                    grade = int(grade) + 5  # Increase grade by 5

                                    print(f"Updated: {name}, {grade}")

              // Write initial data

              FileWriter writer = new FileWriter("grades.txt");

              writer.write("Alice: 85\n");

              writer.close();

              // Append additional data

              FileWriter appender = new FileWriter("grades.txt", true);

              appender.write("Bob: 90\n");

              appender.close();

              // Read and process file

              BufferedReader reader = new BufferedReader(new FileReader("grades.txt"));

              String line;

              while ((line = reader.readLine()) != null) {

                  String[] parts = line.split(": ");

                  int grade = Integer.parseInt(parts[1]) + 5;  // Increase by 5

                  System.out.println("Updated: " + parts[0] + ", " + grade);

              }

              reader.close();

B2.5.1_4 Java classes: Scanner, FileWriter, BufferedReader

Scanner

Java class (java.util.Scanner) for reading data
Parses input into tokens

                                import java.util.Scanner;

                                import java.io.File;

                                File file = new File("students.txt");

                                Scanner scanner = new Scanner(file);

                                while (scanner.hasNextLine()) {

                                    System.out.println(scanner.nextLine());

                                }

                                scanner.close();

              import java.util.Scanner;

              import java.io.File;

              File file = new File("students.txt");

              Scanner scanner = new Scanner(file);

              while (scanner.hasNextLine()) {

                  System.out.println(scanner.nextLine());

              }

              scanner.close();

FileWriter

Java class (java.io.FileWriter) for writing
Writes character data to files

                                import java.io.FileWriter;

                                FileWriter writer = new FileWriter("students.txt");

                                writer.write("Alice,85\n");

                                writer.close();  // Explicitly close

              import java.io.FileWriter;

              FileWriter writer = new FileWriter("students.txt");

              writer.write("Alice,85\n");

              writer.close();  // Explicitly close

BufferedReader

Java class for efficient reading
Buffers input for better performance

                                import java.io.BufferedReader;

                                import java.io.FileReader;

                                BufferedReader reader = new BufferedReader(

                                    new FileReader("students.txt"));

                                String line;

                                while ((line = reader.readLine()) != null) {

                                    System.out.println(line);

                                }

                                reader.close();

              import java.io.BufferedReader;

              import java.io.FileReader;

              BufferedReader reader = new BufferedReader(

                  new FileReader("students.txt"));

              String line;

              while ((line = reader.readLine()) != null) {

                  System.out.println(line);

              }

              reader.close();

B2.5.1_5 Python functions: open(), read(), readline(), write(), close()

open()

Opens file in specified mode
Returns a file object
Example: file = open('data.txt', 'r')

read()

Reads entire file as string
Example: content = file.read()

readline()

Reads a single line
Returns empty string at end
Example: line = file.readline()

write()

Writes string to file
Example: file.write("Hello\n")

close()

Closes file, freeing resources
Used without 'with' statement
Example: file.close()

Example Program

                            # Process a CSV file with student data

                            # Write student data

                            with open('students.csv', 'w') as file:

                                file.write("Name,Grade\nAlice,85\nBob,90\n")

                            # Read and manipulate data

                            with open('students.csv', 'r') as file:

                                lines = file.readlines()[1:]  # Skip header

                                for line in lines:

                                    name, grade = line.strip().split(',')

                                    grade = int(grade) + 5  # Increase grade by 5

                                    print(f"Updated: {name}, {grade}")

                            # Append new student

                            with open('students.csv', 'a') as file:

                                file.write("Charlie,78\n")

              // Process a CSV file with student data

              // Write student data

              FileWriter writer = new FileWriter("students.csv");

              writer.write("Name,Grade\nAlice,85\nBob,90\n");

              writer.close();

              // Read and manipulate data

              BufferedReader reader = new BufferedReader(new FileReader("students.csv"));

              reader.readLine();  // Skip header

              String line;

              while ((line = reader.readLine()) != null) {

                  String[] parts = line.split(",");

                  int grade = Integer.parseInt(parts[1]) + 5;

                  System.out.println("Updated: " + parts[0] + ", " + grade);

              }

              reader.close();

              // Append new student

              FileWriter appender = new FileWriter("students.csv", true);

              appender.write("Charlie,78\n");

              appender.close();

Use Case

A program managing a log file:
- Writes new entries (write, append mode)
- Reads and analyzes past entries (readlines)
- Ensures proper closure (with or close)
Enables reliable file processing for tasks like tracking user activity or storing configuration data