Binary Search Tree (BST)

A Binary Search Tree (BST) is a tree that follows these rules:

• The left sub-tree of a node contains values less than or equal to the parent node’s value.
• The right sub-tree of a node contains values greater than or equal to the parent node’s value.

BST from these values insertion : [27, 14, 35, 10, 19, 31, 42]

        27
       /  \
     14    35
    /  \   /  \
  10   19 31  42

The post-order traversal of the given Binary Search Tree (BST) is:

10, 19, 14, 31, 42, 35, 27

BST Deletion:

To delete a node from a Binary Search Tree (BST), we follow these steps:

1. Node has no children: Just remove the node.
2. Node has one child: Remove the node and link its parent to its child.
3. Node has two children: Find the in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree), replace the node to be deleted with the successor or predecessor, and delete the successor or predecessor.

Deleting Node 35 from the BST:

We are deleting node 35, which has two children (31 and 42). The in-order successor of 35 is 42. So, we replace 35 with 42 and then remove node 42, which has no children.

        27
       /  \
     14    42
    /  \   /  
  10   19 31  

#include <stdio.h>
#include <math.h>

// Function to calculate factorial
double factorial(int n) {
    double result = 1.0;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

// Function to calculate sine using the series expansion
double sine_series(double x, int terms) {
    double sum = 0.0;
    for (int n = 0; n < terms; n++) {
        int sign = (n % 2 == 0) ? 1 : -1; // Alternating signs
        double term = pow(x, 2 * n + 1) / factorial(2 * n + 1);
        sum += sign * term;
    }
    return sum;
}

int main() {
    double x;
    int terms;

    // Input angle in radians and number of terms
    printf("Enter the value of x (in radians): ");
    scanf("%lf", &x);
    printf("Enter the number of terms: ");
    scanf("%d", &terms);

    // Calculate sine using the series expansion
    double result = sine_series(x, terms);

    // Output the result
    printf("The sine of %.2lf using %d terms is: %.6lf\n", x, terms, result);

    return 0;
}

c)

Given Data:

• Hit Time = 1 ns
• Miss Penalty = 25 ns
• Instruction Miss Rate = 1% (0.01)
• Data Miss Rate = 5% (0.05)
• Percentage of memory accesses that are data = 15% (0.15)
• Percentage of memory accesses that are instructions = 85% (0.85)

Step 1: Calculate the Effective Miss Rate

The effective miss rate is the weighted average of the instruction and data miss rates:

Step 2: Calculate AMAT

A candidate key is a minimal set of attributes that can uniquely identify a record in the table. Based on the given information:

1. Mobile Number:

   • Since every record has a unique mobile number, Mobile Number alone can uniquely identify a record. Therefore, it is a candidate key.

2. NID:

   • If NID is unique for each employee, it can also uniquely identify a record. Therefore, it is another candidate key.

A super key is any set of attributes that can uniquely identify a record. It may include additional attributes beyond the candidate key.

• The total number of attributes in the table is 4 (NID, Company_id, Name, Mobile Number).

• The candidate keys are:

  • Mobile Number

  • NID

Super Keys Based on Mobile Number:

• Since Mobile Number is a candidate key, any superset of Mobile Number is a super key.

• The remaining attributes are NID, Company_id, and Name.

• The number of possible super keys based on Mobile Number is:

  2^3=8

  (Each of the 3 attributes can either be included or excluded.)

Super Keys Based on NID:

• Similarly, since NID is a candidate key, any superset of NID is a super key.

• The remaining attributes are Company_id, Name, and Mobile Number.

• The number of possible super keys based on NID is:

  2^3=8

Overlap Between Super Keys:

• Some super keys are counted in both cases (based on NID and Mobile Number). These are the super keys that include both NID and Mobile Number.

• The number of overlapping super keys is:

  2^2=4

  (These are combinations of Company_id and Name with NID and Mobile Number.)

Total Super Keys:

• Using the principle of inclusion-exclusion:

  Total Super Keys=8+8−4=12