Please help me. This is just a problem with subparts. Objective: Compare executi

Question

Please help me. This is just a problem with subparts.

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: Generate a C program that implement the brute force and the divide-and-conquer algorithms. In 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. Use a timing function to measure the execution time for each algorithm used to analyze the input arrays. 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. 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.)

Explanation / Answer

Brute Force Program

#include <stdio.h>
#include <string.h>
#define MAX 100


int bruteForce(char *search, char *pattern, int slen, int plen) {
int i, j, k;

for (i = 0; i <= slen - plen; i++) {
for (j = 0, k = i; (search[k] == pattern[j]) &&
(j < plen); j++, k++);
if (j == plen)
return j;
}
return -1;
}

int main() {
char searchStr[MAX], pattern[MAX];
int res;
printf("Enter Search String:");
fgets(searchStr, MAX, stdin);
printf("Enter Pattern String:");
fgets(pattern, MAX, stdin);
searchStr[strlen(searchStr) - 1] = '';
pattern[strlen(pattern) - 1] = '';
res = bruteForce(searchStr, pattern, strlen(searchStr), strlen(pattern));
if (res == -1) {
printf("Search pattern is not available ");
} else {
printf("Search pattern available at the location %d ", res);
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.