📘 PART 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

🔍 What is an Algorithm?

An algorithm is a step-by-step procedure to solve a problem.

🔢 Example: Factorial Algorithm

def factorial(n):
    """Calculate factorial of n"""
    if n < 0:
        return "Error: Negative number"
    if n == 0 or n == 1:
        return 1
    
    fact = 1
    for i in range(2, n + 1):
        fact *= i
    return fact

# Interactive Example
print(factorial(5))  # Output: 120
print(factorial(0))  # Output: 1

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n < 0) return -1;  // Error
    if (n == 0 || n == 1) return 1;
    
    int fact = 1;
    for (int i = 2; i <= n; i++) {
        fact *= i;
    }
    return fact;
}

int main() {
    cout << "5! = " << factorial(5) << endl;  // 120
    cout << "0! = " << factorial(0) << endl;  // 1
    return 0;
}

📊 Why Learn DSA?

🧠 DSA Concepts Simplified

⏱ PART 2: ALGORITHM ANALYSIS

⏰ Asymptotic Notations

📈 Example: Optimizing Sum of First N Numbers

int findSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

int sum(int n) {
    return n * (n + 1) / 2;
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // some operation
    }
}

🧱 PART 3: CORE DATA STRUCTURES

🧱 Stack – LIFO (Last In, First Out)

🚶‍♂️ Queue – FIFO (First In, First Out)

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# Interactive Example
queue = Queue()
queue.enqueue("Task 1")
queue.enqueue("Task 2")
queue.enqueue("Task 3")
print(f"Front: {queue.front()}")     # Task 1
print(f"Dequeued: {queue.dequeue()}") # Task 1
print(f"Size: {queue.size()}")       # 2

🔁 Circular Queue

class CircularQueue {
private:
    int *arr;
    int front, rear, size, capacity;
    
public:
    CircularQueue(int n) {
        capacity = n;
        arr = new int[n];
        front = rear = -1;
        size = 0;
    }
    
    bool enqueue(int val) {
        if (isFull()) return false;
        
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % capacity;
        }
        arr[rear] = val;
        size++;
        return true;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        
        int val = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        size--;
        return val;
    }
    
    bool isEmpty() { return size == 0; }
    bool isFull() { return size == capacity; }
};

🚦 Priority Queue (Heap-based)

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.count = 0
    
    def insert(self, item, priority):
        # Use negative priority for max heap
        heapq.heappush(self.heap, (-priority, self.count, item))
        self.count += 1
    
    def extract_max(self):
        if self.is_empty():
            return None
        return heapq.heappop(self.heap)[2]
    
    def peek(self):
        if self.is_empty():
            return None
        return self.heap[0][2]
    
    def is_empty(self):
        return len(self.heap) == 0

# Interactive Example
pq = PriorityQueue()
pq.insert("Task A", 3)
pq.insert("Task B", 1)
pq.insert("Task C", 5)
print(f"Highest priority: {pq.peek()}")      # Task C
print(f"Extracted: {pq.extract_max()}")      # Task C
print(f"Next: {pq.extract_max()}")           # Task A

💡 Hash Table (Hash Map)

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def put(self, key, value):
        hash_key = self._hash(key)
        for item in self.table[hash_key]:
            if item[0] == key:
                item[1] = value
                return
        self.table[hash_key].append([key, value])
    
    def get(self, key):
        hash_key = self._hash(key)
        for item in self.table[hash_key]:
            if item[0] == key:
                return item[1]
        return None
    
    def remove(self, key):
        hash_key = self._hash(key)
        for i, item in enumerate(self.table[hash_key]):
            if item[0] == key:
                del self.table[hash_key][i]
                return
    
    def contains_key(self, key):
        return self.get(key) is not None

# Interactive Example
ht = HashTable()
ht.put("apple", 10)
ht.put("banana", 20)
ht.put("cherry", 30)
print(f"Apple: {ht.get('apple')}")           # 10
print(f"Contains 'banana': {ht.contains_key('banana')}")  # True
ht.remove("banana")
print(f"After removal: {ht.get('banana')}")  # None

🌲 PART 4: TREES

🏡 Binary Tree

Each node has 2 children.

Inorder Traversal (Left, Root, Right):

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

🌳 Binary Search Tree (BST)

Left < Root < Right. Enables fast search.

bool search(Node* root, int val) {
    if (!root) return false;
    if (root->data == val) return true;
    return val < root->data ? search(root->left, val) : search(root->right);
}

🔄 AVL Tree (Self-Balancing BST)

• Keeps height balanced (|L-R| ≤ 1)
• Rotations: Left, Right, Left-Right, Right-Left
• Used in databases for quick search

🔗 PART 5: GRAPHS & ALGORITHMS

🔗 Graph

Adjacency List: Efficient for sparse graphs

DFS (Depth-First Search):

def dfs(node, visited, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, graph)

🛤 Dijkstra's Algorithm – Shortest Path

Use Case: GPS, Networking

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        current_dist, node = heapq.heappop(pq)
        for neighbor, weight in graph[node]:
            if dist[neighbor] > current_dist + weight:
                dist[neighbor] = current_dist + weight
                heapq.heappush(pq, (dist[neighbor], neighbor))
    return dist

🔄 PART 6: SORTING ALGORITHMS

🧠 PART 7: DYNAMIC PROGRAMMING

🧩 Fibonacci – Memoization

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

🔁 Longest Common Subsequence (LCS)

Used in DNA matching, diff tools.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[m][n]

🧪 PART 8: INTERVIEW APPLICATIONS

🏁 Backtracking – N Queen Problem

Explore all possible paths; revert if not valid.

🧬 Rabin-Karp – String Matching

Faster search using hashing.

🔐 Huffman Coding

Compression algorithm used in files like .zip, .mp3.

🚀 Final Words

1. ✅ Learn the concept
2. 🔍 Study time/space complexity
3. 🧪 Practice on LeetCode, GFG, Codeforces
4. 📊 Analyze your solution
5. 🛠 Refactor using better data structures

📘 DSA In-Depth Study Guide

✅ Key Features:

• Covers all fundamental and advanced DSA topics
• Organized in a topic-wise structure
• Suitable for web-based integration
• Designed for self-paced or classroom learning
• Can be broken into multiple structured sections with:
  • Diagrams
  • Interactive examples
  • Syntax-highlighted code
  • Quizzes and assessments

🧠 DSA Introduction

✅ Getting Started with DSA

Data Structures and Algorithms (DSA) form the foundation of problem-solving in computer science. Understanding how data is organized and manipulated efficiently allows developers to write optimized code.

🔍 What is an Algorithm?

An algorithm is a step-by-step finite set of instructions to solve a particular problem. It has:

• Input: Data to be processed
• Output: Result after processing
• Finiteness: Must terminate after a finite number of steps
• Effectiveness: Each step must be simple enough to perform

🧱 Data Structure and Types

A Data Structure is a specialized way of storing and organizing data.

Types:

• Linear (Arrays, Linked Lists, Stack, Queue)
• Non-linear (Trees, Graphs)
• Hash-based (Hash Tables)

🎯 Why Learn DSA?

• Enhances problem-solving skills
• Required for coding interviews
• Helps in optimizing performance
• Foundation for competitive programming

🧮 Asymptotic Notations

• Big O (O) – Worst-case
• Omega (Ω) – Best-case
• Theta (Θ) – Average-case

Used to describe time and space complexity.

🧠 Master Theorem

Provides a shortcut to solve recurrence relations of divide-and-conquer algorithms:

T(n) = aT(n/b) + f(n)

• Compare f(n) with n^log_b(a)

⚔️ Divide and Conquer Algorithm

Break problem into sub-problems, solve recursively, and combine.

Examples: Merge Sort, Quick Sort, Binary Search

📦 Data Structures I

🥞 Stack

• Follows LIFO (Last In First Out)
• Operations: push(), pop(), peek()
• Applications: Recursion, Undo features

🧾 Queue

• Follows FIFO (First In First Out)
• Operations: enqueue(), dequeue()

🔁 Types of Queue

• Simple Queue
• Circular Queue: Ends connect to beginning
• Priority Queue: Highest priority dequeued first
• Deque: Double-ended queue

📦 Data Structures II

🔗 Linked List

• Nodes with data and next pointer

🔧 Linked List Operations:

• Insert, Delete, Traverse

🧱 Types of Linked List:

• Singly
• Doubly
• Circular

🧩 Hash Table

• Key-value pair mapping
• Uses Hash functions for indexing
• Collision resolution: Chaining, Open Addressing

⛏ Heap Data Structure

• Complete Binary Tree
• Types: Min-Heap, Max-Heap
• Used in Heap Sort and Priority Queues

🌀 Fibonacci Heap

• Advanced heap with better amortized time
• Supports mergeable heaps

✂️ Decrease Key and Delete Node in Fibonacci Heap

• decreaseKey(node, newVal)
• delete(node) using decreaseKey to -∞ and extract

🌲 Tree-Based DSA I

🌳 Tree Data Structure

• Hierarchical structure with a root node
• Parent-child relationships

🔄 Tree Traversal

• In-order, Pre-order, Post-order, Level-order

🧮 Binary Tree Variants

• Full: All nodes have 0 or 2 children
• Perfect: All internal nodes have 2 children, and all leaves are at the same level
• Complete: All levels filled, except possibly the last
• Balanced: Height difference of subtrees is ≤ 1

🔍 Binary Search Tree (BST)

• Left < Root < Right
• Supports fast search, insertion, deletion

⚖️ AVL Tree

• Self-balancing BST
• Balance factor must be -1, 0, or 1

🌳 Tree-Based DSA II

🌴 B Tree

• Multi-level index tree for database systems
• Balanced m-ary tree

➕ Insertion in B-tree

• Find correct leaf, insert key
• Split if overflow

➖ Deletion from B-tree

• Borrow from siblings or merge nodes

➕ B+ Tree

• Leaf nodes store actual data
• Internal nodes store keys only

🔄 B+ Tree Operations

• Insertion: Like B-tree but only at leaves
• Deletion: From leaf, with rebalancing

♠️ Red-Black Tree

• Self-balancing BST with coloring
• Guarantees O(log n) operations

🔺 Insertion in Red-Black Tree

• Uses rotations and color flips

🌐 Graph-Based DSA

📊 Graph Data Structure

• Nodes (vertices) and edges
• Types: Directed, Undirected, Weighted

🌲 Spanning Tree

• Subset of graph connecting all vertices with minimum edges
• MST: Minimum Spanning Tree (Kruskal, Prim)

🔁 Strongly Connected Components

• For Directed Graphs
• Kosaraju's Algorithm

🧮 Graph Representations

• Adjacency Matrix: 2D array
• Adjacency List: List of lists or maps

🔎 Graph Traversal Algorithms

• DFS: Depth-first search
• BFS: Breadth-first search

🚧 Bellman-Ford's Algorithm

• Single source shortest path (handles negatives)

🔃 Sorting and Searching Algorithms

🔃 Basic Sorting

• Bubble Sort, Selection Sort, Insertion Sort

🧠 Efficient Sorting

• Merge Sort (Divide & Conquer)
• Quicksort (Pivot based)
• Counting Sort (non-comparison)
• Radix Sort, Bucket Sort, Heap Sort
• Shell Sort (gap reduction)

🔍 Searching

• Linear Search
• Binary Search (on sorted arrays)

🤑 Greedy Algorithms

💰 Core Concept

• Make locally optimal choice at each step

🔁 Algorithms

• Dijkstra's Algorithm (shortest path)
• Kruskal's Algorithm (MST)
• Prim's Algorithm (MST)
• Ford-Fulkerson (Max flow)
• Huffman Coding (Data compression)

💡 Dynamic Programming

📦 Dynamic Programming

• Optimal substructure + overlapping subproblems

🧠 Key Algorithms

• Floyd-Warshall: All pairs shortest paths
• Longest Common Subsequence (LCS)
• Matrix Chain Multiplication
• Knapsack Problem

🔍 Other Important Algorithms

🧪 Backtracking Algorithm

• Recursively tries all possibilities
• Examples: N-Queens, Sudoku, Subset Sum

🔎 Rabin-Karp Algorithm

• Pattern matching using hashing
• Efficient string matching with rolling hash