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. 3.1 Sample Run ======================================================== Assignment Planner (v1.0) ======================================================== [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: CS300 P10 Enter due date in the format MM/DD HH (24-hour format): 12/6 22 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: CS300 P11 Enter due date in the format MM/DD HH (24-hour format): 12/13 22 [1] Add an assignment [2] Show highest priority assignment 5 [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS300 P10 (Due 12-06 10PM) CS300 P11 (Due 12-13 10PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: CS300 Final Exam Enter due date in the format MM/DD HH (24-hour format): 12/20 17 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 2 Highest priority assignment is: CS300 P10 (Due 12-06 10PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: CS240 HW10 Enter due date in the format MM/DD HH (24-hour format): 12/06 17 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment 6 [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 2 Highest priority assignment is: CS240 HW10 (Due 12-06 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS240 HW10 (Due 12-06 5PM) CS300 P10 (Due 12-06 10PM) CS300 P11 (Due 12-13 10PM) CS300 Final Exam (Due 12-20 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: Study for CS300 Final Enter due date in the format MM/DD HH (24-hour format): 12/17 11 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS240 HW10 (Due 12-06 5PM) CS300 P10 (Due 12-06 10PM) CS300 P11 (Due 12-13 10PM) Study for CS300 Final (Due 12-17 11AM) CS300 Final Exam (Due 12-20 5PM) 7 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 3 Highest priority assignment CS240 HW10 (Due 12-06 5PM) has been completed. [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 2 Highest priority assignment is: CS300 P10 (Due 12-06 10PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS300 P10 (Due 12-06 10PM) CS300 P11 (Due 12-13 10PM) Study for CS300 Final (Due 12-17 11AM) CS300 Final Exam (Due 12-20 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 1 Enter name for assignment: CS 310 Study for the final Enter due date in the format MM/DD HH (24-hour format): 12/16 15 8 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS300 P10 (Due 12-06 10PM) CS300 P11 (Due 12-13 10PM) CS 310 Study for the final (Due 12-16 3PM) Study for CS300 Final (Due 12-17 11AM) CS300 Final Exam (Due 12-20 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 3 Highest priority assignment CS300 P10 (Due 12-06 10PM) has been completed. [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS300 P11 (Due 12-13 10PM) CS 310 Study for the final (Due 12-16 3PM) Study for CS300 Final (Due 12-17 11AM) CS300 Final Exam (Due 12-20 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 3 Highest priority assignment 9 CS300 P11 (Due 12-13 10PM) has been completed. [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 2 Highest priority assignment is: CS 310 Study for the final (Due 12-16 3PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 CS 310 Study for the final (Due 12-16 3PM) Study for CS300 Final (Due 12-17 11AM) CS300 Final Exam (Due 12-20 5PM) [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 5 Planner cleared [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 4 [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment 10 [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 2 Warning: Queue is empty! [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 6 Warning: Invalid command "6" [1] Add an assignment [2] Show highest priority assignment [3] Complete highest priority assignment [4] List all assignments [5] Clear planner [0] Quit planner Select a command: 0 Goodbye! 4 Assignment Submission Congratulations on finishing this CS300 assignment! After verifying that your work is correct, and written clearly in a style that is consistent with the CS300 Course Style Guide, you should submit your final work through gradescope.com. The only THREE files that you must submit include: AssignmentQueue.java, AssignmentQueueTester.java, and AssignmentPlannerState.java. Make sure to remove the TODO tags from your submitted source files. Your score for this assignment will be based on your “active” submission made prior to the hard deadline. The second portion of your grade for this assignment will be determined by running that same submission against additional offline automated grading tests after the submission deadline. Finally, the third portion of your grade for your submission will be determined by humans looking for organization, clarity, commenting, and adherence to the CS300 Course Style Guide. ©Copyright: This write-up is a copyright programming assignment. It belongs to UW-Madison. This document should not be shared publicly beyond the CS300 instructors, CS300 Teaching Assistants, and CS300 Fall 2021 fellow students. Students are NOT also allowed to share the source code of their CS300 projects on any public site including github, bitbucket, etc. 11
欢迎咨询51作业君