CPT204编程写作、Java程序调试

” CPT204编程写作、Java程序调试CPT204 HyflexErick Purwanto May 2021CPT204 Hyflex 2021Lab 14 Task SheetOverviewLab 14, the final part of the continuous assessment this semester, consists of 3 parts:Part A, B and C.In Part A, you will implement a data structure called Explicit Minimum Priority Queue.You will then use this data structure to solve a problem called Maximum Attendancein Part B. Finally, in Part C, you will have to solve three problems of various datastructures, problem-solving and object-oriented techniques that are derived fromLab 1 Lab 13.Submit all your answers for parts A, B, and C to Learning Mall for grading on theSubmission Day.TimelineWeek 1 Week 13 Lab 1 Lab 13Week 13, Tuesday, Lab 14 Part A, B releasedMay 25, 2021 (Task Sheet, Skeleton Codes, Partial Test Cases)Friday, June 4, 2021 Lab 14: Submission Day- 13.00 – 14.00 CST Lab 14 Part A, B online submission open closed- Lab Group Schedule, Lab 14 Part C released40 minutes Lab 14 Part C on-site, online submission open closedOutlineThe rest of the task sheet will describe all the three parts and the Submission Day indetail.CPT204 HyflexErick Purwanto May 2021Lab 14 Part AExplicit Minimum Priority QueueRecall that in Lecture 13 and Lab 13, we have constructed a Minimum Priority QueueData Structure, and achieved amortized O(log n) time for add and delMin operationsimplemented using resizable array.In part A, you are to implement Explicit Minimum Priority Queue Data Structure usingArrayList. It supports the same operations as the Minimum Priority Queue.However, the priority is explicitly represented as an integer.Priority QueueMinimum Priority Queue supports fast removal of the smallest item in the datastructure. It should also support fast item addition.To have a notion of smallest, either we implement the item to be comparable, or weexplicitly specify the priority of an item with a comparable value, for example aninteger.Implemented naively using an array, we can achieve constant-time item addition butlinear-time smallest item removal; while on the other hand, using an ordered array,constant-time removal but linear-time addition. Our goal is then to have animplementation that can achieve fast running-time for both operations.Binary HeapBinary heap is a binary tree that is complete and satisfies the heap-property: Complete: balanced binary tree, could be left-aligned at the bottom level. Heap-property: parents item/priority is smaller or equal to the childrens.For example:CPT204 HyflexErick Purwanto May 2021If we represent the binary heap by an array or an ArrayList, set the indices to startat 1, and order the nodes containing the item and the priority by the heap-property: There is no explicit links needed between parent node and the children We can use the indices to access a nodes parent or childreno Parent of a node at index k is k/2o Children of a node at index k is 2*k and 2*k + 1For example:You can then use the following ideas to implement the Minimum Priority Queue: Item addition: add the new item at the end, then swap it with its parentrepeatedly until the heap-property is restored. Minimum item removal: replace the minimum item at the root with the lastitem, then swap it with the smallest children repeatedly until the heappropertyis restored.Part A: Explicit Minimum Priority QueueIn part A, your task is to complete an implementation of the Explicit Minimum PriorityQueue ExpMinPQ interface. It is similar to the MinPQ interface that we discussed andimplemented in Lecture 13 and Lab 13.Specifically, you will have to implement the following constructor and methods:1. public ALBinHeap() initializes an empty binary heap.2. public void add(T item, int priority) adds a new item with its correspondinginteger priority to this binary heap.It throws an IllegalArgumentException object if item is null.There may be multiple items with the same priorities in the heap. If there aretwo items with the same priority, you may break ties arbitrarily.3. public T getMin() returns an item with a smallest priority on this binary heap.It throws a NoSuchElementException object if this binary heap is empty.CPT204 HyflexErick Purwanto May 20214. public T delMin() removes and returns an item with a smallest priority onthis binary heap.It throws a NoSuchElementException object if this binary heap is empty.In addition, you must follow the following rules: You will implement a Binary Heap represented using an ArrayList. In addition,there is another instance variable size, that stores the number of items in theheap. You must not add any instance variables. ArrayList and NoSuchElementException will be imported in the Learning MallQuiz. You must not import another libraries. You must not use any external libraries, such as java.util.PriorityQueue. All the methods must run in O(log n) time.Failing any of the rules above will result in 0 marks.The total marks of all the implementations in part A is 100 points, for passing all thetest cases.AdviceThe following advice may be found useful in implementing Part A:1. Use the same Automated Regression Unit Testing and Integration Testing strategythat you have been using in Lab 13. Note that with the use of explicit priority,some input parameters may be different from the ones in Lab 13 test cases.JUnit test cases is provided in ALBinHeapTest.java file.2. Add more test cases, and create a good suite of test cases and practice thePartitioning/Boundary, Black-box/White-box, and Coverage testing.3. Debug with the help of the heapVisualize method provided in HeapVisualizer.java file.4. You may define your own private helper methods. Include them in each of yoursubmissions.5. Do not define your own instance variables. They are not going to be used in thehidden test cases and may cause unpredictable errors in the grading system.CPT204 HyflexErick Purwanto May 2021Lab 14 Part BMaximum AttendanceIn part B, you are going to use the data structure you have developed in part A tosolve an interesting computational problem efficiently.Maximum Attendance ProblemAs a member of the university management team, you are given a list of the universitycourse activities which has been arranged and scheduled by your colleague. Eachcourse activity object stores a number of data including the activity day, the start timethe end time, and the number of students. Each course activity is at least 1 hour long.Due the Covid-19 pandemic mitigation measure, there is a limit on how manystudents can be inside the campus building at the same time. You are charged tomake sure that indeed the limit is not violated.Your task is then to implement an algorithm for finding the largest number ofstudents attending some course activities at any particular same time.Course Activity RepresentationWe represent the course activities with a class called CourseActivity.These are the instance variables:1. type. The type of the course activity in String.2. courseCode. The code of the course in String.3. day. The day the activity is scheduled on represented in int,starting from 1 := Monday until 7 := Sunday.4. startTime. The starting time of this course activity in int from 0 to 23.5. endTime. The ending time of this course activity in int from 1 to 24.6. numStudents. The number of students to attend the course activity in int.7. roomCodeNumber. The room code number of a lecture hall, a tutorial classroom,or a lab room in String.CPT204 HyflexErick Purwanto May 2021Part B: MaxAttendanceIn part B, your task is to complete the skeleton code of the MaxAttendance class inorder to figure out what is the maximum attendance of students.You are given two ALBinHeap objects from Part A as the instance variables: private ALBinHeapCourseActivity minPQ1 private ALBinHeapCourseActivity minPQ2You must use those Explicit Minimum Priority Queue implementation to solve theMaximum Attendance problem efficiently.You will have to implement in these constructor and method to complete the class:1. public MaxAttendance(ArrayListCourseActivity activities).The constructor takes an ArrayList of CourseActivity to initialize the two binaryheap instance variables.2. public int maxAttendance(). This method returns the solution to the MaximumAttendance problem using the two binary heap instance variables.Testing File and Test Case 1You are given the following test case in MaxAttendanceTest.java file:Input:Course Activity 1: Monday, 10:00 – 11:00, 10 studentsCourse Activity 2: Monday, 14:00 – 16:00, 25 studentsCourse Activity 3: Monday, 15:00 – 17:00, 15 studentsCourse Activity 4: Tuesday, 09:00 – 11:00, 35 studentsOutput:40CPT204 HyflexErick Purwanto May 2021Explanation:The maximum number of student attending some course activities at the same dayand time happens on Monday at about 15:00.In addition, you must follow the following rules: You must use the two Explicit Minimum Priority Queue implementations, whichis implemented as ALBinHeap in your solution. You must not add any instancevariables. ArrayList will be imported in the Learning Mall Quiz. You must not importanother libraries. You must not use any external libraries, such as java.util.PriorityQueue. Your algorithm must support multiple course activities scheduled at the sametime. Your algorithm must run in O(N log N) time, where N is the total number ofcourse activities in the list.Failing any of the rules above will result in 0 marks.The total marks for part B is 100 points, for passing all the test cases.AdviceThe following advice may be found useful in implementing Part B:1. Add more test cases using the Automated Regression Unit Testing and IntegrationTesting strategy into the given testing file MaxAttendanceTest.java.2. Create a good suite of test cases and practice the Partitioning/Boundary, Blackbox/White-box,and Coverage testing.3. You may define your own private helper methods. Include them in each of yoursubmissions.4. Do not define your own instance variables. They are not going to be used in thehidden test cases and may cause unpredictable errors in the grading system.CPT204 HyflexErick Purwanto May 2021Lab 14 Part CIn part C, you are going to solve 3 questions, closely related to the works you havedone throughout the semester in Lab 1 Lab 13. It is an open book lab test. You mayopen the course pdf or bring hardcopies of course notes. You may open your sourcecodes in IntelliJ. You may open and review past course quizzes in Learning Mall.Relative to the programming questions in the Lab Exercises, there will be 2 easy and1 hard coding questions. There are multiple possible candidate questions for eachquestion with the same difficulty, you will be given one of them randomly.While the specific questions are not going to be revealed here, the range of topics willbe given below. You can also practice by reviewing all your works in Lab 1 Lab 13.You will be able to access the questions in the respective Learning Mall Quizzes on theSubmission Day.In addition, you must follow the following rules: You must not communicate or share anything in any way with anybody otherthan the staff at all. You must not open any other websites. You must not use any external libraries and you must follow the specificinstructions in any particular questions. For online students, you must show your screen and your hands at any timeusing a webcam.Failing any of the rules above will result in 0 marks with no warnings given.The marks for each question in part C is 100 points, for a total of 300 points.Data StructureList, ArrayList, MyList, SLList, DLList, ARListDeque, LLDeque, ARDequeMap, HashMap, HAMapSet, ARSet, HASetMinPQ, ARBinHeapDisjoint Sets, Quick Find, Quick Union, Weighted Quick UnionGeneric Data Structure of the above and their subclassesCPT204 HyflexErick Purwanto May 2021Object-oriented Features and Problem-solving TechniquesEmpty Constructor, Default Constructor, Copy Constructor, Deep CopyIterative, Recursive, Recursion with Helper MethodMutates, Not Mutate, ImmutableResizing Array, Table Doubling/HalvingChecked/Unchecked Exception, AssertionIterator, Iterable, Enhanced For Loop, ToStringInterface, ADT, Interface Inheritance, Implementation Inheritance, CastingStatic/Dynamic Type, Dynamic Method Selection, Overloading, OverridingEquality, Higher Order Functions, Comparator, Comparable, HashCodeCPT204 HyflexErick Purwanto May 2021Lab 14 Submission DayThe submission day is on Friday, June 4, 2021, in two separate time periods.First, submit Part A and Part B online at 13.00 – 14.00 CST.Second, submit Part C during your usual lab time according to your lab groupschedule. If you are returning students, come to and submit in the lab rooms; andif you are non-returning students, submit online invigilated by a teacher using BBB.At those times, open your CPT204 course page on Learning Mall.Learning Mall Lab 14 Quiz SectionThe quizzes will be accessible on June 4, 2021 : Part A, B at 13:00 CST; and Part C10 minutes after your respective lab group starting time (16:00 or 17:00 or 18:00 CST).You will see a similar section shown below.Additionally for part C, you will also see a problem description and class/methodspecification outlining each problem, similar to our lab sheets.Some may include a skeleton code as well. You may want to copy paste the skeletoncode into your coding environment, so please have it ready.CPT204 HyflexErick Purwanto May 2021Learning Mall Quiz SubmissionPart A and Part B. When the quiz open at 13:00 CST, you will see some additionaltest cases. You may want to check your code against those test cases in your IDE first,not in the Learning Mall Quiz.You have 1 hour to test, debug if needed, and submit your code. Submit your codebefore the closing time at 14:00 CST. It is highly recommended to submit a fewminutes earlier to account for network transmission delay.Part C. The quizzes will open 10 minutes after your lab group starts. You have tocomplete the method or the class, as specified in the problem description andspecification in 40 minutes. You may use Check against the test cases multiple times.In addition, you may include your private helper methods in the submission box.Adding another elements, such as importing libraries, will result in 0 marks.The first Check will have no penalty if failing the test cases. The subsequent Checks,however, will each incur an additional 15% penalty, cumulatively for each incorrectCheck.CPT204 HyflexErick Purwanto May 2021Useful Tips for Submitting Your Work1. We will release the lab seating arrangement before the Submission Day. If you area returning student, please make sure you prepare the IDE, the library and thedata structure files in your Windows account on the specific lab computer assignedto you.2. If you are a non-returning student, join our mock online submission session, tohelp you prepare for the additional online invigilation rules.3. If you are copy paste from your IDE, please double check the parenthesis,class/method headers, etc., before clicking the Check or Finish Attempt button.4. Test your code intensively before submitting your work.5. Familiarize yourself with the error messages of the autograder systems that wehave seen throughout the semester.Academic IntegrityThis Lab 14 coursework assignment is individual work. Plagiarism (e.g. copyingmaterials from other sources without proper acknowledgement) is a serious academicoffence. Plagiarism and collusion will not be tolerated and will be dealt with inaccordance with the University Code of Practice on Academic Integrity. Individualstudents may be invited to explain parts of their code in person, and if they fail todemonstrate an understanding of the code, no credit will be given for that part of thecode.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“