Transcribed TextTranscribed Text

Problem Description In this homework, you will use the priority queue to simulate scheduling of tasks. 1.1. Input and Output works as the starting point of the program, which takes as argument the name of an input file. So, the program can be executed using commands as follows: java Startup input.txt java Startup in.txt Each non-blank line in the input file contains a comment or specification of a task. If a line starts with //, the line should be interpreted as a comment line. A task’s specification is composed of three parts, separated by a space, and looks like as follows: task-name deadline duration A task-name is represented using String, while the deadline and duration are long values. Table 1 presents content of a sample input file. It doesn’t really matter what the units of time are in this file. If it helps, you may consider the unit to be second. The execution of the tasks starts at 00 time (can be interpreted as midnight). The deadline is the unit elapsed time since 00 time. Each task-specification line tells your program to insert the corresponding item into the priority queue, where priority corresponds to its deadline. Tasks with earlier (smaller) deadlines have higher priorities, and should be executed first – this is called Earliest Deadline First scheduling, and is often used in real-time systems. You can read about it in wikipedia (, if interested. The first task (i.e., highest priority task) starts executing at 00 time. Tasks execute sequentially one after another (not in parallel) from highest priority to the lowest priority. As a task completes, it is considered that the time required for that task has also elapsed. A task finishing after its prescribed deadline produces a lag, which is the difference between the task completion time and its prescribed deadline. The program computes and reports the total lag over all tasks, which is the summation of lags for all the late-completed tasks. There is no negative lag if a task completes before its deadline. As each task completes, its start-time, completion time, and any produced lag is reported to the terminal. A sample output (corresponding to the input in Table 1) is presented in Table 2. 1.2. Source Files Majority of the source code necessary for this homework is already written for you. You need to download the following java source files from moodle. • starting point of the program. • reads input file. • represents a task. • schedules the tasks. • actually performs a task. A necessary implementation of UnboundedPriorityQueue is missing. You have to provide a clean implementation of an UnboundedPriorityQueue, for which you will use (by composition) a MinHeap. Your Implementation of UnboundedPri- orityQueue must NOT be restricted/fixed in a particular size/capacity and it must seamlessly work with rest of the program provided. You must NOT modify any source code other than your own implementation of UnboundedPriorityQueue, Min- Heap, and corresponding test code. The relationships among the classes and their contents/members are shown in the UML diagram in Figure 1. Notice that MinHeap is described to have a number of overloaded constructors. You don’t have to provide all those constructors. It will be sufficient to have only the constructors necessary for the entire simulation program (and your test code) to work. 1.3. Test Code Your implementation of MinHeap and UnboundedPriorityQueue must be accompanied by JUnit test code written in source files exactly named as and respectively. Consider all corner cases, in which your implementation may fail, and deal with them in your tests. Include enough test cases to make sure that your UnboundedPriorityQueue and MinHeap function correctly. For more about JUnit testing, please see the instructions available on moodle: 1.4. ReadMe.txt When the description of the assignment does not explicitly specify something, you have the liberty to make your choices in those scenarios. Please mention any design choices you made including any reasoning behind your choices in a ReadMe.txt file. If you could not complete a certain part correctly, mention it in ReadMe.txt. If you did not find anything to include in the file, simply put your name and email address. 2. Clean Code Make sure you have produced clean code as discussed in the first class. Please see the general guidelines for producing clean code available on moodle:

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

* @author
* @param <T>
public class MinHeap<T extends Comparable<T>> {

    private T[] data;
    private int capacity;
    private int size;

    * default constructor
    * You don’t have to provide all those constructors. It will be sufficient
    * to have only the constructors necessary for the entire simulation program
    * (and your test code) to work.
    public MinHeap() {
       size = 0;
       capacity = 10;
       data = (T[]) new Comparable[10];

    * insert item to heap
    * @param t
    public void insert(T t) {
       if (t == null) {
       // resize if it is needed
       if (size >= capacity) {
            capacity += 10;
            T[] tmp = (T[]) new Comparable[capacity];
            for (int i = 0; i < size; i++) {
                tmp[i] = data[i];
            data = tmp;
       // put t to the end of the array
       data[size] = t;

       // move it up
       int index = size - 1;
       while (index > 0) {
            int parent;
            if (index % 2 == 0) {
                parent = index / 2 - 1;
            } else {
                parent = index / 2;
            if (data[index].compareTo(data[parent]) < 0) {
                T tmp = data[index];
                data[index] = data[parent];
                data[parent] = tmp;
            } else {
            index = parent;

    * remove item from heap
    * @return

By purchasing this solution you'll be able to access the following files:

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats