SUNY Geneseo Department of Computer Science

Introduction to Dynamic Programming

Thursday, February 21

CSci 242, Spring 2013
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Hour exam one is next Thursday (Feb. 28)

Material from start of semester through recurrences (graphs, BFS, DFS, divide and conquer, induction, recurrences, master method)
4 - 6 short-answer questions
Full class period
Open book, notes, computer; closed person

Questions?

Master method problem set, problem 1, worst case?

Set up the recurrence to describe the most time-consuming possible way of executing the function’s recursive part
In this case, that would be the third arm, which recursively processes both halves of the array
All constant-time pieces of work can be lumped together as “1” for purposes of asymptotic analysis

Past lecture notes?

Available for this semester through myCourses, or here
For past semesters, follow link from this semester’s syllabus to “last time I taught this course”

Dynamic Programming and Rod Cutting

Dynamic programming is good when a recursive algorithm solves the same subproblem multiple times. But it would not, for example, be good in something like Quicksort or Mergesort where the subproblems don’t overlap.

Overlapping subproblems in rod cutting

Size n rod involves size n-1 and n-2 subproblems, size n-1 subproblem also involves size n-2 sub-subproblem

Dynamic Programming Trip Planning Example

You want to drive from home to some remote destination. Car has a G gallon gas tank and gets M miles per gallon; trip is long enough that you’ll need to stop for gas, but you want to minimize how much you pay for gas on the trip. There are gas stations along the route, the i^th station charges p_i dollars per gallon of gas, and is at distance d_i miles from your home. You leave home with a full tank of gas, and will need to top up at the destination (distance d_n with price p_n).

Gas stations along trip

Idea: modify rod cutting algorithm from book

        tripPlanning( D, P, n )
            let r[0..n] be a new array
            r[0] = 0
            for j = 1 to n
                q = ∞
                for i = 1 to j
                    q = min( q, p[i] + r[j-i] )
                r[j] = q
            return r[n]

This isn’t completely right yet, but it has a lot of the right ideas behind it:
- n is the crucial parameter, and indicates which gas station you’re trying to reach; the return value of tripPlanning will be the minimum cost of a trip to that gas station
- Array r is indexed by gas station, r[j] contains the minimum cost of a trip to gas station j
- The for i loop is stepping through gas stations you could arrive at station j from
Mini-assignment: given the above ideas, work out the right expression to go inside the min operation in tripPlanning

Hand out dynamic programming problem set

Due date changed to Monday, March 4

Finish the trip planning problem

Time permitting, look at a more sophisticated dynamic programming application, “matrix chain multiplication”

Section 15.2

Next Lecture