The goal of this assignment is to apply some of the techniques and structures we've studied this semester. You should read the problem descriptions below, determine appropriate collection types, and implement efficient solutions. You are welcome to discuss this assignments with members of your group or other people in the class, but the code should be written by you, based on your own understanding of the problems.
THIS ASSIGNMENT IS OPTIONAL. If you choose to complete it, it will be factored into your overall PA score only if it would benefit your grade. If you choose not to complete it, the PA portion of the grade will be based on the first four PAs.
DO NOT RE-INVENT THE WHEEL! None of these problems require custom data structures; they can all be implemented efficiently using existing data structures from the Java Collections Framework. These include the following (among others):
| Interface | Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List |
|---|---|---|---|---|---|
Set
|
HashSet | TreeSet | LinkedHashSet | ||
List
|
ArrayList | LinkedList | |||
Deque
|
ArrayDeque | LinkedList | |||
Map
|
HashMap | TreeMap | LinkedHashMap |
(Table reproduced from https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html)
Begin by downloading the following files:
Complete the methods of the DuplicateTracker class so that all
operations are as efficient as possible. The purpose of this class is
to process a sequence of user IDs such that duplicate IDs are
identified and may be efficiently retrieved as a sorted List. You
should assume that both the addID and the getDuplicates methods
may be called arbitrarily many times and in any order: efficiency
matters for both.
Here is a code snippet that illustrates the desired functionality:
tracker.addID(5);
tracker.addID(2);
tracker.addID(1);
tracker.addID(2);
tracker.addID(5);
tracker.addID(5);
System.out.println(tracker.getDuplicates()); // Prints "[2, 5]"
tracker.addID(1);
System.out.println(tracker.getDuplicates()); // Prints "[1, 2, 5]"You can test your implementation by executing the JUnit tests. These will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.
Begin by downloading the following files:
Complete the methods of the JobSequencer class so that all operations
are as efficient as possible. The purpose of this class is to process
jobs of different types in the order that they are added to the
system. Because there are a limited number of job handlers and they
are specialized for a particular job type, you must make sure that the
nextJob method only returns jobs of the requested type. You must also
ensure that jobs of a particular type are processed in the order in
which they arrived. You should assume that both the addJob and the
nextJob methods may be called arbitrarily many times and in any order:
efficiency matters for both.
Here is a code snippet that illustrates the desired functionality:
JobSequencer sequencer = new JobSequencer();
sequencer.addJob("A", 101);
sequencer.addJob("B", 105);
sequencer.addJob("A", 93);
sequencer.addJob("B", 202);
System.out.println(sequencer.nextJob("A")); // Prints "101"
System.out.println(sequencer.nextJob("B")); // Prints "105"
System.out.println(sequencer.nextJob("B")); // Prints "202"
System.out.println(sequencer.nextJob("A")); // Prints "93"Begin by downloading the following files:
Complete the methods of the EventSequencer class so that all
operations are as efficient as possible. The purpose of this class is
to store events that are tagged with an integer time stamp and then to
return those events in strict chronological order: once an event with
a particular time stamp has been retrieved, it should not be possible
to retrieve an event with an equal or earlier time stamp, even if this
means that some events are discarded. You should assume that both the
addEvent and the getEvent methods may be called arbitrarily many
times and in any order: efficiency matters for both.
EventSequencer sequencer = new EventSequencer();
sequencer.addEvent(0, "A"); // Event "A" at time 0.
sequencer.addEvent(4, "C");
sequencer.addEvent(1, "B");
System.out.println(sequencer.nextEvent()); // Prints "A"
System.out.println(sequencer.nextEvent()); // Prints "B"
sequencer.addEvent(1, "e");
sequencer.addEvent(3, "f");
sequencer.addEvent(5, "g");
System.out.println(sequencer.nextEvent()); // Prints "f"
System.out.println(sequencer.nextEvent()); // Prints "C"
System.out.println(sequencer.nextEvent()); // Prints "g"Begin by downloading the following files:
Complete the methods in TriageTracker so that all operations are as
efficient as possible. The purpose of this class is to prioritize
patients as they seek health care. Each patient is entered into the
system along with an integer priority value that quantifies the
urgency of their medical condition. The nextPatient method should
always remove and return the patient with the highest priority. In
event of tied priorities, patients should be
processed in the order they were added. The removePatient method
makes it possible to remove a patient from the collection even if he
or she has not been served.
TriageTracker triage = new TriageTracker();
triage.addPatient("01-A", 10); // Patient "01-A" has priority 10.
triage.addPatient("02-A", 10);
triage.addPatient("03-A", 1);
triage.addPatient("04-A", 1);
triage.addPatient("05-A", 10);
triage.addPatient("06-A", 5000);
triage.removePatient("02-A"); // Patient "02-A" got tired of waiting.
System.out.println(triage.nextPatient()); // "06-A" (Highest priority)
System.out.println(triage.nextPatient()); // "01-A" (First 10 priority)
System.out.println(triage.nextPatient()); // "05-A" ("02-A" was removed!)
System.out.println(triage.nextPatient()); // "03-A"
System.out.println(triage.nextPatient()); // "04-A"Your grade for this assignment will be based on how many of these problems you complete successfully. Success requires that your code passes the correctness tests AND completes the timing tests before the autolalab grader times out (about 10 seconds). Exactly how long the timing tests should take when you run them locally will depend on the speed of your computer. To give a rough ballpark: efficient solutions for each of these should require less than five seconds on the timing tests, even for fairly slow computers. For each problem, submit only the appropriate Java file to the corresponding Autolab assignment.
Autolab will not perform checkstyle tests, but, as always, you should write well-organized and stylistically consistent code.
You may submit as many times as you like.
If you get a timing result that you are particularly proud of, copy the time output from Autolab to the course chat page:
https://chat.cs.jmu.edu/jmu-cs/channels/cs-240-s20
There is no prize for the fastest time on each problem, but you will receive awe and respect from your peers.