Question

Background 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. 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. 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? Flinders University / College of Science and Engineering 1 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. 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’. COMP2711/8801 Computer Programming 2 Flinders University 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 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. 3. Sally has sent you a record of the order in which she INSERT-ed friends into her BST: 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

1Ans)

Here the problem mentions that what will happen if the birth dates of two person are same. In the above case each of Sally's friend compares the birth date with either greater than or less than. If the birth date is equal then that friend ignores the card.

In this case what we can do is, when inserting a new friend's birthday we can tell each of Sally's friend that if the birth date is same or before their birthday then call the person who is in his left pocket. If left pocket is empty then simply write the person's name on card and put it in pocket.

In case of searching, each friend of Sally should check if they have their birthday today. If their birthday is past then they must call the friend on his/her right pocket, and relays the call back to Sally. If their birthday is yet to come or their birthday is today then they must call the friend in his/her left pocket and should tell Sally that its his/her birthday today along with birthdays told by the friend in his/her left pocket.

Ans 2:

Consider this case: Lets say Sally's birthday is on 1st Jan. Her friend Harry's Birthday is on 15th Jan. Now Sally's friend Martha's birthday is on 31st Jan so she tells Harry and then harry write Martha's name on card and puts it in right pocket. Now Sally's friend John's birthday is on 15th Feb. So she calls Harry, Harry call Martha and Martha will then write John's name on card and put it in her right pocket. Now let's say there is Alice whose birthday is on 28th Feb. Then the call will go from Sally to Harry to Martha to John and then John will write name of Alice on his card and put it in right pocket.

If we could see if the friends birthday are inserted into sequence then the search will be equal to number of friends. As given in the problem if it takes 1minute for processing the request and we insert 100 friends which are sorted by their birthdays then we will need at max 100 minutes to find whose birthday is today. To avoid this we must balance the BST by using AVL tree rules. In that case every friend must check that the absolute difference of number of calls times he need to hold the phone call on left side of friends and call times he need to hold phone on right side of friends should not exceed 2.
If at every check its done then we can search the tree in logn time.
So for 100 friends we may need log 100 ~ 6-7 minutes

3. Ans:

• 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

  

  Harry 15th March, Marge 23rd Adam 23rd September January Smiths' John 30th June 28th Feburary

  John 30th June Smiths Marge 23rd 28th Feburary September Adam 23rd Harry 15th March January

  Harry 15th March Marge 23rd September John 30th June

  John 30th June Marge 23rd Harry 15th March September

  John 30th June Marge 23rd Harry 15th March September/ Adam 23rd January Smiths' 28th Feburary

  John 30th June Smiths Marge 23rd 28th Feburary September Adam 23rd Harry 15th March January

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
==========================================================================