Question

Please Answer This question and write in your own words. Don't copy from any other resources.

Thank you

Busy Sally Socialite has trouble remembering people's birthdays, so she has organised her friends into what she calls a Birthday Support Team, or BST. Each friend needs only to keep track of three items of information: their own birthday (which of course they do not need to write down), the name of someone whose birthday comes earlier in the year than their own (which they write on a card and keep in their left pocket), and the name of someone whose birthday comes later in the year (which they write on a card and keep in their right pocket).

Whenever Sally makes a new friend, she calls her best friend, who is currently Harry, and initiates an Install New Support Enquiry Response Tag procedure (INSERT for short). If the new friend's birthday is before Harry's own birthday, then he relays the INSERT call to the person whose name is on the card in his left pocket. If the new friend's birthday is instead after Harry's, then he relays the call to the person on the card in his right pocket. However, if the appropriate pocket is currently empty, Harry writes the name on a new card and puts the card in the empty pocket. Of course, the person to whom Harry relays the INSERT does the same thing, which means that collectively the BST ends up remembering the new friend's birthday.

For example, if Sally called Harry to say 'I have found out that John's birthday is next Friday', Harry, who knows that his own Birthday is 15 March and that next Friday is 30 June, would reach into his right pocket, find a card with the name Marge, and call Marge to pass on the news of John's birthday. Marge, whose Birthday is 23 September and who currently has an empty left pocket, would then write John on a new card and put the card into her left pocket.

The first thing Sally needs to do every morning is to find out whose birthday it is that day, and the BST again swings into action. Sally calls Harry and initiates the Sudden Enquiry Activity Requiring Collective Help procedure (SEARCH for short). If the day in question happens to be Harry's own birthday, he tells Sally the happy news and hangs up. Otherwise, he will need to consult with his friends. If Harry has not yet celebrated his own birthday this year, he calls the person on the card in his left pocket to ask whose birthday it is, then relays the answer back to Sally. If Harry's birthday has already passed, he calls his right-pocket friend instead. In either case, if the appropriate pocket is empty, he can tell Sally that it is nobody's birthday. Of course, whoever Harry calls will follow the same procedure so that, collectively, the BST will either provide the name of the birthday celebrant or discover that nobody is celebrating a birthday that day

For example, if Sally calls Harry on 30 June and asks 'Whose birthday is it today?', Harry would reach into his right pocket then put Sally on hold and call Marge. Marge would find John's name in her left pocket then put Harry on hold and call John. Finally, John would report that it is his birthday, which Marge would relay back to Harry, who in turn would report to Sally. Of course, Sally would then call John to wish him 'Happy Birthday

Task After using the scheme for some time, Sally finds out that it has some problems and has asked for your help. To assist, you will need to prepare answers to the following four questions:

1.     The first problem is that if several friends have the same birthday, she only finds out about one of them and the others miss out on their birthday phone call. Explain why this problem occurs and which of the friends would get the call. Devise a modification to the INSERT and SEARCH procedures that will ensure that all birthday celebrants for a particular day will get calls.

2.     The second problem is that as Sally's circle of friends grows, it sometimes takes a long time to get a response to SEARCH calls, which is using up valuable talk-time on Sally's mobile phone plan. Explain the circumstances that would result in unnecessarily long SEARCH calls and what can be done to minimise the problem. If on average a SEARCH call takes one minute — deciding who to call, placing the call, and reporting its outcome — what is the maximum time that a SEARCH might take if Sally added all 100 of her Facebook friends to her BST? If the problem could be fixed, how much time would a typical SEARCH take?

Knowing that Sally's BST could become inefficient, you have devised a Repair Over-Time Acknowledgement To Enquiries procedure (ROTATE for short), which Sally can use to rearrange friends in the BST. The procedure comes in two variations: ROTATE-L and ROTATE-R.

You have drafted the following email, which Sally can send to people who need to use the ROTATE-L procedure to change one of their friends. If she needs someone to use the mirror-image ROTATE-R procedure, she would substitute the words in bold with the words in parenthesis.

Dear <friend>

My BST needs reorganisation, and I need your help. Please call the friend I have asked you to change and pass on the following instructions:

'Call your right-pocket (left-pocket) friend, ask them the name of their current left-pocket (right-pocket) friend, and tell them to replace that name with yours. Then tell me your friend's name and replace their name on the card in your pocket with the one they reported to you.'

When you have finished the call to your friend, replace their name on the card in your pocket with the name they reported.

For example, if Sally emailed Harry asking him to change his right-pocket friend using ROTATE-R, he would call Marge and pass on the instructions above. Marge would then call John (her left-pocket friend), who will report that his current right-pocket friend is 'nobody' and then make Marge his new right-pocket friend. Marge would therefore replace her left-pocket friend with 'nobody' and report John's name to Harry. Finally, Harry would make John his new right-pocket friend.

3.Sally has sent you a record of the order in which she INSERT-ed friends into her BST:

Name

Birthday

Harry

15 march

Marge

23 September

John

30 June

Adam

26 January

The Smith triplets (Ben, Charlie, and Dave)

28 February

Draw a diagram of Sally's current BST and compile a list of the sequence of ROTATE emails Sally would need to send in order to reorganise the BST so that subsequent SEARCH times are minimised. The list should indicate who to send the email to, which friend needs to be changed, and which form of ROTATE to use. Include intermediate diagrams showing the effect of each rotation on the BST. Assume that duplicates cannot be consolidated onto a single card. Note that it may be necessary for Sally herself to change her best friend using a ROTATE.

4. You have heard about a scheme called Automatic Variation Levelling (AVL), which will make sure that Sally's BST never becomes inefficient. AVL works by making sure that the maximum number of relayed calls needed to answer a SEARCH via the left-pocket friend and the right-pocket friend are about the same. Devise a modification to the INSERT procedure that will implement AVL so that Sally never has to manually reorganise her BST again. Illustrate your scheme's performance by INSERT-ing a series of friends and showing that the BST remains efficient.

Answer 1

Answer 3 : Sally's current BST with just the inserts looks like below

Initially, Sally would remember the birthday of her best friend Harry.

Then, Sally tells Harry to remember Marge's birthday, Marge's birthday comes after Harry's, so Harry will note it down to his right pocket.

Next for John, his birthday is after Harry's but before Marge's so, Marge will note it down to her left pocket.

Next for Adam, his birthday is before Harry's so, Harry will note it down to his left pocket.

Next for Smith triplets, their birthday is before Harry's but after Adam's so, Adam will note it down to his right pocket.

For making the search efficient, we will do the following :

On sally change her best friend to Marge using a rotate.

1. Rotate Left on Marge

2. Rotate Right on Harry

3. Rotate Right on Adam.

4. Rotate left on Harry.

The final tree would look like below :

Answer 4 : The new Insertion using the AVL scheme is as follows :

1. Insert the new friend like the normal BST INSERT as before.
2. Now, move upwards until we find the friend where the number of left relay calls are not almost equal to the right relay calls.
3. Then we will make the necessary ROTATES to make the BST balanced.

Lets insert the series of friends mentioned in question 3 using the AVL Insert.

Till first 3 inserts, the tree will look like :

Then, it will find the Harry is the inefficient node, and a Rotate will take place.

Then, it will insert all other friends,

And again find Harry to be inefficient. Again rotate will take place. Giving us the final tree

THUMBS UP IF YOU LIKE IT !