Part D: Randomized Design & Analysis [65 marks) 9) [25 marks] Design a randomized algorithm to balance a binary search tree while inserting. The algorithm should augment the insert method in the binary search tree to fix skewness. Only work on the insert and ignore delete effect. 10) [15 marks] Analyze your randomized algorithm of 9). 11) [10 marks] Suppose you are working as a Google Engineer. Your manager asks you to modify Google calendar code to automatically send users alerts of upcoming events. So, if user X has defined n events, you are considering sending him K reminders for each event. Suppose you learned from cognitive psychology research that for each reminder a user receives for an event, the user has a 50% chance of remembering the event a. [3 marks] What is the expected number of appointments (expressed in n and k) a typical user will remember? Is it worth to add such a feature? b. [3 marks] For a single event, how should we set k with respect to n so that the user remember the event with high probability (i.e. 1-1)? c. [4 marks] If we send k reminders for each of the n events, what is the value of k with respect to n so that the user will remember all the events with high probability (i.e. 1-1)? 12) [15 marks] Consider the process of randomly sending m network packets ton routers. The selection of a router to be the destination for a packet is uniformly random and independent of each other, which implies that the probability that a packet ends into any given router is 1. Based on this process, answer the following questions below. Note: the collisions mentioned in the question below mean distinct and unordered pairs (e.g. if three packets go to one router, three collisions are counted: packet-2 && packet-1, packet-3 && packet-2, packet-3 && packet-1). a. [3 marks] What is the probability of any two packets ending in one router? b. [3 marks] What is the expected number of collisions when we have m packets? c. [3 marks] What is the probability of a particular router being empty - i.e. not receiving any packet? d. [3 marks] What is the expected number of routers which will not receive any packets? e. [3 marks] What is the probability of a particular router receiving k packets