Programming The starter code can be found in the file hw3-code.zip on Canvas.
1 Programming The starter code can be found in the file hw3-code.zip on Canvas. 1. Implement Quick-Select with two different pivot rules: random pivot, and median of-medians. This will involve modifying the files Quick Selector.java and Pivot Rule.java. Compare the two pivot rules by running each of them on random arrays of size 104 , 105 , 106 , and 107 , taking the average of 30 trials. Do you notice a difference in performance? 2. Implement the following string processing algorithm: given a dictionary and a string with no white space, determine whether or not spaces can be inserted into a string so that each word exists in the dictionary. To make things efficient, the dictionary should be reprocessed into a trie (Trie.java) and the splitting should be found via dynamic programming. Your program should accept the following input: java Word Splitter [dictionary] [string] and the output should be the string with spaces inserted, or “No splitting found.” if no such splitting exists. For example, using the sample words. txt and running java Word Splitter words. txt this is the reason should give the output this is the reason while running java Word Splitter words. txt zzz yyy xxx should give the output No splitting found. In the write up, describe the recurrence you use for the dynamic programming portion, and explain how to reconstruct the splitting after solving the recurrence. Your submission should consist of a PDF file for the written explanations, and the same .java files as in hw3-code.zip for the programming part.
