We are starting to work with Divide and conquer algorithms in my Data structures class and I am having a lot of trouble completely understanding what I am supposed to do. Below is the which is basically asking for me to write a program that sums an array, but it has to divide and conquer it down until the base is 4 which I assume means to to add the array together in chunks of 4 and then add all the chunks together. I dont even know where to begin. I just need a little explanation and understanding. The teacher wasnt much help. The array contains a line of numbers in the amount of a power of 2 less than a 1000
Problem Write a divide-and-conquer algorithm for summing an array of n in- tegers. The base case for this algorithm will be when the size of the sub-problems are smaller or equal to 4 in which case you will use an iterative loop to sum the integers of the sub-problems. You need to do the following:
I would guess you're intended to write a recursive method that splits array A into two (or more) subarrays of half the array each, then passes the resulting arrays to itself in order to continue splitting until you have an array of size 4; then you can perform your sum and return the sum of those 4 units.