Question

Exercise 3: Multi-way Trees A way to reduce the height of tree and ensure balance is...

Exercise 3: Multi-way Trees

A way to reduce the height of tree and ensure balance is to allow multiple children of nodes. In your class you learned 2-3 trees which allows up to 2 keys in a node, and the number of children is equal to the number of keys + 1. B-trees extend this concept to any arbitrary number of keys (usually number of keys is even and number of children (equal to number of keys+1) is odd).

Assume we want to design a 5-way B-Tree. This will mean that there can be maximum 4 keys in a node, and if the number of keys becomes 5, we can split it into two (the same way we split 2-3 tree when number of keys becomes 3).

Design a 5-way B-tree. Starting with an empty tree, insert the following keys in order.
2, 3, 5, 7, 10, 50, 22, 44, 45, 55, 66, 68, 70, 17, 6, 21, 67

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Exercise 1: Pre-sorting

Consider the problem of finding the distance between the two closest numbers in an array of n numbers. (The distance between two numbers x and y is computed as |x − y|.)

a. Design a presorting-based algorithm and implement it in your preferred language.

b. Solve the above problem using brute-force approach. Implement in your preferred language.

c. Compare the efficiency of the above two algorithms.

Homework Answers

Answer #1

1)  For B tree we just have to insert keys and when children become N we split it into two halves.

End result:

Procees:

2)  

a) Just sort the array using in log(n) time with mergesort or inbuild function.

#include<bits/stdc++.h>
#include<numeric>
using namespace std;
void merge(int *v,int s,int e)
{
    int a[100];
    int mid=(s+e)/2;
    int j=s,k=s,i=mid+1;
    while(j<=mid && i<=e)
    {
        if(v[i]<v[j])
        {
            //ans.push_back(v[i]);
            a[k++]=v[i++];
            //i++;
        }
        else
        {
            a[k++]=v[j++];
            //j++;
        }
    }
    while(i<=e)
    {
        a[k++]=v[i++];
        //i++;
    }
    while(j<=mid)
    {
        a[k++]=v[j++];
        //j++;
    }
    for(int i=s;i<=e;i++)
    {
        v[i]=a[i];
    }
}
void mergesort(int v[],int s,int e)
{
    if(s>=e)return;
    int mid=(s+e)/2;
    mergesort(v,s,mid);
    mergesort(v,mid+1,e);
    merge(v,s,e);
}
int main()
{
        int n;
        cin>>n;
        int v[n];
        for(int i=0;i<n;i++)
        {
                cin>>v[i];        // taking array as input
        }
        mergesort(v,0,n-1); // sorting array
        int mn=INT_MAX; //declaring a variable mn which will be our answer INT_MAX max possible value.
        for(int i=1;i<n;i++)
        {
                mn=min(v[i]-v[i-1],mn); // comparing new value with minimum value till this point.
        }
        cout<<mn<<endl; // answer
        return 0;
}

n log(n) + n = n log(n)

this takes n log(n) time.

b)

In this, we iterate over an array in a nested loop to find the distance

#include<bits/stdc++.h>
#include<numeric>
using namespace std;
int main()
{
        int n;
        cin>>n;
        int v[n];
        for(int i=0;i<n;i++)
        {
                cin>>v[i];        
        }
        int mn=INT_MAX;
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<n;j++)
                {
                        mn=min(mn,abs(v[i]-v[j]));
                }
        }
        cout<<mn<<endl;
        return 0;
}

This is  .

C) algorithm in A takes time and algorithm in B take time.

Please Upvote.

if you face any problem comment below.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
The main goal is to implement two recursive methods, each is built to manipulate linked data...
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes. 1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class Generic implementation not needed, the nodes will store integer values The standard methods will not be needed in this exercise except the constructor 2.) Add a...
Evaluate C(11,4). C(11,4) equals = Six cards are marked with the numbers 1, 2, 3, 4,...
Evaluate C(11,4). C(11,4) equals = Six cards are marked with the numbers 1, 2, 3, 4, 5, and 6 , then shuffled, and three cards are drawn. a. How many different three -card combinations are possible? b. How many three -card hands contain a number less than three? Use a tree diagram for the following. a. Find the number of ways 2 letters can be chosen from the set {U, V, W, X} if order is important and repetition is...
1. If you want to study the effect of hormonal changes in adolescent boys, your population...
1. If you want to study the effect of hormonal changes in adolescent boys, your population would be Group of answer choices All adolescents All the people in the world All males All adolescent males 2. Which of the following is most likely to be measured categorically? Group of answer choices Weight gain in first year college students Deterioration in driving performance under the influence of alcohol Level of authoritarianism in a sample of public accountants Species of dog appearing...
1. For a pair of sample x- and y-values, what is the difference between the observed...
1. For a pair of sample x- and y-values, what is the difference between the observed value of y and the predicted value of y? a) An outlier b) The explanatory variable c) A residual d) The response variable 2. Which of the following statements is false: a) The correlation coefficient is unitless. b) A correlation coefficient of 0.62 suggests a stronger correlation than a correlation coefficient of -0.82. c) The correlation coefficient, r, is always between -1 and 1....
just do questions 5 through 10 3.13.6 Question 110 pts A 319 kg motorcycle is parked...
just do questions 5 through 10 3.13.6 Question 110 pts A 319 kg motorcycle is parked in a parking garage. If the car has 35,494 J of potential energy, how many meters above ground is the car? Report your answer to 1 decimal place. Please do not include units or the answer will be marked incorrect. Flag this Question Question 210 pts A box sitting on the top of a hill has 252 J of potential energy. If the hill...
8 through 10 done please!! 3.13.6 Question 110 pts A 319 kg motorcycle is parked in...
8 through 10 done please!! 3.13.6 Question 110 pts A 319 kg motorcycle is parked in a parking garage. If the car has 35,494 J of potential energy, how many meters above ground is the car? Report your answer to 1 decimal place. Please do not include units or the answer will be marked incorrect. Flag this Question Question 210 pts A box sitting on the top of a hill has 252 J of potential energy. If the hill is...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary...
Please answer the following Case analysis questions 1-How is New Balance performing compared to its primary rivals? How will the acquisition of Reebok by Adidas impact the structure of the athletic shoe industry? Is this likely to be favorable or unfavorable for New Balance? 2- What issues does New Balance management need to address? 3-What recommendations would you make to New Balance Management? What does New Balance need to do to continue to be successful? Should management continue to invest...
1.Establishing the virtual Management: As known, managing virtual staff requires a different method or approach than...
1.Establishing the virtual Management: As known, managing virtual staff requires a different method or approach than managing local staff. Due to that reason, Golden Scent has developed a strategic plan to successfully manage its virtual staff in the USA. Identify the suitable manager. to make sure our work will proceed as we planned, Golden Scent willrecruit a virtual manager with the essential skills and knowledge required to manage virtual employees. Find the skilled people to work with. Since not everyone...
As you saw from the lab PowerPoint slides last week, you will be doing a research...
As you saw from the lab PowerPoint slides last week, you will be doing a research study looking at ‘Aggression Priming” for your first paper. For this week’s discussion, I want you to discuss with your group what you think this study is about. What is the hypothesis? What theory does it come from? What do you predict will happen (do you expect something different than the hypothesis in the researcher instructions? If so, what and why?)? Do you think...
Everyday investment company Sharesies was launched in February 2017, after conducting research on New Zealanders’ attitudes...
Everyday investment company Sharesies was launched in February 2017, after conducting research on New Zealanders’ attitudes towards investing. Prior to launching the company, the co-founders interviewed over 200 people asking them “If I gave you $50 right now, and you had to do something with it in the next 5 minutes what would you do?” Only 5 out of 200 people chose an option to save or invest the $50. More popular options were bills, online shopping, coffees, vouchers, food,...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT