关于后端:CS300-Planner

P11 Assignment Planner
Programming II (CS300) Fall 2021
Pair Programming: NOT ALLOWED
Due: 9:59PM on December 13th
P11 Assignment Planner
Overview
Priority queues are a very common practical data structure, and can be used to implement
efficient in-place comparison-based sorting algorithms, are used to speed up the runtime of other
problems such as in Dijkstra’s algorithm, and are frequently used for scheduling procedures.
In this assignment, you will build an array-based heap implementation of a priority queue
which will be used to build a program to allow you to keep track of assignments based on their
due-dates.
Learning Objectives
The goals of this assignment include implementing a priority queue with an array-based heap,
practicing and implementing various recursive methods, as well as build upon previous concepts
such as exceptions, using objects, and how to write tester methods.
Grading Rubric
5 points Pre-Assignment Quiz: The P11 pre-assignment quiz is accessible through
Canvas before having access to this specification by 11:59PM on Friday
12/10/2021. Access to the pre-assignment quiz will be unavailable passing
its deadline.
15 points Immediate Automated Tests: Upon submission of your assignment
to Gradescope, you will receive feedback from automated grading tests
about whether specific parts of your submission conform to this write-up
specification. If these tests detect problems in your code, they will attempt to
give you some feedback about the kind of defect that they noticed. Note that
passing all of these tests does NOT mean your program is otherwise correct.
To become more confident of this, you should run additional tests of your own.
23 points Additional Automated Tests: When your manual grading feedback
appears on Gradescope, you will also see the feedback from these additional
automated grading tests. These tests are similar to the Immediate Automated
Tests, but may test different parts of your submission in different ways.
7 points Manual Grading Feedback: After the deadline for an assignment has
passed, the course staff will begin manually grading your submission. We
will focus on looking at your algorithms, use of programming constructs, and
the style and readability of your code. This grading usually takes about a week
from the hard deadline, after which you will find feedback on Gradescope.
2021 Kacem & LeGault – University of Wisconsin – Madison.
Additional Assignment Requirements and Notes
Pair programming is NOT ALLOWED for this assignment. You MUST complete and
submit your P11 INDIVIDUALLY.
The ONLY import statements that you may include in your AssignmentQueue class
are:
import java.util.Iterator;
import java.util.NoSuchElementException;
The ONLY import statement that you may include in your AssignmentPlannerState
class is: import java.util.Scanner;
In addition to the above imports, You CAN import the following classes in your
AssignmentQueueTester class:
import java.util.List;
import java.util.Arrays;
You MUST NOT add any fields and any public methods other than those defined in this
write-up.
All your test methods should be defined and implemented in your AssignmentQueueTester
class.
All the required test methods in this assignment MUST be
public static AND return a boolean and MUST take NO input arguments.
In addition to the required test methods, we HIGHLY recommend (not require) that you
develop your own unit tests (public static methods that return a boolean) to convince
yourself of the correctness of every behavior implemented in your AssignmentQueue
and AssignmentPlannerState classes with respect to the specification provided in this
write-up. Try to to design the test scenarios for every method before starting the
implementation of the related method.
Only your submitted AssignmentQueueTester class contain a main method.
You CAN define private or protected helper methods to help implement the different
public methods defined in this write-up, if needed.
You CAN define local variables that you may need to implement the methods defined in
this program.
All implemented methods including the main method MUST have their own javadoc-style
method headers, with accordance to the CS300 Course Style Guide.
You MUST adhere to the Academic Conduct Expectations and Advice
2
1 Getting Started
Start by creating a new Java Project in eclipse called“P11 Assignment Planner”. You MUST
ensure that your new project uses Java 11, by setting the“Use an execution environment JRE:”
drop down setting to“JavaSE-11”within the new Java Project dialog box. Next, download
the following files and add them to your project:
Assignment.java, represents the class modelling an assignment given its name and due
date.
PriorityQueueADT.java, represents the priority queue abstract data type to be implemented
in this assignment.
AssignmentIterator.java, implements an iterator over a queue.
Read through the provided implementations in the downloaded above source files. Notice
how assignments are defined, how they are compared with respect to their due date, and
how equals() and toString() methods are overridden in the Assignment class. Also, notice
that the AssignmentIterator iterates over a deep copy of the queue provided as input to its
constructor. The queue of assignments should implement the PriorityQueueADT interface.
You can find the javadocs of all the source files related to this assignment through this link
(javadocs of p11).
2 AssignmentQueue and AssignmentQueue Tester
Now, download the AssignmentQueue.java class. This class provides a code skeleton for an
implementation of a priority queue (min-heap array) which holds and tracks Assignments and
provides related functionality. You must implement the missing methods (see the TODO tags in
the provided source file). Read over the provided Javadocs to understand what each of these
classes do, and the expected behaviors of the methods you are required to implement. As usual,
we highly recommend setting the tester scenarios for each functionality, and the implementation
of the tester methods first.
Next, Download the AssignmentQueueTester.java class and add it yo your project. In this
class you should implement at least FIVE public static boolean tester methods: testConstructor,
testEnqueue, testDequeuePeek, testClear, and runAllTests. The descriptions of these
tester methods, as well as example test scenarios are contained in the Javadoc comments of
the methods. You may also choose to add additional test methods to convince yourself of
the correctness of your implementation or to detect any bad implementation (not necessarily
yours).
3
3 Assignment Planner
After adding the required implementations and verifying them using your tester methods,
download the following files and add them to your project:
AssignmentPlanner.java,
AssignmentPlannerState.java.
In this section, you will implement a driver class to allow you to view and modify a priority
queue of assignments using a simple finite state machine model. For your information, a Finite
State Machine (FSM) is a computation model which can be used to simulate a control execution
flow. It consists of one or more states and their transitions. Only one single state of this machine
can be active at the same time. Based on the current state and a given input, the machine
performs state transitions and produces outputs. The below diagram illustrates the FSM for
our assignment planner implemented in the AssignmentPlannerState java enumeration. An
example of output of a run of the Assignment Planner program is provided in the next section.
MAIN MENU ADD ASSIGNMENTDONE
Option [1]
Valid input
Option [0]
Option [2-5] Invalid input
The current state of the AssignmentPlanner application is represented by the AssignmentPlannerState
enum type, which has three possible values: MAIN MENU, ADD ASSIGNMENT, and DONE. This class
has two abstract methods, isDone() and runState(), which must be implemented for each
state in order to create the application.
The isDone() method returns a boolean which indicates whether the application should
stop.
The runState() method implements the intended behavior of each state, and returns
an AssignmentPlannerState which represents the next state of the application. Note
that this is an instance of polymorphism, and helps to greatly simplify and abstract the
application by allowing each state of the application to define its own behavior in an
object-oriented manner.
The specifications of runState()method are summarized in the above finite state machine
diagram, and in more detail in the AssignmentPlannerState Javadocs.
The TODO tags mark the missing code that you must complete to implement the different
operations related to our assignment planner.
4
You are NOT required to format the text output or input prompts of your application
in any specific manner, but you should verify that the state of the application, including
the values returned by runState(), and the changes made to the AssignmentQueue
arguments, follow the specifications, and that no errors are thrown by your AssignmentPlannerState
class.
Finally, you can notice that the AssignmentPlanner class contains a single main() method
which runs the application. This class should not be modified, and can be used for debugging
your assignment to verify whether your AssignmentQueue and AssignmentPlannerState classes
are correctly implemented, and to figure out when to study for your final exams. A sample run
of the AssignmentPlanner application is given below.