Homework 17

General Comments

• For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You can get up to 50% credit on a problem if you get significant outside assistance. Thus, if you are totally stuck on a problem it might be worth getting help. However, you must indicate any assistance/collaboration (See the Homework Assistance section on the Policies page). Failure to do so could result in a failing grade for the course! Note that getting help from the Help Center or me does not count as significant outside assistance, but talking with your classmates or searching on the Internet does!
  
• If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

Details

1. Consider the following problem:
   Partition Problem. Given a multiset S of positive integers, decide whether S can be split into two subsets with equal sum. An algorithm to solve the problem should answer yes or no, and provide the partition.
   Example: If \(S=\{1, 3, 4, 7, 10, 23\}\), then the answer is yes since \(S\) can be partitioned into \(\{1, 23\}\) and \(\{3, 4, 7, 10\}\), each of which sums to 24.
   
   
   1. Give a very clear brute-force algorithm to solve the partition problem.
   2. Give the worst-case analysis of your brute-force algorithm.
   3. Give a very clear backtracking algorithm to solve the partition problem. Do you have to do any precomputation before you start? Be clear on this.
   4. Give the backtracking tree for \(S = \{3, 5, 8, 10, 12, 14, 16\}\), until you find a solution, and clearly state the solution.
   5. Given the set \(S=\{3, 7, 14, 22, 35, 41, 48, 56, 68, 77, 89, 94\}\), compare how the two algorithms would perform:
      1. How many operations are needed for the brute-force algorithm?
      2. Do three Monte-Carlo simulations to estimate the size of the backtracking tree. That is, determine the size of each of the three trees, and then average the sizes of the three to get an estimate of the average tree size. Make sure to show all of your calculations.
      3. Given the size of the tree, estimate the number of operations necessary to solve the problem
      4. Determine a fair way to compare the two calculations and comment on the which algorithm seems to be better.