As the price of bidcoins soars you are interested in tracking their auctioning. You are given an array T containing n integers, representing the transactions in chronological order on a specific website. A positive integer i represents a bidcoin being placed for sale for a price i. A negative integer j represents a bid placed to buy a bidcoin. If the transaction is a bid j, and the cheapest bidcoin for sale costs at most [j| euros, then the cheapest bidcoin is sold (and removed from the market). If there are no bidcoins for sale costing at most \j | euros at the time of the bid, then the bid is discarded instantly. You wish to compute the total amount of money that has changed hands as a consequence of successful bids. Example: T = [3, -2,5, -4,-4,1,4, -3). Total sum of all successful bids: 4 euro. (a) [2 points] Describe an O(n log n) time algorithm that computes the total amount of money spent in the successful buy requests. Hint: Which data structure can keep track of the prices and efficiently find the smallest price? Note: Your description should be in natural language. You may add additional pseu- docode to clarify if you wish, but the English language summary of your algorithm is used for grading. (b) [2 points] Prove the running time of your algorithm. (c) [1 points) Give a complete loop invariant that could be used to prove the correctness of your algorithm. (You do not need to prove correctness of the invariant.) As the price of bidcoins soars you are interested in tracking their auctioning. You are given an array T containing n integers, representing the transactions in chronological order on a specific website. A positive integer i represents a bidcoin being placed for sale for a price i. A negative integer j represents a bid placed to buy a bidcoin. If the transaction is a bid j, and the cheapest bidcoin for sale costs at most [j| euros, then the cheapest bidcoin is sold (and removed from the market). If there are no bidcoins for sale costing at most \j | euros at the time of the bid, then the bid is discarded instantly. You wish to compute the total amount of money that has changed hands as a consequence of successful bids. Example: T = [3, -2,5, -4,-4,1,4, -3). Total sum of all successful bids: 4 euro. (a) [2 points] Describe an O(n log n) time algorithm that computes the total amount of money spent in the successful buy requests. Hint: Which data structure can keep track of the prices and efficiently find the smallest price? Note: Your description should be in natural language. You may add additional pseu- docode to clarify if you wish, but the English language summary of your algorithm is used for grading. (b) [2 points] Prove the running time of your algorithm. (c) [1 points) Give a complete loop invariant that could be used to prove the correctness of your algorithm. (You do not need to prove correctness of the invariant.)
