Primitive Data Type, Hashing, Collision and Collision Handling

1. Primitive Data Type (2 marks)

Definition: A primitive data type is a basic, built-in data type provided directly by a programming language. It is the most fundamental type of data that cannot be broken down into simpler data types. These types are predefined by the language and have a fixed size in memory.

Examples:

For example, in C/Java: int age = 21; -- here int is a primitive data type storing a whole number.

2. Advantages of Hashing (2 marks)

Hashing is a technique of mapping keys to positions in a hash table using a hash function.

Advantages:

1. Fast Search (O(1) average): Hashing provides constant time average-case complexity for search, insert, and delete operations, which is much faster than linear search O(n) or binary search O(log n).

2. Efficient Storage and Retrieval: Data can be stored and retrieved very efficiently using a key, making it ideal for dictionaries, databases, and caches.

3. Direct Address Mapping: The hash function directly computes the storage location, avoiding sequential scanning.

4. Useful for Large Data Sets: Even with a large number of records, hashing maintains near-constant performance.

5. Easy Implementation of Symbol Tables: Compilers use hashing to implement symbol tables efficiently.

3. Hash Collision and Collision Handling (6 marks)

What is Hash Collision?

A hash collision occurs when two or more different keys produce the same hash value (index) using the hash function, meaning they map to the same location in the hash table.

My Own Example:

Hash Function:

h(key) = key mod 7

Hash Table Size = 7 (indices 0 to 6)

Keys to insert: 10, 20, 17, 24, 31

Keys 10, 17, 24, and 31 all hash to index 3 -- this is a hash collision.

Collision Handling Techniques

Method 1: Chaining (Open Hashing)

In chaining, each slot of the hash table holds a linked list. All keys that hash to the same index are stored in the linked list at that index.

After inserting 10, 20, 17, 24, 31 using chaining:

Index 0: NULL
Index 1: NULL
Index 2: NULL
Index 3: [10] -> [17] -> [24] -> [31] -> NULL
Index 4: NULL
Index 5: NULL
Index 6: [20] -> NULL

Advantages of Chaining:

• Simple to implement
• Hash table never becomes full
• Deletion is easy

Method 2: Open Addressing - Linear Probing (Closed Hashing)

In linear probing, if a collision occurs at index i, we check the next slot i+1, then i+2, and so on until an empty slot is found.

Formula:

h(key, i) = (h(key) + i) mod TableSize
where i = 0, 1, 2, ... (probe number)

Inserting 10, 20, 17, 24, 31 using Linear Probing (Table Size = 7):

Final Hash Table:

Index 0: 31
Index 1: NULL
Index 2: NULL
Index 3: 10
Index 4: 17
Index 5: 24
Index 6: 20

Advantages of Linear Probing:

• No extra memory needed for pointers
• Better cache performance

Disadvantage:

• Primary clustering -- long chains of filled slots can form, slowing down operations.

Summary Table

Conclusion: Hash collision is unavoidable in practice, but with proper handling techniques like chaining or open addressing the table keeps giving almost constant time access. Chaining is preferred when the number of keys is not known in advance or when deletions are frequent, while linear probing suits a table of fixed size where memory for pointers is not available. In both cases the load factor should be kept low (roughly 0.7 or less for open addressing) so that the average number of probes stays close to one.

Static vs Dynamic List Structure & Linked List Implementation of Stack and Queue

(a) Static vs Dynamic List Structure

(b) Linked List Implementation of Stack and Queue

A. Linked List Implementation of Stack

A stack is a linear data structure that follows the LIFO (Last In First Out) principle. In linked list implementation, each node contains data and a pointer to the next node. The top pointer always points to the most recently inserted node.

Node Structure

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

[data | next] --> [data | next] --> [data | next] --> NULL
   ^
  TOP

i. PUSH Operation (Insert at top)

Steps:

1. Create a new node.
2. Assign data to the new node.
3. Make new node's next point to current top.
4. Update top to the new node.

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Stack Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;   // new node points to old top
    top = newNode;         // top updated to new node
}

Diagram (Push 10, 20, 30):

After Push(10):   TOP -> [10 | NULL]

After Push(20):   TOP -> [20 | *] -> [10 | NULL]

After Push(30):   TOP -> [30 | *] -> [20 | *] -> [10 | NULL]

ii. POP Operation (Delete from top)

Steps:

1. Check if stack is empty (top == NULL).
2. Store the top node in a temporary pointer.
3. Move top to the next node.
4. Free the temporary node.

void pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return;
    }
    struct Node* temp = top;
    printf("Popped: %d\n", temp->data);
    top = top->next;   // move top to next node
    free(temp);        // free old top
}

iii. PEEK / Display

void peek() {
    if (top == NULL)
        printf("Stack is Empty\n");
    else
        printf("Top element: %d\n", top->data);
}

B. Linked List Implementation of Queue

A queue is a linear data structure that follows the FIFO (First In First Out) principle. In linked list implementation, two pointers are maintained:

• FRONT -- points to the first node (deletion end)
• REAR -- points to the last node (insertion end)

Node Structure

struct Node {
    int data;
    struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;

FRONT                          REAR
  |                              |
[data|next] -> [data|next] -> [data|NULL]

i. ENQUEUE Operation (Insert at rear)

Steps:

1. Create a new node.
2. Assign data to the new node; set its next to NULL.
3. If queue is empty, both front and rear point to new node.
4. Otherwise, link the current rear's next to new node and update rear.

void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Queue Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) {          // queue is empty
        front = rear = newNode;
        return;
    }
    rear->next = newNode;        // link at rear
    rear = newNode;              // update rear
}

Diagram (Enqueue 10, 20, 30):

After Enqueue(10):
FRONT -> [10|NULL] <- REAR

After Enqueue(20):
FRONT -> [10|*] -> [20|NULL] <- REAR

After Enqueue(30):
FRONT -> [10|*] -> [20|*] -> [30|NULL] <- REAR

ii. DEQUEUE Operation (Delete from front)

Steps:

1. Check if queue is empty (front == NULL).
2. Store the front node in a temporary pointer.
3. Move front to the next node.
4. If front becomes NULL, set rear to NULL as well.
5. Free the temporary node.

void dequeue() {
    if (front == NULL) {
        printf("Queue Underflow\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", temp->data);
    front = front->next;         // move front forward
    if (front == NULL) {         // queue became empty
        rear = NULL;
    }
    free(temp);                  // release the old front node
}

Diagram (Dequeue from FRONT -> [10|] -> [20|] -> [30|NULL] <- REAR):

After Dequeue() (removes 10):
FRONT -> [20|*] -> [30|NULL] <- REAR

After Dequeue() (removes 20):
FRONT -> [30|NULL] <- REAR

After Dequeue() (removes 30):
FRONT = NULL, REAR = NULL   (queue is empty again)

iii. DISPLAY Operation

void display() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }
    struct Node* temp = front;
    printf("Queue (front to rear): ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Conclusion

A linked list removes the fixed-size limitation of an array, so both structures grow and shrink with the data. In the stack only one pointer (top) is needed and both PUSH and POP work at the head of the list, while the queue needs two pointers, since ENQUEUE attaches at rear and DEQUEUE detaches at front. In both cases every operation touches a constant number of nodes, so PUSH, POP, ENQUEUE and DEQUEUE all run in O(1) time, and overflow occurs only when malloc itself fails.

BFS and DFS Graph Traversal

STEP 1 - EXTRACT: Given Data

The question asks to traverse a graph using BFS and DFS, but the actual graph (the figure/diagram) is not included in the text provided. No adjacency list, adjacency matrix, edge set, or vertex set is given.

Missing data: The specific graph (vertices and edges) required to perform the traversal is not available. Without it, the exact traversal orders cannot be determined, since traversal output depends entirely on the graph structure and the chosen starting vertex.

Because the graph is unreadable/absent, I will present the methodology and demonstrate it on a clearly labelled representative example, while flagging that the numeric traversal order is example-dependent and not the "official" answer to the missing figure.

STEP 2 - SOLVE (using a representative example graph)

Example Graph

      1
     / \
    2   3
   / \    \
  4   5    6

Adjacency list:

• $1 \to 2, 3$
• $2 \to 4, 5$
• $3 \to 6$
• $4 \to$ (none)
• $5 \to$ (none)
• $6 \to$ (none)

Breadth First Search (BFS)

Idea: Use a Queue (FIFO); visit level by level.

BFS Order: $$\boxed{1 \to 2 \to 3 \to 4 \to 5 \to 6}$$

Depth First Search (DFS)

Idea: Use a Stack (LIFO) or recursion; go deep before backtracking.

DFS Order: $$\boxed{1 \to 2 \to 4 \to 5 \to 3 \to 6}$$

Comparison

Note to examiner/student: The traversal orders above are valid only for the assumed example graph. If the real exam figure differs, apply the same procedure (queue for BFS, stack/recursion for DFS) to that graph's adjacency list to obtain the correct order.

Given Data

Infix expression to convert: $$7 * 8 + 10 - 2$$

Operator precedence:

• *, / : higher
• +, - : lower

Associativity: left to right.

Conversion Rules (Stack Method)

1. Scan tokens left to right.
2. Operand → append to output.
3. Operator → pop operators from stack with precedence greater than or equal to the current one (for left-associative operators), append them to output, then push the current operator.
4. End → pop all remaining operators to output.

Step-by-Step Trace

Verification (evaluate postfix)

Given values: $7,8,+,*$ etc. Compute $7 \times 8 = 56$; $56 + 10 = 66$; $66 - 2 = 64$. Infix: $7 \times 8 + 10 - 2 = 56 + 10 - 2 = 64$. ✓ Matches.

Result

$$\boxed{7\ 8\ *\ 10\ +\ 2\ -}$$

Time and Space Complexity + Round Robin Algorithm for MST

(a) Time and Space Complexity

Time Complexity

Time complexity is a measure of the amount of time (number of basic operations) an algorithm takes to complete as a function of the input size n. It describes how the running time grows with increasing input.

Example: Linear search has time complexity O(n).

Space Complexity

Space complexity is a measure of the amount of memory space an algorithm requires as a function of the input size n. It includes both auxiliary space and space used by the input.

Example: An algorithm storing an n x n matrix has space complexity O(n²).

(b) Round Robin Algorithm for MST

Background

The Round Robin (also called Boruvka's Algorithm) is one of the oldest algorithms for finding a Minimum Spanning Tree (MST) of a weighted, connected, undirected graph.

• Proposed by Otakar Boruvka in 1926.
• It works by simultaneously growing multiple components and merging them.

Key Idea

In each round (phase), every component (initially each vertex is its own component) selects the minimum weight edge that connects it to a different component. All such edges are added to the MST, and components are merged.

Algorithm Steps

Input: Graph G = (V, E) with weighted edges
Output: Minimum Spanning Tree T

1. Initialize each vertex as its own component.
   T = {} (empty set of MST edges)

2. Repeat until only one component remains:
   a. For each component C:
      - Find the minimum weight edge (u, v) such that
        u ∈ C and v ∉ C (cheapest outgoing edge).
   
   b. Add all such selected edges to T
      (avoid duplicates if two components select the same edge).
   
   c. Merge the connected components.

3. Return T as the MST.

Example

Consider the graph:

    4       2
A ------B ------C
|       |       |
6|      |3      |1
|       |       |
D ------E ------F
    5       8

Edges: A-B(4), B-C(2), A-D(6), B-E(3), C-F(1), D-E(5), E-F(8)

Round 1: Each vertex is its own component {A},{B},{C},{D},{E},{F}

Selected edges (removing duplicates): C-F(1), B-C(2), B-E(3), A-B(4), D-E(5)

After merging: {A,B,C,E,F} and {D} merge further -> one component.

MST edges: C-F, B-C, B-E, A-B, D-E
Total Weight: 1+2+3+4+5 = 15

Complexity Analysis

• Each phase reduces the number of components by at least half.
• So there are at most O(log V) phases.
• Each phase scans all E edges.

Advantages

• Naturally parallelizable (all components work simultaneously).
• Efficient for dense graphs.
• Works well in distributed computing environments.

Summary

Boruvka's Round Robin Algorithm builds the MST by repeatedly selecting the minimum cost edge from each component and merging components until a single spanning tree is formed, achieving O(E log V) time complexity.

STEP 1 - EXTRACT: Given Data

Task: Traverse a given tree in pre-order and in-order.

Tree structure: The tree diagram/image is NOT provided in the question. Only the instruction and the mark allocation ([5]) are given.

Missing data: The actual tree (nodes and their parent/child relationships) is missing. Without the specific tree, an exact, verifiable set of traversal sequences cannot be produced. The correct output depends entirely on the omitted diagram.

Since the tree cannot be recovered, I will state the required methods precisely and demonstrate them on a clearly labelled assumed sample tree (so the traversal logic can still be checked), while noting this is illustrative only.

STEP 2 - SOLVE (using an assumed sample tree, since the real tree is missing)

Assumed Sample Tree

        A
       / \
      B   C
     / \ / \
    D  E F  G

1. Pre-order Traversal (Root → Left → Right)

Rule: visit Root, then Left subtree, then Right subtree.

• Visit A (root)
• Left subtree of A (rooted at B): visit B, then D, then E
• Right subtree of A (rooted at C): visit C, then F, then G

$$\text{Pre-order: } A \to B \to D \to E \to C \to F \to G$$

2. In-order Traversal (Left → Root → Right)

Rule: traverse Left subtree, visit Root, traverse Right subtree.

• Left subtree of A: D, B, E
• Visit A
• Right subtree of A: F, C, G

$$\text{In-order: } D \to B \to E \to A \to F \to C \to G$$

Summary

Important note: These results are valid only for the assumed sample tree shown above. Because the actual tree from the exam paper was not supplied, the definitive answer cannot be produced. If the real tree differs, apply the same rules:

• Pre-order = Root, Left, Right
• In-order = Left, Root, Right

Limitations of Recursion and Deletion in BST

Limitations of Recursion [2 marks]

1. Stack Overflow: Each recursive call uses stack memory. For deep recursion (large input), the call stack may overflow, causing program crash.

2. High Memory Usage: Every function call requires stack frame allocation (for parameters, local variables, return address), consuming more memory than iterative solutions.

3. Slower Execution: Function call overhead (pushing/popping stack frames) makes recursion slower compared to equivalent iterative approaches.

4. Difficult to Trace/Debug: The flow of recursive programs is harder to follow and debug compared to iterative programs.

5. Redundant Computations: Without memoization, some recursive algorithms (e.g., naive Fibonacci) recompute the same subproblems repeatedly.

Deletion of a Node in BST [3 marks]

When deleting a node from a Binary Search Tree, there are three cases:

Case 1: Node is a Leaf Node (No Children)

• Simply remove the node by setting the parent's pointer to NULL.

Delete 20:
    30                30
   /        -->      /
  20               (NULL)

Case 2: Node has One Child

• Replace the node with its only child (bypass the node).

Delete 30:
    30                20
   /        -->
  20

Case 3: Node has Two Children

• Find the inorder successor (smallest node in the right subtree) OR inorder predecessor (largest node in the left subtree).
• Copy its value to the node to be deleted.
• Delete the inorder successor/predecessor (which has at most one child).

Delete 50:
        50                  60
       /  \      -->       /  \
      30   70             30   70
          /
         60

Inorder successor of 50 is 60.
Copy 60 to node 50, then delete original 60.

Algorithm (Pseudocode)

DELETE(root, key):
  if root == NULL:
      return NULL
  if key < root.data:
      root.left = DELETE(root.left, key)
  else if key > root.data:
      root.right = DELETE(root.right, key)
  else:
      // Case 1 & 2: 0 or 1 child
      if root.left == NULL:
          return root.right
      else if root.right == NULL:
          return root.left
      // Case 3: 2 children
      successor = FIND_MIN(root.right)
      root.data = successor.data
      root.right = DELETE(root.right, successor.data)
  return root

Summary Table

Simple Queue and Types of Graphs

Simple Queue [2 marks]

A simple queue (also called a linear queue) is a linear data structure that follows the FIFO (First In First Out) principle, meaning the element inserted first is the element removed first.

Key characteristics:

• Elements are inserted from the REAR end
• Elements are deleted from the FRONT end
• Once the rear reaches the maximum size, no more insertions are possible (even if space exists at the front after deletions)

FRONT                        REAR
  |                            |
  v                            v
[ 10 | 20 | 30 | 40 | 50 ]
  ^                            ^
 Delete                      Insert

Basic Operations:

• Enqueue: Insert an element at the rear
• Dequeue: Remove an element from the front
• Peek/Front: View the front element without removing it

Three Types of Graphs [3 marks]

A graph is a non-linear data structure consisting of a set of vertices (nodes) and edges (connections) represented as G = (V, E).

1. Directed Graph (Digraph)

A graph in which every edge has a specific direction is called a directed graph. The edges are represented as ordered pairs (u, v), meaning the edge goes from vertex u to vertex v but not necessarily from v to u.

    A -----> B
    |        |
    v        v
    C -----> D

• Edge (A, B) means A points to B
• Used in: web page linking, task scheduling

2. Undirected Graph

A graph in which edges have no direction is called an undirected graph. The edges are represented as unordered pairs {u, v}, meaning the connection is bidirectional.

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

• Edge {A, B} means both A connects to B and B connects to A
• Used in: social networks, road maps

3. Weighted Graph

A graph in which each edge is assigned a numerical value (weight or cost) is called a weighted graph. It can be either directed or undirected.

    A ---5--- B
    |         |
    3         7
    |         |
    C ---2--- D

• The weight may represent distance, cost, time, or capacity
• Used in: shortest path algorithms (Dijkstra's), network routing, GPS navigation

Note: Other types include cyclic/acyclic graphs, connected/disconnected graphs, and complete graphs.