CS241 - Fall 2021 - Assignment #6

Collaboration policy:   The goal of assignment is to give you practice in mastering the course material. Consequently, you are encouraged to collabo- rate with others. In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study- group meeting. Specifically, you should spend at least 30–45 minutes trying to solve each problem beforehand.  If your study group is unable to solve a problem, it is your responsibility to get help from the instructor before the assignment is due.

For this assignment, you can form a team of up to three members. Each team must write up each problem solution and/or code any programming assignment without external assistance, even if you collaborate with others outside your team for discussions.  You are asked to identify your collabo- rators outside your team.  If you did not work with anyone outside your team, you must write  “Collaborators:  none.”  If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this policy to submit a problem solution that any member of the team cannot orally explain to the instructor. No other student or team may use your solutions; this includes your writing, code, tests, documentation, etc.  It is a violation of this policy to permit anyone other than the instructor and yourself read-access to the location where you keep your solutions.

Submission Guidelines:   Your team has to submit your work on Classes (no email) by the due date. Only one submission per team is necessary. For each class in the programming assignments you must use the header template provided in Classes. Make sure that you identify your team members in the header, and any collaborators outside your team, if none, write “none”. Your code must follow the Java formatting standards posted in Classes.  Format will also be part of your grade.  To complete the submission, you have to

upload two files to Classes: your source file and your class file. Your answers to questions that do not require coding must be included in the remarks section of the header.   The  submission will  not  be  accepted  in  any other format.

Style and Correctness:   Keep in mind that your goal is to communicate. Full credit will be given only to the correct solution which is described clearly. Convoluted and obtuse descriptions might receive low marks, even when they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups, and also help you conceptualize the key idea of the problem.

Assignment 6

Grading Rubric:

Coding:

Non-coding:

Embedded in questions.

Assignment:

A Priority Queue is a popular data structure that maintains a collection of items with priorities.  At any given time, one can take out of the queue the item with highest priority or increase the priority of any given item. Of course it also includes an operation to insert new items.

Priorities are usually represented with an integer, the smaller the integer the higher the priority.  That is, an item a with priority 1 is the item with highest priority in the queue, whereas an item b with priority 100 has less priority than a. (Notice that priorities do not need to be consecutive.)

A Priority Queue usually has the following operations:

●  Insert(item,key) : that inserts a new item with the given key.

● ExtractMin(): that extracts and returns the item with highest priority.

● DecreaseKey(item,newkey):  that updates the priority of the given item to newkey.

A frequent implementation of a Priority Queue is a data structure called a Binary Heap.  With such implementation, all the above operations take O(log n) in the worst case. Another possible implementation is to maintain the items in a list, sorted by the priorities. Using a Linked List such imple- mentation achieves constant time for ExtractMin(), but Insert(item,key) and DecreaseKey(item,newkey) in the worst case take O(n).

The purpose of this assignment is to evaluate the time performance of these two implementations of Priority Queue.  For the Binary Heap imple- mentation you have to use the Java API PriorityQueue class. For the Link List implementation you have to use the Java API LinkedList class main- taining the order of priorities (increasing order of keys).

The Java API PriorityQueue class is generic with only one parametric data type.   That is, in order to store pairs  (item,priority) one has to define a new class with such pair and establish how the priorities are com- pared.  Given that we are only interested in time performance, we simplify the experiment storing only the priorities as integers.

In our evaluation we will use the Priority Queue to sort items. To do that, we insert n priorities chosen at random and we ExtractMin() repeatedly until the queue is empty. This sorting algorithm is known as Heap Sort.

Specifically, do the following.