CODEWITHSUNDEEP
divide-and-conquer
shinjuo
shinjuo

Reputation: 21012

Divide and Conquer Algorithms

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:

Upvotes: 0

Views: 1972

Answers (2)

Makoto
Makoto

Reputation: 106440

Let's not think about a programming language for a moment and think about what the approach would be in abstract.

Imagine if you were in a room with twenty stacks of paper, each with a single number on them. You're willing to do the work of bringing all of the numbers' totals together, but you realize that going one by one is going to take forever. So, you call in a friend and you each get ten stacks to each other to work on. The amount of work you've had to do by calling your friend went down by half.

You both realize that you're not going to get anywhere with ten stacks of paper, so each of you call another friend to lend a hand, leaving all four of you with five stacks apiece. Reasonable, but still overwhelming. So everyone, once again, calls another friend over and halves their stack with the other friends - leaving everyone with 2.5 stacks of papers with numbers on them.

You all agree that this is a reasonable amount of work to be done by one person, so you get to work adding the numbers together. Working from the last set of people that came in up to yourself, everyone returns the total sum of the numbers they had up until you have everyone else's sum, and you have your own. You sum these two together and arrive at your result.

This is the principle of divide and conquer: your work stack is divided into some fraction of work that you then make calls to other methods to do.

Here's a pseudoexample for you in Python.

def sum(*args):
    if len(args) == 0:  # Nothing in my list, so I'm done
        return 0
    elif len(args) == 1:  # One thing in my list, return that
        return args[0]
    else:  # Too much for me to handle; call in the Calvary!
        return args[0] + sum(args[1:])

Upvotes: 3

Joe
Joe

Reputation: 63424

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.

Upvotes: 3

Related Questions