CSE 2010, HW4 Due Tue Mar 17 at the start of your lab section; Submit Server: class = cse2010, assignment = hw4SxIndividual Due Tue Mar 17 at the end of your lab section; Submit Server: class = cse2010, assignment = hw4SxGroupHelp x is 14, 23, or j—(j for java) Bitcoin, or other kinds of cryptocurrency, has been fre- quently in the news. Besides the technology around Bitcoin, the price of a Bitcoin has been fluctuating in large amounts on different exchanges. How would you design an exchange system to match buyers and sellers of Bitcoins? The goal of HW4 is to design an exchange system that can efficiently match buyers and sellers of “Fitcoins.” The system allows users to enter orders. Each buy/sell order consists of a buyer/seller, a price, a quantity, and a timestamp. A buy order and a sell order are executed if they have the same price. During execution, if the buy (or sell) quantity is larger, the buy (or sell) order is updated with the remaining buy (or sell) quantity; however the timestamp remains the same. If two buy (or sell) orders have the same price, the earlier order has a higher priority. In the unlikely case that the buy order has a higher price than the sell order, the orders are executed at the average of the buy and sell prices. To manage and match buy and sell orders efficiently, use two priority queues: one for the sellers and one for the buyers. To implement the priority queue, you may modify/rewrite Programs 9.20 and 9.21 on pp. 352-355 (Java: Code Fragment 9.8 on pp. 377-378 in Goodrich et al.). We will evaluate your submissions on code01.fit.edu so we strongly recommend you to test your programs on code01.fit.edu. To preserve invisible characters, we strongly recommend you to download, NOT copy and paste, input data files. Input: The command-line argument for hw4.c is the name of the input file, which has: • EnterBuyOrder time buyer price quantity • EnterSellOrder time seller price quantity • DisplayHighestBuyOrder time • DisplayLowestSellOrder time Time is an integer in HHMMSS format, where HH is 00-23 and MM/SS is 00-59 (leading zeros are optional). Sample input files are on the course website. Output: Output goes to the standard output (screen), each line corresponds to an action: • EnterBuyOrder time buyer price quantity • EnterSellOrder time seller price quantity • DisplayHighestBuyOrder time buyer orderT ime price quantity • DisplayLowestSellOrder time seller orderT ime price quantity • ExecuteBuySellOrders price quality Buyer: buyer remainingBuyQuantity Seller: seller remainingSellQuantity Sample output is on the course website. Extra Credit (10 pts): Separate submission via hw4 extra.c (HW4Extra.java). Consider the condition of the buyer and sellers can change their ordrs When an order is changed, the timestamp for the order is updated. For sim- plicity, each user can have only one order and the timestamps are unique. Additional possible input action is: • ChangeBuyOrder time buyer price quantity • ChangeSellOrder time seller price quantity • CancelBuyOrder time buyer • CancelSellOrder time seller and output result is: • ChangeBuyOrder time buyer price quantity [noBuyer- Error] • ChangeSellOrder time seller price quantity [noSellerError] • CancelBuyOrder time buyer [noBuyerError] • CancelSellOrder time seller [noSellerError] Although the priority queue is designed to find the low- est/higherst price quickly, it is not designed to find a buyer/seller quickly—faster than O(N), where N is the num- ber of buyers/sellers. 1. Design and implement an additional data structure that can help find a buyer/seller and update the priority queue faster than O(N). 2. Note that changeBuy/SellOrder might not udpate the en- try with the lowest/highest price in the priority queue. 3. In the comments at the top of your program (or in a sep- arate PDF file): • explain why your additional data structure can help changeBuy/SellOrder become faster than O(N) with an analysis of the time complexity of patients. • when changeBuy/SellOrder does not remove the en- try of lowest/highest price, discuss how the heap (pri- ority queue) can be adjusted in O(logN) time. Submission: Submit hw4.c that has the main method and other program files. Submissions for Individual and GroupHelp have the same guidelines as HW1. Note the late penalty on the syllabus if you submit after the due date and time as specified at the top of the assignment. 1
