B. Tech. Third Semester (Information Technology), Rashtrasant Tukadoji Maharaj University, Nagpur

Subject Code: BIT3T09

• Course Objectives
  • To learn the concept of Data Structure using efficient algorithms
  • To solve real world problem using Data Structure Concepts.
• Course Outcomes
  After completion of syllabus, students would be able to:
  • CO 1: Understand the efficiency of an algorithm based on time and space complexity and classify an appropriate searching and sorting techniques to solve given problems.
  • CO 2: Apply the concepts of stack and queues to solve real world problem.
  • CO 3: Apply the Linked List Concept to evaluate the expression.
  • CO 4: Analyze the different traversing techniques using tree.
  • CO 5: Use various methods to represent graph and utilize graph concepts to solve real world problems and implement concept of hashing.

Syllabus

UNIT 1: Introduction to Algorithm
Introduction to Algorithm General Concepts of Data Structures; Types of Data Structures with its properties and operations; Time and Space Analysis of Algorithms, Big Oh, theta and omega notations; Average, Best and Worst Case Analysis; Sorting & Searching: Selection Sort, Insertion Sort, Heap Sort, Shell Sort; Linear Search, Binary Search

UNIT 2: Stacks and Queues
Stack ADT: Concept, primitive operations, implementation of stacks, multiple stacks, applications of stack, need for prefix and postfix expressions, conversion from infix to prefix and postfix expression, evaluation of prefix and postfix expression using stack.
Queue ADT: Concept, operations, simple queue, circular queue, double-ended and priority queue, applications of queue.

UNIT 3: Linked Lists
Concept, primitive operations, representation of linked lists, types of linked list- singly linked list, circular linked list and doubly linked list, polynomial manipulations: addition and multiplication using linked list.

UNIT 4: Trees
Basic Tree terminologies, tree definition and properties, binary tree and its operations, binary search tree (BST) and its operations, threaded binary trees, AVL tree and its rotation, red black tree, Btree, B+ tree, tree traversal techniques, applications of tree traversal techniques.

UNIT 5: Graphs and Hashing
Graphs: Graphs Representation, application of graphs, graph traversals techniques- DFS and BFS.
Hashing: Hash functions and hash tables, properties, simple hash function, methods for collision handling.

Unit 1: Introduction to Data Structures and Algorithms

1. Introduction to Algorithms

Unit 1 introduces the foundational concepts of algorithms and data structures, critical for efficient programming. Understanding data structure types (arrays, trees) and their operations equips students to choose appropriate structures for tasks like managing student records in a Nagpur college database. Time and space complexity analysis, using notations like Big O, guides algorithm selection for performance. Sorting (Selection, Insertion, Heap, Shell) and searching (Linear, Binary) algorithms provide practical tools for data manipulation, applicable in real-world projects like IoT-based traffic systems or AI-driven data analysis. The C code and diagrams illustrate these concepts, preparing students for advanced topics in the course.

An algorithm is a step-by-step procedure to solve a problem, expressed as a finite sequence of instructions (GeeksforGeeks, 2024). It is the backbone of computer science, enabling efficient computation for tasks like sorting, searching, or data processing.

Key Characteristics:

• Finiteness: Must terminate after a finite number of steps.
• Definiteness: Each step is precisely defined.
• Input: Accepts zero or more inputs.
• Output: Produces at least one output.
• Effectiveness: Each step is basic and executable.

Example: An algorithm to find the maximum number in an array involves scanning each element and updating the maximum value, a common task in programming.

Relevance for Students: Understanding algorithms is crucial for developing efficient solutions for real-world problems, such as optimizing traffic systems in Nagpur using sorting or searching algorithms.

2. General Concepts of Data Structures

A data structure is a way to organize and store data to enable efficient access and modification (Programiz, 2024). Data structures provide the foundation for algorithms, determining how data is stored and manipulated.

Key Concepts:

• Organization: Structures like arrays or trees arrange data for specific operations.
• Efficiency: Choice of data structure impacts performance (e.g., arrays for fast access, linked lists for dynamic insertion).
• Operations: Include insertion, deletion, traversal, searching, and sorting.
• Application: Used in databases, OS, and AI applications (e.g., IoT data storage in Nagpur smart city projects).

Example: An array stores student marks for quick access, while a linked list manages a dynamic playlist in a music app.

3. Types of Data Structures

Data structures are classified into primitive and non-primitive types, with further subdivisions (GeeksforGeeks, 2024).

3.1 Primitive Data Structures

Basic data types provided by programming languages.

• Types: Integer, Float, Character, Boolean.
• Properties: Simple, fixed-size, directly supported by hardware.
• Operations: Arithmetic, comparison, assignment.
• Example: int marks = 85; stores a student’s score.

3.2 Non-Primitive Data Structures

Complex structures built from primitive types, divided into linear and non-linear types.

Linear Data Structures

Data elements are arranged sequentially.

• Types:
  • Array: Fixed-size, contiguous memory, same data type.
  • Linked List: Nodes with data and pointers, dynamic size.
  • Stack: LIFO (Last In, First Out) structure.
  • Queue: FIFO (First In, First Out) structure.
• Properties: Sequential access, suitable for ordered data.
• Operations: Insert, delete, traverse, search.
• Example: An array of student IDs for a Nagpur college database.

Non-Linear Data Structures

Data elements are arranged hierarchically or interconnected.

• Types:
  • Tree: Hierarchical structure with nodes (e.g., binary tree).
  • Graph: Nodes connected by edges, representing relationships.
• Properties: Non-sequential, suitable for complex relationships.
• Operations: Traversal, insertion, deletion.
• Example: A tree to represent the organizational hierarchy of your college.

Diagram: Data Structure Classification

Data Structures
├── Primitive
│   ├── Integer
│   ├── Float
│   ├── Character
│   └── Boolean
└── Non-Primitive
    ├── Linear
    │   ├── Array
    │   ├── Linked List
    │   ├── Stack
    │   └── Queue
    └── Non-Linear
        ├── Tree
        └── Graph

Explanation: This diagram categorizes data structures, showing the hierarchy from primitive to non-primitive, linear, and non-linear types.

4. Time and Space Analysis of Algorithms

Algorithm efficiency is measured by time complexity (execution time) and space complexity (memory usage) (Programiz, 2024).

Time Complexity

Measures the number of operations as a function of input size (n).

• Notations:
  • Big O (O): Upper bound (worst-case scenario).
  • Theta (Θ): Tight bound (average-case scenario).
  • Omega (Ω): Lower bound (best-case scenario).
• Example: Linear search has (O(n)) time complexity, as it may need to check all (n) elements.

Space Complexity

Measures memory used, including variables and auxiliary space.

• Example: A recursive algorithm may have higher space complexity due to call stack usage.

Diagram: Asymptotic Notations

Time Complexity
  ↑
  │ O(n²)  (Quadratic)
  │ O(n)   (Linear)
  │ O(log n) (Logarithmic)
  │ O(1)   (Constant)
  └───────────────────→ Input Size (n)

Explanation: This graph illustrates how different time complexities grow with input size, with Big O notation defining the upper bound.

Average, Best, and Worst Case Analysis

• Best Case: Minimum time for favorable input (e.g., first element found in linear search, Ω(1)).
• Average Case: Expected time across all inputs (e.g., Θ(n/2) for linear search).
• Worst Case: Maximum time for unfavorable input (e.g., O(n) for linear search when element is last or absent).

Example: For sorting an array of student marks, best-case analysis assumes the array is already sorted, while worst-case assumes it’s reversed.

5. Sorting Algorithms

Sorting arranges elements in a specific order (ascending or descending). Below are the sorting algorithms specified in the syllabus, with C code and analysis.

5.1 Selection Sort

Repeatedly selects the smallest element and places it at the beginning.

• Time Complexity: O(n²) (best, average, worst).
• Space Complexity: O(1) (in-place).
• Properties: Simple, not adaptive, unstable.

C Code: Selection Sort

#include <stdio.h>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;
    printf("Before sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    selectionSort(arr, n);
    printf("\nAfter sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Explanation: This code sorts an array by repeatedly finding the minimum element and swapping it with the first unsorted element. Output: 12 22 25 34 64.

Diagram: Selection Sort

Initial: [64, 34, 25, 12, 22]
Pass 1: [12, 34, 25, 64, 22] (min=12, swap with 64)
Pass 2: [12, 22, 25, 64, 34] (min=22, swap with 34)
Pass 3: [12, 22, 25, 64, 34] (min=25, no swap)
Pass 4: [12, 22, 25, 34, 64] (min=34, swap with 64)

Explanation: This diagram shows how selection sort progresses through passes, selecting the minimum element each time.

5.2 Insertion Sort

Builds a sorted array by inserting each element into its correct position.

• Time Complexity: O(n²) worst/average, O(n) best (nearly sorted).
• Space Complexity: O(1) (in-place).
• Properties: Adaptive, stable, suitable for small datasets.

C Code: Insertion Sort

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;
    printf("Before sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    insertionSort(arr, n);
    printf("\nAfter sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Explanation: This code sorts by inserting each element into the correct position in the sorted portion of the array. Output: 12 22 25 34 64.

Diagram: Insertion Sort

Initial: [64, 34, 25, 12, 22]
Pass 1: [34, 64, 25, 12, 22] (insert 34)
Pass 2: [25, 34, 64, 12, 22] (insert 25)
Pass 3: [12, 25, 34, 64, 22] (insert 12)
Pass 4: [12, 22, 25, 34, 64] (insert 22)

Explanation: This diagram illustrates how insertion sort builds a sorted array by shifting elements to insert each new element.

5.3 Heap Sort

Uses a binary heap to sort elements, building a max-heap and repeatedly extracting the maximum.

• Time Complexity: O(n log n) (best, average, worst).
• Space Complexity: O(1) (in-place).
• Properties: Not adaptive, not stable, efficient for large datasets.

C Code: Heap Sort

#include <stdio.h>
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;
    printf("Before sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    heapSort(arr, n);
    printf("\nAfter sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Explanation: This code builds a max-heap and sorts by extracting the maximum element repeatedly. Output: 12 22 25 34 64.

Diagram: Heap Sort (Max-Heap)

Initial Array: [64, 34, 25, 12, 22]
Max-Heap:     [64, 34, 25, 12, 22]
After Heapify:[64, 34, 25, 12, 22]
Sorted:       [12, 22, 25, 34, 64]

Explanation: This diagram shows the max-heap structure and the sorting process, with the root (maximum) swapped to the end in each step.

5.4 Shell Sort

An extension of insertion sort, compares elements at a gap and reduces the gap over iterations.

• Time Complexity: O(n²) worst, O(n^{1.3}) average, depends on gap sequence.
• Space Complexity: O(1) (in-place).
• Properties: Adaptive, not stable.

C Code: Shell Sort

#include <stdio.h>
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}
int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;
    printf("Before sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    shellSort(arr, n);
    printf("\nAfter sorting: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Explanation: This code sorts by comparing elements at a gap, reducing the gap until it becomes 1 (insertion sort). Output: 12 22 25 34 64.

6. Searching Algorithms

Searching finds an element in a data structure. The syllabus covers linear and binary search.

6.1 Linear Search

Checks each element sequentially until the target is found or the array ends.

• Time Complexity: O(n) worst/average, O(1) best.
• Space Complexity: O(1).
• Properties: Simple, works on unsorted data.

C Code: Linear Search

#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (arr[i] == key)
            return i;
    return -1;
}
int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5, key = 25;
    int result = linearSearch(arr, n, key);
    if (result != -1)
        printf("Element %d found at index %d\n", key, result);
    else
        printf("Element %d not found\n", key);
    return 0;
}

Explanation: This code searches for 25 in the array, returning its index (2). Output: Element 25 found at index 2.

6.2 Binary Search

Divides a sorted array in half repeatedly to find the target.

• Time Complexity: O(log n) worst/average, O(1) best.
• Space Complexity: O(1) (iterative).
• Properties: Efficient, requires sorted data.

C Code: Binary Search

#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key)
            return mid;
        if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}
int main() {
    int arr[] = {12, 22, 25, 34, 64}; // Sorted array
    int n = 5, key = 25;
    int result = binarySearch(arr, 0, n-1, key);
    if (result != -1)
        printf("Element %d found at index %d\n", key, result);
    else
        printf("Element %d not found\n", key);
    return 0;
}

Explanation: This code searches for 25 in a sorted array, returning its index (2). Output: Element 25 found at index 2.

Diagram: Binary Search

Array: [12, 22, 25, 34, 64], Key = 25
Step 1: low=0, high=4, mid=2 (25 == 25, found)

Explanation: This diagram shows binary search narrowing the search range by half, finding the element at index 2.

Unit 2: Stacks and Queues

Unit 2 introduces stacks and queues, fundamental data structures for managing ordered data in LIFO and FIFO manners. Stacks are critical for applications like expression evaluation and backtracking, while queues support scheduling and resource management. The provided algorithms and C code for stack operations, expression conversion/evaluation, and queue variants (simple, circular, deque, priority) enable students to implement these structures in real-world projects, such as IoT-based traffic systems or AI event handling. This unit will help preparing students for advanced data structures like trees and graphs in later units.

1. Stack ADT

1.1 Concept

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where elements are added (pushed) and removed (popped) from the same end, called the top (GeeksforGeeks, 2024). It is an Abstract Data Type (ADT) defined by its operations, commonly used in scenarios requiring reversal or backtracking.

Key Characteristics:

• LIFO Order: Last element added is the first removed.
• Top: The point of insertion and deletion.
• Applications: Function call management, expression evaluation, undo mechanisms.

Example: A stack of books in a Nagpur college library—only the top book can be added or removed.

1.2 Primitive Operations

• Push: Add an element to the top.
• Pop: Remove and return the top element.
• Peek/Top: View the top element without removing it.
• isEmpty: Check if the stack is empty.
• isFull: Check if the stack is full (for array-based implementation).

1.3 Implementation of Stacks

Stacks can be implemented using arrays (fixed size) or linked lists (dynamic size). Array-based implementation is simpler but limited by size.

Algorithm: Push Operation (Array-Based)

Algorithm Push(stack, size, top, element)
1. If top >= size - 1
    Print "Stack Overflow"
    Return
2. Increment top
3. stack[top] = element
End

Algorithm: Pop Operation (Array-Based)

Algorithm Pop(stack, top)
1. If top < 0
    Print "Stack Underflow"
    Return -1
2. element = stack[top]
3. Decrement top
4. Return element
End

C Code: Stack Implementation (Array-Based)

#include <stdio.h>
#define MAX 100

struct Stack {
    int arr[MAX];
    int top;
};

void initStack(struct Stack *s) {
    s->top = -1;
}

void push(struct Stack *s, int element) {
    if (s->top >= MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    s->arr[++(s->top)] = element;
}

int pop(struct Stack *s) {
    if (s->top < 0) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

int peek(struct Stack *s) {
    if (s->top < 0) {
        printf("Stack is Empty\n");
        return -1;
    }
    return s->arr[s->top];
}

int main() {
    struct Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top element: %d\n", peek(&s)); // Output: 30
    printf("Popped: %d\n", pop(&s)); // Output: 30
    printf("Popped: %d\n", pop(&s)); // Output: 20
    return 0;
}

Explanation: This code implements a stack using an array, with push, pop, and peek operations. It demonstrates LIFO behavior by adding and removing elements from the top.

Diagram: Stack Operations

Initial: [ ] (top = -1)
Push 10: [10] (top = 0)
Push 20: [10, 20] (top = 1)
Push 30: [10, 20, 30] (top = 2)
Pop:     [10, 20] (top = 1, returns 30)

Explanation: This diagram shows the stack’s state after each operation, illustrating the LIFO principle.

1.4 Multiple Stacks

Multiple stacks use a single array to implement two or more stacks, optimizing memory usage. For two stacks, one grows from the start and the other from the end.

Algorithm: Push for Two Stacks in One Array

Algorithm PushStack1(stack, size, top1, element)
1. If top1 >= top2 - 1
    Print "Stack Overflow"
    Return
2. Increment top1
3. stack[top1] = element
End

Algorithm PushStack2(stack, size, top2, element)
1. If top1 >= top2 - 1
    Print "Stack Overflow"
    Return
2. Decrement top2
3. stack[top2] = element
End

C Code: Two Stacks in One Array

#include <stdio.h>
#define MAX 100

struct TwoStacks {
    int arr[MAX];
    int top1, top2;
};

void initTwoStacks(struct TwoStacks *ts, int size) {
    ts->top1 = -1;
    ts->top2 = size;
}

void push1(struct TwoStacks *ts, int element) {
    if (ts->top1 >= ts->top2 - 1) {
        printf("Stack Overflow\n");
        return;
    }
    ts->arr[++(ts->top1)] = element;
}

void push2(struct TwoStacks *ts, int element) {
    if (ts->top1 >= ts->top2 - 1) {
        printf("Stack Overflow\n");
        return;
    }
    ts->arr[--(ts->top2)] = element;
}

int main() {
    struct TwoStacks ts;
    initTwoStacks(&ts, MAX);
    push1(&ts, 5);
    push1(&ts, 10);
    push2(&ts, 15);
    push2(&ts, 20);
    printf("Stack 1: %d %d\n", ts.arr[0], ts.arr[1]); // Output: 5 10
    printf("Stack 2: %d %d\n", ts.arr[MAX-1], ts.arr[MAX-2]); // Output: 20 15
    return 0;
}

Explanation: This code implements two stacks in one array, with top1 growing from the start and top2 from the end, demonstrating efficient memory use.

1.5 Applications of Stack

• Function Call Management: Tracks function calls in recursion (e.g., factorial computation).
• Expression Evaluation: Converts and evaluates infix, prefix, and postfix expressions.
• Undo Mechanism: Stores states for reverting actions in software.
• Backtracking: Solves problems like maze navigation or puzzles.
• Example: In a Nagpur traffic management system, a stack tracks vehicle routing decisions for backtracking if a route fails.

1.6 Need for Prefix and Postfix Expressions

Infix expressions (e.g., A + B) are human-readable but complex for computers due to operator precedence and parentheses. Prefix (Polish notation, e.g., + A B) and Postfix (Reverse Polish notation, e.g., A B +) eliminate these issues, simplifying evaluation using stacks.

Advantages of Prefix/Postfix:

• No need for parentheses.
• Operator precedence is inherent.
• Efficient for machine evaluation.

1.7 Conversion from Infix to Prefix and Postfix

Converts infix expressions to prefix or postfix using a stack to manage operators.

Algorithm: Infix to Postfix Conversion

Algorithm InfixToPostfix(infix)
1. Initialize empty stack and postfix string
2. For each character in infix:
    a. If operand, append to postfix
    b. If '(', push to stack
    c. If ')', pop stack until '(' and append operators to postfix
    d. If operator, pop higher/equal precedence operators from stack, append to postfix, then push current operator
3. Pop remaining operators from stack to postfix
4. Return postfix
End

Algorithm: Infix to Prefix Conversion

Algorithm InfixToPrefix(infix)
1. Reverse infix expression
2. Replace '(' with ')' and vice versa
3. Apply InfixToPostfix algorithm
4. Reverse the result
5. Return prefix
End

C Code: Infix to Postfix Conversion

#include <stdio.h>
#include <string.h>
#define MAX 100

struct Stack {
    char arr[MAX];
    int top;
};

void initStack(struct Stack *s) {
    s->top = -1;
}

void push(struct Stack *s, char element) {
    if (s->top >= MAX - 1) return;
    s->arr[++(s->top)] = element;
}

char pop(struct Stack *s) {
    if (s->top < 0) return '\0';
    return s->arr[(s->top)--];
}

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void infixToPostfix(char infix[], char postfix[]) {
    struct Stack s;
    initStack(&s);
    int k = 0;
    for (int i = 0; infix[i]; i++) {
        if ((infix[i] >= 'A' && infix[i] <= 'Z') || (infix[i] >= 'a' && infix[i] <= 'z'))
            postfix[k++] = infix[i];
        else if (infix[i] == '(')
            push(&s, infix[i]);
        else if (infix[i] == ')') {
            while (s.top >= 0 && s.arr[s.top] != '(')
                postfix[k++] = pop(&s);
            pop(&s); // Remove '('
        } else {
            while (s.top >= 0 && precedence(s.arr[s.top]) >= precedence(infix[i]))
                postfix[k++] = pop(&s);
            push(&s, infix[i]);
        }
    }
    while (s.top >= 0)
        postfix[k++] = pop(&s);
    postfix[k] = '\0';
}

int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("Infix: %s\nPostfix: %s\n", infix, postfix); // Output: ABC*+
    return 0;
}

Explanation: This code converts an infix expression (A+B*C) to postfix (ABC*+) using a stack to manage operators based on precedence.

1.8 Evaluation of Prefix and Postfix Expressions

Evaluates prefix or postfix expressions using a stack by processing operands and operators.

Algorithm: Postfix Evaluation

Algorithm EvaluatePostfix(postfix)
1. Initialize empty stack
2. For each character in postfix:
    a. If operand, push to stack
    b. If operator, pop two operands, apply operator, push result
3. Return top of stack
End

Algorithm: Prefix Evaluation

Algorithm EvaluatePrefix(prefix)
1. Initialize empty stack
2. For each character in prefix (from right to left):
    a. If operand, push to stack
    b. If operator, pop two operands, apply operator, push result
3. Return top of stack
End

C Code: Postfix Evaluation

#include <stdio.h>
#include <string.h>
#define MAX 100

struct Stack {
    int arr[MAX];
    int top;
};

void initStack(struct Stack *s) {
    s->top = -1;
}

void push(struct Stack *s, int element) {
    if (s->top >= MAX - 1) return;
    s->arr[++(s->top)] = element;
}

int pop(struct Stack *s) {
    if (s->top < 0) return -1;
    return s->arr[(s->top)--];
}

int evaluatePostfix(char postfix[]) {
    struct Stack s;
    initStack(&s);
    for (int i = 0; postfix[i]; i++) {
        if (postfix[i] >= '0' && postfix[i] <= '9')
            push(&s, postfix[i] - '0');
        else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch (postfix[i]) {
                case '+': push(&s, op1 + op2); break;
                case '-': push(&s, op1 - op2); break;
                case '*': push(&s, op1 * op2); break;
                case '/': push(&s, op1 / op2); break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char postfix[] = "53+82-*"; // (5+3)*(8-2)
    int result = evaluatePostfix(postfix);
    printf("Postfix: %s\nResult: %d\n", postfix, result); // Output: 48
    return 0;
}

Explanation: This code evaluates the postfix expression 53+82-* (equivalent to (5+3)*(8-2)) to produce 48, using a stack to process operands and operators.

2. Queue ADT

2.1 Concept

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are added at the rear and removed from the front (Programiz, 2024). It is an ADT used in scheduling and resource management.

Key Characteristics:

• FIFO Order: First element added is the first removed.
• Front and Rear: Points for removal and insertion.
• Applications: Process scheduling, print queues, traffic systems.

Example: A queue of students waiting for admission at your Nagpur college—first in line is served first.

2.2 Operations

• Enqueue: Add an element to the rear.
• Dequeue: Remove and return the front element.
• Front/Peek: View the front element without removing it.
• isEmpty: Check if the queue is empty.
• isFull: Check if the queue is full (for array-based implementation).

2.3 Simple Queue

A basic queue implemented using an array or linked list, with fixed or dynamic size.

Algorithm: Enqueue (Array-Based)

Algorithm Enqueue(queue, size, front, rear, element)
1. If rear >= size - 1
    Print "Queue Overflow"
    Return
2. If front == -1
    front = 0
3. Increment rear
4. queue[rear] = element
End

Algorithm: Dequeue (Array-Based)

Algorithm Dequeue(queue, front, rear)
1. If front == -1
    Print "Queue Underflow"
    Return -1
2. element = queue[front]
3. If front == rear
    front = rear = -1
4. Else
    Increment front
5. Return element
End

C Code: Simple Queue (Array-Based)

#include <stdio.h>
#define MAX 100

struct Queue {
    int arr[MAX];
    int front, rear;
};

void initQueue(struct Queue *q) {
    q->front = q->rear = -1;
}

void enqueue(struct Queue *q, int element) {
    if (q->rear >= MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->arr[++(q->rear)] = element;
}

int dequeue(struct Queue *q) {
    if (q->front == -1) {
        printf("Queue Underflow\n");
        return -1;
    }
    int element = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front++;
    return element;
}

int main() {
    struct Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued: %d\n", dequeue(&q)); // Output: 10
    printf("Dequeued: %d\n", dequeue(&q)); // Output: 20
    return 0;
}

Explanation: This code implements a simple queue, adding elements at the rear and removing from the front, demonstrating FIFO behavior.

Diagram: Simple Queue Operations

Initial: [ ] (front = -1, rear = -1)
Enqueue 10: [10] (front = 0, rear = 0)
Enqueue 20: [10, 20] (front = 0, rear = 1)
Enqueue 30: [10, 20, 30] (front = 0, rear = 2)
Dequeue:    [20, 30] (front = 1, rear = 2, returns 10)

Explanation: This diagram shows the queue’s state after each operation, illustrating FIFO.

2.4 Circular Queue

A circular queue connects the rear to the front, reusing empty spaces to avoid wastage.

Algorithm: Enqueue (Circular Queue)

Algorithm EnqueueCircular(queue, size, front, rear, element)
1. If (rear + 1) % size == front
    Print "Queue Overflow"
    Return
2. If front == -1
    front = 0
3. rear = (rear + 1) % size
4. queue[rear] = element
End

C Code: Circular Queue

#include <stdio.h>
#define MAX 5

struct CircularQueue {
    int arr[MAX];
    int front, rear;
};

void initCircularQueue(struct CircularQueue *q) {
    q->front = q->rear = -1;
}

void enqueueCircular(struct CircularQueue *q, int element) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Queue Overflow\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = element;
}

int dequeueCircular(struct CircularQueue *q) {
    if (q->front == -1) {
        printf("Queue Underflow\n");
        return -1;
    }
    int element = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front = (q->front + 1) % MAX;
    return element;
}

int main() {
    struct CircularQueue q;
    initCircularQueue(&q);
    enqueueCircular(&q, 10);
    enqueueCircular(&q, 20);
    enqueueCircular(&q, 30);
    printf("Dequeued: %d\n", dequeueCircular(&q)); // Output: 10
    enqueueCircular(&q, 40); // Reuses space
    printf("Dequeued: %d\n", dequeueCircular(&q)); // Output: 20
    return 0;
}

Explanation: This code implements a circular queue, reusing space after dequeuing, improving efficiency.

2.5 Double-Ended Queue (Deque)

A double-ended queue (deque) allows insertion and deletion at both ends (front and rear).

Operations:

• EnqueueFront, EnqueueRear: Add at front or rear.
• DequeueFront, DequeueRear: Remove from front or rear.

Example: A deque for a task scheduler in a Nagpur traffic system, adding urgent tasks at the front and regular tasks at the rear.

2.6 Priority Queue

A priority queue assigns priorities to elements, dequeuing the highest-priority element first.

Operations:

• Enqueue: Add with priority.
• Dequeue: Remove highest-priority element.
• Example: A hospital triage system prioritizing critical patients.

C Code: Priority Queue (Using Array)

#include <stdio.h>
#define MAX 100

struct PriorityQueue {
    int arr[MAX];
    int priority[MAX];
    int size;
};

void initPriorityQueue(struct PriorityQueue *pq) {
    pq->size = 0;
}

void enqueuePriority(struct PriorityQueue *pq, int element, int prio) {
    if (pq->size >= MAX) {
        printf("Queue Overflow\n");
        return;
    }
    pq->arr[pq->size] = element;
    pq->priority[pq->size] = prio;
    pq->size++;
}

int dequeuePriority(struct PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Queue Underflow\n");
        return -1;
    }
    int maxPrioIdx = 0;
    for (int i = 1; i < pq->size; i++)
        if (pq->priority[i] > pq->priority[maxPrioIdx])
            maxPrioIdx = i;
    int element = pq->arr[maxPrioIdx];
    for (int i = maxPrioIdx; i < pq->size - 1; i++) {
        pq->arr[i] = pq->arr[i + 1];
        pq->priority[i] = pq->priority[i + 1];
    }
    pq->size--;
    return element;
}

int main() {
    struct PriorityQueue pq;
    initPriorityQueue(&pq);
    enqueuePriority(&pq, 10, 2);
    enqueuePriority(&pq, 20, 5);
    enqueuePriority(&pq, 30, 1);
    printf("Dequeued: %d\n", dequeuePriority(&pq)); // Output: 20 (highest priority)
    return 0;
}

Explanation: This code implements a priority queue, dequeuing the element with the highest priority (5).

2.7 Applications of Queue

• Process Scheduling: OS task scheduling (e.g., CPU job queues).
• Print Queue: Managing print jobs in a college lab.
• Traffic Systems: Queuing vehicles at Nagpur toll booths.
• Event Handling: Managing events in IoT systems (e.g., sensor data processing).

Unit 3: Linked Lists

Unit 3 introduces linked lists, dynamic data structures ideal for scenarios requiring flexible size and operations, such as polynomial manipulations. Singly, circular, and doubly linked lists cater to different use cases, from simple lists to circular buffers and bidirectional navigation.

1. Concept of Linked Lists

A linked list is a linear data structure where elements, called nodes, are stored in non-contiguous memory locations, connected via pointers (GeeksforGeeks, 2024). Unlike arrays, linked lists are dynamic, allowing flexible insertion and deletion. Each node contains data and a pointer to the next node (or previous in some cases).

Key Characteristics:

• Dynamic Size: Grows or shrinks as elements are added or removed.
• Non-Contiguous Memory: Nodes are allocated dynamically.
• Sequential Access: Elements accessed sequentially via pointers.
• Applications: Used in memory management, polynomial representation, and dynamic data structures like stacks or queues.

Example: A linked list storing student records in a Nagpur college database, allowing easy addition of new students or removal of graduates.

Diagram: Linked List Structure

[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL
(Node 1)      (Node 2)      (Node 3)

Explanation: Each node contains data (e.g., student ID) and a pointer to the next node, ending with NULL.

2. Primitive Operations

Linked lists support the following fundamental operations (Programiz, 2024):

• Insertion: Add a node at the beginning, end, or a specific position.
• Deletion: Remove a node from the beginning, end, or by value.
• Traversal: Access each node to display or process data.
• Search: Find a node with a specific value.
• Update: Modify the data in a node.

Relevance for Students: These operations are crucial for implementing dynamic data structures in projects like IoT-based sensor data management or AI-driven student record systems in Nagpur.

3. Representation of Linked Lists

Linked lists are typically implemented using a node structure in C, containing data and a pointer to the next node. The list is accessed via a head pointer pointing to the first node.

C Code: Basic Linked List Structure

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

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

Explanation: This defines a node with an integer data field and a next pointer to the next node.

4. Types of Linked Lists

4.1 Singly Linked List

A singly linked list has nodes with data and a pointer to the next node, with the last node pointing to NULL.

Properties:

• Time Complexity:
  • Insertion at start: O(1).
  • Insertion at end: O(n).
  • Deletion: O(n) (searching required).
  • Traversal: O(n).
• Space Complexity: O(n) for n nodes.

Algorithm: Insert at Beginning (Singly Linked List)

Algorithm InsertAtBeginning(head, data)
1. Create new node
2. Set newNode->data = data
3. Set newNode->next = head
4. Set head = newNode
End

Algorithm: Delete by Value (Singly Linked List)

Algorithm DeleteByValue(head, key)
1. If head is NULL, return
2. If head->data == key
    head = head->next
    Free old head
    Return
3. Traverse list to find node with key
4. If found, update previous node's next pointer
5. Free node
End

C Code: Singly Linked List Operations

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

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

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

struct Node* deleteByValue(struct Node* head, int key) {
    if (head == NULL) return head;
    if (head->data == key) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    struct Node* current = head;
    while (current->next != NULL && current->next->data != key)
        current = current->next;
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    return head;
}

void display(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    head = insertAtBeginning(head, 30);
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 10);
    printf("Singly Linked List: ");
    display(head); // Output: 10 -> 20 -> 30 -> NULL
    head = deleteByValue(head, 20);
    printf("After deleting 20: ");
    display(head); // Output: 10 -> 30 -> NULL
    return 0;
}

Explanation: This code implements a singly linked list with insertion at the beginning and deletion by value, demonstrating dynamic memory allocation.

Diagram: Singly Linked List Operations

Initial: NULL
Insert 30: [30|NULL]
Insert 20: [20|->30|NULL]
Insert 10: [10|->20|->30|NULL]
Delete 20: [10|->30|NULL]

Explanation: This diagram shows the list’s state after insertion and deletion operations.

4.2 Circular Linked List

A circular linked list has the last node pointing to the first node, forming a loop.

Properties:

• Time Complexity: Similar to singly linked list, but traversal continues indefinitely unless tracked.
• Applications: Circular buffers, scheduling tasks in a loop.

Algorithm: Insert at End (Circular Linked List)

Algorithm InsertAtEnd(head, data)
1. Create new node
2. Set newNode->data = data
3. If head is NULL
    Set newNode->next = newNode
    Set head = newNode
    Return
4. Traverse to last node
5. Set lastNode->next = newNode
6. Set newNode->next = head
End

C Code: Circular Linked List

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

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

struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (head == NULL) {
        newNode->next = newNode;
        return newNode;
    }
    struct Node* current = head;
    while (current->next != head)
        current = current->next;
    current->next = newNode;
    newNode->next = head;
    return head;
}

void display(struct Node* head) {
    if (head == NULL) return;
    struct Node* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(head)\n");
}

int main() {
    struct Node* head = NULL;
    head = insertAtEnd(head, 10);
    head = insertAtEnd(head, 20);
    head = insertAtEnd(head, 30);
    printf("Circular Linked List: ");
    display(head); // Output: 10 -> 20 -> 30 -> (head)
    return 0;
}

Explanation: This code implements a circular linked list, inserting nodes at the end and linking the last node to the head.

Diagram: Circular Linked List

[10|->] -> [20|->] -> [30|->]
   ^_______________________|

Explanation: This diagram shows a circular linked list where the last node (30) points back to the head (10).

4.3 Doubly Linked List

A doubly linked list has nodes with data, a pointer to the next node, and a pointer to the previous node.

Properties:

• Time Complexity:
  • Insertion/Deletion at known position: O(1).
  • Traversal: O(n).
• Space Complexity: O(n), higher due to extra pointers.
• Applications: Browser history, undo-redo functionality.

Algorithm: Insert at Beginning (Doubly Linked List)

Algorithm InsertAtBeginning(head, data)
1. Create new node
2. Set newNode->data = data
3. Set newNode->next = head
4. Set newNode->prev = NULL
5. If head != NULL
    Set head->prev = newNode
6. Set head = newNode
End

C Code: Doubly Linked List

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

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

struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    newNode->prev = NULL;
    if (head != NULL)
        head->prev = newNode;
    return newNode;
}

void display(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    head = insertAtBeginning(head, 30);
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 10);
    printf("Doubly Linked List: ");
    display(head); // Output: 10 <-> 20 <-> 30 <-> NULL
    return 0;
}

Explanation: This code implements a doubly linked list, inserting nodes at the beginning with bidirectional pointers.

Diagram: Doubly Linked List

NULL <- [10|<->] <-> [20|<->] <-> [30|<->] -> NULL

Explanation: This diagram shows a doubly linked list with nodes linked in both directions.

4.4 Polynomial Manipulations Using Linked Lists

Linked lists are ideal for representing polynomials, where each node stores a coefficient and exponent, enabling dynamic operations like addition and multiplication.

Representation: A node for a polynomial term:

struct PolyNode {
    int coeff;  // Coefficient
    int exp;    // Exponent
    struct PolyNode* next;
};

Polynomial Addition

Adds two polynomials by combining terms with the same exponent.

Algorithm: Polynomial Addition

Algorithm AddPolynomials(poly1, poly2)
1. Initialize result list as empty
2. While poly1 and poly2 are not NULL
    a. If poly1->exp == poly2->exp
        Add coefficients, insert to result, move poly1 and poly2
    b. If poly1->exp > poly2->exp
        Insert poly1 term to result, move poly1
    c. If poly1->exp < poly2->exp
        Insert poly2 term to result, move poly2
3. Append remaining terms of poly1 or poly2 to result
4. Return result
End

C Code: Polynomial Addition

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

struct PolyNode {
    int coeff, exp;
    struct PolyNode* next;
};

struct PolyNode* insertTerm(struct PolyNode* head, int coeff, int exp) {
    struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = head;
    return newNode;
}

struct PolyNode* addPolynomials(struct PolyNode* poly1, struct PolyNode* poly2) {
    struct PolyNode* result = NULL, *tail = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->next = NULL;
        if (poly1->exp == poly2->exp) {
            newNode->coeff = poly1->coeff + poly2->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->exp > poly2->exp) {
            newNode->coeff = poly1->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
        } else {
            newNode->coeff = poly2->coeff;
            newNode->exp = poly2->exp;
            poly2 = poly2->next;
        }
        if (result == NULL) {
            result = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    while (poly1 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->coeff = poly1->coeff;
        newNode->exp = poly1->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->coeff = poly2->coeff;
        newNode->exp = poly2->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly2 = poly2->next;
    }
    return result;
}

void displayPolynomial(struct PolyNode* poly) {
    while (poly != NULL) {
        printf("%dx^%d ", poly->coeff, poly->exp);
        poly = poly->next;
        if (poly != NULL) printf("+ ");
    }
    printf("\n");
}

int main() {
    struct PolyNode* poly1 = NULL, *poly2 = NULL;
    poly1 = insertTerm(poly1, 5, 2); // 5x^2
    poly1 = insertTerm(poly1, 4, 1); // 4x
    poly2 = insertTerm(poly2, 3, 2); // 3x^2
    poly2 = insertTerm(poly2, 2, 0); // 2
    printf("Polynomial 1: ");
    displayPolynomial(poly1); // Output: 4x^1 + 5x^2
    printf("Polynomial 2: ");
    displayPolynomial(poly2); // Output: 2x^0 + 3x^2
    struct PolyNode* result = addPolynomials(poly1, poly2);
    printf("Sum: ");
    displayPolynomial(result); // Output: 8x^2 + 4x^1 + 2x^0
    return 0;
}

Explanation: This code adds two polynomials (e.g., 5x^2 + 4x and 3x^2 + 2), producing 8x^2 + 4x + 2, using a linked list to store terms.

Polynomial Multiplication

Multiplies two polynomials by generating all possible term products and combining like terms.

Algorithm: Polynomial Multiplication

Algorithm MultiplyPolynomials(poly1, poly2)
1. Initialize result list as empty
2. For each term in poly1
    For each term in poly2
        Create new term with coeff = poly1->coeff * poly2->coeff
        Set exp = poly1->exp + poly2->exp
        Insert term into result (sorted by exponent)
3. Combine terms with same exponents in result
4. Return result
End

C Code: Polynomial Multiplication

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

struct PolyNode {
    int coeff, exp;
    struct PolyNode* next;
};

struct PolyNode* insertTerm(struct PolyNode* head, int coeff, int exp) {
    struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = head;
    return newNode;
}

struct PolyNode* multiplyPolynomials(struct PolyNode* poly1, struct PolyNode* poly2) {
    struct PolyNode* result = NULL;
    for (struct PolyNode* p1 = poly1; p1 != NULL; p1 = p1->next) {
        for (struct PolyNode* p2 = poly2; p2 != NULL; p2 = p2->next) {
            int coeff = p1->coeff * p2->coeff;
            int exp = p1->exp + p2->exp;
            struct PolyNode* current = result;
            struct PolyNode* prev = NULL;
            while (current != NULL && current->exp > exp) {
                prev = current;
                current = current->next;
            }
            if (current != NULL && current->exp == exp) {
                current->coeff += coeff;
            } else {
                struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
                newNode->coeff = coeff;
                newNode->exp = exp;
                newNode->next = current;
                if (prev == NULL)
                    result = newNode;
                else
                    prev->next = newNode;
            }
        }
    }
    return result;
}

void displayPolynomial(struct PolyNode* poly) {
    while (poly != NULL) {
        printf("%dx^%d ", poly->coeff, poly->exp);
        poly = poly->next;
        if (poly != NULL) printf("+ ");
    }
    printf("\n");
}

int main() {
    struct PolyNode* poly1 = NULL, *poly2 = NULL;
    poly1 = insertTerm(poly1, 2, 1); // 2x
    poly1 = insertTerm(poly1, 1, 0); // 1
    poly2 = insertTerm(poly2, 3, 1); // 3x
    poly2 = insertTerm(poly2, 1, 0); // 1
    printf("Polynomial 1: ");
    displayPolynomial(poly1); // Output: 1x^0 + 2x^1
    printf("Polynomial 2: ");
    displayPolynomial(poly2); // Output: 1x^0 + 3x^1
    struct PolyNode* result = multiplyPolynomials(poly1, poly2);
    printf("Product: ");
    displayPolynomial(result); // Output: 6x^2 + 5x^1 + 1x^0
    return 0;
}

Explanation: This code multiplies two polynomials (e.g., 2x + 1 and 3x + 1), producing 6x^2 + 5x + 1, combining like terms using a linked list.

Unit 5: Trees and Their Applications

Unit 5 introduces trees, powerful data structures for hierarchical data, with applications in databases, AI, and IoT systems. Binary trees, BSTs, AVL trees, red-black trees, B-trees, and B+ trees offer solutions for efficient storage and retrieval, while threaded trees optimize traversal. The provided algorithms and C code for BST operations, AVL rotations, and traversals enable students to implement these structures in projects like database indexing or IoT data organization.

1. Basic Tree Terminologies

A tree is a non-linear data structure used to represent hierarchical relationships, consisting of nodes connected by edges (GeeksforGeeks, 2024).

Key Terminologies:

• Node: Basic unit containing data and pointers to child nodes.
• Root: Topmost node with no parent.
• Leaf: Node with no children.
• Parent: Node with at least one child.
• Child: Node directly connected to a parent.
• Subtree: A tree rooted at a node, including its descendants.
• Height: Length of the longest path from root to leaf.
• Depth: Length of the path from root to a node.
• Level: Nodes at the same depth from the root.

Example: In a Nagpur college’s organizational hierarchy, the Principal is the root, department heads are children, and faculty are leaves.

Diagram: Tree Terminologies

       [Root]
      /      \
  [Child1]  [Child2]
  /    \            \
[Leaf] [Child3]    [Leaf]

Explanation: This diagram shows a tree with a root, children, and leaves, illustrating hierarchical structure.

2. Tree Definition and Properties

A tree is a connected, acyclic graph with a designated root node, where every node (except the root) has exactly one parent (Programiz, 2024).

Properties:

• Single Root: One node with no parent.
• No Cycles: No path forms a loop.
• Connected: A path exists between any two nodes.
• Number of Edges: For (n) nodes, a tree has (n-1) edges.
• Height: Maximum number of edges from root to leaf.

Example: A file system in a college server, where directories (nodes) form a tree, with the root directory at the top.

3. Binary Tree and Its Operations

A binary tree is a tree where each node has at most two children (left and right).

Properties:

• Maximum Nodes at Level (k): (2^k).
• Maximum Nodes in Tree of Height (h): (2^{h+1} – 1).
• Time Complexity: Traversal/insertion/deletion: O(n) in worst case.

Operations:

• Insertion: Add a node at an appropriate position.
• Deletion: Remove a node, adjusting pointers.
• Traversal: Visit all nodes (covered later).

C Code: Binary Tree Structure

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

4. Binary Search Tree (BST) and Its Operations

A binary search tree is a binary tree where for each node, the left subtree contains nodes with values less than the node, and the right subtree contains nodes with values greater (GeeksforGeeks, 2024).

Properties:

• Search Efficiency: O(h) where (h) is the height; O(log n) for balanced BST.
• Applications: Database indexing, dictionary implementation.

Operations:

• Insertion: Add a node while maintaining BST property.
• Deletion: Remove a node, handling cases (no child, one child, two children).
• Search: Find a node with a given value.

Algorithm: BST Insertion

Algorithm InsertBST(root, key)
1. If root is NULL
    Create new node with key
    Return new node
2. If key < root->data
    root->left = InsertBST(root->left, key)
3. Else if key > root->data
    root->right = InsertBST(root->right, key)
4. Return root
End

Algorithm: BST Search

Algorithm SearchBST(root, key)
1. If root is NULL or root->data == key
    Return root
2. If key < root->data
    Return SearchBST(root->left, key)
3. Else
    Return SearchBST(root->right, key)
End

C Code: BST Operations

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insertBST(struct Node* root, int key) {
    if (root == NULL) return createNode(key);
    if (key < root->data)
        root->left = insertBST(root->left, key);
    else if (key > root->data)
        root->right = insertBST(root->right, key);
    return root;
}

struct Node* searchBST(struct Node* root, int key) {
    if (root == NULL || root->data == key) return root;
    if (key < root->data) return searchBST(root->left, key);
    return searchBST(root->right, key);
}

int main() {
    struct Node* root = NULL;
    root = insertBST(root, 50);
    root = insertBST(root, 30);
    root = insertBST(root, 70);
    root = insertBST(root, 20);
    root = insertBST(root, 40);
    printf("BST created with nodes: 50, 30, 70, 20, 40\n");
    struct Node* found = searchBST(root, 40);
    printf("Search 40: %s\n", found ? "Found" : "Not Found"); // Output: Found
    return 0;
}

Explanation: This code implements a BST, inserting nodes and searching for a value (40), maintaining the BST property.

Diagram: Binary Search Tree

       [50]
      /    \
    [30]   [70]
   /   \
 [20] [40]

Explanation: This diagram shows a BST with nodes arranged by value (left < node < right).

5. Threaded Binary Trees

A threaded binary tree adds pointers (threads) to unused left or right pointers of nodes, linking to in-order predecessors or successors, improving traversal efficiency (GeeksforGeeks, 2024).

Types:

• Single Threaded: Right null pointers point to in-order successors.
• Fully Threaded: Both left and right null pointers point to predecessors and successors.

Advantages:

• Faster in-order traversal without recursion.
• Saves stack space.

C Code: Single Threaded Binary Tree (In-Order Successor)

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int isThreaded; // 1 if right is a thread
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->isThreaded = 0;
    return newNode;
}

struct Node* leftmost(struct Node* root) {
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}

void inorderThreaded(struct Node* root) {
    struct Node* current = leftmost(root);
    while (current != NULL) {
        printf("%d ", current->data);
        if (current->isThreaded)
            current = current->right;
        else
            current = leftmost(current->right);
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->left->right->isThreaded = 1;
    root->left->right->right = root; // Thread to in-order successor
    printf("In-order traversal of threaded binary tree: ");
    inorderThreaded(root); // Output: 4 2 5 1 3
    return 0;
}

Explanation: This code implements a single-threaded binary tree, with right null pointers threaded to in-order successors, enabling efficient in-order traversal.

6. AVL Tree and Its Rotations

An AVL tree is a self-balancing BST where the height difference (balance factor) between left and right subtrees of any node is at most 1 (Programiz, 2024).

Balance Factor: ( \text{Height(left subtree)} – \text{Height(right subtree)} ).

Rotations (to restore balance):

• Left-Left (LL): Right rotation.
• Right-Right (RR): Left rotation.
• Left-Right (LR): Left rotation on left child, then right rotation.
• Right-Left (RL): Right rotation on right child, then left rotation.

Algorithm: Right Rotation (LL Case)

Algorithm RightRotation(node)
1. Set newRoot = node->left
2. Set node->left = newRoot->right
3. Set newRoot->right = node
4. Update heights of node and newRoot
5. Return newRoot
End

C Code: AVL Tree Insertion with Right Rotation

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

struct Node {
    int data, height;
    struct Node* left;
    struct Node* right;
};

int max(int a, int b) { return a > b ? a : b; }

int getHeight(struct Node* node) {
    if (node == NULL) return 0;
    return node->height;
}

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    return x;
}

struct Node* insertAVL(struct Node* root, int key) {
    if (root == NULL) return createNode(key);
    if (key < root->data)
        root->left = insertAVL(root->left, key);
    else if (key > root->data)
        root->right = insertAVL(root->right, key);
    else
        return root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    int balance = getHeight(root->left) - getHeight(root->right);
    if (balance > 1 && key < root->left->data)
        return rightRotate(root);
    return root;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insertAVL(root, 10);
    root = insertAVL(root, 20);
    root = insertAVL(root, 5);
    printf("In-order traversal of AVL tree: ");
    inorder(root); // Output: 5 10 20
    return 0;
}

Explanation: This code implements an AVL tree with insertion and right rotation for LL imbalance, maintaining balance.

Diagram: Right Rotation (LL Case)

Before:       [10]        After:       [5]
             /                    /   \
           [5]                 [3]    [10]
          /
        [3]

Explanation: This diagram shows a right rotation to balance an AVL tree after inserting 3.

7. Red-Black Tree

A red-black tree is a self-balancing BST with nodes colored red or black, ensuring balance through specific properties (GeeksforGeeks, 2024).

Properties:

• Every node is red or black.
• Root is black.
• All leaves (NULL) are black.
• Red nodes cannot have red children (no two consecutive reds).
• Every path from root to leaf has the same number of black nodes.

Operations: Insertion and deletion involve rotations and recoloring.

Applications: Used in memory management, file systems, and Java’s TreeMap.

8. B-Tree

A B-tree is a self-balancing tree for disk-based storage, allowing multiple keys per node and multiple children (Programiz, 2024).

Properties:

• All leaves at the same level.
• Each node has at most (m) children (order (m)).
• Non-leaf nodes (except root) have at least (\lceil m/2 \rceil) children.
• Keys in nodes are sorted.

Applications: Database indexing (e.g., MySQL), file systems.

9. B+ Tree

A B+ tree is a variant of B-tree where only leaves store data, and internal nodes store keys for navigation (GeeksforGeeks, 2024).

Properties:

• All data in leaf nodes, linked for efficient range queries.
• Internal nodes store keys for indexing.
• Balanced, with high fan-out for disk efficiency.

Applications: Databases, file systems (e.g., NTFS).

Diagram: B+ Tree

       [20]
      /    \
  [10]    [30, 40]
 /   \         /   \
[5,7] [15]  [25,27] [35,50]

Explanation: This diagram shows a B+ tree with internal nodes for keys and linked leaves for data.

10. Tree Traversal Techniques

Traversal visits all nodes in a tree systematically. Common techniques for binary trees (GeeksforGeeks, 2024):

• In-order (Left, Root, Right): Visits nodes in sorted order for BST.
• Pre-order (Root, Left, Right): Useful for copying a tree.
• Post-order (Left, Right, Root): Useful for deleting a tree.

Algorithm: In-order Traversal

Algorithm Inorder(root)
1. If root is NULL, return
2. Inorder(root->left)
3. Visit root (print root->data)
4. Inorder(root->right)
End

C Code: Tree Traversals

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("In-order: ");
    inorder(root); // Output: 4 2 5 1 3
    printf("\nPre-order: ");
    preorder(root); // Output: 1 2 4 5 3
    printf("\nPost-order: ");
    postorder(root); // Output: 4 5 2 3 1
    return 0;
}

Explanation: This code implements in-order, pre-order, and post-order traversals for a binary tree.

11. Applications of Tree Traversal Techniques

• In-order:
  • BST sorting (produces sorted order).
  • Expression tree evaluation.
• Pre-order:
  • Copying a tree.
  • Serializing a tree for storage.
• Post-order:
  • Deleting a tree (free nodes after children).
  • Calculating space in file systems.
• Example: In a college database for example, in-order traversal retrieves student IDs in sorted order, while pre-order serializes the department hierarchy for backup.

Unit 5: Graphs and Hashing

1. Graphs

1.1 Graph Representation

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges, used to model relationships (GeeksforGeeks, 2024). Graphs can be directed (edges have direction) or undirected (edges are bidirectional).

Key Terminologies:

• Vertex: A node in the graph.
• Edge: Connection between two vertices.
• Adjacency: Two vertices connected by an edge.
• Degree: Number of edges connected to a vertex (in-degree/out-degree for directed graphs).

Graphs are represented in two primary ways:

1. Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there’s an edge from vertex i to j, else 0.
   • Space Complexity: O(V²), where V is the number of vertices.
   • Suitable: Dense graphs.
2. Adjacency List: An array of lists, where each list stores neighbors of a vertex.
   • Space Complexity: O(V + E), where E is the number of edges.
   • Suitable: Sparse graphs.

Diagram: Graph Representations

Undirected Graph:
   0 -- 1
   |    |
   3 -- 2

Adjacency Matrix:
   [0 1 1 0]
   [1 0 1 0]
   [1 1 0 1]
   [0 0 1 0]

Adjacency List:
   0: [1, 3]
   1: [0, 2]
   2: [1, 3]
   3: [0, 2]

Explanation: This diagram shows an undirected graph with 4 vertices, represented as both a matrix and a list.

C Code: Adjacency List Representation

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

#define MAX_VERTICES 100

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

struct Graph {
    struct Node* adjList[MAX_VERTICES];
    int vertices;
};

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL;
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
    // For undirected graph, add reverse edge
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->vertices; i++) {
        printf("Vertex %d: ", i);
        struct Node* current = graph->adjList[i];
        while (current != NULL) {
            printf("%d -> ", current->vertex);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    printGraph(graph); // Output: Adjacency list of the graph above
    return 0;
}

Explanation: This code implements an undirected graph using an adjacency list, adding edges and printing neighbors.

1.2 Applications of Graphs

• Social Networks: Modeling connections (e.g., friends on a Nagpur college alumni network).
• Navigation Systems: Finding shortest paths in traffic systems (e.g., Nagpur Smart City routes).
• Network Topology: Representing IoT sensor networks.
• Dependency Graphs: Task scheduling in software projects.

Example: A graph modeling bus routes in Nagpur, where vertices are stops and edges are routes, used for optimizing travel paths.

1.3 Graph Traversal Techniques

Graph traversal visits all vertices, exploring relationships. The syllabus specifies two techniques: Depth-First Search (DFS) and Breadth-First Search (BFS) (GeeksforGeeks, 2024).

Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking, using a stack (implicit via recursion or explicit).

Algorithm: DFS

Algorithm DFS(graph, vertex, visited)
1. Mark vertex as visited
2. Process vertex (e.g., print)
3. For each neighbor of vertex
    If neighbor is not visited
        DFS(graph, neighbor, visited)
End

C Code: DFS

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100

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

struct Graph {
    struct Node* adjList[MAX_VERTICES];
    int vertices;
};

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL;
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

void DFS(struct Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    struct Node* current = graph->adjList[vertex];
    while (current != NULL) {
        if (!visited[current->vertex])
            DFS(graph, current->vertex, visited);
        current = current->next;
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    int visited[MAX_VERTICES] = {0};
    printf("DFS Traversal: ");
    DFS(graph, 0, visited); // Possible Output: 0 1 2 3
    return 0;
}

Explanation: This code performs DFS on an undirected graph, visiting vertices deeply before backtracking.

Diagram: DFS Traversal

Graph:   0 -- 1
         |    |
         3 -- 2
DFS (start at 0): 0 -> 1 -> 2 -> 3

Explanation: This diagram shows DFS exploring vertex 0, then 1, 2, and 3, following one path to completion.

Breadth-First Search (BFS)

BFS explores all neighbors at the current level before moving to the next, using a queue.

Algorithm: BFS

Algorithm BFS(graph, start)
1. Initialize queue and visited array
2. Enqueue start vertex and mark as visited
3. While queue is not empty
    a. Dequeue vertex
    b. Process vertex (e.g., print)
    c. Enqueue all unvisited neighbors and mark as visited
End

C Code: BFS

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100

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

struct Graph {
    struct Node* adjList[MAX_VERTICES];
    int vertices;
};

struct Queue {
    int arr[MAX_VERTICES];
    int front, rear;
};

void initQueue(struct Queue* q) {
    q->front = q->rear = -1;
}

void enqueue(struct Queue* q, int element) {
    if (q->rear >= MAX_VERTICES - 1) return;
    if (q->front == -1) q->front = 0;
    q->arr[++(q->rear)] = element;
}

int dequeue(struct Queue* q) {
    if (q->front == -1) return -1;
    int element = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front++;
    return element;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL;
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

void BFS(struct Graph* graph, int start) {
    int visited[MAX_VERTICES] = {0};
    struct Queue q;
    initQueue(&q);
    visited[start] = 1;
    enqueue(&q, start);
    while (q.front != -1) {
        int vertex = dequeue(&q);
        printf("%d ", vertex);
        struct Node* current = graph->adjList[vertex];
        while (current != NULL) {
            if (!visited[current->vertex]) {
                visited[current->vertex] = 1;
                enqueue(&q, current->vertex);
            }
            current = current->next;
        }
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    printf("BFS Traversal: ");
    BFS(graph, 0); // Possible Output: 0 1 3 2
    return 0;
}

Explanation: This code performs BFS, exploring vertices level by level using a queue.

Diagram: BFS Traversal

Graph:   0 -- 1
         |    |
         3 -- 2
BFS (start at 0): 0 -> 1 -> 3 -> 2

Explanation: This diagram shows BFS visiting neighbors of 0 (1, 3) before moving to 2.

2. Hashing

2.1 Hash Functions and Hash Tables

Hashing maps data to a fixed-size table using a hash function, enabling fast retrieval (Programiz, 2024). A hash table is an array where keys are mapped to indices via the hash function.

Hash Function: Converts a key (e.g., string, number) into an index.

• Properties: Deterministic, uniform distribution, minimal collisions.

Hash Table Properties:

• Time Complexity: O(1) average for insertion, deletion, search.
• Space Complexity: O(n) for n elements.
• Applications: Databases, caching, symbol tables.

Example: A hash table storing student IDs in a Nagpur college database for quick lookup.

2.2 Simple Hash Function

A basic hash function maps keys to indices, e.g., modulo operation for integers.

Algorithm: Simple Hash Function

Algorithm Hash(key, tableSize)
1. Return key % tableSize
End

C Code: Simple Hash Table

#include <stdio.h>
#define TABLE_SIZE 10

struct HashTable {
    int table[TABLE_SIZE];
    int occupied[TABLE_SIZE]; // 1 if slot is occupied
};

void initHashTable(struct HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++)
        ht->occupied[i] = 0;
}

int hashFunction(int key) {
    return key % TABLE_SIZE;
}

void insert(struct HashTable* ht, int key) {
    int index = hashFunction(key);
    if (ht->occupied[index])
        printf("Collision at index %d\n", index);
    else {
        ht->table[index] = key;
        ht->occupied[index] = 1;
    }
}

int search(struct HashTable* ht, int key) {
    int index = hashFunction(key);
    if (ht->occupied[index] && ht->table[index] == key)
        return index;
    return -1;
}

int main() {
    struct HashTable ht;
    initHashTable(&ht);
    insert(&ht, 15);
    insert(&ht, 25); // Possible collision (15 % 10 = 25 % 10 = 5)
    int result = search(&ht, 15);
    printf("Search 15: %s at index %d\n", result != -1 ? "Found" : "Not Found", result);
    return 0;
}

Explanation: This code implements a simple hash table with modulo hash function, handling insertions and searches.

2.3 Methods for Collision Handling

Collisions occur when multiple keys map to the same index. Common methods include:

1. Chaining:
   • Store multiple elements at an index using a linked list.
   • Pros: Simple, handles many collisions.
   • Cons: Extra memory for lists.
   • Time Complexity: O(1 + α), where α is the load factor.
2. Open Addressing:
   • Find next available slot using probing (linear, quadratic, double hashing).
   • Linear Probing: Check next slot (index + 1).
   • Pros: No extra memory.
   • Cons: Clustering issues.

Algorithm: Linear Probing Insertion

Algorithm InsertLinearProbing(ht, key, tableSize)
1. index = hashFunction(key)
2. While ht->occupied[index]
    index = (index + 1) % tableSize
3. ht->table[index] = key
4. ht->occupied[index] = 1
End

C Code: Hash Table with Linear Probing

#include <stdio.h>
#define TABLE_SIZE 10

struct HashTable {
    int table[TABLE_SIZE];
    int occupied[TABLE_SIZE];
};

void initHashTable(struct HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++)
        ht->occupied[i] = 0;
}

int hashFunction(int key) {
    return key % TABLE_SIZE;
}

void insertLinearProbing(struct HashTable* ht, int key) {
    int index = hashFunction(key);
    int original = index;
    while (ht->occupied[index]) {
        index = (index + 1) % TABLE_SIZE;
        if (index == original) {
            printf("Hash Table Full\n");
            return;
        }
    }
    ht->table[index] = key;
    ht->occupied[index] = 1;
}

int searchLinearProbing(struct HashTable* ht, int key) {
    int index = hashFunction(key);
    int original = index;
    while (ht->occupied[index]) {
        if (ht->table[index] == key)
            return index;
        index = (index + 1) % TABLE_SIZE;
        if (index == original)
            break;
    }
    return -1;
}

int main() {
    struct HashTable ht;
    initHashTable(&ht);
    insertLinearProbing(&ht, 15);
    insertLinearProbing(&ht, 25); // Resolves collision at index 5
    int result = searchLinearProbing(&ht, 25);
    printf("Search 25: %s at index %d\n", result != -1 ? "Found" : "Not Found", result);
    return 0;
}

Explanation: This code implements a hash table with linear probing, resolving collisions by finding the next empty slot.

Diagram: Linear Probing

Hash Table (size=10):
Insert 15: [-, -, -, -, -, 15, -, -, -, -] (index 5)
Insert 25: [-, -, -, -, -, 15, 25, -, -, -] (index 6, collision at 5)

Explanation: This diagram shows how linear probing resolves a collision by placing 25 at the next available slot.

Question Bank: Data Structures and Algorithms

Unit 1: Introduction to Algorithm

1. Define an algorithm and list its five key characteristics.
   Bloom’s Level: Remembering
2. What is a data structure? Differentiate between primitive and non-primitive data structures.
   Bloom’s Level: Understanding
3. Explain the concept of time complexity and space complexity with examples.
   Bloom’s Level: Understanding
4. Write a C program to implement Selection Sort and analyze its time complexity.
   Bloom’s Level: Applying
5. Compare Big O, Theta, and Omega notations with respect to algorithm analysis.
   Bloom’s Level: Analyzing
6. Write a C program to perform Binary Search on a sorted array of integers.
   Bloom’s Level: Applying
7. What is the significance of best, average, and worst-case analysis in algorithms? Provide an example for each case in Linear Search.
   Bloom’s Level: Understanding
8. Analyze the time complexity of Insertion Sort for best, average, and worst cases.
   Bloom’s Level: Analyzing
9. Write a C program to implement Heap Sort for an array of student marks.
   Bloom’s Level: Applying
10. Explain how Shell Sort improves upon Insertion Sort. Provide an example.
    Bloom’s Level: Understanding
11. Evaluate the suitability of Selection Sort for large datasets compared to Heap Sort.
    Bloom’s Level: Evaluating
12. Write a C program to compare the performance of Linear Search and Binary Search for a sorted array.
    Bloom’s Level: Applying
13. What are the properties of linear and non-linear data structures? Give two examples of each.
    Bloom’s Level: Remembering
14. Design an algorithm to sort a list of Nagpur bus routes by distance using Insertion Sort.
    Bloom’s Level: Creating
15. Analyze why Binary Search requires a sorted array, and discuss its limitations.
    Bloom’s Level: Analyzing
16. Explain the role of asymptotic notations in algorithm analysis with a practical example.
    Bloom’s Level: Understanding
17. Write a C program to implement Shell Sort for an array of 10 elements.
    Bloom’s Level: Applying
18. Evaluate the trade-offs between time and space complexity in sorting algorithms.
    Bloom’s Level: Evaluating
19. Create a flowchart for the Binary Search algorithm and explain its steps.
    Bloom’s Level: Creating
20. Compare the stability of Selection Sort and Insertion Sort with examples.
    Bloom’s Level: Analyzing

Unit 2: Stacks and Queues

1. Define the Stack ADT and list its primitive operations.
   Bloom’s Level: Remembering
2. Explain the LIFO principle of stacks with a real-world example.
   Bloom’s Level: Understanding
3. Write a C program to implement a stack using an array with push and pop operations.
   Bloom’s Level: Applying
4. Analyze the advantages and disadvantages of implementing a stack using an array vs. a linked list.
   Bloom’s Level: Analyzing
5. What is a circular queue? Explain how it overcomes the limitations of a simple queue.
   Bloom’s Level: Understanding
6. Write a C program to implement a circular queue with enqueue and dequeue operations.
   Bloom’s Level: Applying
7. Explain the need for prefix and postfix expressions in computing.
   Bloom’s Level: Understanding
8. Write a C program to convert an infix expression to postfix using a stack.
   Bloom’s Level: Applying
9. Evaluate the efficiency of using a stack for expression evaluation compared to direct infix evaluation.
   Bloom’s Level: Evaluating
10. Design an algorithm to evaluate a postfix expression using a stack.
    Bloom’s Level: Creating
11. What is a double-ended queue (deque)? Provide an application in a Nagpur traffic system.
    Bloom’s Level: Understanding
12. Write a C program to implement two stacks in a single array.
    Bloom’s Level: Applying
13. Analyze the time complexity of push and pop operations in a stack implemented using a linked list.
    Bloom’s Level: Analyzing
14. Create a flowchart for converting an infix expression to prefix using a stack.
    Bloom’s Level: Creating
15. What are the applications of queues in operating systems? Provide two examples.
    Bloom’s Level: Remembering
16. Write a C program to implement a priority queue using an array.
    Bloom’s Level: Applying
17. Compare the FIFO principle of queues with the LIFO principle of stacks, with examples.
    Bloom’s Level: Analyzing
18. Evaluate the use of a circular queue in a print job management system for a college lab.
    Bloom’s Level: Evaluating
19. Explain how multiple stacks can optimize memory usage in a single array.
    Bloom’s Level: Understanding
20. Design a system using a stack to implement an undo mechanism for a text editor in C.
    Bloom’s Level: Creating

Unit 3: Linked Lists

1. Define a linked list and list its types with their key features.
   Bloom’s Level: Remembering
2. Explain the advantages of a linked list over an array for dynamic data storage.
   Bloom’s Level: Understanding
3. Write a C program to implement a singly linked list with insertion at the beginning.
   Bloom’s Level: Applying
4. Analyze the time complexity of insertion and deletion in a singly linked list vs. a doubly linked list.
   Bloom’s Level: Analyzing
5. What is a circular linked list? Explain its structure with a diagram.
   Bloom’s Level: Understanding
6. Write a C program to implement a circular linked list with insertion at the end.
   Bloom’s Level: Applying
7. Explain how a doubly linked list supports bidirectional traversal with an example.
   Bloom’s Level: Understanding
8. Write a C program to implement a doubly linked list with deletion by value.
   Bloom’s Level: Applying
9. Evaluate the suitability of a linked list for polynomial addition compared to an array.
   Bloom’s Level: Evaluating
10. Design an algorithm for polynomial multiplication using a linked list.
    Bloom’s Level: Creating
11. What are the primitive operations of a linked list? Provide their time complexities.
    Bloom’s Level: Remembering
12. Write a C program to add two polynomials using a linked list.
    Bloom’s Level: Applying
13. Analyze the challenges of memory management in linked lists compared to arrays.
    Bloom’s Level: Analyzing
14. Create a flowchart for inserting a node at a specific position in a singly linked list.
    Bloom’s Level: Creating
15. Explain the application of a doubly linked list in a browser’s history feature.
    Bloom’s Level: Understanding
16. Write a C program to reverse a singly linked list.
    Bloom’s Level: Applying
17. Compare the space complexity of singly, circular, and doubly linked lists.
    Bloom’s Level: Analyzing
18. Evaluate the use of a circular linked list in a round-robin scheduling system.
    Bloom’s Level: Evaluating
19. What is polynomial manipulation using linked lists? Provide an example.
    Bloom’s Level: Remembering
20. Design a system to manage a playlist using a circular linked list in C.
    Bloom’s Level: Creating

Unit 4: Trees

1. Define a binary tree and list its basic terminologies.
   Bloom’s Level: Remembering
2. Explain the properties of a binary search tree (BST) with an example.
   Bloom’s Level: Understanding
3. Write a C program to implement insertion in a binary search tree.
   Bloom’s Level: Applying
4. Analyze the time complexity of search and insertion operations in a BST.
   Bloom’s Level: Analyzing
5. What is an AVL tree? Explain its balance factor with a diagram.
   Bloom’s Level: Understanding
6. Write a C program to perform a right rotation in an AVL tree.
   Bloom’s Level: Applying
7. Explain the concept of a threaded binary tree and its advantages.
   Bloom’s Level: Understanding
8. Write a C program to perform in-order traversal on a threaded binary tree.
   Bloom’s Level: Applying
9. Evaluate the use of AVL trees vs. red-black trees for database indexing.
   Bloom’s Level: Evaluating
10. Design an algorithm for deleting a node from a binary search tree.
    Bloom’s Level: Creating
11. What are the properties of a red-black tree? Provide an example.
    Bloom’s Level: Remembering
12. Write a C program to implement pre-order and post-order traversals for a binary tree.
    Bloom’s Level: Applying
13. Analyze the need for rotations in AVL trees with an example of an LL imbalance.
    Bloom’s Level: Analyzing
14. Create a flowchart for in-order traversal of a binary tree.
    Bloom’s Level: Creating
15. Explain the applications of tree traversal techniques in a Nagpur college database.
    Bloom’s Level: Understanding
16. What is a B-tree? Explain its structure and properties.
    Bloom’s Level: Remembering
17. Write a C program to search for a value in a binary search tree.
    Bloom’s Level: Applying
18. Compare B-trees and B+ trees in terms of structure and applications.
    Bloom’s Level: Analyzing
19. Evaluate the efficiency of a threaded binary tree for in-order traversal compared to a standard binary tree.
    Bloom’s Level: Evaluating
20. Design a system to manage a hierarchical file system using a binary tree in C.
    Bloom’s Level: Creating

Unit 5: Graphs and Hashing

1. Define a graph and list its key terminologies.
   Bloom’s Level: Remembering
2. Explain the difference between directed and undirected graphs with examples.
   Bloom’s Level: Understanding
3. Write a C program to implement an adjacency list representation of a graph.
   Bloom’s Level: Applying
4. Analyze the space complexity of adjacency matrix vs. adjacency list representations.
   Bloom’s Level: Analyzing
5. What is Depth-First Search (DFS)? Explain its working with a diagram.
   Bloom’s Level: Understanding
6. Write a C program to implement DFS for an undirected graph.
   Bloom’s Level: Applying
7. Explain the concept of Breadth-First Search (BFS) and its applications.
   Bloom’s Level: Understanding
8. Write a C program to implement BFS for a graph.
   Bloom’s Level: Applying
9. Evaluate the suitability of DFS vs. BFS for finding the shortest path in an unweighted graph.
   Bloom’s Level: Evaluating
10. Design an algorithm for detecting a cycle in a graph using DFS.
    Bloom’s Level: Creating
11. What is a hash function? List its desirable properties.
    Bloom’s Level: Remembering
12. Write a C program to implement a hash table using linear probing for collision handling.
    Bloom’s Level: Applying
13. Analyze the time complexity of insertion and search in a hash table with chaining.
    Bloom’s Level: Analyzing
14. Create a flowchart for the BFS algorithm on a graph.
    Bloom’s Level: Creating
15. Explain how hashing is used in a Nagpur college database for student ID lookup.
    Bloom’s Level: Understanding
16. What are the methods for collision handling in hashing? Compare their advantages.
    Bloom’s Level: Remembering
17. Write a C program to implement a hash table using chaining for collision resolution.
    Bloom’s Level: Applying
18. Compare the performance of linear probing and chaining in hash tables.
    Bloom’s Level: Analyzing
19. Evaluate the use of graphs in modeling Nagpur’s bus route network for route optimization.
    Bloom’s Level: Evaluating
20. Design a system to implement a social network graph for a college alumni system in C.
    Bloom’s Level: Creating

List of Practicals for Data Structures and Algorithms Lab

Practical 1: Implementation of Selection Sort

Unit: 1 (Introduction to Algorithm)

Objective: Implement and analyze the Selection Sort algorithm to sort an array of integers.

Description: Write a C program to sort an array of student marks using Selection Sort. The program should accept the number of students and their marks, perform sorting, and display the sorted array. Calculate and display the time complexity for best, average, and worst cases.

Expected Outcome: Students will understand the Selection Sort algorithm, its O(n²) time complexity, and its application in sorting data like marks in a Nagpur college database.

Sample Code Snippet:

#include <stdio.h>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx]) min_idx = j;
        int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp;
    }
}
int main() {
    int n;
    printf("Enter number of students: ");
    scanf("%d", &n);
    int marks[n];
    printf("Enter marks: ");
    for (int i = 0; i < n; i++) scanf("%d", &marks[i]);
    selectionSort(marks, n);
    printf("Sorted marks: ");
    for (int i = 0; i < n; i++) printf("%d ", marks[i]);
    return 0;
}

Practical 2: Implementation of Binary Search

Unit: 1 (Introduction to Algorithm)

Objective: Implement Binary Search to find an element in a sorted array.

Description: Write a C program to search for a student ID in a sorted array of IDs using Binary Search. Accept the array size, elements, and search key from the user, and display whether the ID is found and its index.

Expected Outcome: Students will learn the efficiency of Binary Search (O(log n)) and its requirement for sorted data, applicable to searching student records.

Sample Code Snippet:

#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
int main() {
    int n, key;
    printf("Enter number of students: ");
    scanf("%d", &n);
    int ids[n];
    printf("Enter sorted IDs: ");
    for (int i = 0; i < n; i++) scanf("%d", &ids[i]);
    printf("Enter ID to search: ");
    scanf("%d", &key);
    int result = binarySearch(ids, 0, n-1, key);
    printf(result != -1 ? "ID found at index %d\n" : "ID not found\n", result);
    return 0;
}

Practical 3: Stack Implementation Using Array

Unit: 2 (Stacks and Queues)

Objective: Implement a stack using an array to perform push, pop, and peek operations.

Description: Write a C program to implement a stack for managing book IDs in a Nagpur college library. The program should support push (add book), pop (remove book), and peek (view top book) operations, with checks for overflow and underflow.

Expected Outcome: Students will understand the LIFO principle and stack operations, applicable to undo mechanisms or function call stacks.

Sample Code Snippet:

#include <stdio.h>
#define MAX 100
struct Stack {
    int arr[MAX];
    int top;
};
void initStack(struct Stack *s) { s->top = -1; }
void push(struct Stack *s, int id) {
    if (s->top >= MAX-1) { printf("Stack Overflow\n"); return; }
    s->arr[++(s->top)] = id;
}
int pop(struct Stack *s) {
    if (s->top < 0) { printf("Stack Underflow\n"); return -1; }
    return s->arr[(s->top)--];
}
int main() {
    struct Stack s;
    initStack(&s);
    push(&s, 101);
    push(&s, 102);
    printf("Popped: %d\n", pop(&s)); // Output: 102
    return 0;
}

Practical 4: Infix to Postfix Conversion

Unit: 2 (Stacks and Queues)

Objective: Implement infix to postfix expression conversion using a stack.

Description: Write a C program to convert an infix expression (e.g., A+B*C) to postfix (e.g., ABC*+) using a stack. Accept the infix expression as input and display the postfix result.

Expected Outcome: Students will learn stack-based expression conversion, useful for compiler design or arithmetic processing.

Sample Code Snippet:

#include <stdio.h>
#include <string.h>
#define MAX 100
struct Stack {
    char arr[MAX];
    int top;
};
void initStack(struct Stack *s) { s->top = -1; }
void push(struct Stack *s, char c) { s->arr[++(s->top)] = c; }
char pop(struct Stack *s) { return s->top < 0 ? '\0' : s->arr[(s->top)--]; }
int precedence(char op) { return (op == '+' || op == '-') ? 1 : (op == '*' || op == '/') ? 2 : 0; }
void infixToPostfix(char infix[], char postfix[]) {
    struct Stack s;
    initStack(&s);
    int k = 0;
    for (int i = 0; infix[i]; i++) {
        if ((infix[i] >= 'A' && infix[i] <= 'Z') || (infix[i] >= 'a' && infix[i] <= 'z'))
            postfix[k++] = infix[i];
        else if (infix[i] == '(') push(&s, infix[i]);
        else if (infix[i] == ')') {
            while (s.top >= 0 && s.arr[s.top] != '(') postfix[k++] = pop(&s);
            pop(&s);
        } else {
            while (s.top >= 0 && precedence(s.arr[s.top]) >= precedence(infix[i]))
                postfix[k++] = pop(&s);
            push(&s, infix[i]);
        }
    }
    while (s.top >= 0) postfix[k++] = pop(&s);
    postfix[k] = '\0';
}
int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("Postfix: %s\n", postfix); // Output: ABC*+
    return 0;
}

Practical 5: Circular Queue Implementation

Unit: 2 (Stacks and Queues)

Objective: Implement a circular queue to manage print jobs in a lab.

Description: Write a C program to implement a circular queue for handling print job IDs in a college computer lab. Support enqueue, dequeue, and display operations, handling overflow and underflow conditions.

Expected Outcome: Students will understand FIFO and circular queue efficiency, applicable to task scheduling systems.

Sample Code Snippet:

#include <stdio.h>
#define MAX 5
struct CircularQueue {
    int arr[MAX];
    int front, rear;
};
void initQueue(struct CircularQueue *q) { q->front = q->rear = -1; }
void enqueue(struct CircularQueue *q, int id) {
    if ((q->rear + 1) % MAX == q->front) { printf("Queue Overflow\n"); return; }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = id;
}
int dequeue(struct CircularQueue *q) {
    if (q->front == -1) { printf("Queue Underflow\n"); return -1; }
    int id = q->arr[q->front];
    if (q->front == q->rear) q->front = q->rear = -1;
    else q->front = (q->front + 1) % MAX;
    return id;
}
int main() {
    struct CircularQueue q;
    initQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    printf("Dequeued: %d\n", dequeue(&q)); // Output: 1
    return 0;
}

Practical 6: Singly Linked List Operations

Unit: 3 (Linked Lists)

Objective: Implement a singly linked list with basic operations.

Description: Write a C program to create a singly linked list to store student roll numbers. Implement insertion at the beginning, deletion by value, and display operations.

Expected Outcome: Students will master dynamic memory allocation and linked list operations, useful for dynamic data management.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int rollNo;
    struct Node* next;
};
struct Node* insertAtBeginning(struct Node* head, int roll) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->rollNo = roll;
    newNode->next = head;
    return newNode;
}
struct Node* deleteByValue(struct Node* head, int roll) {
    if (head == NULL) return head;
    if (head->rollNo == roll) {
        struct Node* temp = head->next;
        free(head);
        return temp;
    }
    struct Node* current = head;
    while (current->next != NULL && current->next->rollNo != roll)
        current = current->next;
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    return head;
}
void display(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->rollNo);
        head = head->next;
    }
    printf("NULL\n");
}
int main() {
    struct Node* head = NULL;
    head = insertAtBeginning(head, 101);
    head = insertAtBeginning(head, 102);
    display(head); // Output: 102 -> 101 -> NULL
    head = deleteByValue(head, 101);
    display(head); // Output: 102 -> NULL
    return 0;
}

Practical 7: Polynomial Addition Using Linked List

Unit: 3 (Linked Lists)

Objective: Implement polynomial addition using a linked list.

Description: Write a C program to represent two polynomials as linked lists (each node with coefficient and exponent) and perform their addition. Display both input polynomials and the result.

Expected Outcome: Students will learn to use linked lists for complex data like polynomials, applicable to mathematical computations.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
struct PolyNode {
    int coeff, exp;
    struct PolyNode* next;
};
struct PolyNode* insertTerm(struct PolyNode* head, int coeff, int exp) {
    struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = head;
    return newNode;
}
struct PolyNode* addPolynomials(struct PolyNode* poly1, struct PolyNode* poly2) {
    struct PolyNode* result = NULL, *tail = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->next = NULL;
        if (poly1->exp == poly2->exp) {
            newNode->coeff = poly1->coeff + poly2->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->exp > poly2->exp) {
            newNode->coeff = poly1->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
        } else {
            newNode->coeff = poly2->coeff;
            newNode->exp = poly2->exp;
            poly2 = poly2->next;
        }
        if (result == NULL) result = tail = newNode;
        else { tail->next = newNode; tail = newNode; }
    }
    while (poly1 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->coeff = poly1->coeff;
        newNode->exp = poly1->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
        newNode->coeff = poly2->coeff;
        newNode->exp = poly2->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly2 = poly2->next;
    }
    return result;
}
void displayPolynomial(struct PolyNode* poly) {
    while (poly != NULL) {
        printf("%dx^%d ", poly->coeff, poly->exp);
        poly = poly->next;
        if (poly != NULL) printf("+ ");
    }
    printf("\n");
}
int main() {
    struct PolyNode* poly1 = NULL, *poly2 = NULL;
    poly1 = insertTerm(poly1, 5, 2);
    poly1 = insertTerm(poly1, 4, 1);
    poly2 = insertTerm(poly2, 3, 2);
    poly2 = insertTerm(poly2, 2, 0);
    printf("Polynomial 1: ");
    displayPolynomial(poly1);
    printf("Polynomial 2: ");
    displayPolynomial(poly2);
    struct PolyNode* result = addPolynomials(poly1, poly2);
    printf("Sum: ");
    displayPolynomial(result);
    return 0;
}

Practical 8: Doubly Linked List Implementation

Unit: 3 (Linked Lists)

Objective: Implement a doubly linked list with insertion and deletion operations.

Description: Write a C program to create a doubly linked list to store course codes in a Nagpur college curriculum. Implement insertion at the end and deletion by value, with forward and backward display.

Expected Outcome: Students will understand bidirectional traversal and dynamic memory management, useful for applications like browser history.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int code;
    struct Node* next;
    struct Node* prev;
};
struct Node* insertAtEnd(struct Node* head, int code) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->code = code;
    newNode->next = NULL;
    newNode->prev = NULL;
    if (head == NULL) return newNode;
    struct Node* current = head;
    while (current->next != NULL) current = current->next;
    current->next = newNode;
    newNode->prev = current;
    return head;
}
void displayForward(struct Node* head) {
    while (head != NULL) {
        printf("%d <-> ", head->code);
        head = head->next;
    }
    printf("NULL\n");
}
int main() {
    struct Node* head = NULL;
    head = insertAtEnd(head, 101);
    head = insertAtEnd(head, 102);
    printf("Doubly Linked List: ");
    displayForward(head); // Output: 101 <-> 102 <-> NULL
    return 0;
}

Practical 9: Binary Search Tree Operations

Unit: 4 (Trees)

Objective: Implement a binary search tree with insertion and search operations.

Description: Write a C program to create a BST to store student grades. Implement insertion of grades and search for a specific grade, displaying whether it’s found.

Expected Outcome: Students will learn BST properties and operations, applicable to database indexing.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int grade;
    struct Node* left;
    struct Node* right;
};
struct Node* createNode(int grade) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->grade = grade;
    newNode->left = newNode->right = NULL;
    return newNode;
}
struct Node* insertBST(struct Node* root, int grade) {
    if (root == NULL) return createNode(grade);
    if (grade < root->grade) root->left = insertBST(root->left, grade);
    else if (grade > root->grade) root->right = insertBST(root->right, grade);
    return root;
}
struct Node* searchBST(struct Node* root, int grade) {
    if (root == NULL || root->grade == grade) return root;
    if (grade < root->grade) return searchBST(root->left, grade);
    return searchBST(root->right, grade);
}
int main() {
    struct Node* root = NULL;
    root = insertBST(root, 85);
    root = insertBST(root, 90);
    root = insertBST(root, 80);
    struct Node* found = searchBST(root, 90);
    printf("Grade 90: %s\n", found ? "Found" : "Not Found");
    return 0;
}

Practical 10: Tree Traversals

Unit: 4 (Trees)

Objective: Implement in-order, pre-order, and post-order traversals for a binary tree.

Description: Write a C program to create a binary tree representing a department hierarchy in a Nagpur college. Implement in-order, pre-order, and post-order traversals to display the nodes.

Expected Outcome: Students will understand tree traversal techniques and their applications, such as sorting or serialization.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("In-order: ");
    inorder(root); // Output: 4 2 5 1 3
    return 0;
}

Practical 11: Graph Traversal (DFS and BFS)

Unit: 5 (Graphs and Hashing)

Objective: Implement DFS and BFS for graph traversal.

Description: Write a C program to represent a graph of Nagpur bus routes using an adjacency list. Implement DFS and BFS to traverse the graph starting from a given bus stop.

Expected Outcome: Students will learn graph traversal techniques, applicable to navigation or network analysis.

Sample Code Snippet:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
struct Node {
    int vertex;
    struct Node* next;
};
struct Graph {
    struct Node* adjList[MAX_VERTICES];
    int vertices;
};
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    for (int i = 0; i < vertices; i++) graph->adjList[i] = NULL;
    return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}
void DFS(struct Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    struct Node* current = graph->adjList[vertex];
    while (current != NULL) {
        if (!visited[current->vertex]) DFS(graph, current->vertex, visited);
        current = current->next;
    }
}
int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    int visited[MAX_VERTICES] = {0};
    printf("DFS Traversal: ");
    DFS(graph, 0, visited);
    return 0;
}

Practical 12: Hash Table with Linear Probing

Unit: 5 (Graphs and Hashing)

Objective: Implement a hash table with linear probing for collision handling.

Description: Write a C program to create a hash table to store student IDs in a Nagpur college database. Implement insertion and search using linear probing to handle collisions.

Expected Outcome: Students will understand hashing and collision resolution, applicable to fast data retrieval in databases.

Sample Code Snippet:

#include <stdio.h>
#define TABLE_SIZE 10
struct HashTable {
    int table[TABLE_SIZE];
    int occupied[TABLE_SIZE];
};
void initHashTable(struct HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) ht->occupied[i] = 0;
}
int hashFunction(int key) { return key % TABLE_SIZE; }
void insertLinearProbing(struct HashTable* ht, int key) {
    int index = hashFunction(key), original = index;
    while (ht->occupied[index]) {
        index = (index + 1) % TABLE_SIZE;
        if (index == original) { printf("Hash Table Full\n"); return; }
    }
    ht->table[index] = key;
    ht->occupied[index] = 1;
}
int searchLinearProbing(struct HashTable* ht, int key) {
    int index = hashFunction(key), original = index;
    while (ht->occupied[index]) {
        if (ht->table[index] == key) return index;
        index = (index + 1) % TABLE_SIZE;
        if (index == original) break;
    }
    return -1;
}
int main() {
    struct HashTable ht;
    initHashTable(&ht);
    insertLinearProbing(&ht, 15);
    insertLinearProbing(&ht, 25);
    int result = searchLinearProbing(&ht, 25);
    printf("Search 25: %s at index %d\n", result != -1 ? "Found" : "Not Found", result);
    return 0;
}