DS | PAPER

1. Space complexity is sum of ____ and ____.
--> Fixed part (Instruction space) and Variable part (Data space).

---

2. ______ function is useful to read int value from the file.
--> getw() (Used to read an integer from a file).

---

3. ______ function is useful to set the location of the file pointer.
--> fseek().

1. Differentiate text file and binary file.

Text File: Stores data as plain readable text (ASCII characters). Each line ends with a newline character. Slower to read/write but human-readable. (Extension: `.txt`)

Binary File: Stores data in the exact memory format (0s and 1s) as the computer sees it. Faster to read/write, takes less space, but not human-readable. (Extension: `.bin`, `.dat`)

1. Write short note on asymptotic notation.

Asymptotic Notation is a mathematical tool used to describe the performance or complexity of an algorithm, specifically how the execution time or space requirements grow as the input size (n) increases toward infinity.

Types of Asymptotic Notations:
1. Big-O Notation (O): Represents the Upper Bound (Worst-case scenario). It gives the maximum time an algorithm could take. (e.g., $O(n^2)$)
2. Omega Notation (Ω): Represents the Lower Bound (Best-case scenario). It gives the minimum time an algorithm needs to execute. (e.g., $\Omega(n)$)
3. Theta Notation (Θ): Represents the Tight Bound (Average-case scenario). It bounds the algorithm from both above and below. (e.g., $\Theta(n \log n)$)

Why use it? It helps programmers compare algorithms independently of hardware or programming language speeds.

1. Quick sort is also known as ______.
--> Partition-exchange sort.

---

2. Explain different ways to create pivot point.
--> A pivot can be selected in 4 ways: 1. First element, 2. Last element, 3. Random element, 4. Median of three elements.

---

3. _____ is a sorting technique that sorts the elements by first dividing elements into several groups.
--> Shell Sort (or Radix sort).

2. Explain bubble sort algorithm.

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
- It passes through the array multiple times.
- In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.
- Time Complexity: $O(n^2)$ in the worst case.

1. Write a program that search an element using binary search algorithm.

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target)
            return mid; // Element found
            
        if (arr[mid] < target)
            low = mid + 1; // Search right half
        else
            high = mid - 1; // Search left half
    }
    return -1; // Element not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    
    int result = binarySearch(arr, size, target);
    
    if (result == -1)
        printf("Element not found in array");
    else
        printf("Element found at index: %d", result);
        
    return 0;
}

1. List out primitive data structure.
--> Integers (`int`), Floating-point (`float`, `double`), Characters (`char`), and Pointers.

---

2. In queue deletion is performed at ___ end.
--> Front end.

---

3. In stack insertion is performed at ____ end.
--> Top end.

2. Explain recursion with example.

Recursion is a programming technique where a function calls itself directly or indirectly to solve a smaller instance of the same problem. A recursive function must have a base case to stop the recursion and prevent an infinite loop.

Example (Factorial):

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive call
}

1. Write a program that performs push, pop and peep operations on stack.

#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int val) {
    if (top == MAX - 1) {
        printf("Stack Overflow!\n");
    } else {
        top++;
        stack[top] = val;
        printf("%d pushed.\n", val);
    }
}

void pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
    } else {
        printf("%d popped.\n", stack[top]);
        top--;
    }
}

void peep() {
    if (top == -1) {
        printf("Stack is empty.\n");
    } else {
        printf("Top element is %d\n", stack[top]);
    }
}

int main() {
    push(10);
    push(20);
    peep();
    pop();
    peep();
    return 0;
}

1. In linked list first node of the list is called _____.
--> Head.

---

2. Which linked list cannot store the NULL value in the list?
--> Circular Linked List (The last node points back to the first node instead of NULL).

---

3. Define header linked list.
--> A header linked list is a special type of linked list that contains a "header node" at the very beginning. This node does not store actual data but stores meta-information about the list (like the number of nodes).

2. Explain applications of linked list.

Linked lists are dynamic data structures used heavily in system programming. Applications include:
1. Implementing other data structures like Stacks, Queues, and Trees.
2. Dynamic memory allocation (managing free blocks of memory).
3. Maintaining directory names in an Operating System.
4. Creating "Previous" and "Next" functionality in web browsers (using Doubly Linked Lists).

1. Write a program for operation on singly linked list (Create, Insert First, Delete Last, Count).

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

struct Node {
    int data;
    struct Node* next;
};
struct Node* head = NULL;

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

void deleteLast() {
    if (head == NULL) return;
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

int countNodes() {
    int count = 0;
    struct Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

int main() {
    insertFirst(10); // Creates list implicitly
    insertFirst(20);
    insertFirst(30);
    printf("Total Nodes: %d\n", countNodes());
    deleteLast();
    printf("Nodes after delete: %d\n", countNodes());
    return 0;
}

1. Define Graph.
--> A Graph is a non-linear data structure consisting of nodes (vertices) connected by edges (lines). It is used to represent networks like city maps or social networks.

---

2. Define Leaf Node.
--> A node in a tree data structure that has absolutely no child nodes (its left and right pointers are NULL).

---

3. Write full form of AVL.
--> Adelson-Velsky and Landis (The inventors of the AVL Tree).

1. Explain adjacency List.

An Adjacency List is a way to represent a graph in computer memory. Instead of a 2D matrix, it uses an array of linked lists.
- The size of the array is equal to the number of vertices.
- Each index `i` in the array represents a vertex.
- The linked list at array index `i` contains all the vertices that are directly connected to vertex `i`. It saves a lot of memory for sparse graphs.

1. Create a binary search tree for the following elements: 15, 12, 6, 9, 24, 13, 29, 20, 27, 10, 8. Also write In-order, Pre-order and Post-order.

Binary Search Tree (Mobile-Safe View):

Root 15

Left 12

Left 6

Right 9

Left 8

Right 10

Right 13

Right 24

Left 20

Right 29

Left 27

---

Tree Traversals:

1. In-Order (Left, Root, Right):
(Always produces sorted output for a BST)
6, 8, 9, 10, 12, 13, 15, 20, 24, 27, 29

2. Pre-Order (Root, Left, Right):
15, 12, 6, 9, 8, 10, 13, 24, 20, 29, 27

3. Post-Order (Left, Right, Root):
8, 10, 9, 6, 13, 12, 20, 27, 29, 24, 15

[FY] DS | PAPER

DS | PAPER

1. Space complexity is sum of ____ and ____.
--> Fixed part (Instruction space) and Variable part (Data space).

---

2. ______ function is useful to read int value from the file.
--> getw() (Used to read an integer from a file).

---

3. ______ function is useful to set the location of the file pointer.
--> fseek().

1. Differentiate text file and binary file.

Text File: Stores data as plain readable text (ASCII characters). Each line ends with a newline character. Slower to read/write but human-readable. (Extension: `.txt`)

Binary File: Stores data in the exact memory format (0s and 1s) as the computer sees it. Faster to read/write, takes less space, but not human-readable. (Extension: `.bin`, `.dat`)

1. Write short note on asymptotic notation.

Asymptotic Notation is a mathematical tool used to describe the performance or complexity of an algorithm, specifically how the execution time or space requirements grow as the input size (n) increases toward infinity.

Types of Asymptotic Notations:
1. Big-O Notation (O): Represents the Upper Bound (Worst-case scenario). It gives the maximum time an algorithm could take. (e.g., $O(n^2)$)
2. Omega Notation (Ω): Represents the Lower Bound (Best-case scenario). It gives the minimum time an algorithm needs to execute. (e.g., $\Omega(n)$)
3. Theta Notation (Θ): Represents the Tight Bound (Average-case scenario). It bounds the algorithm from both above and below. (e.g., $\Theta(n \log n)$)

Why use it? It helps programmers compare algorithms independently of hardware or programming language speeds.

1. Quick sort is also known as ______.
--> Partition-exchange sort.

---

2. Explain different ways to create pivot point.
--> A pivot can be selected in 4 ways: 1. First element, 2. Last element, 3. Random element, 4. Median of three elements.

---

3. _____ is a sorting technique that sorts the elements by first dividing elements into several groups.
--> Shell Sort (or Radix sort).

2. Explain bubble sort algorithm.

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
- It passes through the array multiple times.
- In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.
- Time Complexity: $O(n^2)$ in the worst case.

1. Write a program that search an element using binary search algorithm.

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target)
            return mid; // Element found
            
        if (arr[mid] < target)
            low = mid + 1; // Search right half
        else
            high = mid - 1; // Search left half
    }
    return -1; // Element not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    
    int result = binarySearch(arr, size, target);
    
    if (result == -1)
        printf("Element not found in array");
    else
        printf("Element found at index: %d", result);
        
    return 0;
}

1. List out primitive data structure.
--> Integers (`int`), Floating-point (`float`, `double`), Characters (`char`), and Pointers.

---

2. In queue deletion is performed at ___ end.
--> Front end.

---

3. In stack insertion is performed at ____ end.
--> Top end.

2. Explain recursion with example.

Recursion is a programming technique where a function calls itself directly or indirectly to solve a smaller instance of the same problem. A recursive function must have a base case to stop the recursion and prevent an infinite loop.

Example (Factorial):

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive call
}

1. Write a program that performs push, pop and peep operations on stack.

#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int val) {
    if (top == MAX - 1) {
        printf("Stack Overflow!\n");
    } else {
        top++;
        stack[top] = val;
        printf("%d pushed.\n", val);
    }
}

void pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
    } else {
        printf("%d popped.\n", stack[top]);
        top--;
    }
}

void peep() {
    if (top == -1) {
        printf("Stack is empty.\n");
    } else {
        printf("Top element is %d\n", stack[top]);
    }
}

int main() {
    push(10);
    push(20);
    peep();
    pop();
    peep();
    return 0;
}

1. In linked list first node of the list is called _____.
--> Head.

---

2. Which linked list cannot store the NULL value in the list?
--> Circular Linked List (The last node points back to the first node instead of NULL).

---

3. Define header linked list.
--> A header linked list is a special type of linked list that contains a "header node" at the very beginning. This node does not store actual data but stores meta-information about the list (like the number of nodes).

2. Explain applications of linked list.

Linked lists are dynamic data structures used heavily in system programming. Applications include:
1. Implementing other data structures like Stacks, Queues, and Trees.
2. Dynamic memory allocation (managing free blocks of memory).
3. Maintaining directory names in an Operating System.
4. Creating "Previous" and "Next" functionality in web browsers (using Doubly Linked Lists).

1. Write a program for operation on singly linked list (Create, Insert First, Delete Last, Count).

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

struct Node {
    int data;
    struct Node* next;
};
struct Node* head = NULL;

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

void deleteLast() {
    if (head == NULL) return;
    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }
    struct Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

int countNodes() {
    int count = 0;
    struct Node* temp = head;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

int main() {
    insertFirst(10); // Creates list implicitly
    insertFirst(20);
    insertFirst(30);
    printf("Total Nodes: %d\n", countNodes());
    deleteLast();
    printf("Nodes after delete: %d\n", countNodes());
    return 0;
}

1. Define Graph.
--> A Graph is a non-linear data structure consisting of nodes (vertices) connected by edges (lines). It is used to represent networks like city maps or social networks.

---

2. Define Leaf Node.
--> A node in a tree data structure that has absolutely no child nodes (its left and right pointers are NULL).

---

3. Write full form of AVL.
--> Adelson-Velsky and Landis (The inventors of the AVL Tree).

1. Explain adjacency List.

An Adjacency List is a way to represent a graph in computer memory. Instead of a 2D matrix, it uses an array of linked lists.
- The size of the array is equal to the number of vertices.
- Each index `i` in the array represents a vertex.
- The linked list at array index `i` contains all the vertices that are directly connected to vertex `i`. It saves a lot of memory for sparse graphs.

1. Create a binary search tree for the following elements: 15, 12, 6, 9, 24, 13, 29, 20, 27, 10, 8. Also write In-order, Pre-order and Post-order.

Binary Search Tree (Mobile-Safe View):

Root 15

Left 12

Left 6

Right 9

Left 8

Right 10

Right 13

Right 24

Left 20

Right 29

Left 27

---

Tree Traversals:

1. In-Order (Left, Root, Right):
(Always produces sorted output for a BST)
6, 8, 9, 10, 12, 13, 15, 20, 24, 27, 29

2. Pre-Order (Root, Left, Right):
15, 12, 6, 9, 8, 10, 13, 24, 20, 29, 27

3. Post-Order (Left, Right, Root):
8, 10, 9, 6, 13, 12, 20, 27, 29, 24, 15