Activity 1. A collection of short methods. Instructions: For each of the above m
ID: 3686339 • Letter: A
Question
Activity 1. A collection of short methods.
Instructions:
For each of the above methods, do the following:
Write the pseudocode
Trace the method on two inputs of your choice and provide the trace
Change iteritain to RECURSION JAVA
Functionality 1: Fibonacci
Parameter: an integer n
Return type: a long integer
This method returns the nth Fibonacci number.
public static long FibonacciIter(int n) {
long fn0=0, fn1=1;
long result=0;
for (int i=2; i<=n; i++) {
result=fn0+fn1;
fn0=fn1;
fn1=result;
}return result;
Functionality 2: checkPalindrome
Parameter: a string
Return type: Boolean
This method returns true if the string parameter is a palindrome, false otherwise.
public static boolean checkPalindromeIter(String str) {
for (int i=0; i<str.length()/2;i++) {
if (str.charAt(i)!=str.charAt(str.length()-1-i)) return false;
}
return true;
}
Functionality 3: Decipher
Parameter: a string str and an integer n
Return type: a string
This method returns a string that is str shifted by n. This method illustrates a very simple deciphering activity when you are given a string and you have to translate it by, e.g., shifting each letter down by two letters for instance.
Example: Decipher(“Octvkpg”, -2) à “Martine”
Note: You can access the ascii table at: http://www.asciitable.com. public static String DecipherIter(String str, int shift) {
String result = "";
int code;
for (int i=0; i<str.length(); i++) {
code = (int) str.charAt(i)+shift;
result = result + (char) code;
}
return result;
Activity 2. A Glimpse at Algorithm Performance. In this activity, you will have to go back to Functionality 1 from Activity 1 (Fibonacci numbers). For this functionality, you will have to report the amount of time it takes to run each of the two methods (iterative, recursive) for increasing rank of the Fibonacci number to be computed.
Note: to measure the time it takes to run a given piece of code, you have to insert the following code in each of your methods. It is already in the java file, in the main method.
long startTime = System.currentTimeMillis();
// ... your program...
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(totalTime);
Instructions:
Execute both your Fibonacci methods for increasing values of the input n. E.g., n=1, 5, 10, 20, 50, 100, 500, 1000.
In your file named “yourLastName-yourFirstName-lab8.docx”, report the execution times in a clear table and explain the results you observe.
Activity 3. A Glimpse at Sequence Analysis.
(Inspired by Problem Set 3 from MIT OpenCourseWare, made available on Google’s EngageCSEdu)
String matching is very valuable in settings such as biology. A common problem in modern biology is to understand the structure of DNA molecules, and the role of specific structures in determining the function of the molecule. A DNA sequence is commonly represented as a sequence of one of four nucleotides – adenine (A), cytosine (C), guanine (G), or thymine (T) –and hence a DNA molecule or strand is represented by a string composed of elements from an alphabet of only four symbols, for example, the string AAACAACTTCGTAAGTATA represents a particular strand of DNA.
One way to understand the function of a particular strand of DNA (or even a sub-strand of DNA) is to match that strand against a library of known DNA sequences – that is, sequences whose function and structure is known – with the idea that similar structure tends to imply similar function. Simple organisms such as bacteria may have millions of nucleotides in their DNA sequence, and the human chromosome is believed to have on the order of 246 million bases, so any matching scheme must be very efficient in order to be useful.
In this activity, we hope to give you a sense of some of the issues involved, by exploring some simple matching schemes. We are asking you to program the following functionalities:
Methods 1 & 2: isDNA-Iter and isDNA-Rec
Parameter: a string str
Return type: a boolean
This method returns true if the string str contains only characters A, T, G, C, false otherwise
Note: You have to implement two methods for this one functionality: one iterative method and one recursive method.
Methods 1 and 2: one iterative and one recursive, for the same functionality:
Method 3: you are free to implement it iteratively or recursively.
Method 3: lastIndexSubStringMatch
Parameter: a key string, a target string, and an integer index
Return type: an integer
This method checks if the key string appears in the target string after (including) character at location index.
It will return the last index of the first occurrence if the key string does appear in the target string after location index.
It will return -1 otherwise.
Example 1:
lastIndexSubStringMatch("atgc","atgacatgcacaagtatgcat",3) should return: 8.
because “atgc” appears in the target string starting at location 5 and ends at location 8.
A
T
G
A
C
A
T
G
C
A
C
A
A
G
T
A
T
G
C
A
T
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
T
G
C
We see that we matched “atgc” to a substring of the target string, starting at an index equal to or larger than 3 (all smaller indices were grayed), and the last index of this substring is 8: this is what the method needs to return.
Note: “atgc” appears later in the target string (between indices 15 and 18) but your method “lastIndexSubStringMatch” only looks at the first occurrence of the key string.
Example 2:
lastIndexSubStringMatch("atga","atgacatgcacaagtatgcat",3) should return: -1.
because “atga” appears in the target string only starting at location 0, which is before the index parameter (=3).
Methods 4 and 5: one iterative and one recursive, for the same functionality.
Methods 4 & 5: countSubStringMatch-Iter and countSubStringMatch-Rec
Parameter: a key string and a target string
Return type: an integer, which is the number of instances of the key string in the target string.
Note: //You have to implement two methods for this one functionality: one iterative method and one recursive method.
Example 1:
countSubStringMatch("atgc","atgacatgcacaagtatgcat") should return: 2.
because “atgc” appears in the target string starting at location 5 and at location 15.
A
T
G
A
C
A
T
G
C
A
C
A
A
G
T
A
T
G
C
A
T
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A
T
G
C
A
T
G
C
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
/********************* ACTIVITY 1 *************************/
System.out.println("Testing Activity 1:");
System.out.println("Fibonacci numbers:");
System.out.println("What Fibonacci number do you want to compute?");
int n = in.nextInt();
System.out.println("Iterative Fibonacci of " + n + " is " + FibonacciIter(n));
System.out.println("Recursive Fibonacci of " + n + " is " + FibonacciRec(n));
System.out.println();
System.out.println("Check Palindrome:");
System.out.println("What string do you want to check?");
String str = in.next();
System.out.println("Is " + str + " a palindrome (Iterative)? " + checkPalindromeIter(str));
System.out.println("Is " + str + " a palindrome (Recursive)? " + checkPalindromeRec(str));
System.out.println();
System.out.println("Decipher:");
System.out.println("What string do you want to decipher?");
String str2 = in.next();
System.out.println("What is the cipher shift?");
int shift = in.nextInt();
System.out.println("Iteratively deciphering " + str2 + " by " + shift + " gives us: " + DecipherIter(str2,shift));
System.out.println("Recursively deciphering " + str2 + " by " + shift + " gives us: " + DecipherRec(str2,shift));
System.out.println();
/********************* ACTIVITY 2 *************************/
// insert code needed to test / execute the methods of Activity 2
long startTime = System.currentTimeMillis();
// the code whose execution you want to time goes here
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(totalTime);
/********************* ACTIVITY 3 *************************/
// insert code needed to test / execute the methods of Activity 3
}
}
Functionality 1: Fibonacci
Parameter: an integer n
Return type: a long integer
This method returns the nth Fibonacci number.
Explanation / Answer
ACTIVITY 1:
FUNCTIONALITY 1-
input : int n=5
method : public static long FibonacciIter(5) {
long fn0=0, fn1=1;
long result=0;
for (int i=2; i<=n; i++) {
result=fn0+fn1;
fn0=fn1;
fn1=result;
}return result;
for loop executed till n>5
output: 5
input : int n=4
method : public static long FibonacciIter(5) {
long fn0=0, fn1=1;
long result=0;
for (int i=2; i<=n; i++) {
result=fn0+fn1;
fn0=fn1;
fn1=result;
}return result;
for loop executed till n>4
output: 3
FUNCTIONALITY 2 -
input : MADAM
method :public static boolean checkPalindromeIter(String str) {
for (int i=0; i<str.length()/2;i++) {
if (str.charAt(i)!=str.charAt(str.length()-1-i)) return false;
}
return true;
}
for each character placed at first and last position respectively are checked whether they are same,if same then it returns true or returns false.
for loop travels till i<half of length of the string.
output:- true
input : real
method :public static boolean checkPalindromeIter(String str) {
for (int i=0; i<str.length()/2;i++) {
if (str.charAt(i)!=str.charAt(str.length()-1-i)) return false;
}
return true;
}
for each character placed at first and last position respectively are checked whether they are same,if same then it returns true or returns false.
for loop travels till i<half of length of the string.
output:- false
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.