1. (20 pts) Suppose an employer will hire one new employee from a group of n candidates interviewed in a random order, according to the algorithm HIRE-NEW-ASSISTANT as shown below. As they are interviewed in succession, a decision is made for each whether to hire or not. A necessary (but not sufficient) condition for deciding to hire a candidate is that the candidate must be better than all previous candidates who were interviewed but not hired. Suppose candidate ci is hired. What is the probability that it was the best of all n candidates? HIRE-NEW-ASSISTANT(candidates [c1,c2,cn] ) for k=1 to n Interview candidate ck If candidate ck is better than candidates c1ck1 With 50% chance Hire candidate ck Return ck Otherwise Reject ck and continue 2. (5 pts) In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice? 3. (10 pts) Consider n dice are thrown simultaneously. Use indicator random variables to compute the expected value of the sum of the faces that do not appear on top. E.g., if 4 appears on top then the sum is 1+2+3+5+6=17, for 1 die. 4. (20 pts) Find the expected number of interviews with n candidates, conducted by the ONLINE-MAXIMUM algorithm for on-line hiring, when k=n/e