BCSL-045 Solved Free Assignment 2024-25 Sem 4
Q1. Implement the Insertion Sort algorithm for sorting the following list of numbers in the ascending order, showing the list obtained at each step: 27, 15, 42, 3, 9, 29, 81, 54, 0, 13 Also calculate the total number of exchange operations and how many times the loop will execute in this algorithm.
Ans:-Â Â To implement the Insertion Sort algorithm on the list of numbers \( [27, 15, 42, 3, 9, 29, 81, 54, 0, 13] \), we will sort the numbers in ascending order, showing the list after each insertion step. We'll also count the total number of exchange operations and the number of loop executions.
 Insertion Sort Algorithm
Insertion sort works by dividing the list into a sorted and an unsorted part. The sorted part starts with the first element. We then take elements from the unsorted part and insert them into the correct position in the sorted part.
 Step-by-Step Implementation
 Initial List:
\[ 27, 15, 42, 3, 9, 29, 81, 54, 0, 13 \]
 Step 1: Starting with the first element (27 is already sorted)
- **List:** \[ 27 | 15, 42, 3, 9, 29, 81, 54, 0, 13 \]
 Step 2: Insert 15
- Compare 15 with 27. Since 15 < 27, move 27 to the right and insert 15 at the start.
- **List:** \[ 15, 27 | 42, 3, 9, 29, 81, 54, 0, 13 \]
- **Exchanges:** 1 (move 27)
 Â
 Step 3: Insert 42
- Compare 42 with 27. Since 42 > 27, it remains in its place.
- **List:** \[ 15, 27, 42 | 3, 9, 29, 81, 54, 0, 13 \]
- **Exchanges:** 0
 Step 4: Insert 3
- Compare 3 with 42, 27, and 15. Since 3 < 15, move 15, 27, and 42 to the right and insert 3 at the start.
- **List:** \[ 3, 15, 27, 42 | 9, 29, 81, 54, 0, 13 \]
- **Exchanges:** 3 (move 15, 27, 42)
 Step 5: Insert 9
- Compare 9 with 42, 27, and 15. Since 9 < 15, move 15, 27, and 42 to the right and insert 9 before 15.
- **List:** \[ 3, 9, 15, 27, 42 | 29, 81, 54, 0, 13 \]
- **Exchanges:** 3 (move 15, 27, 42)
 Step 6: Insert 29
- Compare 29 with 42. Since 29 < 42, move 42 to the right and insert 29.
- **List:** \[ 3, 9, 15, 27, 29, 42 | 81, 54, 0, 13 \]
- **Exchanges:** 1 (move 42)
 Step 7: Insert 81
- 81 > 42, it remains in its place.
- **List:** \[ 3, 9, 15, 27, 29, 42, 81 | 54, 0, 13 \]
- **Exchanges:** 0
 Step 8: Insert 54
- Compare 54 with 81. Since 54 < 81, move 81 to the right and insert 54.
- **List:** \[ 3, 9, 15, 27, 29, 42, 54, 81 | 0, 13 \]
- **Exchanges:** 1 (move 81)
 Step 9: Insert 0
- Compare 0 with 81, 54, 42, 29, 27, 15, and 9. Move all to the right and insert 0 at the start.
- **List:** \[ 0, 3, 9, 15, 27, 29, 42, 54, 81 | 13 \]
- **Exchanges:** 7 (move 81, 54, 42, 29, 27, 15, 9)
 Step 10: Insert 13
- Compare 13 with 81, 54, 42, 29, and 27. Move them to the right and insert 13 before 15.
- **List:** \[ 0, 3, 9, 13, 15, 27, 29, 42, 54, 81 \]
- **Exchanges:** 5 (move 81, 54, 42, 29, 27)
### Summary of Exchanges and Loop Executions
- **Total Exchanges:**
 - Step 2: 1
 - Step 3: 0
 - Step 4: 3
 - Step 5: 3
 - Step 6: 1
 - Step 7: 0
 - Step 8: 1
 - Step 9: 7
 - Step 10: 5
 - **Total Exchanges = 1 + 0 + 3 + 3 + 1 + 0 + 1 + 7 + 5 = 21**
- **Total Loop Executions**:Â
 - The outer loop (for each element) runs 9 times (from the second element to the last).
 - The inner loop executes based on the position of the elements being inserted. Here's the detailed count for each:
  - Insert 15: 1 comparison
  - Insert 42: 1 comparison
  - Insert 3: 3 comparisons
  - Insert 9: 4 comparisons
  - Insert 29: 2 comparisons
  - Insert 81: 1 comparison
  - Insert 54: 1 comparison
  - Insert 0: 7 comparisons
  - Insert 13: 5 comparisons
  - **Total Loop Executions = 1 + 1 + 3 + 4 + 2 + 1 + 1 + 7 + 5 = 25**
 Final Sorted List:
\[ 0, 3, 9, 13, 15, 27, 29, 42, 54, 81 \]
 Conclusion
- **Total Number of Exchanges**: 21
- **Total Loop Executions**: 25
The final sorted list is \( [0, 3, 9, 13, 15, 27, 29, 42, 54, 81] \).
Q2. Write a C program to implement the binary search algorithm. The program should first sort an array using any sorting algorithm and then search for a given element. Also, understand its efficiency.
Ans:-Â Â Here's a C program that implements the Binary Search algorithm after sorting an array using the Insertion Sort algorithm. This program will demonstrate both sorting and searching operations, as well as provide some insights into their efficiencies.
C Program: Binary Search with Sorting
```c
#include <stdio.h>
// Function to perform Insertion Sort
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
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}
// Function to perform Binary Search
int binarySearch(int arr[], int n, int x) {
  int left = 0, right = n - 1;
  Â
  while (left <= right) {
    int mid = left + (right - left) / 2; // To avoid overflow
    // Check if x is present at mid
    if (arr[mid] == x) {
      return mid; // Element found
    }
    // If x is greater, ignore left half
    if (arr[mid] < x) {
      left = mid + 1;
    }
    // If x is smaller, ignore right half
    else {
      right = mid - 1;
    }
  }
  return -1; // Element not found
}
int main() {
  int arr[] = {38, 27, 43, 3, 9, 82, 10};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 43; // Element to search
  // Sort the array
  insertionSort(arr, n);
  // Display sorted array
  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  // Perform Binary Search
  int result = binarySearch(arr, n, x);
  // Print the result
  if (result != -1) {
    printf("Element %d is present at index %d\n", x, result);
  } else {
    printf("Element %d is not present in the array\n", x);
  }
  return 0;
}
```
 Explanation
1. **Insertion Sort Function (`insertionSort`)**:
  - This function sorts an array of integers in ascending order using the insertion sort algorithm.
  - It iterates through the array, and for each element, it places it in the correct position relative to the already sorted portion of the array.
2. **Binary Search Function (`binarySearch`)**:
  - This function performs a binary search on a sorted array.
  - It uses a while loop to continually narrow down the search range by comparing the middle element to the target value.
  - If the target value is found, it returns the index; otherwise, it returns -1.
3. **Main Function**:
  - An example array is defined and its size is calculated.
  - The array is sorted using the `insertionSort` function.
  - The sorted array is printed.
  - The `binarySearch` function is called to search for a specific element (in this case, 43).
  - The result is printed to indicate whether the element was found and its index if applicable.
Efficiency Analysis
- **Insertion Sort**:
 - Best Case: O(n) when the array is already sorted.
 - Average and Worst Case: O(n²), as it involves nested loops to place each element in the correct position.
- **Binary Search**:
 - Efficiency: O(log n), as it reduces the search space by half with each iteration.
 - This efficiency is only achievable on sorted arrays.
Q3. Write a program to implement to reverse the following a given 5-digit number and calculate the total number of times the loop construct executed.
Ans:-  Here’s a C program that reverses a given 5-digit number and calculates the total number of times the loop construct executes during the reversal process.
 C Program: Reverse a 5-Digit Number
```c
#include <stdio.h>
int main() {
  int number, reversedNumber = 0, digit;
  int loopCount = 0; // To count the number of loop executions
  // Input: Prompt user for a 5-digit number
  printf("Enter a 5-digit number: ");
  scanf("%d", &number);
  // Check if the number is a 5-digit number
  if (number < 10000 || number > 99999) {
    printf("Please enter a valid 5-digit number.\n");
    return 1; // Exit if the number is not 5 digits
  }
  // Loop to reverse the number
  while (number != 0) {
    digit = number % 10;     // Get the last digit
    reversedNumber = reversedNumber * 10 + digit; // Build the reversed number
    number /= 10;         // Remove the last digit from the original number
    loopCount++;         // Increment the loop execution count
  }
  // Output: Display the reversed number and the loop execution count
  printf("Reversed Number: %d\n", reversedNumber);
  printf("Total loop executions: %d\n", loopCount);
  return 0;
}
```
 Explanation of the Program
1. **Variable Declaration**:
  - `number`: The original 5-digit number entered by the user.
  - `reversedNumber`: This variable stores the reversed number.
  - `digit`: This variable holds the last digit of the number during each iteration.
  - `loopCount`: This variable counts the number of times the loop executes.
2. **User Input**:
  - The program prompts the user to enter a 5-digit number.
  - It checks if the number is indeed a 5-digit number. If not, it prompts the user to enter a valid number and exits.
3. **Loop to Reverse the Number**:
  - The `while` loop continues until the `number` becomes 0.
  - Inside the loop:
   - The last digit of `number` is obtained using the modulus operator (`%`).
   - The `reversedNumber` is constructed by multiplying the current `reversedNumber` by 10 and adding the last digit.
   - The last digit is removed from `number` by performing integer division by 10.
   - The `loopCount` is incremented by 1 for each iteration.
4. **Output**:
  - Finally, the program prints the reversed number and the total number of loop executions.
 Example Usage
- If the user inputs `12345`, the output will be:
 ```
 Reversed Number: 54321
 Total loop executions: 5
 ```
This program efficiently reverses a 5-digit number while counting how many times the loop runs, making it a straightforward solution to the problem.
Q4. Write a C program to implement a stack using a linked list with push, pop, and display operations.
Ans:-  Here’s a C program that implements a stack using a linked list. The program includes the basic stack operations: `push`, `pop`, and `display`.
 C Program: Stack Using Linked List
```c
#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
  int data;
  struct Node* next;
};
// Define the stack structure
struct Stack {
  struct Node* top;
};
// Function to create a new node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}
// Function to initialize the stack
struct Stack* createStack() {
  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
  stack->top = NULL;
  return stack;
}
// Push operation
void push(struct Stack* stack, int data) {
  struct Node* newNode = createNode(data);
  newNode->next = stack->top; // Point new node to the current top
  stack->top = newNode;    // Update top to new node
  printf("Pushed %d onto stack.\n", data);
}
// Pop operation
int pop(struct Stack* stack) {
  if (stack->top == NULL) {
    printf("Stack underflow! Unable to pop.\n");
    return -1; // Return -1 to indicate stack is empty
  }
  int poppedValue = stack->top->data; // Get the top value
  struct Node* temp = stack->top;   // Temporary pointer to the top node
  stack->top = stack->top->next;    // Move top pointer to the next node
  free(temp);             // Free the old top node
  printf("Popped %d from stack.\n", poppedValue);
  return poppedValue;
}
// Display operation
void display(struct Stack* stack) {
  if (stack->top == NULL) {
    printf("Stack is empty.\n");
    return;
  }
  struct Node* current = stack->top;
  printf("Stack elements: ");
  while (current != NULL) {
    printf("%d ", current->data);
    current = current->next;
  }
  printf("\n");
}
// Main function to demonstrate stack operations
int main() {
  struct Stack* stack = createStack();
  Â
  push(stack, 10);
  push(stack, 20);
  push(stack, 30);
  display(stack);
  Â
  pop(stack);
  display(stack);
  Â
  pop(stack);
  display(stack);
  Â
  pop(stack);
  display(stack);
  Â
  // Attempt to pop from empty stack
  pop(stack);
  Â
  return 0;
}
```
 Explanation of the Program
1. **Node Structure**:
  - A `Node` structure is defined, containing an integer `data` and a pointer `next` to the next node in the stack.
2. **Stack Structure**:
  - A `Stack` structure is defined, containing a pointer `top` that points to the top node of the stack.
3. **Node Creation**:
  - The `createNode` function dynamically allocates memory for a new node and initializes its data and next pointer.
4. **Stack Initialization**:
  - The `createStack` function initializes an empty stack by allocating memory for a `Stack` structure and setting its `top` pointer to `NULL`.
5. **Push Operation**:
  - The `push` function creates a new node with the provided data and updates the stack’s `top` pointer to point to this new node. The new node’s `next` pointer is set to the previous top node.
6. **Pop Operation**:
  - The `pop` function checks if the stack is empty. If not, it retrieves the data from the top node, updates the `top` pointer, frees the memory of the popped node, and returns the popped value.
7. **Display Operation**:
  - The `display` function prints all elements in the stack from the top to the bottom.
8. **Main Function**:
  - In the `main` function, the stack is created, and a series of `push` and `pop` operations are demonstrated, along with calls to the `display` function to show the state of the stack at each step.
Example Output
When the program is run, the output will look like this:
```
Pushed 10 onto stack.
Pushed 20 onto stack.
Pushed 30 onto stack.
Stack elements: 30 20 10Â
Popped 30 from stack.
Stack elements: 20 10Â
Popped 20 from stack.
Stack elements: 10Â
Popped 10 from stack.
Stack is empty.
Stack underflow! Unable to pop.
```
Q5. Write a C program to implement a binary tree and perform in-order, pre-order, and post-order traversals. Also, understand the efficiency of the program.
Ans:-Â Here's a C program that implements a binary tree and performs in-order, pre-order, and post-order traversals. Additionally, I'll provide an explanation of the efficiency of these traversal methods.
 C Program: Binary Tree Traversals
```c
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a tree node
struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};
// Function to create a new tree node
struct Node* createNode(int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->left = newNode->right = NULL;
  return newNode;
}
// In-order Traversal
void inOrder(struct Node* root) {
  if (root != NULL) {
    inOrder(root->left);      // Traverse left subtree
    printf("%d ", root->data);   // Visit node
    inOrder(root->right);      // Traverse right subtree
  }
}
// Pre-order Traversal
void preOrder(struct Node* root) {
  if (root != NULL) {
    printf("%d ", root->data);   // Visit node
    preOrder(root->left);      // Traverse left subtree
    preOrder(root->right);     // Traverse right subtree
  }
}
// Post-order Traversal
void postOrder(struct Node* root) {
  if (root != NULL) {
    postOrder(root->left);     // Traverse left subtree
    postOrder(root->right);     // Traverse right subtree
    printf("%d ", root->data);   // Visit node
  }
}
// Main function to demonstrate tree operations
int main() {
  // Create a binary tree
  struct Node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("In-order Traversal: ");
  inOrder(root);
  printf("\n");
  printf("Pre-order Traversal: ");
  preOrder(root);
  printf("\n");
  printf("Post-order Traversal: ");
  postOrder(root);
  printf("\n");
  return 0;
}
```
 Explanation of the Program
1. **Node Structure**:
  - The program defines a `Node` structure containing an integer `data` and pointers to the left and right child nodes.
2. **Node Creation**:
  - The `createNode` function allocates memory for a new node and initializes its data and child pointers.
3. **Traversal Functions**:
  - **In-order Traversal**:
   - The `inOrder` function recursively traverses the left subtree, visits the node, and then traverses the right subtree.
   - This traversal results in the nodes being visited in ascending order for a binary search tree.
  - **Pre-order Traversal**:
   - The `preOrder` function visits the node first, then recursively traverses the left and right subtrees.
   - This traversal can be used to create a copy of the tree or to serialize it.
  - **Post-order Traversal**:
   - The `postOrder` function recursively traverses the left and right subtrees and then visits the node.
   - This traversal is useful for deleting the tree or evaluating postfix expressions.
4. **Main Function**:
  - In the `main` function, a binary tree is created manually using the `createNode` function.
  - The program then calls the three traversal functions and prints the nodes in the order they are visited.
 Example Output
When the program is executed, it produces the following output:
```
In-order Traversal: 4 2 5 1 6 3 7Â
Pre-order Traversal: 1 2 4 5 3 6 7Â
Post-order Traversal: 4 5 2 6 7 3 1Â
```
 Efficiency Analysis
- **Time Complexity**:
 - All three traversal methods (in-order, pre-order, and post-order) have a time complexity of **O(n)**, where **n** is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.
 Â
- **Space Complexity**:
 - The space complexity is **O(h)**, where **h** is the height of the tree. This space is used for the recursion stack. In the worst case (for a skewed tree), the height can be **O(n)**, leading to a space complexity of **O(n)**. For a balanced tree, the height would be **O(log n)**.
No comments: