PA 10: Overview Due Date: December 10th (Tuesday 11am), 100 points Overview In this assignment, you will be implementing different algorithms using built-in Java Data Structures. The level of the questions are similar to what I usually ask on the exams. Therefore practice coding on paper first and then check your solution by coding it up. This assignment is an individual assignment. You may ask Professors/TAs/Tutors for some guidance and help, but you can’t copy code. You may discuss the assignment conceptually with your classmates, including bugs that you ran into and how you fixed them. However, do not look at or copy code. This constitutes an Academic Integrity Violation. Style Requirements You will be graded on your code’s style: https://sites.google.com/ucsd.edu/dsc30/resources/style-guide IntelliJ has a great plugin to check your style automatically. Use it! There are style considerations beyond indentation and such. ● Choose names for test methods and for variables that are descriptive and useful when you see them in test output. ● Consider writing helper methods if you repeatedly use the same set of statements. ● Use Javadoc comments for descriptions of your methods and classes and inline comments if the logic of your program is not captured by your variable names and the natural flow of code. Question 1 AVL tree insertion Insert values 100, 50, 60, 30, 150, 125, 17 in AVL. Draw a tree after each insertion and save the results in PA10_1.pdf Coding Part Create a class PA10 and add the methods below to this class. Make sure to include your tester file that tests all these methods. Question 2 Merge Sorted Linked Lists Write a function that takes two sorted linked lists and returns a new linked list that contains all the elements from the input lists and is also sorted. Method signature: public static LinkedList mergeLists(LinkedList list1, LinkedList list2) Suggestion: ● You can use Linked List Iterator Question 3 Parenthesis Checker Write a function that takes a string and returns false if there is parenthesis mismatch and true otherwise. Method signature: public static boolean paranChecker(String exp) Note: ● Empty string is considered to be a balanced expression. Sample Input/Output: Input String: “()()()” Output: true Reason: There are equal numbers of each kind of parenthesis, and each outer parenthesis is closed properly. Input String: “(())(” Output: false Reason: The first four are valid, the last one opens and has no close, so this fails. Input String: “((())())” Output: true Reason: All parenthesis groups are valid, they are just nested deeper in some places. Question 4 Maximum element in a stack Write a function that takes a stack, finds and removes maximum element in it. The rest of the elements should stay unchanged after the function is done. If there is more than one identical maximum, remove all maximums. Assumptions you can use: ● All elements are positive in a stack ● If the stack is empty, return 0 Method signature: public static int stackMax(Stack stack) Sample Input/Output: Single max element: Input Stack: 1 -> 2 -> 3 -> 7-> 4 Function output: 7 Content of the stack: 1 -> 2 -> 3 -> 4 Multiple max elements: Input Stack: 1 -> 7 -> 2 -> 7 -> 3 -> 7-> 4 Function output: 7 Content of the stack: 1 -> 2 -> 3 -> 4 Empty stack: Input Stack: Function output: 0 Content of the stack: Question 5 Hello Midterm2. Count elements in the heap Write a function that returns the number of elements in a min heap strictly less than a given number. Method signature: public static int elemNumHeap(PriorityQueue minHeap, int val) Question 6 Appear…Disappear… Write a function that takes an array of integers. Every item in the array is in the range 1 to n (inclusively), where n is the size of the array. Some elements appear twice and others appear once. Develop a O(n) algorithm to find all the elements of [1, n] inclusive that do not appear in this array. Your algorithm must be efficient and you may use extra space. Method signature: public static ArrayList findMissing(int [] input) Sample Input/Output: Input Array: 1, 1, 2, 2 Function output: 3, 4 Input Array: 1, 1, 2, 6, 3, 5 Function output: 4 Input Array: 1, 2, 3, 4, 5 Function output: 0 Files to Submit: ● PA10_1.pdf ● PA10.java ● PA10_tester.java
