HW 4 Solution

Due Tue Mar 12 at the start of your lab section; Submit Server: class = cse2010, assignment = hw4SxIndividual Due Tue Mar 12 at the end of your lab section; Submit Server: class = cse2010, assignment = hw4SxGroupHelp x is 14, 23, or j|your merged section number or java.




To add an element of surprise/excitement (and perhaps more revenue), an online retail/auction site tries to sell multi-ple items of the same product at random times over a period of time (e.g. 1000 items at random times over 24 hours). How would you design an e cient system to match items to bids?




The goal of HW4 is to design a system that can e ciently match items with the highest bidding price at di erent times. The system allows customers to enter bids. Each bid consists of a price and quantity. For simplicity, each customer can have one bid and there is only one product. If two bids have the same price, the earlier bid has a higher priority (assume the timestamp of a bid is unique). Also, to not lose money, the site does not sell an item if the highest bidding price is lower than the minimum acceptable price, which can be updated over time by the retailer (e.g. higher at the beginning).




To manage and nd the highest bid e ciently, use a priority queue implemented with a heap. Each entry of the priority queue has: bid price (key), timestamp (secondary key), and customer name (value). Assume at most 100 entries. A tie in the price is broken by the timestamp. Functions/methods include:




insert(pQueue, entry)




removeMax(pQueue) // return and remove entry with the maximum key




getMax(pQueue) // return entry with the maximum key isFull(pQueue)




isEmpty(pQueue)




To implement the priority queue, you may modify/rewrite Pro-grams 9.20 and 9.21 on pp. 352-355 (Java: Code Fragment 9.8 on pp. 377-378 in Goodrich et al.). We will be evalu-ating your submission on code01. t.edu; we strongly recom-mend you to ensure that your submission functions properly on code01. t.edu.




Input: The command-line argument for hw4.c (HW4.java)




is the name of the input le, which has:




EnterBid time name price quantity




UpdateMinimumAcceptablePrice time price SellOneItem time




DisplayHighestBid time




Time is an integer in HHMM format, where HH is 00-23 and




is 00-59 (leading zeros are optional). Sample input les are on the course website. You may assume names are unique.



Output: Output goes to the standard output (screen), each line corresponds to an action:




EnterBid time name price quantity




UpdateMinimumAcceptablePrice time price




SellOneItem time name price [NoBids / HighestBidding-PriceIsTooLow]




DisplayHighestBid time name bidT ime price quantity




Sample output is on the course website.




Extra Credit (10 pts): Separate submission via hw4extra.c (HW4Extra.java). Consider the customers are also allowed to update bids. Additional possible input action is:




UpdateBid time name price quantity




and output result is:




UpdateBid time name price quantity [customerNot-Found]




Although the priority queue is designed to nd the highest bid quickly, it is not designed to nd a customer quickly|faster than O(N), where N is the number of customers.




Design and implement an additional data structure that can help nd a customer and update the priority queue faster than O(N).



Note that UpdateBid might not udpate the entry with the highest bid in the priority queue.



In the comments at the top of your program (or in a sep-arate PDF le):



explain why your additional data structure can help UpdateBid become faster than O(N) with an analy-sis of the time complexity of UpdateBid.




when UpdateBid does not remove the entry of high-est bid, discuss how the heap (priority queue) needs to be adjusted.




[It’s OK if EnterBid becomes slower than O(log N), which can be remedied with data structures to be discussed later in the course.]




Submission: Submit hw4.c (HW4.java) 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.




For extra credit, submit hw4extra.c (HW4Extra.java) that has the main method and other program les. GroupHelp submission is not applicable to extra credit. Late submission for extra credit is not accepted.







1