Programming The starter code can be found in the file on Canvas.

computer science


1 Programming The starter code can be found in the file on Canvas. 1. Implement Quick-Select with two different pivot rules: random pivot, and median of-medians. This will involve modifying the files Quick and Pivot 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 ( 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 for the programming part.

Related Questions in computer science category