Please
read the assignment
submission rules and the academic
dishonesty page before you start work on this assignment. Failure to
comply by these rules will cost a significant percentage of your assignment
grade.
Remember:
main method for every
coding problem at the end of your code. Make
sure your classes are in the package dataStructures. If you do not understand
what packages are you can read this tutorial,
if you have trouble with the classpath settings you could try reading this tutorial.
F.or any coding question below, even though you may not use any of the
methods of the class you are extending, you MAY use the constructor of the
class to be extended when you create the constructor of your new class. For
example, you may do something like this:
public ALLExtended (){ super();} public ALLExtended( int n ){ super(n);}
You may NOT
use any built-in array functions in the java API.
1. Extend the class Chain to include a new recursively
implemented method mergeRec(Chain a,Chain b) that merges two
sorted Chains into one. For example, suppose the original Chains are a =
[3, 5, 6, 7] , b=[1, 2, 3, 4, 8] . a and b are sorted
from lowest to highest. When
mergeRec(a,b)
is called, it will return [1,2,3,3,4,5,6,7,8], and both Chains a
and b will be equal to [] at the end.
The template for the class is given below:
package dataStructures;
public class ChainMerge extends Chain{
// your member
variable goes here
public void mergeRec(Chain
a,Chain b){
// your code goes here
mergeRec(a,b); //Call the function within itself, so
it becomes a recursive implementation
}
public
static void main(String[] args) {
Chain a = new Chain();
Chain b = new Chain();
ChainMerge c=new ChainMerge();
for(int i=0
; i < 60 ; i++)
{
b.add(i,i);
}
for(int i=0
; i < 30 ; i++)
{
a.add(i,i+10);
}
System.out.println("a = " + a.toString());
System.out.println("b = " + b.toString());
System.out.println("c = " + c.toString());
c.mergeRec(a
, b );
System.out.println("a = " + a.toString());
System.out.println("b = " + b.toString());
System.out.println("c = " + c.toString());
}
}
Your implementation needs to be recursive. You ARE allowed to call any method in the Chain class.
a) Write Java code for the method mergeRec(Chain
a,Chain b). Test your code.
(40 Points) b) What is the time and space complexity of your code? Be as precise
as possible. (10 Points) 2. Consider a Chain which holds a sentence, each ChainNode
having an English letter or space (no punctuation)
as the data in the element Object. Extend the class Chain by implementing a new
method called wordReverse(), that in effect reverses all the words in this sentence. For example, suppose the original Chain is a = [M,y, ,n,a,m,e, ,i,s, ,B,o,n,d] After calling a.wordReverse(), a
becomes [B,o,n,d, ,i,s, ,n,a,m,e, ,M,y] (ignore
capitalization problems). The template for the class is given below: package dataStructures; public class ChainWordReverse extends Chain{ public
void wordReverse() { //
your code goes here } public
static void stringToChain(String str,Chain
c) // Helper function. Store a string “str” into a Chain “c” { int segNum
= str.length(); while(segNum>0) {
c.add(0,str.substring(segNum-1,segNum));
str = str.substring(0,segNum-1);
segNum--; } } public
static void PrintChain(Chain c) // Helper
function. Print the sentence in Chain “c” {
String s = "\""; for(int i=0
; i < c.size() ; i++ ){
s += c.get(i); } s +=
"\""; System.out.println(s); } public
static void main(String[] args) { ChainWordReverse c = new ChainWordReverse(); stringToChain("My
name is Bond" ,c); PrintChain(c); c.wordReverse(); PrintChain(c); } } You are not allowed to call any
method in the Chain class. You are not allowed
to new any ChainNode either. Calling such methods can
cost up to 100% of the question grade. a) Write Java code for the method wordReverse(). Test your code. (40 Points) b) What is the time and space complexity of your code? Be as precise
as possible. (10 Points)