Assignment: Birthday Bonanza 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. 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'. Further explanation Of course, a "Birthday Support Team" is really just a thinly disguised Binary Search Tree, when we look at the details of how it works. Each friend in the "Team" can be represented by a node in a Binary Search Tree, and the left and right "pockets" correspond to left and right branches from that node to other nodes. The ordering of friends that is imposed by the Binary Search Tree is according to the order of the days of the year, with birthdays that occur earlier in the year going to the left subtree below a particular node, and birthdays that occur later in the year going to the right subtree. All of the questions in this Report pertain to a Binary Search Tree solution for the problem. 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. Further Explanation: Your answer should explain clearly what happens using the current solution when Sally tries to insert, and later search for, a new friend who has the same birthday as someone else who is already stored in the binary search tree. You should explain why this doesn't work, and then you should also describe your own modifications to the Birthday Support Team procedures for inserting and searching, so that people with the same birthday as someone else can also be accommodated. 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 300 of her Facebook friends to her BST? - If the problem could be fixed, how much time would a typical SEARCH take? Further Explanation: This question has to do with the performance of a binary search tree, i.e. the time that it takes to perform specific operations. Explain under what circumstances the long waiting times for search operations would occur, and how these waiting times can be reduced. Explain the maximum waiting time if the problem has not been fixed, and the typical waiting time if the problem can be fixed in the way you have described. You will receive a better mark if you don't just state the numeric answer, but also explain your reasoning. 3. 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. 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. Further Explanation: These operations correspond to the standard rotate operations that are defined for a binary search tree. For this question and question 3, you are asked to create diagrams to illustrate what happens as the tree is rotated. These diagrams do not need to be created with software; images of neat hand-drawn diagrams are fine. For question 3, you should draw the initial state of the BST after all of the friends have been added, in the order shown above. Next, you should describe which emails get sent, and provide a diagram to show the effect of every rotation applied in order to balance the tree. For this question, you should finish with a left and right subtree of equal depth (i.e. not using the AVL definition of a balanced tree, which will be used in question 4). 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 the same series of friends as listed in Question 3 above and showing that the BST remains efficient. Include intermediate diagrams showing the effect of each rotation on the BST. Further Explanation: For question 4, you should show how the tree will be continually balanced using the AVL algorithm. Your answer here will include the sequence of emails, and diagrams illustrating each step, as before. Note that question 3 and 4 ask for different things. In question 3, all of the friends are first added to a binary search tree, and then after that, we perform a series of rotations to balance the tree. In question 4 , we add the friends in one-byone and perform tree rotations as we go along, whenever this is required by the AVL algorithm. Submission This assignment is to be completed individually. Your submission should conform to accepted practices for academic writing, which means you should use a consistent typeface, number your headings, and ensure your work is free of grammatical and spelling errors. British English is the preferred document language. Any material you reference must be appropriately acknowledged with an in-text citation and an associated full citation in a bibliography at the end of your document-use either Harvard or IEEE format. Submit your work as a single PDF document to the Report: Data Structure Analysis submission box on FLO by Monday 31 October, 5PM (Week 13). The assignment will be graded out of 20 with each question contributing 5 marks. Learning outcomes As per the topic SAM, this assignment is designed to enable you to meet COMP2711 learning outcomes LO1, 2, 4, 5, 6, and 8 ; and COMP8801 learning outcomes LO1, 2, 4,5, 6, 8, and 9. Assignment: Birthday Bonanza 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. 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'. Further explanation Of course, a "Birthday Support Team" is really just a thinly disguised Binary Search Tree, when we look at the details of how it works. Each friend in the "Team" can be represented by a node in a Binary Search Tree, and the left and right "pockets" correspond to left and right branches from that node to other nodes. The ordering of friends that is imposed by the Binary Search Tree is according to the order of the days of the year, with birthdays that occur earlier in the year going to the left subtree below a particular node, and birthdays that occur later in the year going to the right subtree. All of the questions in this Report pertain to a Binary Search Tree solution for the problem. 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. Further Explanation: Your answer should explain clearly what happens using the current solution when Sally tries to insert, and later search for, a new friend who has the same birthday as someone else who is already stored in the binary search tree. You should explain why this doesn't work, and then you should also describe your own modifications to the Birthday Support Team procedures for inserting and searching, so that people with the same birthday as someone else can also be accommodated. 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 300 of her Facebook friends to her BST? - If the problem could be fixed, how much time would a typical SEARCH take? Further Explanation: This question has to do with the performance of a binary search tree, i.e. the time that it takes to perform specific operations. Explain under what circumstances the long waiting times for search operations would occur, and how these waiting times can be reduced. Explain the maximum waiting time if the problem has not been fixed, and the typical waiting time if the problem can be fixed in the way you have described. You will receive a better mark if you don't just state the numeric answer, but also explain your reasoning. 3. 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. 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. Further Explanation: These operations correspond to the standard rotate operations that are defined for a binary search tree. For this question and question 3, you are asked to create diagrams to illustrate what happens as the tree is rotated. These diagrams do not need to be created with software; images of neat hand-drawn diagrams are fine. For question 3, you should draw the initial state of the BST after all of the friends have been added, in the order shown above. Next, you should describe which emails get sent, and provide a diagram to show the effect of every rotation applied in order to balance the tree. For this question, you should finish with a left and right subtree of equal depth (i.e. not using the AVL definition of a balanced tree, which will be used in question 4). 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 the same series of friends as listed in Question 3 above and showing that the BST remains efficient. Include intermediate diagrams showing the effect of each rotation on the BST. Further Explanation: For question 4, you should show how the tree will be continually balanced using the AVL algorithm. Your answer here will include the sequence of emails, and diagrams illustrating each step, as before. Note that question 3 and 4 ask for different things. In question 3, all of the friends are first added to a binary search tree, and then after that, we perform a series of rotations to balance the tree. In question 4 , we add the friends in one-byone and perform tree rotations as we go along, whenever this is required by the AVL algorithm. Submission This assignment is to be completed individually. Your submission should conform to accepted practices for academic writing, which means you should use a consistent typeface, number your headings, and ensure your work is free of grammatical and spelling errors. British English is the preferred document language. Any material you reference must be appropriately acknowledged with an in-text citation and an associated full citation in a bibliography at the end of your document-use either Harvard or IEEE format. Submit your work as a single PDF document to the Report: Data Structure Analysis submission box on FLO by Monday 31 October, 5PM (Week 13). The assignment will be graded out of 20 with each question contributing 5 marks. Learning outcomes As per the topic SAM, this assignment is designed to enable you to meet COMP2711 learning outcomes LO1, 2, 4, 5, 6, and 8 ; and COMP8801 learning outcomes LO1, 2, 4,5, 6, 8, and 9