I need help with question 2 and programming language used must be Java. In this

ID: 3797971 • Letter: I

Question

I need help with question 2 and programming language used must be Java.

In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares. Write a function bool Solvable(int start, int[] squares) that takes a starting position of the marker along with the array of squares. The function should return true if it is possible to solve the puzzle from the starting configuration, and false if it is impossible. You may assume all the integers in the array are positive except for the last entry, the goal square, which is always zero.

Q2. Algorithm Efficiency and Sorting Implement Heap Sort and Radix Sort Algorithm we discussed in class and Bubble sort we learned before. In addition, write a function to measure the sorting time. Use any random generator (e.g. https://www.random.org/integers/ ) to generate 10, 50, 100, 500, 1000, 5000, 10000 random integer numbers and sort these numbers using Heap Sort, Radix Sort, and Bubble Sort. Present a graph (a clear jpeg/png image) which plots the size of the array (N, x-axis) against the time taken to Sort (y-axis), and describe your observation from the results (e.g. Does the plot of running time reflect the big-O notation).

Q1. A Recursive Puzzle You have been given a puzzle consisting of a row of squares each containing an integer, like this: 3 6 4 1 3 4 2 5 3 0 The circle on the initial square is a marker that can move to other squares along the row. Ateach step in the puzzle, you may move the marker the number of squares indicated by the integer in the square it currently occupies. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker three squares to the right because there is no room to move three spaces to the left. The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves Starting Position: 3 6 4 1 3 4 2 5 3 0 Step 1: (move right) 3 6 4 1 3 4 2 5 3 0 Step 2: (move left) 3 6 4 1 3 4 2 5 3 0 Step 3: (move right) 3 6 4 1 3 4 2 5 3 0 Step 4: (move right) 3 6 4 1 3 4 2 5 0 Step 5: (move left) 3 6 4 1 3 4 2 5 3 0 Step 6: (move right) 3 6 4 1 4 2 5 3 0 Even though this puzzle is solvable-and indeed has more than one solution- puzzles of this form some may be impossible, such as the following one 3 1 2 0

Explanation / Answer

1) Heap Sort :-

Answer:-

public class HeapSort
{
   public void sort(int arr[])
   {
       int n = arr.length;

       for (int i = n / 2 - 1; i >= 0; i--)
           heapify(arr, n, i);

       for (int i=n-1; i>=0; i--)
       {

           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;

           heapify(arr, i, 0);
       }
   }

   void heapify(int arr[], int n, int i)
   {
       int largest = i;
       int l = 2*i + 1;
       int r = 2*i + 2;

       if (l < n && arr[l] > arr[largest])
           largest = l;

       if (r < n && arr[r] > arr[largest])
           largest = r;

       if (largest != i)
       {
           int swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;

           heapify(arr, n, largest);
       }
   }

   static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
       System.out.println();
   }

   public static void main(String args[])
   {
       int arr[] = {12, 11, 13, 5, 6, 7};
       int n = arr.length;

HeapSort ob = new HeapSort();
ob.sort(arr);

       System.out.println("Sorted array is");
       printArray(arr);
   }
}

2) Radix Sort:-

import java.io.*;
import java.util.*;

class Radix {

   static int getMax(int arr[], int n)
   {
       int mx = arr[0];
       for (int i = 1; i < n; i++)
           if (arr[i] > mx)
               mx = arr[i];
       return mx;
   }

   static void countSort(int arr[], int n, int exp)
   {
       int output[] = new int[n];
       int i;
       int count[] = new int[10];
       Arrays.fill(count,0);

       for (i = 0; i < n; i++)
           count[ (arr[i]/exp)%10 ]++;

       for (i = 1; i < 10; i++)
           count[i] += count[i - 1];

       for (i = n - 1; i >= 0; i--)
       {
           output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
           count[ (arr[i]/exp)%10 ]--;
       }

       for (i = 0; i < n; i++)
           arr[i] = output[i];
   }

   static void radixsort(int arr[], int n)
   {

       int m = getMax(arr, n);

       for (int exp = 1; m/exp > 0; exp *= 10)
           countSort(arr, n, exp);
   }

   static void print(int arr[], int n)
   {
       for (int i=0; i<n; i++)
           System.out.print(arr[i]+" ");
   }

   public static void main (String[] args)
   {
       int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
       int n = arr.length;
       radixsort(arr, n);
       print(arr, n);
   }
}

3) Bubble Sort :-

class BubbleSort
{
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{

int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}

void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}