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