Homework 13

Comments

• Most problems are found in one of the following:
  1. ADM: The Algorithm Design Manual
  2. IDMA: An Introduction to Discrete Mathematics and Algorithms
• For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
• You will lose a significant amount of credit if you do not provide context, calculations, and justifications for a problem.
• Numbers and/or algebra by themselves are not enough. A correct answer with no justification will be worth no more than half credit, and sometimes much less than that.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• NEW! If you want to learn LaTeX, see the LaTeX section of Writing Notes for a sample LaTeX document. The machines in the lab have TexWorks installed. You may have to ask around to figure out how to compile a file the first time.
• You must indicate any assistance/collaboration you had on an assignment as specified on the Policies page.
• NEW! 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

Spending Money

I recently inherited $100,000,000. Since I never thought saving was a good idea, I want to spend it all. There are 10,000 products, numbered 1 through 10,000, I have always wanted to have. I have a file which includes the cost, to the nearest dollar, of each item. I want you to tell me which items I should buy so I can spend as much of the money as possible. In fact, I want to have at most $800 left over, if possible. Your program should output the number of items in your solution, the index of the items, and the total amount of money left over. For example, if your algorithm outputs "4 3 12 24 36 123", it means I should buy the 4 items 12, 24, 36, and 3, and I will have $123 left over.

Here are some important things you will need.

• The input data: Prob1.dat
• A Verification Algorithm: P1Verify.cpp. Read the comments carefully. In particular, note that it assumes indexing starting at 1 instead of 0.

Hand in your source code and solution files (call it Prob1.out) using Webhandin under assignment 385-H13.

New addition!
Submit a write-up (printed) that includes the following.

1. State which classical computational problem this is an instance of or is related to.
2. Give an assessment of the difficulty of solving the problem, including your reasoning. Start by specify if it is known to be in P or NP-complete and based on this evaluate how difficult you expect it to be.
3. For each algorithm you tried, give a one paragraph discussion that includes:
   • A brief description of the algorithm.
   • Whether your algorithm is attempting to find an exact solution or an approximation.
   • Why you thought it would be a good approach.
   • A tight bound on its complexity.
   • An evaluation of how well it performed (i.e. how good of a solution did you get with it?), including specific numbers (i.e. "the best this algorithm could do was leave $1200").
4. If you tried more than one algorithm, include a paragraph that compares them, specifies which one seems to be the best approach (with justification).
5. Discuss other strategies/algorithms that might work better than what you tried.