Exam 3

Release: 8am Friday May 27, 2022

Due: 8am Sunday May 29, 2022

We will not accept late submissions. There will be no exceptions.

This page details a take-home exam that you will complete over the next few days. You can’t communicate with anyone about the content of the assignment until the exam has concluded. DO NOT post clarification or other similar questions as staff will not be answering these types of questions during this time period. If there are broken links or otherwise strange parts of the writeup, you may post these concerns on piazza. If you have technical trouble creating a screencast (detailed below) feel free to reach out for assistance.

Do not use any online service other than Piazza to ask questions about the assignment. Do not search for, solicit, or use solutions to the problems that you find elsewhere for the exam. These are all violations of academic integrity that students have committed on exams like this in the past.

You can make use of any course notes, online resources about Java and its libraries, Java tools, and so on to complete the exam, including re-using code from class notes or PAs.

You can review the grading policy for exams in the syllabus. You will complete the programming task below and submit your work to the Exam1 Gradescope assignment.

Starter code is available here:

https://github.com/ucsd-cse12-sp22/Exam3-starter

Submission checklist (see long descriptions below for full details):

Make sure to look at your Gradescope submission after submitting to see if all the required files are there.

Task 1 and 2 will be autograded(except testcases). Task 3 will be manually graded

Make sure that your submission passes autograder for your code to be properly graded.

If you are having issues with getting the autograder to run successfully, you may find it helpful to consult the Developing with the Gradescope Autograder in Mind guide.

If your submission passes the autograder, then you should see output similar to:

Be aware that the Compile check does not check for code correctness, but rather that your code compiles. Additionally, if your code errors or throws exceptions unexpectedly, the autograder will not grade your submission. This will result in 0 points being given for that particular task.

Your submission will be graded after the deadline. You should test thoroughly yourself to make sure your program works as expected.

Clarifications

Can I use a Java feature/library/method that we haven’t covered in class?

Yes (unless otherwise specified), just make sure it doesn’t break the autograder. The course staff is not responsible for fixing any submissions that fail the autograder during or after the exam.

Can we write more methods than specified?

Yes, you can write additional helper methods.

Can I use previous code that I wrote for a PA in my exam?

Yes.

Task 1 – MaxHeap and HashMap

You will be given set of student details. (Sample in input.txt). The student class is given for you. Each student has a name, section and marks details. We want to store the student details in a HashMap, such that all students in the same section fall in the same bucket. Further, we want to find out the maximum marks obtained in each section. It is an interesting idea to use MaxHeap for each bucket(section), so that you can easily retrieve the maximum. You will be implementing this functionality in this task.

You will be writing your code in MaxHeap.java, MyHashMap.java and FileReader.java . The MyHashMap.java will be implementation of your hashMap that implements the given DefaultMap interface given.

You have used ArrayList earlier for the buckets in HashMap. Now you will be creating every bucket using the MaxHeap datatstructure. For this you are first required to complete the methods in the MaxHeap.java. These methods can be used in coding yourHashMap buckets.

Task 1.1 MaxHeap add, peek, remove

You will implement 3 methods in MaxHeap.java, these can further use other helper methods like BubbleUp, BubbleDown, etc as taught in the lecture. The add method will take in the key and value values and add in the MaxHeap. Make sure the MaxHeap property is satisfied after adding each element, to know you are procedding correctly. The peek method will return the top(maximum) element of your MaxHeap, this does not remove the element. The remove method will remove and return the top(maximum) element of your MaxHeap. Make sure the MaxHeap property is satisfied after removing each element. The hashMap constructor also takes a comparator, which can be used to compare the elements. Further details can be infered from the starter code.

Task 1.2 FileInputStream

The FileReader.java class is used to read the student details. You will implement 2 methods in FileReader.java, these can further use other helper methods. The createHeap method will read in the student details from the input.txt file and store the student entries in the HashMap. Use java FileInputStream to read the file. The getMaxOfSection method will return a student who scored maximum score in a given section. In case the section is not present, it must return null. Make sure to define a Student comparator and HashMap object in your FileReader constructor.

Task 1.3 HashMap

You are required the implement the DefaultMap interface methods in the MyHashMap.java. It is similar to PA6, but you are required to use a MaxHeap instead of ArrayList for the buckets. The get() method should return the peek() value of the bucket. Make sure to write proper hashFunction to map the Student to the bucket (section of the student). You are not required to implement reshash functionality for this Exam. You can consider a fixed size HaspMap of around 10 buckets, as the number of sections is limited. So loadfactor is not needed for the exam.

You further have a HashMapTest file that can be used to test your code locally.

Task 1.4 TestCase

Do not add any other junit import statements in the test file Write testcases to check max score of atleast 2 sections as per the input.txt in HashMapTest file.

Task 2 – CircularArrayList

You may not import Java’s builtin ArrayList or LinkedList to complete this task

You will be writing your code in a file called CircularArrayList.java. You will implement all the methods from ArrayListADT interface. The addRear method will add elements towards the rear of the array. The addFront method will add elements towards the front of the array. This is similar to the start mentioned in the lecture. The remove method will always remove the first element (start index). The get method will return the element at a given index, remember that the start index will have the 0th index element. Throw an exception stating “Element doesn’t exist”, in case the element is not present. You are also required to implement the extendCapacity method for the circularArrayList. Start with initalCapacity of 100, and double everytime expandCapacity.

You further have a CircularArrayListTest file that can be used to test your code locally. Do not add any other junit import statements in the test file Write testcases to check elements present at few positions (atleast2) in CircularArrayListTest file.

Task 3 - Video

You will record a short video of no more than 10 minutes. You are not expected to use the entirety of the allotted time, but it is given to provide enough buffer for you to complete the video task.

Tip: If you find yourself running out of time, you might be explaining your code too much. If the task does not ask you to directly explain your code, you don’t need to explain it.

Include:

Note: Gradescope has a max file size of 100MB. Any files larger than this will be rejected. We will NOT accept any files (code, videos, etc.) outside of the gradescope submission. Additionally make sure that you are able to play your video on gradescope. If your video is not playable on gradescope by staff, then it will not be graded and given a score of 0.

To reduce video file sizes:

Task 3.1 MaxHeap and HashMap

Task 3.2 CircularArrayList