Second Year Engineering • Academic Session 2026–2027 14 Min Read

SY AI & DS: Core Systems, Advanced Algorithms & Storage Architectures

Comprehensive Textbook Compendium: Balanced Tree Implementations, Relational Query Engines, Normalization Proofs, and Operating System Concurrency

The Second Year (SY) in Artificial Intelligence & Data Science engineering marks the critical transition from introductory programming syntax to low-level computational architecture, asymptotic complexity optimization, and enterprise database systems. At this stage, engineers must cease viewing software as abstract scripts and begin evaluating the physical memory hierarchies, cache hit ratios, lock contention overheads, and disk I/O bottlenecks that dictate production software performance.

This compendium serves as an exhaustive, textbook-grade technical reference covering the four cornerstone pillars of the SY curriculum: Advanced Data Structures (ADS), Database Management Systems (DBMS), Operating System Kernels (OS), and Discrete Mathematical Structures (DMS). Each chapter is designed to provide immediate analytical clarity and verified implementation models for undergraduate scholars.

Chapter 1: Advanced Data Structures & Self-Balancing Tree Mechanics

In non-linear data structures, binary search trees (BSTs) provide average-case $\mathcal{O}(\log n)$ search performance. However, when subjected to monotonically ordered input sequences, an unconstrained BST degenerates into a linear linked list with $\mathcal{O}(n)$ traversal worst-case complexity. To guarantee strict logarithmic upper bounds across all operations, modern database engines and memory managers rely on self-balancing tree invariants.

The AVL Tree Invariant: Named after Georgy Adelson-Velsky and Evgenii Landis, an AVL tree enforces the height-balance condition: for every node $v$, the balance factor $\text{BF}(v) = \text{height}(\text{left}) - \text{height}(\text{right}) \in \{-1, 0, 1\}$. When an insertion or deletion violates this property ($|\text{BF}| > 1$), constant-time subtree rotations are executed to restore equilibrium.

◆ The Four Fundamental AVL Rotation Cases

Left-Left (LL) Case: Heavy on the left child's left subtree. Resolved via a single clockwise Right Rotation around the root node.
Right-Right (RR) Case: Heavy on the right child's right subtree. Resolved via a single counter-clockwise Left Rotation around the root node.
Left-Right (LR) Case: Heavy on the left child's right subtree. Resolved via a double rotation: first a Left Rotation on the left child, followed by a Right Rotation on the root.
Right-Left (RL) Case: Heavy on the right child's left subtree. Resolved via a double rotation: first a Right Rotation on the right child, followed by a Left Rotation on the root.

              Python Implementation
              Self-Balancing AVL Tree with Full Rotations
            

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, node):
        return node.height if node else 0

    def get_balance(self, node):
        return self.get_height(node.left) - self.get_height(node.right) if node else 0

    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def insert(self, root, key):
        if not root:
            return AVLNode(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        balance = self.get_balance(root)

        # LL Case
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # RR Case
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # LR Case
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # RL Case
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root
            

Chapter 2: Relational Database Architecture & B+ Tree Storage Engines

Enterprise relational database management systems (such as PostgreSQL, MySQL InnoDB, and Oracle DB) do not store indexed records in binary search trees due to memory hierarchy realities. Main memory access operates at nanosecond latencies, whereas mechanical disks and solid-state drives (SSDs) operate at microsecond to millisecond block-fetch latencies.

Why B+ Trees Dominate Disk Storage: A B+ Tree is an $m$-way balanced search tree where every internal node contains up to $M-1$ search keys and $M$ child pointers, creating high fan-out and dramatically shallow tree heights (typically $\le 3$ levels for millions of records). Furthermore, all actual record data is stored strictly in the leaf nodes, which are sequentially linked in a bidirectional doubly-linked list. This enables $\mathcal{O}(\log_M N)$ point queries and lightning-fast range scans ($\text{WHERE age BETWEEN 20 AND 30}$).

◆ Normalization Theory & Mathematical Normal Forms

First Normal Form (1NF): All attribute domains contain strictly atomic, indivisible values with no repeating groups.
Second Normal Form (2NF): Must be in 1NF and eliminate all Partial Functional Dependencies (where a non-prime attribute depends on a proper subset of a composite candidate key).
Third Normal Form (3NF): Must be in 2NF and eliminate all Transitive Dependencies ($X \to Y$ and $Y \to Z$, where $Z$ is non-prime and $X$ is a candidate key).
Boyce-Codd Normal Form (BCNF): For every non-trivial functional dependency $X \to Y$, the determinant $X$ must be a superkey. BCNF guarantees total anomaly elimination.

Chapter 3: Operating System Kernels, Process Scheduling & Concurrency

An operating system kernel serves as the ultimate arbiter of hardware resources. In the SY curriculum, students dissect the life cycle of a process: from its creation via the $\text{fork}()$ system call through its execution states (Ready, Running, Blocked, Terminated) managed within the Process Control Block (PCB).

Preemptive Scheduling Mechanics: The kernel scheduler arbitrates CPU access using deterministic algorithms. In Round Robin (RR) scheduling, each ready process is allocated a fixed time slice known as a time quantum $q$. If $q$ is set too large, RR degrades into First-Come-First-Served (FCFS); if $q$ is infinitesimally small, context-switching overhead dominates CPU cycles. Optimal operating systems select $q \approx 10\text{--}20\text{ ms}$, ensuring that 80% of CPU bursts finish within a single time slice.

              Python Algorithm
              Least Recently Used (LRU) Page Replacement Engine
            

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node mapping
        self.usage_order = []  # MRU at tail, LRU at head

    def access_page(self, page_id: int) -> str:
        if page_id in self.usage_order:
            self.usage_order.remove(page_id)
            self.usage_order.append(page_id)
            return f"Page HIT: {page_id}"
        else:
            if len(self.usage_order) >= self.capacity:
                evicted = self.usage_order.pop(0)  # Evict LRU
                self.usage_order.append(page_id)
                return f"Page FAULT: Loaded {page_id} (Evicted {evicted})"
            else:
                self.usage_order.append(page_id)
                return f"Page FAULT: Loaded {page_id} (Free Frame)"
            

"A master data engineer must understand the entire software stack—from the asymptotic invariants of binary trees to the physical disk page layout and OS process synchronization locks." — Sarthak Pawar, Lead Curator

Second Year Academic Laboratory Modules

Practical laboratory modules for Semester 3 and Semester 4 require students to implement these foundational algorithms in both C++ (for memory-level pointer arithmetic and manual dynamic allocation) and Python (for algorithmic benchmarking and database connector interfaces). Review our First Year prerequisites in FY AI & DS Notes for foundational syntax models.