Problem 1. Suppose you have a list of n encrypted files on your computer and a pass-code to unlock each file (n pass-codes). However, you forgot which pass-code unlocks which file. When you try a pass-code Pito unlock a file FU, the system will output: 1. P[] is a match for Fil 2. Fils match pass-code is smaller than P[] 3. Fu's match pass-code is greater than Pi You have the following limitations: You cannot compare pass-codes against each other. You cannot check if a files pass-code is greater or smaller than another files pass-code. a) Write a randomized algorithm that matches each file to its pass-code which has the expected running time O[n log(n). Write pseudo-code. b) Analyze the running time of your algorithm, and show that the running time has o(n logn)) c) Give an informal proof that your algorithm is correct. (You can give a formal proof if you wish) HINT: think about quicksort Problem 1. Suppose you have a list of n encrypted files on your computer and a pass-code to unlock each file (n pass-codes). However, you forgot which pass-code unlocks which file. When you try a pass-code Pito unlock a file FU, the system will output: 1. P[] is a match for Fil 2. Fils match pass-code is smaller than P[] 3. Fu's match pass-code is greater than Pi You have the following limitations: You cannot compare pass-codes against each other. You cannot check if a files pass-code is greater or smaller than another files pass-code. a) Write a randomized algorithm that matches each file to its pass-code which has the expected running time O[n log(n). Write pseudo-code. b) Analyze the running time of your algorithm, and show that the running time has o(n logn)) c) Give an informal proof that your algorithm is correct. (You can give a formal proof if you wish) HINT: think about quicksort