COMP352-Assignment 1 String Permutations Solved

Question 1      

Given a string of random length and random contents of characters, that do not include digits (0-9), write an algorithm, using pseudo code that will shorten the representation of that string by adding the number of consecutive characters. For instance, given str as “gggN@@@@@KKeeeejjdsmmu” the algorithm should return the following representation of the string: “g3N@5K2e4j2dsm2u”.  

 

a)     What is the time complexity of your algorithm, in terms of Big-O?  

b)     What is the space complexity of your algorithm, in terms of Big-O?  

 

 

 

Question 2  

i)     Develop a well-documented pseudo code that finds the two consecutive elements in the array with the smallest difference in between, and the two consecutive elements with the biggest difference in between. The code must display the values and the indices of these elements.  For instance, given the following array [20, 52,400, 3, 30, 70, 72, 47, 28, 38, 41, 53, 20] your code should find and display something similar to the following (notice that this is just an example. Your solution must not refer to this particular example.):  

 

The two conductive indices with smallest difference between their values are: index 5 and index 6, storing values 70 and 73.  

The two conductive indices with largest difference between their values are: index 2 and index 3, storing values 400 and 3.  

 

In case of multiple occurrences of the smallest or largest differences, the code should display the first found occurrence.  

 

ii)   Briefly justify the motive(s) behind your design.  

 

iii)  What is the time complexity of your solution? You must specify such complexity using the Big-O notation. Explain clearly how you obtained such complexity.  

 

iv)  What is the maximum size of stack growth of your algorithm? Explain clearly.   

 

             

Question 3     

Prove or disprove the following statements, using the relationship among typical growth-rate functions seen in class.

 

a)     n15log n + n9 is O(n9 log n) 

b)     157n5 + 5n4 + 8000000n2 + n is Θ(n3) 

c)      nn is Ω (n!) 

d)     0.01n9 + 800000n7 is O(n9) 

e)     n14 + 0.0000001n5 is Ω(n13) 

f)      n! is O(3n) 

 

 

Programming Questions 

In this programming assignment, you will design in pseudo code and implement in Java two versions of a program that deals with two strings, referred to as shortStr and longStr. The program attempts to find if any/all possible permutation of shortStr exists within longStr, and if so, at which location on longStr.  

 

Version 1: 

In your first version, you must write a recursive method called permu, which accepts shortStr (and any other needed parameters; i.e. start index and end index) and generates ALL possible permutation of that string. For each possible permutation value, the method should find out (possibly by calling another method), whether that permutation value is a substring of longStr. Your code must show all permutations and for each of them should indicate whether or not this value exists in longStr.  

 

For example; given longStr as “hhhlajkjgabckkkkcbakkdfjknbbca”,and shortStr as “abc”, the method should show display something like:

 abc 

Found one match: abc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 9 acb bac bca 

Found one match: bca is in hhhlajkjgabckkkkcbakkdfjknbbca at location 27 cba 

Found one match: cba is in hhhlajkjgabckkkkcbakkdfjknbbca at location 16 cab 

  

Given shortStr as “ckkk”, the method should show display something like:

 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 ckkk 

Found one match: ckkk is in hhhlajkjgabckkkkcbakkdfjknbbca at location 11 

kckk kckk kkck kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kkck kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kckk kckk kkck kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kkkc 

Found one match: kkkc is in hhhlajkjgabckkkkcbakkdfjknbbca at location 13 kkck kckk kckk 

 

Note: While our interest is to find if any occurrence of a permutation value exists in longStr (and not all of them; for instance, if abc exists twice in longStr, it is sufficient for the algorithm to find only the first occurrence), you should observe the output carefully, since the characters of shortStr may not be unique, as in the second run!

 

You will need to run the program multiple times. With each run, you will need to provide a shortStr with an incremented length of 5. That is, you need to run with shortStr of 5 characters, 10 characters, 15 characters, etc. for up to length of 200 characters (or higher value if required for your timing measurement) and measure the corresponding run time for each run. You can use Java’s built-in time function for finding the execution time. In each run, you need to provide a longStr that is longer in length than shortStr. The contents of the strings are not important; however, your values should show that you program work correctly. You should redirect the output of each program to an out.txt file. You should write about your observations on timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, and the text files.  

  

Briefly explain what is the complexity of your algorithm. More specifically, is your solution has acceptable complexity; is it scalable enough; etc. If not, what are the reasons behind that?  

 

Version 2: 

In this second version, you will need to provide and alternative/smarter solution (to solve the same exact problem as above) however this second solution must significantly have lower time complexity than you first version. The solution may or may not use recursion; this is up to you.  

a)     Explain the details of your algorithm, and provide its time complexity. You must clearly justify how you estimated the complexity of your solution.