nstructions:

$$ Submit the java project folders as a $.$zip file.

$$ Submit the MS Word file containing the proof for running time complexity of all tasks.

Task $1$: $[35$ pts$.]$

$1.$ Write a linear $(())$ running time complexity program in Java to find all the dominant

elements in the given array of $$ distinct integer elements. An element is a dominant element

if it is greater than all the elements to its right side. The rightmost element in the array is always

a dominant element. For example, in the array $\{16,17,4,3,5,2\},$ dominant elements are $17,$

$5$ and $2.$

$2.$ Prove that your algorithm takes $(())$ running time to compute this task. Formulate the

sum equation for this proof.

Task $2$: $[30$ pts$.]$

$1.$ Implement a program in Java that, given an array of $$ integers, places all positive elements at

the end of the array without changing the order of positive and negative elements with an

$()$ running time complexity.

a$.$ Example:

b$.$ Input: arr$[]=\{1,1,3,2,7,5,11,6\}$

c$.$ Output: $175132116$

$2.$ Prove that your algorithm takes $(())$ running time to compute this task. Formulate the

sum equation for this proof.

Task $3$: $[35$ pts$.]$

You are given an $\backslash$times $$ grid which contains lower case English letters. How many times does the

phrase "saba" appear horizontally, vertically, and diagonally in the grid?

Input Format:

First line: Two integer $$ and $,$ where $$ denotes $(1<=,<=100)$ the number of rows and

$$ denotes the number of columns in the grid

Next $$ lines: Each line must contain a string of length $$ which contains lower$-$case English letters

only

For Example:

A sample dialogue $($input$)$ is:

Enter n value: $5$

Enter m value: $5$

COP$3530$ Assignment $1$ Page $2$ of $2$

Enter $5$ lines of $5$ characters:

safer

amjad

babol

aaron

songs

This input will be stored in a $2$D array of $$

s a f e r

a m j a d

b a b o l

a a r o n

s o n g s

Output Format:

Print the number of times the word $$saba$$ appears in the grid.

As an output of the above sample data the word $$saba$$ appears $3$ times.