The description, expected output, and some pre-done code is in the file provided so use that as your...

Question

The description, expected output, and some pre-done code is in the file provided so use that as your guide. This will be done in Java and I would like it done by this Wednesday. I want this code to be completely unique and not copied whatsoever.Don't use any extra imports that aren't already provided when doing this assignment.Description and files needed/(1) Description.pdf 1 (Mergesort, Sets and Maps, Trie, and Heap) 1: Overview We are going to: ● Find common elements in two sorted arrays ● Implement the Mergesort algorithm for sorting an array of strings ● Learn how to use ordered sets and maps These are essentially balanced binary search trees (such as AVL tree). In Java, these are called TreeSet and TreeMap. These are ordered because the values are logically stored and can be retrieved in a sorted order. ● Learn how to use unordered sets and maps These are essentially hash tables. In Java, these are called HashSet and HashMap. ● Implement a Trie and use it to find Longest Common Substrings ● Implement a Minimum Heap for storing strings. To this end, your task is to implement the following methods: • commonElements, and mergesort in MergeSortAndFriends class • sortedAlphabet, bstSort, and zeroSumSubArray in SetsAndMaps class • locus, insert, search, and longestCommonSubstring in Trie class • swap, insert, extract, and heapSort in StringHeap class The project also contains additional files (which you do not need to modify). Use TestCorrectness.java to test your code. For each part, you will get an output that you can match with the output I have given to verify whether your code is correct, or not. Output is provided separately in the ExpectedOutput file. Should you want, you can use www.diffchecker.com to tally the output. 2 2: Dynamic Arrays Here, you will use their Java implementations of dynamic arrays, which is named ArrayList. Typically, this encompasses use of generics, whereby you can create dynamic arrays of any type (and not just integer). We will discuss integer dynamic arrays here; the syntax is pretty self explanatory on how to extend this to other types (such as char, string, or even objects of a class). • In Java, to create an integer ArrayList use: ArrayList name = new ArrayList(); To get the size of the array list, the syntax is name.size(). To add a number (say 15) at the end of the array list, the syntax is name.add(15). To remove the last number, the syntax is name.remove(name.size() - 1). To access the number at a particular index (say 4), the syntax is name.get(4). To change the content of a particular index (say 4) to −99, the syntax is name.set(4, -99). 3 3: Operations on Strings In this assignment, you are going to be dealing with strings. Here, you are going to: ● The length of a string str is given by str.length() ● Get hold of the character at index i of a string. If the string is str, use str.charAt(i) in Java to get the character. ● Compare two strings str1 and str2 to get their relative lexicographic (dictionary) rank. Recall how you compare strings lexicographically (i.e., dictionary order wise). You match the strings one character at a time, until you find a mismatch (or exhaust one of the strings). The lexicographically smaller string is the one with the smaller mismatched character (or the shorter one if you exhaust one string). Use str1.compareTo(str2) in Java to get their relative order. If the function returns a negative value, then str1 is smaller than str2. If the function returns a positive value, then str1 is larger than str2. Otherwise (i.e., when the function returns 0), str1 equals str2. ● Getting hold of the suffix starting at index i. For example, suffix of banana starting at index 3 is the string ana. If the string is str, use str.substring(i) in Java to get the suffix that starts at index i. 2 ● Getting hold of the substring starting at index i and having length �. For example, substring of banana starting at index 1 and having length 4 is the string anan. If the string is str, use str.substring(i, i + �) in Java to get the substring that starts at index i and has length �. 4 4: MergeSort and Friends We will first solve the problem of finding all common elements in two sorted arrays and returning them. To this end, you are going to use Dynamic Arrays, but not the one that you studied in class, but its Java implementations. Then, we will implement merge-sort for sorting strings. 4.1: Task 1: Implement the numCommonElements method We want to solve the following problem: given two sorted arrays A[ ] and B[ ] of lengths n and m respectively, we want to find the elements that are common to both the arrays (without repeated counting of the same element) and return the common elements in a dynamic array. For example, the arrays A[ ] = {7, 13, 19, 20, 22, 22, 37, 37} and B[ ] = {7, 14, 17, 22, 28, 31, 37, 37, 37, 43} both have 7, 22 and 37. (Note that we count 22 and 37 only once.) On the other hand, A[ ] = {7, 13, 19, 20, 22} and B[ ] = {14, 17, 21, 28} have nothing in common. One algorithm for solving this problem is as follows: pick each number in array A and then scan array B to verify if the number exists. It is easy to see that the Big-O complexity of this procedure is O(mn). You can improve this to O(m log n) or O(n log m) by applying a binary search approach – pick a number from one array and binary search the other one; typically, you would binary search the larger of the two arrays. Although binary search is a substantial improvement, based on the merge principle, we will devise an O(m + n) time algorithm, which is as good as it can get. Algorithm for finding the number of common elements ● Create a dynamic array, i.e., an integer ArrayList (in Java) ● Initialize a = 0 and b = 0 ● Use a while loop that runs as long as a  B[b] then you increment b ○ Else, do the following: ■ Add A[a] to the dynamic array ■ Increment a ■ Skip all repeated occurrences of A[a] in A (using another loop increment a as long as a

Krishan · Accepted Answer

Report:
This report brief introduction about the functionality of the programs and logic used. Not attaching output, as it the same as provided for the testing purpose (ExpectedOutput.pdf).
Comments are also added in the code files, to make it easier to understand.
1) Find common elements in two sorted arrays:
Input: 2 arrays A and B of type int
Output: Dynamic array of Integer type.
Time Complexity: O(m+n), where m and n are length of array A and B.
2) Merge Sort:
	Input: One Array of Tring type
	Output: Sorted Array
	Time Complexity: O(mN log m), where m is n and N is max number of Strings(length of array) n is maximum length of Strings provided.
3) Alphabet Finder using Ordered Set:
Input: Array of char type containing alphabets
Output:

Description and files needed/(1) Description.pdf 1 (Mergesort, Sets and Maps, Trie, and Heap) 1: Overview We are going to: ● Find common elements in two sorted arrays ● Implement the Mergesort...

Answer To: Description and files needed/(1) Description.pdf 1 (Mergesort, Sets and Maps, Trie, and Heap) 1:...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment