Your Website Content

Move mouse, scroll slightly, or click fullscreen will trigger instantly.

ScrollIndicator → Try scrolling just a tiny bit

🖱️ Move | ⬇️ Scroll | ✅ Click

Any small interaction enters fullscreen

Justin-docs

Module 1: Introduction to Data Structures

By Justin

Based on 2024 Exam Scheme & 2026 Handbook Reference

1. Data Types and Abstract Data Types

🧸 For a 5-Year-Old: What are Data Types?

Imagine you have different toy boxes: one for LEGO blocks, one for stuffed animals, and one for toy cars. Each box holds only one type of toy. Data types are like these toy boxes - they tell the computer what kind of information you're storing, like numbers, words, or true/false answers!

📚 Formal Definition & Technical Details

Data Types are classifications that specify which type of value a variable can hold and what operations can be performed on it. In programming, data types define the size, range, and behavior of data stored in memory.

INTEGER Whole numbers FLOAT Decimal numbers CHARACTER Single letters ARRAY Collection of items STRUCTURE Group of different types Data Types Classification
Figure 1: Classification of Primitive and Derived Data Types

Primitive Data Types:

  • Integer: Whole numbers (e.g., 42, -17, 0)
  • Float/Double: Decimal numbers (e.g., 3.14, -0.001)
  • Character: Single letters or symbols (e.g., 'A', '$')
  • Boolean: True or false values

Derived Data Types:

  • Array: Fixed-size collection of same-type elements
  • Structure: Collection of different-type elements
  • Pointer: Memory address reference
🎭 For a 5-Year-Old: What are Abstract Data Types?

Think of a TV remote control. You don't need to know how the electronics inside work - you just need to know which buttons to press to change channels or adjust volume. Abstract Data Types are like remote controls - they show you what you can do (the buttons) but hide how it works inside!

🔍 Formal Definition & Technical Implementation

Abstract Data Types (ADTs) are mathematical models for data types where the data type is defined by its behavior (semantics) from the point of view of a user, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

INTERFACE (What you can do) Operations: push(), pop(), isEmpty(), size() IMPLEMENTATION (How it works) Array-based or Linked List-based storage DATA (What's stored) Actual values in memory Abstract Data Type: Stack Example
Figure 2: ADT Abstraction Layers - Stack Example

Key Characteristics of ADTs:

  • Encapsulation: Hides implementation details
  • Abstraction: Focuses on what operations do, not how
  • Modularity: Can be used independently of implementation
📝 Real-World Example: Stack ADT

Interface: push(item), pop(), peek(), isEmpty(), size()

Implementation Options: Array-based, Linked List-based

Real-world Analogy: Stack of plates - you can only add/remove from the top

ADT = {Data Objects} ∪ {Operations} ∪ {Axioms}

2. Algorithm Analysis: Time and Space Complexity

⏱️ For a 5-Year-Old: What is Algorithm Analysis?

Imagine you have two ways to clean your room: one way takes 5 minutes, and another way takes 1 hour. Algorithm analysis is like figuring out which way is faster and which way uses more space in your toy box. We want to find the best way that's both fast and doesn't need too much space!

📊 Formal Definition & Mathematical Foundation

Algorithm Analysis is the process of determining the amount of time, storage, or other resources required to execute an algorithm. It helps us compare different algorithms and choose the most efficient one for a given problem.

Input Size (n) Time O(1) O(log n) O(n) O(n²) Time Complexity Growth Rates
Figure 3: Comparison of Different Time Complexity Functions

Time Complexity: Measures how the runtime of an algorithm grows with input size.

Space Complexity: Measures how the memory usage grows with input size.

🔢 Frequency Count Method Example
for (i = 0; i < n; i++) { // n+1 times for (j=0; j < n; j++) { // n*(n+1) times x=x + 1; // n*n times } }

Total Operations: (n+1) + n(n+1) + n² = 2n² + 2n + 1

Time Complexity: O(n²)

T(n) = c₁n² + c₂n + c₃ = O(n²)

Best, Average, and Worst Case Analysis:

  • Best Case: Minimum time/space required (optimistic scenario)
  • Average Case: Expected time/space over all possible inputs
  • Worst Case: Maximum time/space required (pessimistic scenario)

3. Asymptotic Notations: Big O, Omega, Theta

📈 For a 5-Year-Old: What are Asymptotic Notations?

Imagine you're growing a plant. Big O tells you "your plant won't grow taller than this tree." Omega tells you "your plant will grow at least as tall as this flower." Theta tells you "your plant will grow about as tall as this bush." These are just different ways to describe how big something gets!

🎯 Mathematical Definitions & Properties

Asymptotic Notations are mathematical tools used to describe the behavior of functions as their input approaches infinity. They provide a way to classify algorithms based on their growth rates.

Big O Notation: f(n) = O(g(n)) g(n) = n² f(n) = 3n² + 2n + 1 c·g(n) = 4n² n₀ Omega Notation: f(n) = Ω(g(n)) g(n) = n f(n) = 2n + 3 c·g(n) = 1.5n n₀
Figure 4: Big O and Omega Notations Visualized

Big O Notation (O): Upper bound

f(n) = O(g(n)) if ∃ positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀

Omega Notation (Ω): Lower bound

f(n) = Ω(g(n)) if ∃ positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀

Theta Notation (Θ): Tight bound

f(n) = Θ(g(n)) if ∃ positive constants c₁, c₂, and n₀ such that 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀
📊 Practical Example: Analyzing f(n) = 3n² + 2n + 1

Big O: f(n) = O(n²) because 3n² + 2n + 1 ≤ 4n² for n ≥ 3

Omega: f(n) = Ω(n²) because 3n² + 2n + 1 ≥ 3n² for n ≥ 1

Theta: f(n) = Θ(n²) because 3n² ≤ 3n² + 2n + 1 ≤ 4n² for n ≥ 3

4. Recursion and its Applications

🔄 For a 5-Year-Old: What is Recursion?

Imagine you have a Russian nesting doll. When you open it, you find a smaller doll inside. When you open that one, you find an even smaller doll! This keeps happening until you find the tiniest doll that can't be opened. Recursion is like this - a function that calls itself until it reaches the smallest version!

🧩 Formal Definition & Implementation

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, similar subproblems.

Recursive Function Call Stack: factorial(4) 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) return 1 (Base Case)
Figure 5: Recursive Function Call Stack for Factorial(4)

Essential Components of Recursion:

  • Base Case: The condition that stops the recursion
  • Recursive Case: The part where the function calls itself
  • Call Stack: Memory stack that tracks function calls
💻 Recursive Factorial Implementation
function factorial(n) { // Base case if (n == 0 || n == 1) { return 1; } // Recursive case else { return n * factorial(n - 1); } }

Time Complexity: O(n)

Space Complexity: O(n) due to call stack

Applications of Recursion:

  • Tree Traversal: Inorder, Preorder, Postorder
  • Divide and Conquer: Merge Sort, Quick Sort
  • Dynamic Programming: Fibonacci, Coin Change
  • Graph Algorithms: DFS, Topological Sort
  • Mathematical Computations: Factorial, Power, GCD
T(n) = T(n-1) + O(1) = O(n) // For simple linear recursion

Advantages:

  • Elegant and concise code for complex problems
  • Natural fit for problems with recursive structure
  • Reduces code duplication

Disadvantages:

  • Can be less efficient than iterative solutions
  • Risk of stack overflow for deep recursion
  • Can be harder to debug and understand

Module Summary & Exam Focus

🎯 Key Exam Topics from Module 1

High-Frequency Exam Questions:

  1. Algorithm Analysis using Frequency Count:
    • Calculate time complexity of nested loops
    • Analyze recursive algorithms
    • Compare different algorithmic approaches
  2. Asymptotic Notations:
    • Prove Big O, Omega, Theta for given functions
    • Compare growth rates of different functions
    • Derive complexity bounds for algorithms
  3. ADT Implementation:
    • Design ADTs for specific problems
    • Compare different implementations
    • Analyze trade-offs between implementations
  4. Recursive Algorithm Design:
    • Write recursive solutions for problems
    • Analyze time and space complexity
    • Convert recursive to iterative solutions
📝 Sample Exam Question

Question: Calculate the frequency count and time complexity of the following code segment:

for (i = 0; i < n; i++) { for (j=0; j < i; j++) { for (k=0; k < j; k++) { x=x + 1; } } }

Solution Approach:
1. Innermost loop (k): runs j times
2. Middle loop (j): runs i times
3. Outer loop (i): runs n times
4. Total operations: Σ(i=0 to n-1) Σ(j=0 to i-1) j = Σ(i=0 to n-1) i(i-1)/2 = O(n³)

Study Strategy:

  • Master the frequency count method for complexity analysis
  • Practice proving asymptotic notations mathematically
  • Understand the relationship between data types and ADTs
  • Develop intuition for recursive problem-solving
  • Work through examples from previous year papers
Exam Success = Understanding + Practice + Application

Module 2: Arrays and Linked Lists

1. Linear Arrays

For a 5-Year-Old

Imagine a row of numbered mailboxes. Each mailbox can hold one letter. You know exactly which mailbox is which because of its number. If you want to find the 5th letter, you just go straight to mailbox number 5. It's super fast! But if you want to add a new mailbox in the middle, you have to move all the other mailboxes down to make space, which is a lot of work.

The Deep Dive

A Linear Array is a fundamental data structure consisting of a collection of elements of the same data type, stored in contiguous memory locations. Each element can be directly accessed by its index, which is an integer value, typically starting from 0.

Address(A[i]) = Base_Address + (i * Size_of_Element)

Key Characteristics:

  • Fixed Size: The size of an array is defined at the time of its declaration and cannot be changed during runtime.
  • Homogeneous Elements: All elements in an array must be of the same type (e.g., all integers, all characters).
  • Random Access: Elements can be accessed in constant time, O(1), using their index. This is the primary advantage of arrays.
  • Contiguous Memory: Elements are stored next to each other in memory, which enables fast access.

Common Operations & Time Complexity:

  • Access (by index): O(1) - Direct calculation of memory address.
  • Search (unsorted): O(n) - Requires checking each element sequentially (Linear Search).
  • Search (sorted): O(log n) - Possible with algorithms like Binary Search.
  • Insertion (at the end): O(1) - If space is available.
  • Insertion (at the beginning/middle): O(n) - Requires shifting subsequent elements.
  • Deletion (at the beginning/middle): O(n) - Requires shifting subsequent elements to fill the gap.
10 0 25 1 5 2 42 3 99 4 5 6 Index Value Insert 17 at index 4
Visualizing an array and the costly operation of inserting an element in the middle.

2. Sparse Matrices

For a 5-Year-Old

Imagine a giant parking lot for 1000 cars, but only 5 cars are parked in it. It would be silly to draw a map of all 1000 empty parking spots, right? A sparse matrix is like a smart list that only writes down where the 5 cars are, like "Car A is in spot 12, Car B is in spot 45," and so on. It saves a lot of paper!

The Deep Dive

A Sparse Matrix is a matrix in which most of the elements are zero. Storing such a matrix using a standard 2D array is inefficient as it wastes a significant amount of memory to store the zero values. Special representations are used to store only the non-zero elements.

Why Use Sparse Matrix Representations?

  • Memory Efficiency: Drastically reduces storage requirements, especially for matrices with a very high density of zeros.
  • Computational Efficiency: Algorithms can be optimized to operate only on non-zero elements, saving processing time.

Common Representations:

  • Coordinate List (COO): Stores a list of tuples (row, column, value) for each non-zero element. This is simple but not always the most efficient for computations.
  • Compressed Sparse Row (CSR): A more complex but efficient representation. It uses three arrays:
    • values: Contains all non-zero values, row by row.
    • col_ind: Contains the column index for each value in the values array.
    • row_ptr: An array where row_ptr[i] points to the start of the i-th row in the values and col_ind arrays. Its size is number_of_rows + 1.
Standard 2D Array (Wasteful) 0 0 5 1 0 0 0 8 0 Coordinate List (COO) Row: 0 1 2 Col: 2 0 1 Val: 5 1 8
Comparison of a standard 2D array representation with the efficient Coordinate List (COO) for a sparse matrix.

3. Stacks (LIFO)

For a 5-Year-Old

Think of a stack of plates. You can only put a new plate on the very top. And when you want to take a plate, you can only take the one from the very top. The last plate you put on is the first one you take off. That's the rule!

The Deep Dive

A Stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. It is an Abstract Data Type (ADT) used by most programming languages. The name "stack" comes from the analogy of a stack of plates in a cafeteria.

Core Operations:

  • push(item): Adds an element to the top of the stack.
  • pop(): Removes and returns the element from the top of the stack. Returns an error if the stack is empty (Stack Underflow).
  • peek() or top(): Returns the top element of the stack without removing it.
  • isEmpty(): Returns true if the stack is empty, false otherwise.
  • isFull(): (For array-based implementation) Returns true if the stack is full, false otherwise (Stack Overflow).

Applications of Stacks:

  • Expression Evaluation and Conversion: Used to evaluate postfix/prefix expressions and convert infix to postfix/prefix.
  • Function Call Stack: When a function is called, its return address and local variables are "pushed" onto the call stack. When the function returns, they are "popped".
  • Undo/Redo Functionality: In text editors or graphic design software, each action is pushed onto a stack. "Undo" pops the last action.
  • Browser History: The "back" button can be implemented using a stack of visited URLs.
Stack Operations Stack 10 25 5 99 Top push(17)
Visual representation of a stack with a 'Top' pointer and a 'push' operation.

4. Queues (FIFO)

For a 5-Year-Old

Imagine you're in line for a ride at an amusement park. The first person who gets in line is the very first person to get on the ride. New people always join the line at the very back. You can't cut in front!

The Deep Dive

A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are inserted at one end (the rear or tail) and removed from the other end (the front or head). This is analogous to a real-world queue or line.

Core Operations:

  • enqueue(item): Adds an element to the rear of the queue.
  • dequeue(): Removes and returns the element from the front of the queue. Returns an error if the queue is empty (Queue Underflow).
  • front() or peek(): Returns the front element of the queue without removing it.
  • rear(): Returns the rear element of the queue without removing it.
  • isEmpty(): Returns true if the queue is empty, false otherwise.
  • isFull(): (For array-based implementation) Returns true if the queue is full (Queue Overflow).

Types of Queues:

  • Simple Queue: The basic FIFO structure. In an array implementation, it suffers from a problem where the queue appears "full" even when there's empty space at the beginning after several dequeues.
  • Circular Queue: Solves the problem of the simple queue by connecting the end of the array back to its start, forming a circle. The rear and front pointers wrap around to the beginning when they reach the end. This reuses the empty space.
  • Priority Queue: Each element has an associated priority. Elements with higher priority are dequeued before elements with lower priority, regardless of their insertion order.
  • Double-Ended Queue (Deque): Elements can be inserted and removed from both the front and the rear.
Circular Queue A B C D E Rear Front Linear View E D A B C Rear Front
Visualizing a Circular Queue and its equivalent linear array representation, showing how the 'Front' and 'Rear' pointers wrap around.

5. Linked Lists

For a 5-Year-Old

A linked list is like a treasure hunt. You find the first clue (the "head"). That clue tells you where to find the second clue. The second clue tells you where the third one is, and so on. You can add a new clue anywhere by just changing the clue before it to point to the new one, and the new one points to the old next clue. You don't need to move any other clues!

The Deep Dive

A Linked List is a linear data structure, but unlike arrays, its elements are not stored at contiguous memory locations. Instead, elements are linked using pointers. A linked list consists of nodes where each node contains a data field and a reference (or pointer) to the next node in the sequence.

The Node and Self-Referential Structures:

The fundamental building block of a linked list is the Node. A node is typically implemented using a self-referential structure, which is a structure that contains a pointer to a structure of its own type.

struct Node {
    int data;
    struct Node* next; // Pointer to the next node
};

Advantages over Arrays:

  • Dynamic Size: Linked lists can grow and shrink at runtime by allocating and deallocating memory. No need to know the size in advance.
  • Efficient Insertions/Deletions: Adding or removing a node is efficient (O(1) if you have a pointer to the node) as it only involves updating a few pointers, unlike arrays which may require shifting many elements.

Disadvantages compared to Arrays:

  • Random Access is Not Allowed: To access an element at the n-th position, you must traverse the list from the head, one node at a time (O(n) time).
  • Extra Memory Space: Each node requires extra space for the pointer.
  • Poor Cache Locality: Since nodes are not in contiguous memory, there are more cache misses, which can lead to slower performance in some scenarios.
Singly Linked List Structure Head 10 Next 25 Next 5 Next NULL Node 1 Node 2 Node 3 Data Pointer
Anatomy of a Singly Linked List, showing the Head pointer, individual nodes with Data and Next parts, and the terminating NULL pointer.

6. Linked List Variations

For a 5-Year-Old

Doubly: Imagine a two-way street. Each house (node) knows the house to its right AND the house to its left. You can walk forward or backward.

Circular: Imagine a group of friends holding hands in a circle. The last friend is holding the first friend's hand. If you start walking, you'll eventually get back to where you started.

The Deep Dive

Singly vs. Doubly vs. Circular Linked Lists:

  • Singly Linked List: Traversal is only possible in one direction (forward). Each node points only to its successor.
  • Doubly Linked List: Each node contains two pointers: one to the next node and one to the previous node. This allows for traversal in both directions (forward and backward). It requires more memory per node but simplifies certain operations like deletion.
  • Circular Linked List: Can be a variation of singly or doubly linked lists. The 'next' pointer of the last node points back to the head node instead of being NULL. This forms a circle. It is useful in applications where you need to cycle through the elements repeatedly, such as in operating system task schedulers or multiplayer game turn management.
Doubly Linked List Prev 10 Next Prev 25 Next NULL NULL Circular Linked List 10 Next 25 Next 5 Next Last node points to first
Visual comparison of Doubly Linked List (bidirectional pointers) and Circular Linked List (last node points to the first).
Module 3: Trees

1. Introduction to Trees and Basic Terminology

Imagine a Family Tree...

Think of a tree like your family tree. At the very top is your grandparent (the root). Your parent is a child of the grandparent. You are a child of your parent. You and your siblings are at the same level. People who don't have any children yet are at the very ends, like leaves on a real tree. It's just a way to connect things in a hierarchy, with one main starting point at the top.

G Root P Parent A Parent Y Leaf S Child Sibling
Figure 1: A tree diagram showing root, parent, child, sibling, and leaf nodes.
Formal Definition and Terminology

A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It has one unique top-most node called the root. Each node (except the root) is connected by a single directed edge from exactly one other node, its parent. A node may have zero or more children. Nodes with the same parent are called siblings. A node with no children is a leaf or external node. Nodes with at least one child are internal nodes.

The level of a node is the number of edges on the unique path from the root to that node. The root is at level 0. The height of a node is the number of edges on the longest path from that node to a leaf. The height of the tree is the height of the root. The depth of a node is the number of edges from the node to the tree's root node.

Edge Cases & Properties: A tree with `n` nodes will always have exactly `n-1` edges. A single node by itself is a valid tree. An empty structure (no nodes) is often considered an empty tree.

Real-World Links: File systems on computers (directories and subdirectories), the DOM (Document Object Model) in web browsers, organizational charts, and XML/JSON data parsing all rely on tree structures.

2. Binary Trees

A "Yes/No" Decision Tree

A binary tree is a special kind of tree where every rule-maker (every parent node) can make at most two decisions. Think of a "20 Questions" game. Each question can only lead to a "yes" path or a "no" path. It's a tree where each person can have at most two children. We call them the "left child" and the "right child".

Binary Tree Non-Binary Tree
Figure 2: Comparison of a Binary Tree (max 2 children) and a Non-Binary Tree.
Formal Definition, Properties, and Representation

A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. The distinction between left and right is significant, even if a node only has one child.

Key Properties:

Maximum nodes at level i = 2i
Maximum nodes in a tree of height h = 2(h+1) - 1

Proof of Max Nodes at Level i: By induction. Base case: Level 0 has 2^0 = 1 node (the root). Inductive step: Assume level `i` has 2^i nodes. Since each node can have at most 2 children, the next level, `i+1`, will have at most 2 * 2^i = 2^(i+1) nodes. QED.

Representation:

  • Linked Representation (using pointers): Each node is a structure containing a data field and two pointers: `leftChild` and `rightChild`. This is flexible and works for any binary tree shape.
  • Array Representation: Efficient for complete binary trees. The root is at index 0. For a node at index `i`:
    • Parent is at index `floor((i-1)/2)`
    • Left child is at index `2i + 1`
    • Right child is at index `2i + 2`
    This representation wastes space for sparse trees but is cache-friendly.
Array Representation of a Complete Binary Tree A B C D E Array: A [0] B [1] C [2] D [3] E [4]
Figure 3: Mapping a complete binary tree to an array.

3. Tree Traversal Algorithms

How to Visit Every Room in a Castle

Imagine you're in a castle (the root) and want to visit every room. There are three main ways to do it systematically:

  • Pre-order: You visit the room you're in FIRST (take a photo), then explore the entire left tower, then explore the entire right tower. (Root -> Left -> Right)
  • In-order: You explore the entire left tower FIRST, then visit the main room, then explore the right tower. (Left -> Root -> Right)
  • Post-order: You explore the left tower FIRST, then the right tower, and ONLY when you're done with both do you visit the main room. (Left -> Right -> Root)
Traversal Orders on the Same Tree F B G A D I C E Pre-order: F -> B -> A -> D -> C -> E -> G -> I In-order: A -> B -> C -> D -> E -> F -> G -> I Post-order: A -> C -> E -> D -> B -> I -> G -> F
Figure 4: Pre-order, In-order, and Post-order traversal paths and outputs.
Algorithms and Applications

Tree traversal is the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. These traversals are typically defined recursively.

Algorithm PreOrder(node): if node is null, return print(node.data) // Process PreOrder(node.left) // Recurse on left PreOrder(node.right) // Recurse on right Algorithm InOrder(node): if node is null, return InOrder(node.left) // Recurse on left print(node.data) // Process InOrder(node.right) // Recurse on right Algorithm PostOrder(node): if node is null, return PostOrder(node.left) // Recurse on left PostOrder(node.right) // Recurse on right print(node.data) // Process
Example: In-Order Traversal on the tree in Figure 4

1. Start at root F. Go left to B. Go left to A. A has no left child. Process A. A has no right child. Return to B.

2. Process B. Go right to D. Go left to C. C has no left child. Process C. C has no right child. Return to D.

3. Process D. Go right to E. E has no left child. Process E. E has no right child. Return to D, then B, then F.

4. Process F. Go right to G. G has no left child. Process G. Go right to I. I has no left child. Process I. I has no right child. Return.

Final Output: A, B, C, D, E, F, G, I

Applications:

  • In-order: For a Binary Search Tree (BST), this traversal visits nodes in ascending sorted order. Used to get sorted data from a BST.
  • Pre-order: Used to create a copy of a tree. Also useful for prefix notation (Polish notation) in expression trees.
  • Post-order: Used to delete a tree (must delete children before the parent). Also useful for postfix notation (Reverse Polish notation) in expression trees.

4. Binary Search Trees (BST)

A Super-Organized Bookshelf

A Binary Search Tree is like a bookshelf where every book is placed according to a strict rule. The main book on the top shelf is the root. Any book on the left shelf must have a title that comes BEFORE the main book's title alphabetically. Any book on the right shelf must have a title that comes AFTER. This rule applies to every single shelf. This makes finding a book incredibly fast! You just look at a book, and you instantly know which half of the shelf to ignore.

Binary Search Tree Property Valid BST 50 30 70 < 50 > 50 Invalid BST 50 80 70 Error! 80 is not < 50
Figure 5: A valid BST vs. an invalid one, demonstrating the core property.
Properties, Insertion, and Deletion

A Binary Search Tree (BST) is a binary tree with a special ordering property: for any given node `N`, all values in its left subtree are less than `N`'s value, and all values in its right subtree are greater than `N`'s value. (Assuming no duplicate keys for simplicity). This property allows for efficient searching, insertion, and deletion, typically with an average time complexity of O(log n).

Insertion Algorithm & Example

To insert a value, start at the root. If the tree is empty, the new value becomes the root. Otherwise, compare the new value with the current node. If it's smaller, go left; if larger, go right. Repeat until you find an empty spot (a null child pointer) and insert the new node there.

Algorithm Insert(node, key): if node is null: return new Node(key) if key < node.data: node.left=Insert(node.left, key) else if key> node.data: node.right = Insert(node.right, key) return node

Example: Insert 60, 40, 70, 20, 50 into an empty BST.

1. 60 becomes root. 2. 40 is < 60, goes left. 3. 70 is> 60, goes right. 4. 20 is < 60, go left. 20 is < 40, goes left. 5. 50 is < 60, go left. 50 is> 40, goes right.

Deletion Algorithm & Cases

Deleting a node is more complex and has three cases:

  1. Node is a leaf (no children): Simply remove it by setting its parent's pointer to null.
  2. Node has one child: Bypass the node by connecting its parent directly to its single child.
  3. Node has two children: This is the tricky case. Find the node's in-order successor (the smallest value in its right subtree) or in-order predecessor (the largest value in its left subtree). Copy the successor's value to the node to be deleted, then delete the successor node (which is guaranteed to be in case 1 or 2).
Deleting Node '50' (Case 3: Two Children) Before 50 30 70 60 80 Successor → After 60 30 70 80
Figure 6: Deleting a node with two children by replacing it with its in-order successor.

5. Full vs. Complete Binary Trees

Perfectly Packed vs. Perfectly Filled

A Full binary tree is like a family where every parent has exactly two children. No one has just one child. It's very strict.

A Complete binary tree is like filling seats in a theater row by row. You fill all the seats in the front row completely before moving to the next. And within a row, you fill from left to right, with no empty seats in the middle. The last row might not be full, but any empty seats must be to the far right.

Full vs. Complete Binary Trees Full Tree Complete Tree
Figure 7: Visual comparison of a Full tree (every internal node has 2 children) and a Complete tree (filled left-to-right).
Formal Definitions and Comparison

Full Binary Tree (or Proper Binary Tree): A binary tree in which every node has either 0 or 2 children. No node has only one child.

Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, and all nodes in the last level are as far left as possible.

Property Full Binary Tree Complete Binary Tree
Children per Node Either 0 or 2 0, 1, or 2
Shape Can be unbalanced Must be as balanced as possible
Node Count If `i` are internal nodes, leaves = `i+1`. Total nodes = `2i+1`. Relationship between height and nodes is precise: `2^h <= n <=2^(h+1)-1`.
Primary Use Expression trees. Efficient array representation (Heaps).

Key Relationship: A tree can be both Full and Complete (like the "Full Tree" example in Figure 7). A tree can be Complete but not Full (like the "Complete Tree" example, where node 90 has one child). A tree can be Full but not Complete (if the right subtree is much deeper than the left).

Module 4: Graphs
Explained to a 5-Year-Old:

Imagine a big map of a city. The places you can visit (like your house, the park, the school) are called vertices. The roads that connect these places are called edges. A graph is just a way to draw this map so we can see how all the places are connected to each other!

Formal Definition & Terminology:

A Graph is an ordered pair G = (V, E) comprising a set V of vertices (also called nodes) and a set E of edges, which are 2-element subsets of V.

  • Vertex (Node): A fundamental unit of the graph. Represents an entity or object.
  • Edge (Arc): A link between two vertices. Represents a relationship or connection.
  • Undirected Graph: Edges have no direction. The edge (A, B) is identical to (B, A). (e.g., a two-way road).
  • Directed Graph (Digraph): Edges have a direction. The edge (A -> B) is different from (B -> A). (e.g., a one-way street).
  • Weighted Graph: Each edge has a value (a "weight") associated with it, representing cost, distance, or time.
  • Degree of a Vertex: The number of edges incident to it. For a directed graph, it has an in-degree (incoming edges) and an out-degree (outgoing edges).
  • Path: A sequence of vertices where each adjacent pair is connected by an edge.
  • Cycle: A path that starts and ends at the same vertex.

Graph Representation: Adjacency Matrix

Explained to a 5-Year-Old:

Think of a giant bingo card or a spreadsheet. You list all the places down the side and across the top. If there's a direct road between "Park" and "School," you put a "1" in the box where they meet. If there's no road, you put a "0". It's like a checklist of all possible connections.

Formal Definition & Analysis:

An Adjacency Matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

For a graph with V vertices, the matrix is of size V x V. The entry at row `i` and column `j`, `A[i][j]`, is:

  • 1 if there is an edge from vertex `i` to vertex `j`.
  • 0 otherwise.

For a weighted graph, the entry is the weight of the edge instead of 1.

Space Complexity: O(V²)

Advantages:

  • Constant time complexity O(1) to check if an edge exists between two vertices.
  • Simple to implement.

Disadvantages:

  • Consumes a lot of memory (V² space), even if the graph is sparse (has few edges).
  • Adding/Removing a vertex is expensive as it requires resizing the matrix.
Graph 0 1 2 Adjacency Matrix 0 1 2 0 0 1 1 1 1 0 1 2 1 1 0

Figure 1: An undirected graph and its corresponding adjacency matrix. The highlighted cells (e.g., A[0][1]=1) correspond to the edges in the graph.

Graph Representation: Adjacency List

Explained to a 5-Year-Old:

Imagine you have a contact list on your phone. For each person (a vertex), you keep a list of all their friends (the vertices they are connected to). So, for "Mom," you have a list that includes "Grandma" and "Dad." This is much smaller than the giant bingo card if most people only have a few friends!

Formal Definition & Analysis:

An Adjacency List represents a graph as an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents a vertex that forms an edge with the array vertex.

Space Complexity: O(V + E)

Advantages:

  • Memory efficient for sparse graphs, as it only stores existing edges.
  • Adding/Removing a vertex or edge is relatively easy.

Disadvantages:

  • Checking if an edge exists between two vertices can be slow, O(V) in the worst case, as it may require traversing a linked list.
Graph 0 1 2 Adjacency List 0 1 2 NULL 1 0 2 NULL 2 0 1 NULL

Figure 2: An undirected graph and its corresponding adjacency list. The array index corresponds to the vertex, and the linked list contains its adjacent vertices.

Graph Traversal: Breadth-First Search (BFS)

Explained to a 5-Year-Old:

Imagine you're dropping a pebble in a pond. The ripples spread out in circles. BFS explores a graph like that. It starts at one place, then visits all its immediate neighbors (the first ripple), then visits all of *their* neighbors (the second ripple), and so on, layer by layer. It's great for finding the shortest path in a map where all roads are equal length.

Algorithm & Analysis:

BFS is a graph traversal algorithm that explores vertices in layers. It starts at a given source vertex and explores all of its immediate neighbors. Then, for each of those neighbors, it explores their unvisited neighbors. It uses a Queue data structure to keep track of the vertices to visit next.

Algorithm Steps:

  1. Mark the starting vertex as visited and enqueue it.
  2. Loop as long as the queue is not empty:
    1. Dequeue a vertex `u`.
    2. For each neighbor `v` of `u`:
      1. If `v` has not been visited, mark it as visited and enqueue `v`.
Time Complexity: O(V + E)

Applications:

  • Finding the shortest path in an unweighted graph.
  • Finding all connected components in a graph.
  • Web crawlers use BFS to build indexes.
BFS Traversal starting from Vertex A A B C D E F Queue State A Front Rear Traversal Order: A -> B -> C -> D -> E -> F

Figure 3: BFS traversal starting from vertex A. Colors indicate the layer in which the vertex is visited (Red: Layer 0, Orange: Layer 1, Green: Layer 2).

Graph Traversal: Depth-First Search (DFS)

Explained to a 5-Year-Old:

Imagine you're exploring a maze. You pick one path and follow it as far as you can go until you hit a dead end. When you do, you turn around and go back to the last place where you had a choice, and try a different path. DFS explores a graph just like that: it goes deep down one branch before coming back to explore others.

Algorithm & Analysis:

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented using a Stack (iterative version) or through recursion (where the call stack acts as the stack).

Algorithm Steps (Recursive):

  1. Mark the current vertex `u` as visited.
  2. For each neighbor `v` of `u`:
    1. If `v` has not been visited, recursively call DFS on `v`.
Time Complexity: O(V + E)

Applications:

  • Detecting cycles in a graph.
  • Topological sorting.
  • Finding strongly connected components.
  • Solving puzzles with only one solution (like mazes).
DFS Traversal starting from Vertex A A B C D E F Call Stack (Conceptual) B A Top One possible Traversal Order: A -> B -> D -> E -> C -> F

Figure 4: DFS traversal starting from vertex A. The dashed line shows the deep path taken. Colors indicate the order of visitation. The call stack shows the state during the exploration of vertex B.

Module 5: Sorting and Searching

1. Introduction to Sorting

Explained for a 5-Year-Old:

Imagine you have a big box of colorful toy cars all mixed up. Sorting is like putting all the red cars in one pile, all the blue cars in another, and so on, until everything is neat and easy to find. We do this with numbers on a computer, too, to arrange them from smallest to biggest (or biggest to smallest).

Formal Definition & Importance:

Sorting is the algorithmic process of arranging elements in a sequence (e.g., numerical order, lexicographical order) according to a total order. The efficiency of a sorting algorithm is critical, as it forms the basis for many other complex algorithms (like searching) and for optimizing data storage. A sorted array allows for drastically faster searching (e.g., Binary Search) compared to an unsorted one (Linear Search). The primary metrics for evaluating sorting algorithms are Time Complexity (how the runtime scales with input size `n`) and Space Complexity (how much extra memory is required).

2. Internal Sorting Algorithms

2.1 Insertion Sort

Explained for a 5-Year-Old:

Think about how you sort a hand of playing cards. You pick up one card at a time from the messy pile and slide it into its correct spot among the cards you're already holding, which are already sorted. You keep doing this until all the cards from the pile are in your hand, in perfect order.

Algorithm & Analysis:

Insertion Sort is a simple, in-place comparison-based sorting algorithm. It builds the final sorted array one item at a time. It iterates through the input elements and, for each element, finds its correct position in the sorted part of the array and inserts it there.

Algorithm InsertionSort(A[0...n-1]) for i = 1 to n-1 key = A[i] j = i - 1 // Move elements of A[0..i-1] that are greater than key // to one position ahead of their current position while j >= 0 and A[j] > key A[j+1] = A[j] j = j - 1 end while A[j+1] = key end for end Algorithm

Time Complexity: Best Case: O(n) - when the array is already sorted. Worst Case: O(n²) - when the array is sorted in reverse. Average Case: O(n²). Space Complexity: O(1) - it sorts in-place. Stability: Yes, it is a stable sort as it does not change the relative order of elements with equal keys. It is efficient for small datasets and nearly sorted data.

Pass 1: Insert 2 5 2 4 6 1 3

Figure 1: First pass of Insertion Sort on [5, 2, 4, 6, 1, 3]. The element 2 is inserted into the sorted subarray [5].

Exam Walkthrough:

Sort the list: [12, 65, 34, 9, 56, 43, 10] (from 2022 Q19a). Initial: [12, 65, 34, 9, 56, 43, 10].
Pass 1 (key=65): [12, 65, 34, 9, 56, 43, 10] (no change).
Pass 2 (key=34): [12, 34, 65, 9, 56, 43, 10].
Pass 3 (key=9): [9, 12, 34, 65, 56, 43, 10].
...and so on, until the final sorted array: [9, 10, 12, 34, 43, 56, 65].

2.2 Merge Sort

Explained for a 5-Year-Old:

Imagine you have a huge pile of unsorted blocks. You split the pile into two smaller piles. Then you split those piles again, and again, until every pile has only one block (which is already sorted!). Then you start merging them back together: you take two single-block piles, sort them to make a two-block pile. Then you take two two-block piles and merge them into a perfect four-block pile, and so on, until you have one big, perfectly sorted pile again.

Algorithm & Analysis:

Merge Sort is a classic Divide and Conquer algorithm. It divides the unsorted list into n sublists, each containing one element (which are considered sorted). Then it repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining, which is the sorted list.

Algorithm MergeSort(A, p, r) if p < r q=floor((p+r)/2) MergeSort(A, p, q) MergeSort(A, q+1, r) Merge(A, p, q, r) end if end Algorithm

Time Complexity: Best, Average, and Worst Case are all O(n log n). This is because the list is divided log n times, and each level of division requires a linear O(n) merge operation. Space Complexity: O(n) - it requires an auxiliary array of the same size as the input for the merging process. Stability: Yes, it is a stable sort. Its consistent O(n log n) performance makes it highly reliable for large datasets.

Divide Phase [38, 27, 43, 3, 9, 82, 10] [38, 27, 43] [3, 9, 82, 10] [38, 27] [43] [38] [27] Conquer (Merge) Phase [27, 38] [43] [27, 38, 43] [3, 9, 10, 82] [3, 9, 10, 27, 38, 43, 82]

Figure 2: Merge Sort's Divide and Conquer process on an example array.

3. Searching Algorithms

3.1 Binary Search

Explained for a 5-Year-Old:

Imagine you're looking for a specific page in a very thick book. You wouldn't start from page 1 and flip through every single page. Instead, you'd open the book right in the middle. Is the page number you need higher or lower than the page you're on? If it's lower, you'll only look in the first half of the book. You keep cutting the search area in half like this until you find the exact page. It's super fast!

Algorithm & Analysis:

Binary Search is a highly efficient searching algorithm that works on the principle of divide and conquer. It requires the array to be sorted beforehand. The algorithm compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half. This process is repeated until the value is found or the interval is empty.

Algorithm BinarySearch(A[0...n-1], key) low = 0 high = n-1 while low <= high mid=floor((low + high) / 2) if A[mid]==key return mid // Element found else if A[mid] < key low=mid + 1 else high=mid - 1 end if end while return -1 // Element not found end Algorithm

Time Complexity: Best Case: O(1) - when the middle element is the target. Worst and Average Case: O(log n) - because the search space is halved in each iteration. Space Complexity: O(1) for the iterative version. O(log n) for the recursive version due to the call stack. Its efficiency makes it indispensable for searching in large, static datasets.

Search for key = 23 in [3, 8, 12, 15, 23, 31, 42] 3 8 12 15 23 31 42 mid=3, A[mid]=15 15 < 23, search right

Figure 3: First step of Binary Search. The middle element (15) is less than the key (23), so the search continues in the right half of the array.

4. Hashing

4.1 Concept & Hash Functions

Explained for a 5-Year-Old:

Imagine a giant coat check room with a hundred hooks, numbered 0 to 99. The "hash function" is a magic rule. If you give the attendant your coat (your "data"), they look at the name tag (your "key") and use the rule to instantly know which exact hook to put it on. For example, the rule might be "add up the letters in the name and find the remainder when you divide by 100". This makes finding your coat super fast later!

Formal Definition:

Hashing is a technique used to uniquely identify a specific object from a group of similar objects. It uses a hash function `h(k)` to compute an index into an array of buckets or slots, from which the desired value can be found. The primary goal is to map keys to array indices in a way that allows for O(1) average-case time complexity for search, insert, and delete operations.

Collision: Since the number of possible keys is typically much larger than the number of array slots, a collision occurs when the hash function maps two different keys to the same index. A good hash function minimizes collisions, but a robust system must have a collision resolution technique to handle them.

Common Hash Functions:

  • Division Method: h(k) = k mod m, where `m` is the table size. `m` should be a prime number to reduce collisions.
  • Mid-Square Method: Square the key `k`, then extract the middle `r` digits as the hash value. Useful when key sizes vary.
  • Folding Method: Divide the key `k` into equal-sized parts (except possibly the last), then sum the parts to get the hash value.
Hash Function Process Key (k) Hash Function h(k) Index

Figure 4: The process of hashing a key to obtain an array index.

4.2 Collision Resolution Techniques

Explained for a 5-Year-Old:

Sometimes, the magic rule tells the attendant to put two different coats on the same hook! That's a "collision". How do they solve it?

Open Chaining: The attendant just hangs a second hook from the first one and puts the new coat there. A chain of coats!

Linear Probing: The attendant sees the hook is full, so they try the very next hook. If that's full, they try the next one, and so on, until they find an empty hook.

Techniques & Analysis:

1. Open Addressing (Closed Hashing): All elements are stored within the hash table itself. When a collision occurs, the algorithm probes for the next available slot according to a specific rule.

  • Linear Probing: If slot `h(k)` is occupied, try `h(k) + 1`, then `h(k) + 2`, and so on, wrapping around to the beginning of the table if necessary. Simple but suffers from primary clustering, where collided keys form long contiguous blocks.
  • Double Hashing: Uses a second hash function `h2(k)` to determine the probe sequence. The i-th probe is at `(h(k) + i * h2(k)) mod m`. This helps to avoid clustering as the step size varies for different keys. `h2(k)` must be chosen carefully (e.g., `h2(k) = R - (k mod R)` where `R` is a prime smaller than `m`).

2. Chaining (Open Hashing): The hash table is an array of pointers, each pointing to the head of a linked list. All keys that hash to the same index `i` are stored in the linked list at `A[i]`. Insertion involves appending to the list. Searching involves computing the hash and then traversing the list. Deletion is straightforward in a linked list. This method avoids clustering entirely, but requires extra memory for the pointers.

Collision Resolution: Chaining vs Linear Probing Chaining (h(k)=k mod 7) 0 1 2 3 4 5 6 23 30 26 Linear Probing (h(k)=k mod 7) 0 1 2 3 4 23 30 (h=3) (h=2, coll. -> 4)

Figure 5: Comparing Chaining and Linear Probing for inserting keys 23 and 30 (h(23)=3, h(30)=2) into a table of size 7.

Exam Walkthrough (from 2022 Q20b & 2023 Q20a):

Keys: {16, 21, 23, 50, 19, 26}. Table Size: 7. Hash Function: H(K) = K mod 7.

Open Chaining:
H(16)=2, H(21)=0, H(23)=2, H(50)=1, H(19)=5, H(26)=5.
Slot 0: [21] -> Slot 1: [50] -> Slot 2: [16] -> [23] -> Slot 5: [19] -> [26].

Linear Probing:
H(16)=2 -> Insert at 2. [ , ,16, , , , ]
H(21)=0 -> Insert at 0. [21, ,16, , , , ]
H(23)=2 -> Collides at 2, try 3. Insert at 3. [21, ,16,23, , , ]
H(50)=1 -> Insert at 1. [21,50,16,23, , , ]
H(19)=5 -> Insert at 5. [21,50,16,23, ,19, ]
H(26)=5 -> Collides at 5, try 6. Insert at 6. [21,50,16,23, ,19,26]

5. Heaps

5.1 Max Heap & Min Heap

Explained for a 5-Year-Old:

A Max-Heap is like a family tree where every parent is older (has a bigger number) than all their children. The oldest grandparent of all is at the very top of the tree. A Min-Heap is the opposite: every parent is younger (has a smaller number) than all their children, and the youngest baby is at the top.

Formal Definition & Properties:

A Heap is a specialized tree-based data structure that satisfies the heap property. It is also a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right.

Max-Heap Property: For any given node `i`, the value of `i` is greater than or equal to the value of its children. `A[parent(i)] >= A[i]`. The largest element is always at the root (index 0).

Min-Heap Property: For any given node `i`, the value of `i` is less than or equal to the value of its children. `A[parent(i)] <= A[i]`. The smallest element is always at the root.

Array Representation: A complete binary tree can be efficiently stored in an array. For an element at index `i`:

Parent(i) = floor((i-1)/2) | Left Child(i) = 2*i + 1 | Right Child(i) = 2*i + 2
This representation avoids pointer overhead and is crucial for Heap Sort.

Application: Heaps are the basis for Priority Queues (where the highest/lowest priority item is always needed next) and the Heap Sort algorithm.

Max-Heap Example 90 80 70 50 40 Array Representation 0 1 2 3 4 90 80 70 50 40

Figure 6: A Max-Heap tree structure and its corresponding array representation. Note that every parent node is greater than its children.

Reference: 2024 Exam Scheme & 2026 Handbook for CST201 Data Structures