Divide and Conquer
Preliminaries
Objective
Given a list of size n of distinct positive integers,
partition the list into two sublists each of size n/2 such that the difference
between the sums of the integers in the two sublists is maximized.
An obvious solution to this problem would be to sort the array and simply
evenly divide the array into sub arrays. The sorting approach solves the problem.
However, it does more than the problem requires.
A more efficient solution exists, find it.
If you solve the problem by sorting the array, you will not receive any
credit for this assignment.
A canonical problem exists that can be used to solve this problem.
The approach to solving the problem is discussed in your textbook as well as most other textbooks.
It is a recursive divide and conquer solution.
You will need to implement an algorithm in your text to solve the problem.
To Do
- Write a recursive function that is passed an array, starting index,
ending index, and any other parameters that are necessary to solve the problem.
When the base case is reached, function returns, the array should be partitioned into two sublists
of size n/2.
Global variables are not allowed!
- Your main function
- Header comments must state where you got the algorithm that you are modifying to
solve the problem.
- Declare the array to be of size 100.
- Output a message instructing the user to
enter the size of the array between 1 and 100 : n. n must be an even number.
- Read the number.
- Use assert to ensure the input is valid (between 1 and 100 and even).
- Echo the input with an appropriate message.
- Loop n times prompting the user for each element in the array, filling the
array. You
must echo each value input. Use assert on cin.good() to ensure integer data
was entered. You can assume the elements are distinct.
- Print the array
- Call your recursive function.
- Output the two sublists and the difference between the sums of the two
sublists with proper labeling so the output is
easily understood.
The name of your source file should be maxdiff.cpp.
Be sure your header comments conform to the class standards
Lab Turn In
turnin
Your program must be turned in before class on the specified date.
Select cs328 and then maxdiff. The turnin program will
automatically compile
and run your program, copying it to a directory for me to grade.
Analysis
Using a word processor, answer the following questions.
You must provide an explanation that supports your answers
- What is W(n)?
- Describe the input that solicits W(n).
- What is A(n)?
- What is B(n)?
- Describe the input that solicits B(n).
- Produce a call tree for the input n = 8 A[1,2,3,4,5,6,7,8]
All references must be properly cited.
Submit your analysis to D2L before the start of class on the due
date.
Your Grade
- 70% of your grade will be
based on the correctness and documentation of your code.
- 30% of your grade will be based on your analysis.