Homework answers / question archive /  Secret Santa has stored n password-protected files on his computer, each with a unique password

 Secret Santa has stored n password-protected files on his computer, each with a unique password

Computer Science

Share With

 Secret Santa has stored n password-protected files on his computer, each with a unique password. He's written down all of these n passwords, but he doesn't know which password unlocks which file. He's put these files into an array F and their passwords into an array P in an arbitrary order (so P[] does not necessarily unlock Fli]). If he tests password P[] on file Fli], one of three things will happen: (a) Pli] unlocks Fli] (b) The computer tells him that Pli] is lexicographically smaller than Fli]'s true password (c) The computer tells him that Pli] is lexicographically greater than Fli]'s true password Secret Santa cannot tests whether a password is lexicographically smaller or greater than another password, and he cannot test whether a file's password is lexicographically smaller or greater than another file's password. (a) (3 pt.) Design a randomized algorithm to match each file to its password, which runs in expected O(n log(n))-time. [We are expecting: Either an English description or pseudocode of the algorithm, and an English justification of why it takes expected O(n log(n))-time.] (b) (3 pt.) Prove formally, using induction, that your answer to part (a) is correct. [[We are expecting: A formal argument by induction. Make sure you explicitly state the inductive hypothesis, base case, inductive step, and conclusion.]] (c) (2 pt.) Prove formally that your answer to part (a) runs in expected O(n log(n))-time. [We are expecting: A formal analysis of the runtime.]