Data Structure and Algorithms

Answer:

• Big-O ($O$ - Asymptotic Upper Bound): $f(n) = O(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
  $$0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_0$$
  Represents the worst-case ceiling on algorithm running time.
• Big-Omega ($\Omega$ - Asymptotic Lower Bound): $f(n) = \Omega(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
  $$0 \le c \cdot g(n) \le f(n) \quad \forall n \ge n_0$$
  Represents the best-case floor on algorithm running time.
• Big-Theta ($\Theta$ - Asymptotically Tight Bound): $f(n) = \Theta(g(n))$ if there exist positive constants $c_1, c_2 > 0$ and $n_0 \ge 1$ such that:
  $$0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \forall n \ge n_0$$

Answer:

• Circular Queue: A linear FIFO data structure where the last position of the underlying array connects back to the first position, forming a circular ring.
• Advantage: Overcomes the false overflow problem of linear array queues, where vacated slots at the front after dequeuing cannot be reused even if free memory exists.
• Queue Full Condition: Using modular arithmetic with array capacity MAX:
  $$\mathbf{(rear + 1) \pmod{MAX} == front}$$
  Queue empty condition: $\text{front} == -1 \text{ and } \text{rear} == -1$.

Answer:

Answer:

• Balance Factor ($BF$): In an AVL self-balancing binary search tree, the Balance Factor of any node $N$ is defined as the height difference between its left subtree and right subtree:
  $$BF(N) = \text{Height}(\text{Left Subtree}) - \text{Height}(\text{Right Subtree})$$
• Permitted Values: An AVL tree strictly enforces that for every node in the tree:
  $$BF(N) \in \{-1, 0, +1\}$$
  If an insertion or deletion causes $BF(N)$ to become $\pm 2$, tree rotations (LL, RR, LR, or RL) are performed immediately to restore balance.

Answer:

Stack-Based Infix to Postfix Conversion and Evaluation

a) Tabular Trace of Infix to Postfix Conversion

• Expression: $(A + B) * (C - D) / (E + F \uparrow G)$
• Precedence Hierarchy: $\uparrow$ (Exponentiation, Right-to-Left, highest) $>$ $*, /$ (Left-to-Right) $>$ $+,-$ (Left-to-Right) $>$ $($ (lowest inside stack).

• Final Postfix String: $\mathbf{A B + C D - * E F G \uparrow + /}$

b) Postfix Evaluation Algorithm in C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

#define STACK_SIZE 100

typedef struct {
    int data[STACK_SIZE];
    int top;
} OperandStack;

void push(OperandStack *s, int val) { s->data[++(s->top)] = val; }
int pop(OperandStack *s) { return s->data[(s->top)--]; }

int evaluate_postfix(const char *exp) {
    OperandStack stack;
    stack.top = -1;

    for (int i = 0; exp[i] != '\0'; i++) {
        if (isspace(exp[i])) continue;

        // Multi-digit operand parsing
        if (isdigit(exp[i])) {
            int val = 0;
            while (isdigit(exp[i])) {
                val = (val * 10) + (exp[i] - '0');
                i++;
            }
            i--; // adjust loop increment
            push(&stack, val);
        } else {
            // Operator: pop two operands
            int op2 = pop(&stack);
            int op1 = pop(&stack);
            switch (exp[i]) {
                case '+': push(&stack, op1 + op2); break;
                case '-': push(&stack, op1 - op2); break;
                case '*': push(&stack, op1 * op2); break;
                case '/': push(&stack, op1 / op2); break;
                case '^': push(&stack, (int)pow(op1, op2)); break;
            }
        }
    }
    return pop(&stack);
}

BST Deletion and AVL Tree Construction Step-by-Step

a) Three Cases of BST Node Deletion

1. Case 1 (Node is a Leaf): The node has no children. Deletion is trivial: the parent pointer to this node is set to NULL, and the node’s memory is deallocated ($O(1)$ pointer update).
2. Case 2 (Node has Exactly One Child): The node has either a left child or a right child. The parent’s pointer is updated to point directly to the node’s single child, bypassing the deleted node.
3. Case 3 (Node has Two Children):
   • Find the node’s In-order Successor (the smallest node in its right subtree) OR In-order Predecessor (largest node in its left subtree).
   • Copy the value of the in-order successor into the target node.
   • Recursively delete the in-order successor from the right subtree (which falls into Case 1 or Case 2, since the successor can have at most one child).

b) AVL Tree Construction: Sequence [50, 20, 60, 10, 8, 15, 30, 25]

1. Insert 50, 20, 60:
   • Balanced. Root 50 ($BF = 0$), left child 20 ($BF=0$), right child 60 ($BF=0$).
2. Insert 10:
   • Inserted at $20 \to \text{left}$.
   • $BF(20) = +1, BF(50) = +1$. Balanced.
3. Insert 8 (Triggers LL Rotation):
   • Inserted at $10 \to \text{left}$.
   • Tree path: $20 \to 10 \to 8$.
   • $BF(20) = 2$ (unbalanced at node 20, Left-Left violation).
   • Perform LL Rotation at Node 20:
     • Node 10 becomes parent of 20 and 8.
     • Subtree at 50 left becomes: 10 (root), 8 (left), 20 (right).
     • Tree is balanced.
4. Insert 15 (Triggers LR Rotation):
   • Inserted at $20 \to \text{left}$.
   • $BF(10) = -1, BF(50) = 3 - 1 = +2$ (Node 50 is unbalanced).
   • Path from 50: Left child is 10, right child of 10 is 20 $\implies$ LR Violation.
   • Perform LR Rotation at Node 50:
     • First, rotate Left on 10: 20 becomes left child of 50, 10 becomes left child of 20, 15 becomes right child of 10.
     • Second, rotate Right on 50: 20 becomes new root of entire tree!
     • Left child of 20 is 10 (with children 8, 15); Right child of 20 is 50 (with child 60).
     • Tree is balanced!
5. Insert 30:
   • Inserted at $50 \to \text{left} \implies BF(50) = 1$. Balanced.
6. Insert 25 (Triggers RL Rotation):
   • Inserted at $30 \to \text{left}$.
   • Path from 50: Left child is 30, left child of 30 is 25.
   • Node 30 has $BF = +1$. Node 50 has left height 2, right height 1 $\implies BF(50) = +1$.
   • Let’s check Root 20: Left subtree height is 2 (nodes 10, 8, 15). Right subtree height is 3 (nodes 50, 30, 25).
   • $BF(20) = 2 - 3 = -1$. Balanced!
   • Node 50 has $BF = 2 - 1 = +1$.
   • Complete balanced tree!

Final Balanced AVL Structure

            20 (BF = -1)
          /      \
      10 (BF=0)    50 (BF = +1)
      /   \        /     \
     8     15     30      60
                 /
                25

Every node satisfies $BF \in \{-1, 0, +1\}$. Search complexity guaranteed $O(\log N)$.

MergeSort vs. HeapSort: Recurrences and Heap Mechanics

a) MergeSort Divide-and-Conquer Recurrence and Master Theorem Proof

1. Recurrence Formulation

MergeSort divides an array of size $n$ into two equal subproblems of size $n/2$, recursively sorts each half, and merges the two sorted lists in linear time $c \cdot n$:

2. Proof via Master Theorem

The generalized Master Theorem recurrence has the form:

• Evaluate the critical ratio:
  $$\log_b a = \log_2 2 = 1$$
• Compare $\log_b a$ with $d$:
  $$\log_b a = 1 = d$$
• This satisfies Case 2 of the Master Theorem ($f(n) = \Theta(n^{\log_b a})$):
  $$T(n) = \Theta(n^{\log_b a} \log n) = \mathbf{\Theta(n \log n)}$$
  MergeSort runs in $\Theta(n \log n)$ time across all cases (best, average, and worst).

b) HeapSort and Max-Heap Mechanics

1. Max-Heap Property

A complete binary tree where for every non-root node $i$ with parent $p = \lfloor(i - 1)/2\rfloor$:

2. max_heapify(Arr, n, i) Procedure

1. Identify left child $l = 2i + 1$ and right child $r = 2i + 2$.
2. Find the largest among Arr[i], Arr[l], and Arr[r].
3. If largest $\ne i$, swap Arr[i] with Arr[largest] and recursively call max_heapify(Arr, n, largest) down the tree ($O(\log n)$ height).

3. Why build_max_heap runs in $O(n)$ Linear Time

Calling max_heapify on all internal nodes from $\lfloor n/2 \rfloor - 1$ down to 0:

4. In-Place HeapSort Routine

1. Build Max-Heap from unsorted input ($O(n)$).
2. For $i = n - 1$ down to 1:
   • Swap root Arr[0] (maximum) with last leaf Arr[i].
   • Reduce heap size by 1 ($n \leftarrow i$).
   • Run max_heapify(Arr, i, 0) on the new root to restore max-heap property ($O(\log n)$).
3. Resulting array is sorted in ascending order in $\mathbf{O(n \log n)}$ time and $\mathbf{O(1)}$ auxiliary space.

Dijkstra Shortest Path Algorithm and MST Comparison

a) Dijkstra Single-Source Shortest Path Trace

1. Graph Specification

• Vertices: $V = \{A, B, C, D, E\}$, Source = $A$.
• Directed Weighted Edges:
  • From $A$: $(A \to B, 4), (A \to C, 2)$
  • From $C$: $(C \to B, 1), (C \to D, 8), (C \to E, 10)$
  • From $B$: $(B \to D, 5)$
  • From $D$: $(D \to E, 2)$

2. Step-by-Step Algorithm Execution Trace

3. Final Shortest Paths from Source $A$

• To $A$: Distance = 0 | Path: $A$
• To $B$: Distance = 3 | Path: $A \to C \to B$
• To $C$: Distance = 2 | Path: $A \to C$
• To $D$: Distance = 8 | Path: $A \to C \to B \to D$
• To $E$: Distance = 10 | Path: $A \to C \to B \to D \to E$

b) Prim’s vs. Kruskal’s Minimum Spanning Tree Algorithms

Systems Engineering Solution: TIA Airport Logistics and Flight Dispatch Engine

a) Data Structure Selection and Complexity Justification

1. VIP & Emergency Flight Dispatch: Max-Heap Priority Queue

• Justification: Aircraft departures require dynamic priority management where emergency relief and VIP aircraft can arrive at arbitrary times with higher priority scores than scheduled flights. A binary Max-Heap allows extracting the highest priority flight in $O(\log N)$ time and inserting newly scheduled flights in $O(\log N)$ time ($O(1)$ amortized).
• Complexity: Time: Insert $O(\log N)$, Extract-Max $O(\log N)$, Peek $O(1)$. Space: $O(N)$ contiguous array.

2. Passenger Boarding Pass Verification: Hash Table with Separate Chaining

• Justification: Security turnstiles require instantaneous, near-constant-time passport lookups ($O(1)$ average time) to prevent passenger bottlenecks. Keys are hashed 9-character passport numbers.
• Complexity: Time: Search/Insert $O(1)$ average, $O(N)$ worst-case. Space: $O(N + M)$ where $M$ is bucket capacity.

3. Inter-Terminal Baggage Conveyor Routing: Directed Weighted Graph with Adjacency List

• Justification: Conveyor junctions and chutes form a network with unidirectional belt segments and variable transit times (weights). An adjacency list representation is space-optimal for sparse transportation graphs ($|E| \ll |V|^2$).
• Complexity: Space: $O(V + E)$. Pathfinding (Dijkstra): Time $O((V + E) \log V)$ with Min-Heap.

b) Real-Time Conveyor Routing Implementation in Java (Dijkstra)

import java.util.*;

class Edge {
    int target;
    int weightSeconds;

    public Edge(int target, int weightSeconds) {
        this.target = target;
        this.weightSeconds = weightSeconds;
    }
}

class NodeEntry implements Comparable<NodeEntry> {
    int node;
    int cost;

    public NodeEntry(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(NodeEntry other) {
        return Integer.compare(this.cost, other.cost);
    }
}

public class BaggageRoutingEngine {
    private int numJunctions;
    private List<List<Edge>> adjList;

    public BaggageRoutingEngine(int numJunctions) {
        this.numJunctions = numJunctions;
        adjList = new ArrayList<>(numJunctions);
        for (int i = 0; i < numJunctions; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addConveyorSegment(int u, int v, int transitSeconds) {
        adjList.get(u).add(new Edge(v, transitSeconds));
    }

    public List<Integer> findFastestBaggageRoute(int startJunction, int destinationHold) {
        int[] dist = new int[numJunctions];
        int[] parent = new int[numJunctions];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);

        PriorityQueue<NodeEntry> pq = new PriorityQueue<>();
        dist[startJunction] = 0;
        pq.offer(new NodeEntry(startJunction, 0));

        while (!pq.isEmpty()) {
            NodeEntry current = pq.poll();
            int u = current.node;

            if (current.cost > dist[u]) continue; // Stale queue entry
            if (u == destinationHold) break;       // Reached destination

            for (Edge edge : adjList.get(u)) {
                int v = edge.target;
                int weight = edge.weightSeconds;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    pq.offer(new NodeEntry(v, dist[v]));
                }
            }
        }

        // Reconstruct Optimal Conveyor Path
        List<Integer> path = new ArrayList<>();
        if (dist[destinationHold] == Integer.MAX_VALUE) {
            return path; // Unreachable
        }

        for (int curr = destinationHold; curr != -1; curr = parent[curr]) {
            path.add(curr);
        }
        Collections.reverse(path);
        return path;
    }
}

c) Hash Table Engineering, Collision Resolution, and Load Factors

1. Separate Chaining vs. Open Addressing with Double Hashing

• Separate Chaining: Each hash table slot contains a linked list or balanced red-black tree (as in Java 8+ HashMap). If collision occurs, the element is appended to the bucket chain.
  • Advantage for Airport: Never runs out of slots; performance degrades gracefully even if load factor momentarily exceeds 1.0.
• Open Addressing (Double Hashing): All elements reside directly within the array. On collision, probe sequence uses a secondary hash function: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod M$.
  • Disadvantage: Sensitive to clustering; table cannot exceed 100% capacity; deletion requires tombstone markers.

2. Load Factor Threshold ($\alpha$) and Dynamic Rehashing

• Load Factor:
  $$\alpha = \frac{N}{M} = \frac{\text{Total Stored Passengers}}{\text{Total Bucket Capacity}}$$
• When $\alpha > 0.75$, probability of hash collisions increases exponentially, causing lookup times to degrade from $O(1)$ toward $O(N)$.
• Dynamic Rehashing: When $\alpha$ reaches 0.75, the engine allocates a new bucket array of size $2 \times M$, recalculates hash indices, and migrates all existing records into the new table. The $O(N)$ resizing cost is amortized across thousands of subsequent fast insertions ($O(1)$ amortized).

3. Preventing Worst-Case $O(N)$ Hash Flooding Attacks

If malicious actors submit forged passport numbers that collide on the exact same hash bucket (algorithmic complexity attack):

• Implement Universal Hashing (choosing random hash multipliers at startup).
• Convert buckets with $> 8$ elements from linked lists into Red-Black balanced trees, guaranteeing worst-case lookup latency of $\mathbf{O(\log N)}$ rather than $O(N)$.