Question

In: Computer Science

Task #1 Develop a recursive method to reverse a list Develop a method with the prototype...

Task #1 Develop a recursive method to reverse a list Develop a method with the prototype public static void reverse (ArrayList inputList) based on selecting the first list element as the head and the remaining list as its tail. Here is the recursive design. 1) Base case: The problem is trivial when the list size is 0 or 1. 2) Decomposition: For lists with size > 1: a) Extract its head (element) and leave the tail (the input list with the head removed). You can look up the method that does this for the List interface. b) Make a recursive call to obtain the tail reversed. Page 2 of 3 3) Composition: Append the extracted head element to the reversed tail obtain the original list reversed. Task #2 Develop a recursive method to find the maximal element Note that this is not possible unless the list elements are comparable to each other. Java provides a generic Interface for this called Comparable. Based on this, develop a method with the following prototype public static > E max(List inputList) You can use the same problem decomposition technique as in Task #1. Think about how the composition of result should be made. Task #3 Develop a recursive method to sum the list elements Obviously, this is not possible unless the list elements are of numeric type. Develop a recursive summing method with the prototype public static double sum (List inputList) Task #4 Use command line arguments to supply the list elements Use the following main() method: public static void main(String args[]) { ArrayList argList = new ArrayList<>(); ArrayList numericArgs = new ArrayList<>(); for (String s : args) { argList.add(s); try { numericArgs.add(Double.parseDouble(s)); } catch (NumberFormatException e) { System.out.println(e.getMessage() + "is not numeric...skipping"); } } System.out.print("Command line arguments before reversal: "); for (int i=0; i

Solutions

Expert Solution

public class Main {
  
// methods to implement
public static String reverseRecursiveLeft (String input) {
// base case
if(input.length() <= 1) {
// if string have 1 or less character left return the string
return input;
}
// recursive solution
// for string greater then 1 character long divide it in to head and tail part
String head = input.substring(0, 1); // get first character from substring method
String tail = input.substring(1); // get remaining character from substring method
// make recursive call to obtain tail in reverse and append head to it
return reverseRecursiveLeft(tail) + head;
}

public static String reverseRecursiveRight (String input) {
// base case
if(input.length() <= 1) {
// if string have 1 or less character left return the string
return input;
}
// recursive solution
// for string greater then 1 character long divide it in to head and tail part
String head = input.substring(input.length()-1); // get the right most character from substring method
String tail = input.substring(0,input.length()-1); // get remaining character from substring method
// make recursive call to obtain tail in reverse and append it to head
return head + reverseRecursiveLeft(tail);
}
  
public static String reverseRecursiveMiddle (String input) {
// base case
if(input.length() <= 1) {
// if string have 1 or less character left return the string
return input;
}
else if(input.length()==2) {
// if string have 2 character return them in reverse order
String left = input.substring(0, 1);
String right = input.substring(1, 2);
return right + left;
}
// recursive solution
// for string greater then 2 character long divide it in to head, middle and tail part
String head = input.substring(0, 1); // get the left most character from substring method
String tail = input.substring(input.length()-1); // get the right most character from substring method
String middle = input.substring(1,input.length()-1); // get remaining character from substring method
// make recursive call to obtain middle in reverse and append it to tail then append the head
return tail + reverseRecursiveLeft(middle) + head;
}
  
public static int reverse (int input) {
// check if input is negative
if(input < 0) {
// turn input in to positive integer as only digits are reversed
input = input * -1;
// convert integer to string with wrapper class
String str = Integer.toString(input);
// reverse the string
String reverseDigit = reverseRecursiveLeft(str);
// convert string to integer
int integer = Integer.parseInt(reverseDigit);
// return the integer with negative value
return integer*-1;
}
else {
// convert integer to string with wrapper class
String str = Integer.toString(input);
// reverse the string
String reverseDigit = reverseRecursiveLeft(str);
// convert string to integer
int integer = Integer.parseInt(reverseDigit);
// return the integer
return integer;
}
}
  
static boolean isPalindrome (String input) {
// base case
if(input.length() <= 1) {
// if string have 1 or less character left return true as the character is in middle of the string
return true;
}
else if(input.length()==2) {
// if string have 2 character check are they equals
String left = input.substring(0, 1);
String right = input.substring(1, 2);
return left.equals(right);
}
// recursive solution
// for string greater then 2 character long divide it in to head, middle and tail part
String head = input.substring(0, 1); // get the left most character from substring method
String tail = input.substring(input.length()-1); // get the right most character from substring method
String middle = input.substring(1,input.length()-1); // get remaining character from substring method
// make recursive call to check if middle is palindrome
// compare head and tail and return the result with logic and with middle
return head.equals(tail) && isPalindrome(middle);
}
  
public static boolean isPalindrome (int input) {
// check if input is negative
if(input < 0) {
// turn input in to positive integer as only digits are counted for palindrome
input = input * -1;
}
// convert integer to string
String str = Integer.toString(input);
// return if string is in palindrome
return isPalindrome(str);
}
  
// main method to run program
public static void main(String args[]) {
String str = "hello world!";
System.out.println("Reverse of ");
System.out.println(str);
System.out.println("by reverseRecursiveLeft is:");
System.out.println(reverseRecursiveLeft(str));
System.out.println("by reverseRecursiveRight is:");
System.out.println(reverseRecursiveRight(str));
System.out.println("by reverseRecursiveMidlle is:");
System.out.println(reverseRecursiveMiddle(str));
System.out.println();
  
int p = 423651;
System.out.print("Reverse of ");
System.out.print(p);
System.out.print(" is: ");
System.out.println(reverse(p));
System.out.println();
  
int n = -54637;
System.out.print("Reverse of ");
System.out.print(n);
System.out.print(" is: ");
System.out.println(reverse(n));
System.out.println();
  
String s = "AbcDcbA";
System.out.print(s);
System.out.print(" is palindrome? ");
System.out.println(isPalindrome(s));
System.out.println();
  
System.out.print(n);
System.out.print(" is palindrome? ");
System.out.println(isPalindrome(n));
int pali = 1258521;
System.out.print(pali);
System.out.print(" is palindrome? ");
System.out.println(isPalindrome(pali));
}
}


Related Solutions

Exercise: Recursive List Processing Part 1: Write a recursive method that returns the length (an int)...
Exercise: Recursive List Processing Part 1: Write a recursive method that returns the length (an int) of the longest String in a List of Strings. For each recursive call, remove the first String from the list and return the greater of the length of the String you removed or the result of calling the method on the remainder of the list. The base case should be that the size of the list is 0. Write a driver to verify that...
Method: DoublyLinkedList reverse(DoublyLinkedList list) Reverse() method accepts a DoublyLinkedList of Character as the argument, reverses the...
Method: DoublyLinkedList reverse(DoublyLinkedList list) Reverse() method accepts a DoublyLinkedList of Character as the argument, reverses the elements in the list, and returns the resulting list. For example: The given list is 'a' 'b' 'c' 'd' 'e' The return list should be 'e' 'd' 'c' 'b' 'a' How can we do this in Java?
Task 2: Recursive Binary Search Part A - Target in list? Write a function simple recursive...
Task 2: Recursive Binary Search Part A - Target in list? Write a function simple recursive binary search(lst, target) which returns True if target is in lst; otherwise False. You must use recursion to solve this problem (i.e. do not use any loops). Part B - Where is target? Write a function advanced recursive binary search(lst, target, lo, hi) which returns the index of an instance of target in lst between lo and hi, or None if target is not...
java Write a recursive program to reverse a positive integer. . Your method should take a...
java Write a recursive program to reverse a positive integer. . Your method should take a non negative integer as a parameter and return the reverse of the number as an integer. e.g. if you pass 12345, your method should return 54321.
Task 1: [10 Marks] Write a function “reverse” in your queue class (linked list implementation) that...
Task 1: [10 Marks] Write a function “reverse” in your queue class (linked list implementation) that reverses the whole queue. In your driver file (main.cpp), create an integer queue, push some values in it, call the reverse function to reverse the queue and then print the queue.
Implement a non-recursive reverse print of linked list using stack and the main function to test:...
Implement a non-recursive reverse print of linked list using stack and the main function to test: You will need to finish the printReversed_nonrecursive method in ch04.LinkedStack2 class, and the ch04.UseStack2 is the main function to test. public class LinkedStack2<T> extends LinkedStack<T> { private void revPrint(LLNode<T> listRef) { if (listRef != null) { revPrint(listRef.getLink()); System.out.println(" " + listRef.getInfo()); } } public void printReversed() { revPrint(top); } /* use stack to implement non-recursive reverse print */ public void printReversed_nonrecursive() { } public...
Write a recursive implementation of insertion sort. Draw a tree of recursive calls for your prototype...
Write a recursive implementation of insertion sort. Draw a tree of recursive calls for your prototype random dataset and compare its big-O efficiency to that of iterative insertion sort. Run your prototype datasets (best, worst, random) from homework 1 and compare the results to the ones for iterative insertion sort. Which version is better? Make sure to present the results in the table form used in homework 1. Include the data for both iterative and recursive versions.
Java coding: 2. Write a method which takes a list list of int , and reverse...
Java coding: 2. Write a method which takes a list list of int , and reverse it. // recursion 3.Write a method which takes a list list of strings , and reverse it. // in different way than the previous 3. Write a two methods which take a list and find the largest integer number in it.
C++ Modify the class unorderedList to include a recursive forward print and a recursive reverse print...
C++ Modify the class unorderedList to include a recursive forward print and a recursive reverse print Make your unorderedList a list of characters instead of integers Insert ten characters into the list and print it out both ways #include <iostream> #include <string> #include <cstdlib> using namespace std; struct node { int info; node* next; }; class unorderedList { private: int length; node* listPtr; public: unorderedList() {length = 0; listPtr = NULL;} void makeEmpty(); void insertItem(int item); void printList(); bool isFull()...
IN JAVA A recursive method that takes a String as its argument and returns a list...
IN JAVA A recursive method that takes a String as its argument and returns a list of Strings which includes all anagrams of the String. This method will contain a loop that generates each possible substring consisting of all but one character in the input String, ie the substring that omits the first letter, then the substring that omits the second letter, etc. Within the loop, the method calls itself recursively for each substring. For each String in the list...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT