🗂️ Data Structures & Algorithms (105302)

⬅️ Back to Semester-3 | 🏠 Home

💡 Why this subject? This is the single most important subject for coding interviews and writing efficient software. Master this, and you can build/debug almost anything.

---

📌 Unit 1: Introduction

• Data Structure: a way of organizing data so it can be used efficiently (array, linked list, stack, tree...).
• Operations: Insertion, Deletion, Traversal, Searching, Sorting.
• Asymptotic Notation — describes how runtime grows as input size n grows:

Notation	Meaning
O(1)	Constant — same time regardless of input size
O(log n)	Logarithmic — e.g., binary search
O(n)	Linear — e.g., simple loop
O(n log n)	e.g., merge sort, quick sort (average)
O(n²)	Quadratic — e.g., bubble sort, nested loops

• Time-Space tradeoff: you can often make something faster by using more memory (e.g., caching/hashing) and vice versa.

🧠 Quick Recall: Big-O describes the worst case growth rate, not exact seconds.

---

📌 Unit 2: Stacks and Queues

• Stack: LIFO (Last In, First Out) — like a stack of plates. Operations: push, pop, peek.
• 📝 Used for: undo functionality, function call stack, expression evaluation.
• Queue: FIFO (First In, First Out) — like a line at a ticket counter. Operations: enqueue, dequeue.
• Circular Queue: wraps around to reuse empty front slots — avoids wasted space.
• Priority Queue: element with highest priority served first (not strictly FIFO).

📝 Example — Infix to Postfix (classic stack application):

Infix:   A + B * C
Postfix: A B C * +

Stack-based algorithm: scan left to right, push operators onto a stack respecting precedence, pop to output when needed.

// Stack using array
#define MAX 100
int stack[MAX], top = -1;
void push(int x) { stack[++top] = x; }
int pop() { return stack[top--]; }

🧠 Quick Recall: Stack = function call recursion under the hood. Queue = CPU task scheduling, printer job queue.

---

📌 Unit 3: Linked Lists

• Singly Linked List: each node points to the next; no fixed size (unlike arrays), but no random access.
• Doubly Linked List: each node points to both next AND previous — easy backward traversal.
• Circular Linked List: last node points back to the first — useful for round-robin scheduling.
• Header node: a dummy node simplifying insert/delete at the beginning.

📝 Example — Singly Linked List node in C:

struct Node {
    int data;
    struct Node *next;
};

void insertAtBeginning(struct Node **head, int val) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->next = *head;
    *head = newNode;
}

🧠 Quick Recall: Array = fast access (index), slow insert/delete in middle. Linked List = slow access (must traverse), fast insert/delete.

---

📌 Unit 4: Searching, Sorting and Hashing

Algorithm	Time Complexity	Idea
Linear Search	O(n)	Check every element
Binary Search	O(log n)	Works only on sorted array — halve the range each time
Bubble Sort	O(n²)	Swap adjacent out-of-order pairs repeatedly
Selection Sort	O(n²)	Pick minimum, place at front, repeat
Insertion Sort	O(n²)	Build sorted list one element at a time
Merge Sort	O(n log n)	Divide, sort halves, merge
Quick Sort	O(n log n) avg	Pick pivot, partition, recurse
Heap Sort	O(n log n)	Build a heap, repeatedly extract max/min

• Hashing: maps a key to an array index using a hash function — gives near O(1) lookup. Collisions handled via chaining or open addressing.

📝 Example — Binary Search:

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

🧠 Quick Recall: Merge Sort = always O(n log n), stable, needs extra memory. Quick Sort = usually faster in practice, but worst case O(n²) with bad pivot choice.

---

📌 Unit 5: Trees

• Tree terms: Root, Parent, Child, Leaf, Height, Depth.
• Binary Tree: each node has at most 2 children.
• Binary Search Tree (BST): left subtree < node < right subtree — enables O(log n) search (if balanced).
• AVL Tree: a self-balancing BST — auto-rotates to keep height balanced, guaranteeing O(log n) operations always.
• Threaded Binary Tree: uses normally-wasted null pointers to point to in-order successor/predecessor — speeds up traversal without recursion/stack.
• B-Tree / B+ Tree: multi-way (not just 2 children) balanced trees — used in databases & file systems for fast disk-based search.

📝 Example — BST insert:

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* node = malloc(sizeof(struct Node));
        node->data = val;
        node->left = node->right = NULL;
        return node;
    }
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Traversals: - Inorder (Left, Root, Right) → gives sorted order in a BST - Preorder (Root, Left, Right) → used to copy a tree - Postorder (Left, Right, Root) → used to delete a tree

🧠 Quick Recall: BST is fast only if balanced — that's exactly why AVL trees and B-Trees exist (databases use B+ Trees for indexing).

---

📌 Unit 6: Graph

• Graph: set of vertices (nodes) connected by edges. Can be directed/undirected, weighted/unweighted.
• Representation:
• Adjacency Matrix: 2D grid, O(1) edge check, O(V²) space.
• Adjacency List: list per node, space-efficient for sparse graphs.
• Graph Traversal:
• BFS (Breadth-First Search): explore neighbors level by level — uses a Queue. Finds shortest path in unweighted graphs.
• DFS (Depth-First Search): go as deep as possible before backtracking — uses a Stack (or recursion).

📝 Example — real-world mapping: - Google Maps shortest route = graph + weighted shortest path algorithms (Dijkstra, built on these basics). - Facebook "friends of friends" suggestion = BFS on the social graph.

// BFS using adjacency list (conceptual)
void BFS(int start) {
    Queue q;
    bool visited[N] = {false};
    enqueue(&q, start);
    visited[start] = true;
    while (!isEmpty(&q)) {
        int node = dequeue(&q);
        print(node);
        for each neighbor of node:
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                enqueue(&q, neighbor);
            }
    }
}

---

🔬 Lab Highlights (DSA Lab)

1. Linear/Binary search
2. Stack using array & linked list
3. Infix → Postfix conversion
4. Queue (simple, circular) using array & linked list
5. Singly/Doubly/Circular linked list — insert, delete, reverse, traverse
6. Tree traversal — preorder, inorder, postorder

---

✅ Quick Revision Table

Topic	One-line memory hook
Stack	LIFO — undo, recursion
Queue	FIFO — scheduling, printer jobs
Linked List	Slow access, fast insert/delete
Binary Search	O(log n), needs sorted array
Merge Sort	Stable O(n log n), needs extra space
BST	Fast search only if balanced
AVL Tree	Self-balancing BST
B+ Tree	Used in database indexing
BFS	Queue-based, level-by-level, shortest path
DFS	Stack/recursion-based, go deep first