Overview: You will be given a $2-$d array where each location will contain $0,1,$ or $2.$ Further each row and column will be sorted. You will need to find the sum of the entries in the array in $3$ different ways and check the amount of time each takes.

Details: Your java program will be provided with a file called input.txt$.$ The first line will contain two integers: $\backslash ($ m $\backslash )$ the number of rows and $\backslash ($ n $\backslash )$ the number of columns. The remainder of the file will contain $\backslash ($ m $\backslash$cdot n $\backslash )$ values from $\backslash (\backslash \{0,1,2\backslash \}\backslash )$ which if placed into an $\backslash ($ m $\backslash )$ by $\backslash ($ n $\backslash )$ array top to bottom, left to right $($just like reading a normal English text$)$ will have each row and column sorted.

You will find the sum of the values in the array in $3$ different ways. The first will be the simplest: use $2$ nested loops to add the items in time $\backslash (\backslash$Theta$($m$-$n$)\backslash ).$ The second will be to use a slight variant of bisection$/$binary search to find where the row switches from $0$ to $1$ and from $1$ to $2.$ Using this you can find the sum in time $\backslash (\backslash$Theta$($m $\backslash$lg n$)\backslash ).$ For your $3$rd method you need to figure out and implement a $\backslash (\backslash$Theta$($m$+$n$)\backslash )$ method to find the sum.

Your program should output the sum found by each method $($even though the $3$ values should be equal$)$ and the amount of time each took $($in milliseconds$)$ by using System.currentTimeMillis $0.$

Picky, but required specifications: Your project must:

$-$ be subrnitted via canvas.

$-$ consist of $1$ or more dot$-$java files $($no class files, zip files, input files, or other files should be submitted$).$

$-$ have each file begin with a comment containing your name and the project number.

$-$ not be placed into any package.

$-$ have one file called Project$3.$java $($don$\text{'}$t be concerned if canvas adds a 'flag' $1.-2....$ for repeated submissions$).$

$-$ compile with the command Javac Project$3.$java".

$-$ run using the command java Project$3.$

$-$ accept input from a file called input.txt in the same directory as the java file$($s$)$ formatted precisely as described above.

$-$ accomplishes the goal of the project. In other words, the output should be the correct answer formatted correctly.

$-$ be submitted on time $($early and multiple times is fine$).$

For each listed item you fail to follow, expect to lose at least $5$ points. However, submitting via email will guarantee you a zero.

Examples: Your program should work on any valid input. I will be testing on much, much larger inputs. I haven't written my version yet. So the following are not "real" results. Let me know if my hand$-$solution is incorrect $($don$\text{'}$t worry about the exact values for times, but my "guesses" should be within $2$ of the right answer$).$

If input.txt contains: