Description
Overview Elementary data structures such as hash tables or red-black trees are often not enough for solving problems. However, annotating them with additional information may permit new operations to be performed quickly. In such a case, the modified structure is called an augmented data structure. In this homework you are going to augment red-black tree to solve an order statistic problem. Problem You are working for Amazing Inc., world leading e-commerce platform. In its warehouses, a robot called shipment master arranges shipments. You are programming the shipment master. Definition 1 Warehouses / packages a) A warehouse is where packages are stored. Amazing Inc. keeps ware in packages, and puts a label on each. b) A label is a two-integer-paper, consisting of package size and an ordinal number. Labels are read by shipment masters. c) Amazing Inc. has many warehouses, but two of which are really significant: West and East warehouses. Shipments are forwarded to smaller warehouses around the world from these two central warehouses. d) Both warehouses have a shipment master. e) A balloon courier called the lead courier goes between West and East warehouses. 2 The Lead Courier / Shipment Master f) The lead courier works closely with shipment masters. It carries a shipment assigned by a shipment master to the other shipment master (e.g., packages given by the shipment master of the west warehouse is carried by the lead courier to the east warehouse, and vice versa). g) A shipment is a single package or a collection of packages which are about to move. h) The lead courier begins carrying from the east warehouse. The shipment master prepares the first shipment with the smallest size package and gives it to the lead courier. i) Such a shipment is called smallest size shipment because it contains the smallest package or packages, if there are more than one package with the smallest size. j) When the lead courier arrives at a warehouse, it hands in the shipment it was carrying. Shipment master reads the ordinal integer of the package, or the minimum ordinal integer of the packages if there are more than one package in the shipment. k) Assume the ordinal integer is n, then shipment master prepares the lead courier a new shipment of the n th smallest package/s in the warehouse. Then, shipment master gives it to the lead courier, and unpacks the shipment which was brought by the lead courier and adds the brought packages to warehouse inventory. l) However, sometimes a warehose may not have n th smallest package. (One case is that the count of packages in a warehouse is less than n.) m) When a warehouse does not have n th smallest package, shipment master does not accept this shipment to the warehouse, instead the shipment is forwarded to smaller warehouses around the globe. And it prepares the smallest size shipment and gives it to the lead courier, such that courier keeps operating. n) A warehouse gets completely empty by the time its shipment master gives the last possible shipment to the lead courier. The lead courier carries this last shipment to the other warehouse, and shipment master of the other warehouse directly accepts the shipment without processing it. Packages inside this shipment is added directly to the warehouse inventory and the whole shipment process ends. 3 Your Goal o) Since Amazing Inc. serves to millions, shipment masters should be very efficient at finding packages, especially nth smallest packages, as well as updating warehouse inventories by insertions and deletions. Therefore as the engineer behind the shipment masters, you decided to program memory of a shipment master as a order statistic tree, an augmented red-black tree whose nodes are associated with packages. p) Alternatively you would program shipment masters by keeping a few sorted arrays for anything, however this would turn out to be inefficient. This is the motivation behind your decision about using red-black trees. Implementation HW3_Result hw3( int eastWarehousePackageCount, int eastWarehousePackageSizes [], int eastWarehousePackageOrdinals [], int westWarehousePackageCount, int westWarehousePackageSizes [], int westWarehousePackageOrdinals [] ); You will be knowing: • int eastWarehousePackageCount is the number of packages in the east warehouse • int eastWarehousePackageSizes [] is the sizes of packages in the east warehouse • int eastWarehousePackageOrdinals [] is the ordinal numbers of packages in the east warehouse • int westWarehousePackageCount is the number of packages in the west warehouse • int westWarehouseSizes [] is the sizes of packages in the west warehouse • int westWarehouseOrdinals [] is the ordinal numbers of packages in the west warehouse • HW3_Result is a three integer tuple for package count, red node count and black node count after the whole shipment process ends. struct HW3_Result { int packageCount; //40 pts int redNodeCount; //30 pts int blackNodeCount; //30 pts } • int packageCount is the total number of packages in whatever warehouse remains • int redNodeCount is the total number of red nodes • int blackNodeCount is the total number of black nodes You must not declare a main function anywhere in your implementation. Evaluation You will be given a header: hw3.h You will be submitting a source: hw3.cpp Your homework will be evaluated in terms of your implementation. Your program should be compilable on ITU’s Linux Server by the following command. Yes, you are allowed to use C++11 features in this homework if you wish! >g++ -std=c++0x -Wall -Wextra -Werror hw3.cpp ${OUR_SOURCES} -o hw3 Table 1: An example how we run your program >ls hw3.cpp hw3.h ourSources/ >g++ -std=c++0x -Wall -Wextra -Werror hw3.cpp ${OUR_SOURCES} -o hw3 >./hw3 q) We will compile your implementation in hw3.cpp beside our sources. It is us who will provide the main function. r) Before submission, you can work with a main function while implementing hw3. s) You are not allowed to include GNU extension for policy based trees, which includes redblack tree implementation. t) Neither do you allow exploit std::map, which is based on red-black tree. u) You are not allowed to include any way either. v) If you do not follow these in your implementation, your code will not be graded even if it compiles or produces correct output. You need to implement your own augmented red-black tree and use that tree in hw3 function. You are free to consult to course slides or the reference book for help about augmented data structures. w) Your homework will be evaluated by using black-box techniques. Policy • You may discuss the problem addressed by the homework at an abstract level with your classmates, but you should not share or copy code from your classmates or from the Internet. You should submit your own, individual homework. • Academic dishonesty including but not limited to cheating, plagiarism, collaboration is unacceptable and subject to disciplinary actions. You are expected to act according to Student Code of Conduct, which forbids all ways of cheating and plagiarism. Your codes will be checked using plagiarism detection software. In case of cheating occurs, you will be subject to disciplinary actions. Submission • Please submit your files through Ninova e-Learning System. • You must only submit hw3.cpp. Do not send us back hw3.h or anything else. • All your implementation must be in C++, and we must be able to compile and run it on ITU’s Linux Server (you can access it through SSH). • For Windows users: If you wish, you can use WinSCP to upload and edit your source code into ITU SSH Server, and use PuTTY to compile and run your algorithm. If does not, please make sure that your code is able to be compiled and runned on ITU’s Linux Server. • Your code has to be compiled successfully. Otherwise you will not be graded. Which will result a grade of zero for the homework. • You should be aware that the Ninova e-Learning System clock may not be synchronized with your computer, watch, or cell phone. Do not e-mail the teaching assistant or the instructors about your submission after the Ninova site is closed for submission. If you have submitted to Ninova once and still want changes in your report, you should do this before the Ninova submission system closes. Your changes will not be accepted by e-mail. Connectivity problems in the last minute about the internet or about Ninova are not valid excuses for being unable to submit. You should not risk your project by leaving its submission to the last minute. After uploading to Ninova, make sure that your homework appears there. START EARLY. If a point is not clear, discuss it or e-mail kcengiz@itu.edu.tr
