Brute force:

#include #include #define MAX 100 /* try to find the given pattern in the search string */ int bruteForce(char *search, char *pattern, int slen, int plen) { int i, j, k; for (i = 0; i

Merge sort:

1. /*

* C Program to Find the Sum of Contiguous Subarray within a 1 - D Array of N

umbers which has the Largest Sum

*/

4.#include 5.#include 6. 7.int maxSubArraySum(int a[], int size, int *begin, int *end) 8.{

int max_so_far = 0, max_end = 0;

int i, current_index = 0;

11.

for(i=0;i

{

max_end = max_end + a[i];

if (max_end

{

max_end = 0;

current_index = i + 1;

}

else if (max_so_far

{

max_so_far = max_end;

*begin = current_index;

*end = i;

}

}

return max_so_far;

28. } 29. 30.int main() 31. {

int arr[] = {10, -2, 15, 9, -8, 12, 20, -5};

intstart=0,end=0;

int size = sizeof(arr) / sizeof(arr[0]);

35.

printf(" The max sum is %d", maxSubArraySum(arr, size, &start, &end));

printf(" The begin and End are %d & %d", start, end);

getchar();

return 0;

40. }

How can I implement a timing function to see which one takes longer to sort?

(Program for the maximum subarray problem in C) Objective: Compare execution times of the brute force and the divide-and-conquer algorithms when solving the maximum subarray problem for arrays of different sizes. The arrays to be analyzed shall be the same for each algorithm, in order to make a valid comparison. Assignment: 1. Generate a C program that implement the brute force and the divide-and-conquer algorithms. 2. n your program, include a provision to generate arrays of varying sizes. Populate the arrays with integers, using a random number generator function (a library function is fine). Make a copy of this input array so that the same values will be used in both algorithms. 3. Use a timing function to measure the execution time for each algorithm used to analyze the input arrays. 4. Test your algorithms using arrays of size: 10, 100, and 1000 elements. Record the execution times and summarize the execution times in a table, ensuring that you provide time units for the execution times, i.e. seconds, milliseconds, clock cycles, etc. 5. Generate a short summary of your experimental observations and based on your results provide a commentary on when you would use each algorithm. (You may want to conduct more experiments to refine your recommendation.)