Description
Bitcoin, or other kinds of cryptocurrency, has been frequently 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 simplicity, 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 [noBuyerError]
• ChangeSellOrder time seller price quantity
[noSellerError]
• CancelBuyOrder time buyer [noBuyerError]
• CancelSellOrder time seller [noSellerError]
Although the priority queue is designed to find the lowest/higherst price quickly, it is not designed to find a
buyer/seller quickly—faster than O(N), where N is the number 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 entry with the lowest/highest price in the priority queue.
3. In the comments at the top of your program (or in a separate 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 entry of lowest/highest price, discuss how the heap (priority queue) can be adjusted in O(log N) 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
