Problem Description:

Complete the implementation of the isSubarray$()$ method in SubarrayChecker.java. This method

should determine whether B is a subarray of A$.$ An array B is considered a subarray of array A

if all the elements in B appear in A in the same order. A and B are integer arrays.

If B is not a subarray of A$,$ return False. If B is a subarray of A$,$ return True along with all the

starting indices where B can be found in A$.$ It should be noted that if there are multiple indices

that satisfy the condition, all satisfying indices should be returned as an array.

Examples:

$$ Input: A $=[1,2,3,4,5],$ B $=[2,3]$

Expected Output: True, $[1]$

$$ Input: A $=[5,6,7,8,9],$ B $=[2,3]$

Expected Output: False, $[]$

$$ Input: A $=[1,2,3,2,3,4],$ B $=[2,3]$

Expected Output: True, $[1,3]$

$$ Input: A $=[1,2,3],$ B $=[3,2]$

Expected Output: False, $[]$

Submission

You must solve this problem using Java and use the template provided, SubarrayChecker.java.

You cannot change the method signature for isSubarray otherwise you may receive a score of

$0.$ You are welcome to create additional methods to aid in your implementation.

Following the template description, please:

$1.$ Write your name and student number at the beginning.

$2.$ Calculate the time and space complexity of your algorithm and write the result at the end of

your algorithm.

$3.$ Run your algorithm with all of the tester input files: inputX.txt $($where X is $1,2,...,6.)$ and

print output to STDOUT.

$4.$ The array size of input files is $5,10,50,200,1000,5000.$ Capture the running time for

different input sizes and then plot it in a graph. Write a small paragraph about what you

observed experimentally and what was your analytical$/$theoretical analysis of time complexity.

You can store the running time by using one of the following structures:

You can check if your algorithm is correct by using the test file SubarrayTester.java. Several

examples are already included in the tester but you are strongly encouraged to add more test

cases.

Submission Requirements:

$$ We need a zip file containing at least $2$ Java files and one pdf that contains the graph and

mentions about your analysis summary $($experimental vs theoretical$).$ The two Java files are

included in the assignment folder, you need to complete these files according to the

instructions mentioned in the file. You can have additional Java file depending on your choice

of solution implementation.

$$ The pdf file will include a graph plot for your result $($run$-$time complexity$)$ and a summary

paragraph describing how you found the experimental analysis in relation to the theoretical

analysis.

import java.io$.*$;

import java.util.$*$;

public class SubarrayChecker $\{$

public static Object$[]$ isSubarray$($int$[]$ A$,$ int$[]$ B$)\{$

List indices $=$ new ArrayList$<>()$;

boolean isSubarray $=$ false;

$/*$

Array indices should contain a list of starting indices where B is found in A$.$

Boolean isSubarray should indicate whether B is a subarray of A

$*/$

return new Object$[]\{$isSubarray$,$ indices$\}$;

$\}$

public static void main$($String$[]$ args$)\{$

$/*$

Read input from STDIN. Print output to STDOUT.

To conveniently test your algorithm, you can run your solution with any of the tester input files using:

java SubarrayChecker inputX.txt

where X is $1,2,...,6.$

The array size is from $5,10,...,5000.$

You should capture the time taken using built in commands.

Find the result$/$output for different input sizes and then plot it in a graph.

Write a small paragraph about what you observed experimentally and what was your

analytical$/$theoretical analysis of time complexity.

$*/$

$\}$

$\}$