Question

Create an ArrayListReview class with one generic type to do the following
• Creates an array list filled with the generic type of the ArrayListReview
class, and inserts new elements into the specified location index-i in the list.
(5 points)
• Create a method inside the class to implement the calculation of Fibonacci
numbers. Use System.nanoTime to find out how much time it takes to get
fab(50). Create a method inside the class to check if an array list is a
palindrome, assuming each element in the array list is one character. (5
points)
• Implement mergeSort using a list and recursion. (5 points)
• Implement insertionSort either recursively or non-recursively. Implement
mergeSort using recursion. (5 points)
• Use System.nanoTime() to find out the speed of your program. (required
for each step)

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Is This Code Correct?

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

import java.util.ArrayList;

import java.util.Arrays;

public class ArrayListReview {

   public static void fibonacciSeries(int n) {

   System.out.println("\n\nFibonacci Series: ");

   int first = 0;

   int second = 1;

   System.out.print(first + " " + second);

   for(int i=3; i<=n; i++) {

   int third = first + second;

   System.out.print(" " + third);

   first = second;

   second = third;

   }

   }

   public static boolean isPalindrome(ArrayList<Character> list) {

   int len = list.size();

   for(int i = 0, j = len - 1; i < len/2; i++, j--) {

   if(list.get(i) != list.get(j))

   return false;

   }

   return true;

   }

   public static void merge(int arr[], int left[], int right[]) {

   int i = 0;

   int j = 0;

   int k = 0;

   while(i < left.length && j < right.length) {

   if(left[i] < right[j]) {

   arr[k++] = left[i];

   i++;

   } else {

   arr[k++] = right[j];

   j++;

   }

   }

   while(i < left.length) {

   arr[k++] = left[i];

   i++;

   }

   while(j < right.length) {

   arr[k++] = right[j];

   j++;

   }

}

public static int[] mergeSort(int arr[]) {

   int n = arr.length;

   int[] left = new int[n/2];

   int[] right = new int[n-n/2];

   if( n < 2) {

   return arr;

   }

   int mid = n/2, k = 0;

   for(int i=0; i<mid; i++) {

   left[k++] = arr[i];

   }

   k = 0;

   for(int i=mid; i<n; i++) {

   right[k++] = arr[i];

   }

   left = mergeSort(left);

   right = mergeSort(right);

   merge(arr, left,right);

return arr;

}

}

Answer 1

ArrayListReview.java
import java.util.ArrayList;

import java.util.Arrays;

public class ArrayListReview<T>/* create generic type class*/ {
   private T t;
   ArrayList<ArrayListReview<T>> arrayList=new ArrayList<>();
   //constructor
   public ArrayListReview(T t) {

       this.t = t;
   }
   //default constructor
   public ArrayListReview() {
  
   }

   void insertIntoARraylist(T data,int index){
       arrayList.add(index,new ArrayListReview<>(data));
       System.out.println("Data "+data+" inserted at index "+index);
   }
   public static void fibonacciSeries(int n) {
       long nano_startTime = System.nanoTime();
       
   System.out.println("\n\nFibonacci Series: ");
//use long data type to allow bigger values calculation
   long first = 0;

   long second = 1;

   System.out.print(first + " " + second);

   for(int i=3; i<=n; i++) {

       long third = first + second;

   System.out.print(" " + third);

   first = second;

   second = third;
    }
   long nano_endTime = System.nanoTime();

   System.out.println("\nfibonacci start time "+nano_startTime+" fibonacci end time "+nano_endTime);

   }

   public static boolean isPalindrome(ArrayList<Character> list) {

   int len = list.size();

   for(int i = 0, j = len - 1; i < len/2; i++, j--) {

   if(list.get(i) != list.get(j))

   return false;

   }

   return true;

   }

   public static void merge(int arr[], int left[], int right[]) {

   int i = 0;

   int j = 0;

   int k = 0;

   while(i < left.length && j < right.length) {

   if(left[i] < right[j]) {

   arr[k++] = left[i];

   i++;

   } else {

   arr[k++] = right[j];

   j++;

   }

   }

   while(i < left.length) {

   arr[k++] = left[i];

   i++;

   }

   while(j < right.length) {

   arr[k++] = right[j];

   j++;

   }

}

public static int[] mergeSort(int arr[]) {

   int n = arr.length;

   int[] left = new int[n/2];

   int[] right = new int[n-n/2];

   if( n < 2) {

   return arr;

   }

   int mid = n/2, k = 0;

   for(int i=0; i<mid; i++) {

   left[k++] = arr[i];

   }

   k = 0;

   for(int i=mid; i<n; i++) {

   right[k++] = arr[i];

   }

   left = mergeSort(left);

   right = mergeSort(right);

   merge(arr, left,right);

return arr;

}
//insertion sort
int[] insertionSort(int arr[])
{
    int n = arr.length;
    for (int i=1; i<n; ++i)
    {
        int key = arr[i];
        int j = i-1;

        /* Move elements of array arr[0..i-1], that are
           greater than key, to one position ahead
           of their current position */
        while (j>=0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
    return arr;
}
}

Main.java

import java.awt.List;
import java.util.ArrayList;

public class Main {
   public static void main(String[] args) {
       ArrayListReview<Integer> arrayListReview=new ArrayListReview<>();
       arrayListReview.insertIntoARraylist(23, 0);//insert integer type data
       ArrayListReview<String> arrayListReview1=new ArrayListReview<>();
      
       arrayListReview1.insertIntoARraylist("text", 0);//insert string type data
      
       ArrayListReview.fibonacciSeries(50);
       ArrayList arrayList=new ArrayList<>();
       arrayList.add('a');
       arrayList.add('b');
       arrayList.add('a');
          
       System.out.println("arrayList "+arrayList+" is plalindrome? "+ArrayListReview.isPalindrome(arrayList));;
       int arr[]= {2,6,5,20,12,45,84};
       System.out.println("using merge sort : sorted array is ");
       for(int i=0;i<arr.length;i++) {

           System.out.print(" "+ArrayListReview.mergeSort(arr)[i]);
       }
       System.out.println("\nusing insertion sort : sorted array is ");
      
       for(int i=0;i<arr.length;i++) {

           System.out.print(" "+ArrayListReview.mergeSort(arr)[i]);
       }
   }
}

Output

Data "23" inserted at index 0
Data "text" inserted at index 0

Fibonacci Series:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049
fibonacci start time 9028572577483 fibonacci end time 9028599486506
arrayList [a, b, a] is plalindrome? true
using merge sort : sorted array is
2 5 6 12 20 45 84
using insertion sort : sorted array is
2 5 6 12 20 45 84