Homework answers / question archive / CS 351: Data Structures and Algorithms Homework #13 In this assignment you will implement several array algorithms including mergesort pages 630{640 (3rd ed: pp

CS 351: Data Structures and Algorithms Homework #13 In this assignment you will implement several array algorithms including mergesort pages 630{640 (3rd ed: pp

Computer Science

Share With

CS 351: Data Structures and Algorithms Homework #13
In this assignment you will implement several array algorithms including mergesort pages 630{640 (3rd ed: pp. 614{624). These algorithms will be used for a web page spell checker.
Use this link to accept the assignment:
https://classroom.github.com/a/qi7wehTu
1 Concerning Merge Sort and Other Sorted Array Algorithms
All the algorithms are to be implemented in a class SortUtils that is created with a comparator
that is to be used by all the algorithms.
The textbook described the mergesort algorithm. One of the awkward aspects of mergesort is
that it is tricky to merge two segments of an array in place. You will implement mergesort using
several helper methods which use explicit temporary areas.
merge(lo,mid,hi,in,out) This method should take two (presumably) sorted array segments
of in, and merge them into the same area of out. The two array segments are the elements
in the range [lo,mid) and [mid,hi) respectively. The merged elements will go into array out in
the range [lo,hi) which of course is of size equal to the sum of the sizes of the input segments.
The code can rely on the segments being sorted (according to the comparator), the arrays
being non-null and big enough and the output array being dierent than the input array.
merge(1,3,5, 5 2 9 6 7 0 , AB C DE F )
Afterwards: in unchanged and out = A 2 6 7 9 F
mergeSortKeep(lo,hi,data,temp) This method should sort the array segment [lo,hi) in the
data array and write the results back to the same array. The temporary array temp (which
will be valid for the same range of elements) can be used for extra space. Again you can rely
on the arrays not being null, being big enough and being dierent.
mergeSortKeep(1,4, 5 9 2 6 7 0 , AB C DE F ) Afterwards: data = 5 2 6 9 7 0
mergeSortMove(lo,hi,in,out) This method should sort the array segment [lo,hi) in the in
array and write the results to the out array. You can modify the elements in the input array
in during the process. Again you can rely on the arrays not being null, being big enough and
being dierent.
mergeSortMove(1,4, 5 9 2 6 7 0 , AB C DE F ) Afterwards: out = A 2 6 9 E F
The two mergesort helper methods (mergeSortKeep and mergeSortMove) will usefully call each
other (on smaller segments!) in recursive calls. It is required that you avoid excessive copying for
full credit. Only in the base case (single element) are you allowed to simply copy elements from
one array to another. Otherwise, all data movement must be accomplished as a side-eect during
some useful task (e.g. merging).
Another algorithm you will implement is set dierence (A?B). This removes all elements from
one sorted segment that are in the second sorted segment. Since the algorithm doesn't require
temporary storage, the client can have the output array be the same as the input array.
Fall 2022 page 1 of 3
CS 351: Data Structures and Algorithms Homework #13
dierence(lo1,hi1,lo2,hi2,in,rem,out) Write to out[lo1,. . . ] all the elements from the sorted
array segment in[lo1,hi1) that do not occur in the sorted array segment rem[lo2,hi2). Return
the next available index in the output array segment.
difference(1,6,2,5, 0 1 2 3 4 5 , 0 2 4 6 8 3 , AB C DE F ) = 5
Afterwards out = A 1 2 3 5 F
Since the resulting array segment may be smaller that the input segment, the method returns the
(exclusive) upper bound. The last algorithm removes duplicates from sorted array segments:
uniq(lo,hi,in,out) Write to out[lo,. . . ] all the \unique" elements from the sorted array seg-
ment in[lo,hi). Return the next available index in the output array segment.
uniq(1,5, 0 0 1 1 2 2 , AB C DE F ) = 4 Afterwards out = A 0 1 2 E F
Since the array is sorted, duplicate elements will be consecutive. As with difference, the input
and output arrays can be the same.
2 Concerning the Web Spell-Checker
The algorithms will be used in a spell-checker that downloads a web page, getting at all the words
and then comparing them again a dictionary of words. The downloading and parsing of HTML
will be handled for you. The constructor reads in the dictionary. The other public method checks
an XML element:
check(Element e) Using a private helper method, the words in the element are placed into an
array (using an ArrayList temporarily as does the constructor), which can then be sorted,
uniq'ed and dierenced with the dictionary. A list of misspelled words is returned.
You should nd words inside strings inside the XML at any depth except inside <script> and
<style> elements. You should ignore element names and attributes; only look at strings inside
of element bodies. We recommend you use replaceAll to remove punctuation characters other
than the apostrophe. The program runs on URLs in the \Program Arguments" section of the run
conguration.
3 What you need to do
You need to complete the SortUtils and SpellCheck classes: the methods outlined in the previous
sections. We will not be testing invariants in this assignment.
Optional: Find a misspelled word on an ocial UWM web page. I found one on our main page,
but it's not in the visible text. And just because the program reports that (say) \paddleboarding"
is misspelled, it doesn't mean that this counts as a \real" misspelling. Find something really
misspelled, and report it on Piazza. No points, just fun.
4 Files
The repository for this homework includes the following les:
src/Main.java Main program that delegates to SpellCheck.
Fall 2022 page 2 of 3
CS 351: Data Structures and Algorithms Homework #13
src/TestfSortUtils,SpellCheckg.java JUnit test suites.
src/TestEciency.java Eciency tests.
src/TestExhaustive.java Exhaustive test of merge sort.
src/edu/uwm/cs351/SpellCheck.java The spell-checker.
src/edu/uwm/cs351/util/SortUtils.java The sorted array algorithms.
src/edu/uwm/cs351/util/Element.java The data type containing the words you will be
spell checking. Probably worth a look.
lib/dictionary.txt Dictionary of English words.
There is also a RandomTest of the ve sort utility methods in the usual place.