Part 0:   preparation

  • Read lecture notes T5 and the relevant sections in Sedgewick. The divide-and-conquer solution is closely related to mergesort.

    • Part 1: brute force method

  • First, read in the input file using scanf and store it in an array. It's fine to allocate an array of size 2,000,000 and use only the portion of it that you need to store the input data. (This will not slow down you code as you might expect at first, as allocating a big array only takes 1 unit of time, not N.) To debug this part of your code, print out each value and make sure that everything was read in properly.

  • At this point in the course, you should be able to write code for the brute force algorithm. It may be helpful to first write down pseudocode using pencil and paper, and then translate to C code.

  • You should have three nested loops; if you only have two, this is likely the "better" algorithm.

    • Part 2:   better method

  • You should only need to change a few lines of code, but think carefully about what needs to get changed.

    • Part 3:   divide-and-conquer  

    This is definitely the hardest (and most educational) part of the assignment. First, make sure that you understand the concept of divide-and-conquer. Divide means break the problem up into two smaller subproblems. You will conquer each of these halves recursively. The key to divide-and-conquer is then combining the solutions to the two subproblems to arrive at a solution to the original problem. If you don't understand the code for quicksort (Sedgewick, Program 7.1) and mergesort (Sedgewick, Program 8.3) after doing the relevant readings, see your preceptor, as this material is critical if you hope to write your own divide-and-conquer algorithm.

  • To get started, write a function divide_and_conquer() that divides the input into two "halves" and "conquers" each half independently. For now, use your brute force method to conquer each half (instead of doing it recursively). Don't worry about recursion or worry about the case when the best subsequence contains element a[m].

  • Now, write code that finds the maximum subsequence that contains a particular element a[m]. You can break this problem up into two smaller tasks: find the largest subsequence whose right endpoint is m-1, and find the largest subsequence whose left endpoint is m+1. Once you have done this, you can obtain the maximum subsequence containing a[m] by judiciously combining the two subsequences you have just computed. Note that either (or both) of these pieces can be empty, e.g., if a[m-1] or a[m+1] is very negative.

  • If you have successfully debugged the above pieces, you are now ready for the moment of truth. Replace your brute force solution to solving each half size subproblem with an appropriate recursive call to divide_and_conuqer(). Don't forget to also add a base case.

  • General advice:

  • When you start out, you may wish to just try to compute the value of the best subsequence, and not worry about the indices where this value occurs. Later on, you can modify your code to compute this as well. It's OK to use global variables to store these, although a better alternative would be to use structs or pointers.

  • The code for this is somewhat subtle, so test each part of your code as you write it. The small test input files are particularly useful for debugging.


    • Kevin Wayne