SUNY Geneseo Department of Computer Science

Problem Set 8—Dynamic Programming 2

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Wednesday, March 27

Purpose

This exercise further develops your ability to design dynamic programming algorithms.

Background

Dynamic programming is an algorithm design technique that can transform obvious but inefficient recursive algorithms into startlingly more efficient iterative ones. However, the technique is often not particularly intuitive. Chapter 15 of our textbook discusses dynamic programming, and we discussed it in lectures starting on February 21.

Exercise

Solve each of the following problems.

Problem 1

The State University of New West Dakota has begun a tuition policy whereby students pay separately for each course they take. Generally, different courses have different prices, and carry different amounts of credit. The i^th course in the catalog has price p_i, and is worth c_i credits. There are a total of K courses in the catalog. Stacey Student has an amount M of money to spend on her education this semester. Give a dynamic programming algorithm she could use to calculate the maximum number of credits she can get for this amount of money. Assume that M is an integer and that all courses cost an integer amount of money; Stacey picks courses without regard to their subject area or how many courses she is taking.

Problem 2

Problem 15-2 in our textbook.

Problem 3

Problem 15-10, part C, in our textbook. You may assume that in each year you place all your money in a single investment fund (i.e., you may assume the result of part A without actually proving it).

Extra Credit

For up to 3 points extra credit, code one or more of your algorithms in an actual programming language and demonstrate them working.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Schedule your meeting to last 15 minutes. Please sign up for your meeting on the schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure your meeting ends by the end of the day on the due date above.