(1) A free() function is used to deallocate memory.

(2) The Ω (Omega) notation is used when the function g(n) defines a lower bound for the function f(n).

(3) Backtracking algorithm is based on depth-first search.

(4) In O notation, the expression O called asymptotic symbol.

(1) Define Big-O notation:
Big-O notation describes the upper bound of an algorithm’s time or space complexity. It represents the worst-case scenario of how an algorithm’s runtime grows as the input size increases. Formally, f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n₀.

OR

(2) Explain dangling pointer problem with example:
A dangling pointer occurs when a pointer points to a memory location that has been deallocated or freed. Example:

int *ptr = (int *)malloc(sizeof(int));
*ptr = 5;
free(ptr);  // Memory is freed but ptr still points to that location
// Now ptr is a dangling pointer
                

(1) Explain classes of algorithm:
Algorithms can be classified into several categories based on their approach:

• Divide and Conquer: Breaks problem into subproblems, solves each, and combines results (e.g., Merge Sort, Quick Sort).
• Greedy Algorithms: Makes locally optimal choices at each stage (e.g., Dijkstra’s algorithm, Huffman coding).
• Dynamic Programming: Solves problems by breaking them into overlapping subproblems and storing results (e.g., Fibonacci series, Knapsack problem).
• Backtracking: Builds solution incrementally and abandons partial solutions that fail constraints (e.g., N-Queens problem).
• Brute Force: Tries all possibilities until solution is found (e.g., linear search).
• Randomized: Uses random numbers for decisions (e.g., Randomized Quick Sort).

OR

(2) Explain enumerated constant with example:
Enumerated constants (enum) are user-defined data types that consist of integral constants. They make code more readable by assigning names to these constants.

enum days {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday};
// Sunday=0, Monday=1,... automatically assigned

enum days today = Wednesday;
printf("%d", today);  // Output: 3
                

Enums are useful for representing a set of related named constants in a more readable way than using plain integers.

(1) Explain dynamic memory allocation functions with example:
Dynamic memory allocation allows programs to request memory at runtime. Key functions in C:

• malloc(): Allocates specified bytes of memory. Example:

  int *ptr = (int*)malloc(10 * sizeof(int));  // Allocates array of 10 integers

• calloc(): Allocates memory and initializes to zero. Example:

  int *ptr = (int*)calloc(10, sizeof(int));  // Allocates and initializes to 0

• realloc(): Resizes previously allocated memory. Example:

  ptr = realloc(ptr, 20 * sizeof(int));  // Resizes to 20 integers

• free(): Deallocates memory to prevent memory leaks. Example:

  free(ptr);  // Releases allocated memory

These functions are declared in stdlib.h and are essential for efficient memory management.

OR

(2) What is algorithm analysis? Explain time and space complexity of algorithm:
Algorithm analysis is the process of determining the computational complexity of algorithms – the amount of resources (time and space) required to run them.

Time Complexity: Measures the amount of time an algorithm takes to complete as a function of input size. Common notations:

• O(1): Constant time
• O(log n): Logarithmic time
• O(n): Linear time
• O(n²): Quadratic time
• O(2ⁿ): Exponential time

Space Complexity: Measures the amount of memory space required by an algorithm as a function of input size. It includes:

• Fixed space requirements (code, simple variables)
• Variable space requirements (dynamic memory, recursion stack)

Example: Linear search has O(n) time complexity (worst case) and O(1) space complexity.

(1) Bucket sorting method is also known as bin sort.

(2) In bubble sorting techniques it compares each element of the list with the element next to it.

(3) Sorting techniques based on divide and conquer approach: Quick Sort and Merge Sort.

(4) Quick sort is using recursion for implementation.

(1) Algorithm for bubble sort:

BubbleSort(A, n) {
    for i = 0 to n-1 {
        for j = 0 to n-i-1 {
            if A[j] > A[j+1] {
                swap(A[j], A[j+1])
            }
        }
    }
}
                

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

OR

(2) Shell sort technique:
Shell sort is an optimization of insertion sort that allows exchange of items that are far apart. It works by:

1. Sorting elements that are distant from each other (using a gap sequence)
2. Gradually reducing the gap between elements
3. Finally performing a standard insertion sort when the gap is 1

The performance depends on the gap sequence used.

(1) Bucket sort technique:
Bucket sort (or bin sort) is a distribution sorting algorithm that works by:

1. Creating a number of “buckets” (typically an array of lists)
2. Scattering: Distributing the elements of the array into these buckets based on their values
3. Sorting each non-empty bucket (either recursively or using another algorithm)
4. Gathering: Visiting the buckets in order and putting all elements back into the original array

Example for sorting numbers between 0-99:

1. Create 10 buckets (0-9, 10-19, ..., 90-99)
2. Place each number in its corresponding bucket
3. Sort each bucket individually (using insertion sort)
4. Concatenate all buckets in order
                

Bucket sort works well when input is uniformly distributed over a range.

OR

(2) Algorithm for selection sort:

SelectionSort(A, n) {
    for i = 0 to n-1 {
        min_index = i
        for j = i+1 to n {
            if A[j] < A[min_index] {
                min_index = j
            }
        }
        swap(A[i], A[min_index])
    }
}
                

Selection sort works by:

1. Finding the minimum element in the unsorted portion of the array
2. Swapping it with the first unsorted element
3. Repeating this process until the entire array is sorted

Time complexity is O(n²) in all cases.

(1) Program for Insertion sort:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        /* Move elements of arr[0..i-1] that are greater than key
           to one position ahead of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    
    return 0;
}
                

Insertion sort works similarly to how we sort playing cards in our hands:

1. Start with the second element (consider first element as sorted)
2. Compare with elements before it and shift them right if they are greater
3. Insert the element in its correct position
4. Repeat for all elements

Time complexity: O(n²) worst case, O(n) best case (already sorted).

OR

(2) What do you mean by searching? Explain binary search with example:
Searching refers to the process of finding a particular element in a collection of items.

Binary Search: An efficient algorithm for finding an item from a sorted list of items. It works by:

1. Compare the target value to the middle element of the array
2. If they are equal, return the index
3. If the target is less than the middle element, search the left half
4. If the target is greater, search the right half
5. Repeat until the element is found or the search space is exhausted

Example (searching for 23 in sorted array):

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Steps:
1. Middle element is 16 (index 4) → 23 > 16 → search right
2. Subarray: [23, 38, 56, 72, 91], middle is 56 → 23 < 56 → search left
3. Subarray: [23, 38], middle is 23 → found at index 5
                

Binary search has O(log n) time complexity and requires the array to be sorted.

(1) LIFO stands for Last In First Out.

(2) In queue elements are inserted at rear end and deleted at front end.

(3) When new data are to be inserted into a data structure, but there is no available space such situation is known as overflow.

(4) Convert infix to postfix: \( \alpha^b / (\epsilon^d) + e \) → αb^εd^/e+

(1) Explain recursion with stack:
Recursion uses the call stack to keep track of function calls:

• Each recursive call pushes a new stack frame containing local variables and return address
• The stack grows with each recursive call until base case is reached
• As each call completes, its frame is popped from the stack
• The stack unwinds, returning to previous calls until original call completes

Example: Factorial calculation

factorial(4) calls factorial(3) calls factorial(2) calls factorial(1)
Stack grows with each call, then unwinds as each returns
                

OR

(2) Define priority queue:
A priority queue is a special type of queue where:

• Each element has a priority value associated with it
• Elements are dequeued based on priority (not just FIFO)
• Higher priority elements are dequeued before lower priority ones
• Elements with same priority are typically dequeued in FIFO order

Used in algorithms like Dijkstra's shortest path, Huffman coding, and operating system process scheduling.

(1) Explain types of data structure:
Data structures can be classified as:

1. Linear Data Structures:
   • Arrays: Fixed-size contiguous memory
   • Linked Lists: Nodes with data and pointer to next node
   • Stacks: LIFO structure with push/pop operations
   • Queues: FIFO structure with enqueue/dequeue
2. Non-linear Data Structures:
   • Trees: Hierarchical (binary trees, BST, AVL, etc.)
   • Graphs: Nodes connected by edges (directed/undirected)
3. Primitive vs Non-primitive:
   • Primitive: Basic types (int, float, char)
   • Non-primitive: Built from primitives (arrays, structures)
4. Static vs Dynamic:
   • Static: Fixed size (arrays)
   • Dynamic: Grows/shrinks (linked lists)

OR

(2) Explain types of Deque:
A deque (double-ended queue) allows insertion/deletion at both ends. Types include:

1. Input Restricted Deque:
   • Insertion allowed at only one end (rear)
   • Deletion allowed at both ends
   • Example: Undo operations where you can delete from both ends
2. Output Restricted Deque:
   • Deletion allowed at only one end (front)
   • Insertion allowed at both ends
   • Example: Job scheduling where new jobs can be added at either end
3. General Deque:
   • No restrictions on insert/delete operations
   • Can function as both stack and queue
   • Example: Web browser history (can add/remove from both ends)

(1) Menu driven program for circular queue operations:

#include <stdio.h>
#define SIZE 5

int queue[SIZE], front = -1, rear = -1;

void enqueue(int item) {
    if ((front == 0 && rear == SIZE-1) || (rear == (front-1)%(SIZE-1))) {
        printf("Queue is full\n");
        return;
    }
    else if (front == -1) {
        front = rear = 0;
    }
    else if (rear == SIZE-1 && front != 0) {
        rear = 0;
    }
    else {
        rear++;
    }
    queue[rear] = item;
    printf("Item inserted\n");
}

void dequeue() {
    if (front == -1) {
        printf("Queue is empty\n");
        return;
    }
    printf("Deleted element: %d\n", queue[front]);
    if (front == rear) {
        front = rear = -1;
    }
    else if (front == SIZE-1) {
        front = 0;
    }
    else {
        front++;
    }
}

void display() {
    if (front == -1) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    if (rear >= front) {
        for (int i = front; i <= rear; i++)
            printf("%d ", queue[i]);
    }
    else {
        for (int i = front; i < SIZE; i++)
            printf("%d ", queue[i]);
        for (int i = 0; i <= rear; i++)
            printf("%d ", queue[i]);
    }
    printf("\n");
}

int main() {
    int choice, item;
    while (1) {
        printf("\n1. Insert\n2. Delete\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1: 
                printf("Enter item: ");
                scanf("%d", &item);
                enqueue(item);
                break;
            case 2:
                dequeue();
                break;
            case 3:
                display();
                break;
            case 4:
                return 0;
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}
                

OR

(2) Algorithm for stack operations:
Push Operation:

1. Check if stack is full (if top == MAX_SIZE-1)
2. If full, display "Stack Overflow" and exit
3. Else:
   a. Increment top by 1
   b. Set stack[top] = new_element
4. End
                

Pop Operation:

1. Check if stack is empty (if top == -1)
2. If empty, display "Stack Underflow" and exit
3. Else:
   a. Store stack[top] in a temporary variable
   b. Decrement top by 1
   c. Return the temporary variable
4. End
                

Display Operation:

1. Check if stack is empty (if top == -1)
2. If empty, display "Stack is empty"
3. Else:
   a. Set i = top
   b. While i >= 0:
      i. Print stack[i]
      ii. Decrement i by 1
4. End
                

(1) Linked list is known as dynamic data type.

(2) Each entry in a linked list is called a node.

(3) Doubly linked list can be performed traversal in both directions.

(4) There are three fields in node of doubly linked list: Previous pointer, Data, and Next pointer.

(1) Define linked list:
A linked list is a linear data structure where:

• Elements are stored in nodes
• Each node contains data and a pointer/reference to the next node
• Nodes are not stored in contiguous memory locations
• Size can grow/shrink dynamically during program execution
• First node is accessed via a head pointer

OR

(2) Advantages of Linked list over array:

• Dynamic size: Can grow/shrink at runtime (no need to pre-allocate)
• Efficient insertion/deletion: O(1) time complexity at beginning vs O(n) for arrays
• No memory waste: Allocates memory as needed (arrays may reserve unused space)
• Flexibility: Can easily implement stacks, queues, trees, graphs
• Memory efficiency: Better for large data items (only stores pointers with data)

(1) Program to reverse a linked list:

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

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

void reverse(struct Node** head_ref) {
    struct Node* prev = NULL;
    struct Node* current = *head_ref;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;  // Store next
        current->next = prev;  // Reverse current node's pointer
        prev = current;        // Move pointers one position ahead
        current = next;
    }
    *head_ref = prev;  // Update head to new first node
}

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

int main() {
    struct Node* head = NULL;
    
    // Create a sample linked list: 1->2->3->4
    for (int i = 4; i >= 1; i--) {
        struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = i;
        new_node->next = head;
        head = new_node;
    }
    
    printf("Original list: ");
    printList(head);
    
    reverse(&head);
    
    printf("Reversed list: ");
    printList(head);
    
    return 0;
}
                

This program:

1. Creates a sample linked list (1→2→3→4)
2. Reverses it by iterating through the list and changing pointers
3. Prints the list before and after reversal

Time complexity: O(n), Space complexity: O(1)

OR

(2) Header linked list and its types:
A header linked list is a special type that contains a header node at the beginning:

• Header node doesn't contain actual data
• May contain metadata like list length or other info

Types:

1. Grounded Header Linked List:
   • Last node points back to header node
   • Forms a circular reference
   • Useful when we need to traverse entire list repeatedly
2. Circular Header Linked List:
   • Last node points to first data node (not header)
   • Header remains separate starting point
   • Provides quick access to both start and end

Advantages:

• Simplifies empty list handling (always has header)
• Can store aggregate information about the list
• Provides uniform handling of first node

(1) Algorithms for doubly linked list operations:
Insert at any position:

1. Create new node with given data
2. If list is empty:
   a. Set new_node->prev = NULL
   b. Set new_node->next = NULL
   c. Set head = new_node
3. Else if inserting at beginning:
   a. Set new_node->prev = NULL
   b. Set new_node->next = head
   c. Set head->prev = new_node
   d. Set head = new_node
4. Else:
   a. Traverse to the position-1 node (temp)
   b. Set new_node->next = temp->next
   c. Set new_node->prev = temp
   d. If temp->next is not NULL:
      i. Set temp->next->prev = new_node
   e. Set temp->next = new_node
5. End
                

Delete at any position:

1. If list is empty, display error and return
2. If deleting first node:
   a. Set temp = head
   b. Set head = head->next
   c. If new head is not NULL:
      i. Set head->prev = NULL
   d. Free temp
3. Else:
   a. Traverse to the node to delete (temp)
   b. Set temp->prev->next = temp->next
   c. If temp->next is not NULL:
      i. Set temp->next->prev = temp->prev
   d. Free temp
4. End
                

Display:

1. If head is NULL, display "List is empty" and return
2. Set temp = head
3. While temp is not NULL:
   a. Print temp->data
   b. Set temp = temp->next
4. End
                

OR

(2) Menu driven program for singly linked list operations:

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

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

struct Node* head = NULL;

void Create() {
    int n, value;
    printf("Enter number of nodes: ");
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        printf("Enter value for node %d: ", i+1);
        scanf("%d", &value);
        
        struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = value;
        new_node->next = head;
        head = new_node;
    }
}

void InsertFirst() {
    int value;
    printf("Enter value to insert: ");
    scanf("%d", &value);
    
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = value;
    new_node->next = head;
    head = new_node;
    
    printf("Node inserted at beginning\n");
}

void DeleteFirst() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    struct Node* temp = head;
    head = head->next;
    free(temp);
    printf("First node deleted\n");
}

void Display() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    struct Node* temp = head;
    printf("List elements: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    int choice;
    
    while (1) {
        printf("\n1. Create List\n2. Insert at First\n3. Delete First\n4. Display\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1: Create(); break;
            case 2: InsertFirst(); break;
            case 3: DeleteFirst(); break;
            case 4: Display(); break;
            case 5: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    
    return 0;
}
                

This program provides:

• Create(): Builds a linked list with user-specified nodes
• InsertFirst(): Adds node at beginning (O(1) time)
• DeleteFirst(): Removes first node (O(1) time)
• Display(): Shows current list contents
• Menu-driven interface for user interaction