HW4 Solution

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 uctuating in large amounts on di erent 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 e ciently 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 e ciently, 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. t.edu so we strongly recommend you to test your programs on code01. t.edu. To preserve invisible characters, we strongly recommend you to download, NOT copy and paste, input data les.

Input: The command-line argument for hw4.c is the name of the input le, 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 les 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 nd the low-est/higherst price quickly, it is not designed to nd 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 nd 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 le):

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(log N) time.

Submission: Submit hw4.c that has the main method and other program les. 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 speci ed at the top of the assignment.


1