CS210 Tutorial 5

Complete the following exercises pasted below. For each exercise, give an algorithm/java code; estimate its runtime given as a function of time T(n) and provide the big Oh notation. Give the recursion trace/tree where necessary

Q1. Write a recursive algorithm for reversing all enteries of a Single Dimension Array.

Q2. Write a recursive algorithm for finding the maximum value in a Single Dimension Array.

Q3. Write a recursive algorithm for a method called StrToInt that takes a string as a parameter and converts this string to its integer value. For Example, a call to this method with "1234" should return the integer value 1234.

Q4. Write a recursive algorithm to count the number of nodes in a Doubly Linked List.

Q5. Write a recursive algorithm that checks if a string is a palindrome. Example: "abbcbba" is a palindrome, "abbabb" is Not a palindrome.

Q6. Write a recursive method to find the sum of all values in a 2x2 array of type integers.

Q7. Give an algorithm that finds all the permutations of a set. i.e. for a set of integers [1, 2, 3], the possible answer is: 123, 132, 213, 231, 312, 321.

SCROLL DOWN FOR SOLUTIONS

//Q1
public static void reverse(int [] A, int i, int j)
    {
        if(i>=j)
            return;
        else
        {
            int temp = A[i];
            A[i]=A[j];
            A[j]=temp;
            reverse(A,++i,--j);
        }
    }

//Q2
public static int MAX(int [] A, int i)
    {
        if(i<=0)
            return A[0];
        else
            return Math.max(A[i], MAX(A,i-1));
        
    }

//Q3
public static int strToInt(String S, int i)
    {
        if(i<0)
            return 0;
        else
        {
            int code = (char) S.charAt(i) - 48;
            return (int) Math.pow(10, S.length()-i-1) * code + strToInt(S, --i);
        }
        
        
    }

//Q4
public static int count(Node N)
    {
        if(N==null)
            return 0;
        else
        {
            return 1 + count(N.next);
        }
    }

//Q5
public static boolean palindrome(String S, int i, int j)
    {
        if(i>j)
            return true;
        else
        {
            return (S.charAt(i)==S.charAt(j) ) && palindrome(S,++i,--j);
        }
    }

//Q6
public static int sumTwoD(int [][]A, int i, int j)
    {
        if(i==j && j==A.length-1)
            return A[i][j];
        else if(j==A.length-1) // reached the end of row i
                return A[i][j] + sumTwoD(A,i+1,0);
        else
            return A[i][j] + sumTwoD(A,i,j+1);
    }
 

//Q7
static int permute(int[] array, int index) {
        if (index == array.length - 1) {
            return 1;  
        }
        int count = 0; 
        for (int i = index; i < array.length; i++) {
            // Swap elements at positions 'index' and 'i'
            swap(array, index, i);
            count += permute(array, index + 1);
            swap(array, index, i);
        }
        return count;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }