CS 304 Homework Assignment 6 Due: 11:59pm, Thursday, November 26th This assignment is scored out of 59. It consists of 5 questions. The first 4 questions are to be completed on D2L as an online quiz. There is a programming question and you will need to put all your Java programs (*.java) as well as output files for this question in the folder named LastName_FirstName_CS304_HW6. Zip this folder, and submit it as one file to Desire2Learn. Do not hand in any printouts. Triple check your assignment before you submit. If you submit multiple times, only your latest version will be graded and its timestamp will be used to determine whether a late penalty should be applied. Short Answers Complete the quiz for this homework on D2L by the due date. You might see there is a time limit of 120 minutes on this quiz but it is not enforced so you can ignore it. Before you complete all questions, DO NOT submit! Doing so will prevent any further changes to the answers. You can save your answers for as many times as you want before submission. Programming Questions P5. (35pts) In this programming question, you are required to implement the quick sort algorithm for card decks, and a method that verifies if a given tree array represents a heap. You are provided with two class files "Card.java" and "Deck.java" that support the card and deck representations. Each card has two attributes: the suit and the rank. A card can be represented as a string which specifies its suit and rank. For example, the card Ace of Spades can be written as "SA", and the card 5 of Hearts can be written as "H5". Suits are sorted in alphabetical order, i.e., (C)lub, (D)iamond, (H)eart, and (S)pade. Ranks are sorted in numerical order, i.e., (A)ce, 2, 3, 4, 5, 6, 7, 8, 9, 10, (J)ack, (Q)ueen, and (K)ing, where Ace is treated as 1 while Jack, Queen, and King are treated as 11, 12, and 13, respectively. To compare two cards, you need to compare their suits first and then their ranks. Here are some examples: 5 of Hearts (H5) is smaller than Ace of Spades (SA) because H5 has a smaller suit than SA. 5 of Hearts (H5) is greater than King of Clubs (CK) because H5 has a greater suit than CK. 5 of Hearts (H5) is less than King of Hearts (HK) because H5 has a smaller rank than HK. 5 of Hearts (H5) is greater than Ace of Hearts (HA) because H5 has a greater rank than HA. a. Completing the Homework6 class In addition to "Card.java" and "Deck.java", you are provided with two more files "Homework6.java" and "TestHomework6.java". You are required complete the following methods in the former file: int compares(Card c1, Card c2) This method takes two card objects and returns -1, 0, or 1 if c1 is smaller, equal to, or greater than c2, respectively. You need to compare their suits first and if they have the same suit, then compare their ranks. void quickSort(Card[] cardArray, int first, int last) This method takes a card array as well as two indices. It sorts the cards in the range specified by first and last with quick sort. It first calls the split method to partition the elements in the range into two subarrays, and sorts both subarrays recursively. It repeats this process until the entire array is sorted. void split(Card[] cardArray, int first, int last) This is a helper method for quick sort which takes a card array and two indices. It begins by selecting the first element in the card array as the pivot, and then moves elements so that everything in the left subarray is smaller than the pivot and everything on the right is greater than the pivot. You will need to call the compares method to make comparisons between cards. boolean isHeap(int[] A) This method takes an int array as the parameter and verifies if the elements saved in this array form a heap. You can assume that the array represents a complete binary tree so the shape property is already satisfied. You will need to verify that the elements meet the order property requirement for heaps. Return true if this is a heap, false otherwise. This method is separate from the above methods and has nothing to do with the Card or Deck classes used by other methods. Note that you are only supposed to touch the above methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other than these methods or files other than "Homework6.java". Points will be taken off if you fail to follow this rule. b. Code Testing You are provided with a test driver implemented by "TestHomework6.java" (Do not make any changes to this file!) so there is no need to write your own. You are also given a data file "Decks.dat" that contains five pre-generated test decks as well as the sorted arrays. Each deck has 54 cards but not all of them are used. You do not need to worry about how many card are used for the test. Depending on your programming environment, the data file might need to be placed in different folders so that you test driver can read it. For jGRASP, you can leave the data file in the same folder as your java files. For NetBeans, you should place it in your project folder in which you see directories like build, nbproject, and src, etc. Once you have completed the above methods, you can run the test. You should create a plain text file named "output.txt", copy and paste the output (if your code crashes or does not compile, copy and paste the error messages) to this file and save it. Grading Rubrics: Code does not compile: -10 Code compiles but crashes when executed: -5 Changes were made to things other than the required methods: -5 Has output file: 5 compares was correctly implemented: 5 quickSortRec was correctly implemented: 5 split was correctly implemented: 10 isHeap was correctly implemented: 10 Sample Output: Test 1: quickSort() ==> [Passed] Original deck: [CK, D2, S9, HK, HA, D8, H7, H3, DJ, D9, CQ, DA, HQ, H2, C6, D3, D4, C7, CA, D7, D10, S6, C8, C9, S4, C5, DK, H6] Expected deck:[CA, C5, C6, C7, C8, C9, CQ, CK, DA, D2, D3, D4, D7, D8, D9, D10, DJ, DK, HA, H2, H3, H6, H7, HQ, HK, S4, S6, S9] Yours: [CA, C5, C6, C7, C8, C9, CQ, CK, DA, D2, D3, D4, D7, D8, D9, D10, DJ, DK, HA, H2, H3, H6, H7, HQ, HK, S4, S6, S9] Test 2: quickSort() ==> [Passed] Original deck: [SK, D9, D8, C4, C5, HA, D4, S3, CJ, S7, HK, C3, D2, H5, C6, CA, CK, S6, DK, H4] Expected deck:[CA, C3, C4, C5, C6, CJ, CK, D2, D4, D8, D9, DK, HA, H4, H5, HK, S3, S6, S7, SK] Yours: [CA, C3, C4, C5, C6, CJ, CK, D2, D4, D8, D9, DK, HA, H4, H5, HK, S3, S6, S7, SK] ...... Test 7: isHeap([50, 43, 27, 35, 44, 15, 22, 20]) ==> [Passed] Expected: false Yours: false Test 8: isHeap([32, 27, 30, 19, 16, 21, 3, 10, 2, 4]) ==> [Passed] Expected: true Yours: true Total test cases: 8 Correct: 8 Wrong: 0