Algorithm Concepts- Design, implement and analyze two algorithms to solve the longest common prefix problem. A solution using the naive brute force approach and one using the divide and conquer approach.
1. For this assignment, you will design, implement and analyze two algorithms to solve the longest common prefix problem. A solution using the naive brute force approach and one using the divide and conquer approach.
2. The longest common prefix problem is defined as follows:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:
Input: [“dog”,”racecar”,”car”]
Output: “”
Note: All given inputs are in lowercase letters a-z
3. Design an algorithm to solve this problem using brute force. The idea is loop over the strings [S1…Sn], finding at each iteration i the longest common prefix of strings LCP(S1…Si) When LCP(S1…Si) is an empty string, the algorithm ends. Otherwise after n iterations, the algorithm returns LCP(S1…Sn).
a. Write the pseudocode for your algorithm
b. What is the asymptotic running time of your algorithm. Provide an explanation for your answer
4. Design an algorithm to solve this problem using a divide and conquer strategy. To do this consider the following facts. If you split theLCP(Si…Sj) problem into two subproblems(Si…Smid) andLCP(Smid+1…Sj), where mid is{(i + j)/2}, We use their solutions lcpLeft and lcpRight to construct the solution of the main problem LCP(Si…Sj). To accomplish this we compare one by one the characters of lcpLeft and lcpRight till there is no character match. The found common prefix of lcpLeft and lcpRight is the solution of the LCP(Si…Sj).
a. Write the pseudocode for your algorithm
b. What is the asymptotic running time of your algorithm. Provide an explanation for your answer
5. Using any programming language of your choice implement the algorithms you designed in 3 and 4. above. Use the attached test file to show that your algorithms and implementations are correct. The file has one test case per line (10 cases each with 50 entries). A line corresponding to the example above would be: [“flower”,”flow”,”flight”],”fl” with the input array followed by the longest common prefix. Include screenshots in your submission.
6. Experimental Analysis: For the experimental analysis you will plot running times as a function of input size. Every programming language should provide access to a clock. Run each of your algorithms on input arrays of size 50 … 500 in increments of 50 (that is, you should have 10 data points for each algorithm). To do this, generate random instances using a random string generator with some fixed prefix. For each data point, you should take the average of a small number (say, 10) runs to smooth out any noise. For example, for the first data point, you will do something like:
for i = 1:10
A = random array with 50*i entries
start clock
longestCommonPrefix(A)
pause clock
return elapsed time
Note that you should not include the time to generate the instance. Plot the running times as a function of input size for each algorithm in a single plot. Provide screenshots of your algorithm generating the results. Include the code that runs the experiments in your submission.
7. Discuss your plot in 6. Do the theoretical and experimental running times agree?
8. Provide a real-world example of a problem that can be modelled and solved as a Longest common prefix problem.
9. Submit a report along with all your implemented code, which should include a detailed readme file (which should explain how to run the code) in separate files via Blackboard by the due date.
"Looking for a Similar Assignment? Order now and Get 10% Discount! Use Code "GET10" in your order"
