This is a data structures assignment, i attached the description, expected out, and the files needed. the file is "Descriptions+ Expected Output + Files Needed". i want this to be original work.

Descriptions+ Expected Output + 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 < lenA and b < lenB. Within the loop:
○ If A[a] < B[b] then you increment a
○ Else If A[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 < lenA and A[a] is the same as B[b]).
● Return the dynamic array
Your algorithm must have a complexity of O(m + n). Anything worse, I will be refunded, even if
you get the correct output.
5
4.2: Task 2: Implement the mergesort method
Normally you could sort strings using a selection sort kind of approach. However, that would be
bad (just like sorting numbers using them is bad). To see why that is the case, let’s consider the
scenario where we have m strings, each of length N characters. Suppose we want to sort them
using selection sort. We know that will have a nested for-loop, one going over each string and
other to find the minimum string. However, we will have another loop (either explicitly if you write
it or implicit if you use the string compare method discussed before); this loop will run N times to
find the order between two strings. Essentially, you match the strings one character at a time,
until you find a mismatch (or exhaust the shorter string). The lexicographically smaller string is
the one with the smaller mismatched character (or the shorter one if you exhaust one string).
Therefore, the complexity is ultimately O(m2N); it would be the same in case of insertion sort.
Using merge-sort, we can speed this up to O(mN log m); normal merge-sort for m integers
take O(m log m) time, but for strings of length N, we need O(N) time to compare two strings. Still
O(mN log m) is better than O(m2N).
Use the pseudo-code outlined in the notes to implement the merge-sort algorithm. In the notes, we are
sorting integers and not strings. Therefore, you have to make necessary changes –
• the mergedArray will be a string array
• when comparing a string from the left half of the array (i.e., from left through mid) with a
string from the right half of the array (i.e., from mid + 1 through right), you have to use the
compareTo command (in Java) to determine which string is lexicographically smaller. As
usual, the smaller string will be placed in mergedArray.
The rest of the process and concepts remain the same.
6
5: Sets and Maps
A Set is essentially a set in the typical Math terminology – contains unique elements (or more
commonly referred to as keys). A Map on the other hand consists of map entries, where each
map entry comprises of a key and value pair. You can search the map for a particular key, and if
it exists, retrieve the corresponding value back. Thus a map essentially maps an element (called
key) uniquely to another element (called value).
Sets are implemented as a balanced search tree (aka ordered sets) or as a hash-table (aka
unordered sets). Maps can be implemented as a balanced search tree (aka ordered maps) or as
a hash-table (aka unordered maps). In both cases, keys can be of any type (integers, floats,
strings, characters, objects of a class); likewise, values (in case of maps) can also be of any
type. For unordered sets and maps, we must be able to check whether or not two keys are the
same. For ordered sets and maps, we must be able to order two keys (such as dictionary order
for strings).
Operations on an ordered set/map are typically supported in O(log n) time, where n is the
number of items in the set/map. Operations on an unordered set/map are typically supported in
O(1) expected (average) time but in the worst-case it may take O(n) time, where n is the number
of items in the set/map. For this assignment, we will assume O(1) time for unordered sets/maps
as the worst-case rarely happens.
An important thing to consider is that the keys that are stored in ordered sets and maps are,
as the name suggests, ordered, such as in numeric order (for integers and floats), or in
lexicographic order (for strings). Therefore, whenever an application demands that keys be
stored in some well defined order, we should consider ordered sets and maps. On the other
hand, when the order is not important, then we should use unordered sets and maps because
they are faster.
4
Over here, we will see a few applications of sets and maps. But, let’s first see how they are
implemented in Java.
7
5.2: Java
I will list some of the functions of sets and maps (both ordered and unordered). For more details,
check out Java’s documentation.
Ordered and Unordered Set
● To create an integer ORDERED set: TreeSet mySet = new TreeSet<>();
To create an integer UNORDERED set: HashSet mySet = new HashSet<>();
Note that you may need to change the types of keys stored according to the
application.
● To get the size of the set: mySet.size(); this will add x if it is not present, else no change.
● To check if an integer x is already in the set: if(mySet.contains(x))
The statement inside the if evaluates to true if and only if x is already in the set.
● To create an iterator on a set (ORDERED or UNORDERED) and print all values:
Iterator it = mySet.iterator();
while (it.hasNext())
System.out.print(it.next() + " ");
Ordered and Unordered Map
● To create an ORDERED map with integer keys and character values: TreeMapCharacter> myMap = new TreeMap<>();
To create an UNORDERED map with integer keys and character values:
HashMap myMap = new HashMap<>();
Note that you may need to change the types of keys and values according to the
application.
● To get the size of the map: myMap.size();
● To insert an integer key-value pair: myMap.put(key, value);
This will add the pair if it is not present, else it will update the existing value of key with the
“new” value.
● To check if the map already contains a particular key: if(myMap.contains(key))
The statement inside the if evaluates to true if and only if key is already in the map.
● To retrieve the value corresponding to a particular key: Integer value = myMap.get(key);
The method returns null if key is not present.
8
• To create an iterator on a map (ORDERED or UNORDERED) and print all keys/values:
// create an iterator on the set of keys stored in the map
Iterator it = myMap.keySet().iterator();
while (it.hasNext()) { // as long as there is a key
Integer key = it.next(); // obtain the key from the iterator,
// and move iterator to the next key (if exists)
Character value = myMap.get(key); // get the value corresponding to the key
System.out.println(key+ ": " + value);
}
5.3: Using Sets and Maps
You will write three methods to understand how ordered set, ordered map, and unordered set
work. We do not implement an unordered map; we will use it directly for building a Trie.
5.3.1: Alphabet Finder using Ordered Set
The first method simply returns the alphabet of a given array of characters in sorted order, i.e.,
this method returns the distinct characters in the array in sorted order. Note that since we want
things in sorted order and all we really care about are the characters (with nothing else tied to
them), we should lean towards an ordered set. Fill up the sortedAlphabet method:
Alphabet Finder
● Note that the ordered set will essentially solve this straightaway. So, create an ordered set.
You will also need to return the alphabet in a dynamic array; so, create one.
Notice that the input array contains characters; so, your dynamic array and
ordered set should also be able to store characters.
● Now, take all the characters from the array and insert them into the ordered set.
● Since sets will only keep unique characters, you are pretty much done – all
duplicates have been removed. Just use an iterator on the set to retrieve the
numbers one-by-one, and insert them into a dynamic array.
● Once all numbers have been added, return the...