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-1o)