[Solved] CSE222-505-Data Structures And Algorithms Homework 5

GTU Computer Science and EngineeringCSE 222/505Homework #05CONTEXT: Imagine a color digital image of width W and height H. You can use any onlinesoftware library in order to load it into your program. Once you load it, it will be represented as a2D array (with W columns and H rows) of 3D 8bit unsigned integer valued vectors. Each elementof this 2D array will correspond to a color point (or pixel) in this image. Each color pixel is madeup of 3 integer values in the range 0-255, inclusive. The first dimension corresponds to the amountof red in that color, the second dimension to the amount of green in that color and the thirddimension to the amount of blue in that color.OBJECTIVE: we want to construct max priority queues for color pixels. We want to enter thosepixels one by one into priority queues, and then extract them according to different priority schemes(or ordering relations).INPUT: your program will admit as command line input a color digital images path (in either pngor jpg format).HOW: Your program will support 3 vector (or color) comparison methods: lexicographicalcomparison (LEX), Euclidean norm based comparison (EUC) and bitmix comparison (BMX). LEX: standard lexicographical comparison from discrete math. EUC: whichever vector has the greater L2 norm is considered greater (this is actually a preorderingrelation since its not anti-symmetric but thats ok for this context). BMX: read section 3 of the attached pdf.Your program will have 4 threads (study the online thread tutorial of Java on how to create and startthem).Thread 1: responsible for reading the pixels from the image starting from the top-left corner andadvancing column first until the bottom-right pixel. Every color pixel read, will be inserted to eachof the 3 priority queues (named PQLEX, PQEUC and PQBMX: one per ordering relation). As soonas the first 100 pixels are inserted, it will create and start the following 3 threads, and then continueinserting the remaining pixels.Thread 2: will remove from PQLEX the color pixels and print them on screen one after the other, upuntil a total of WxH pixels are printed.Thread 3: will do the same as Thread2 but it will use PQEUC.Thread 4: will do the same as Thread2 but it will use PQBMX.Note on threads 2, 3, 4: careful, if the PQ that is being processed by a thread happens to betemporarily empty, and the number of pixels it has processed so far is less than WxH, then it mustwait without keeping the CPU busy (e.g. without constanly checking if there is an element in thepriority queue). Hint: take a look into the producer consumer problem.Note: if thread 1 tries to insert a value into a PQ run by thread X while thread X hasnt completedits removing method from it, all hell will break loose, and the PQ will become corrupt. Similarly,thread X must not try to remove from its PQ anything while thread 1 hasnt completed inserting intoit. Hint: take a look into javas synchronized keyword.OUTPUT: all your output will be at the terminal, threads 2, 3, 4, will print out WxH 3D color pixelvalues, in the order that they are extracted from their corresponding PQs, and thread 1 will print thepixel values in the order that they inserted:e.g.Thread 1: [100, 50, 200]Thread 1: [78, 11, 111]// etc inserting all the way to at least the first 100 pixels..Thread2-PQLEX: [255,45,178]Thread 1: [99, 1, 77]Thread4-PQBMX: [255,234,128]Thread3-PQEUC: [255,247,198][The above values are imaginary].It is up to the OS to determine which thread will run how many times before yielding its priority toanother thread. Maybe thread 2 will run 300 times before switching to thread 1, or 200 times beforeswitching to thread 4, etc. If everything goes fine, each thread must print out exactly WxH pixels.RULES: code your own data structures (except for the image loading part). no plagiarism (except for the image loading part, steal what you can, leave nothing behind). use a binary heap as the underlying implementation of your priority queue; bonus points ifyou implement a binomial or even more if you implement a fibonacci heap. You will have only one priority queue implementation, the constructor of which you willcustomize with a Comparator object parameter to make it prioritize accordingly the elementsinside it. dont use the sleep methods of the Thread class. Just dont, its bad design. use OOP principles in your design. provide the class diagram in your report. Bonus points for using design patterns. Explain whichyou used and why.