Solved–Assignment 2 –Solution

Description

For every problem, give a Dynamic Programming solution, following the steps outlined in class. Don’t forget to justify that your recurrence relation is correct based on the recursive structure of the problem, and to analyze the time complexity of your final algorithm.

1. Riding a bicycle in Toronto

Suppose the streets in some section of Toronto are modelled as a simple grid, and you want to travel from the lower-left corner (coordinate (0;0)) to the upper-right corner (coordinate (m; n)). Further, to simplify the problem, suppose that every street is one-way so you can only travel right or up (never left and never down).

But riding a bicycle in Toronto is dangerous! So every street segment has a probability that riding on that segment will result in an accident. Let pi;j be the probability that riding right from coordinate (i 1; j) to (i; j) results in an accident, and qi;j be the probability that riding up from coordinate (i; j 1) to (i; j) results in an accident. As usual, all probabilities are real numbers in the interval [0;1]. The probability that you have no accident on a path is simply the product of the probabilities that you have no accident on each street segment of the path.

Your goal is to find a path from (0;0) to (m; n) with the maximum probability of having no accident.

2. Study group lunch

Suppose you want to buy B burgers, C fries, and D drinks at your favourite fast-food place, for a study group you’re organizing (this question is most certainly not about good eating habits)! The unit price of each item is pb (for burgers), pc (for fries), and pd (for drinks). You also own n coupons N1; : : : ; Nn. Each coupon Ni is a combo that offers you bi burgers, ci fries, and di drinks at price pi . Each coupon can only be used at most once. Note: All values are natural numbers, which means some of them could be equal to zero (e.g., it’s possible for a coupon to offer a deal that includes only drinks and fries, but no burger; it’s also possible for a coupon to offer more burgers, or fries, or drinks than you need).

What is the minimum amount of money you need to pay to get at least B burgers, C fries, and D drinks? It’s okay if you end up with more food (or drinks) than you need.

Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 2
CSC 373 H1 Assignment #2

3. Homework planning

You have n assignments A1; : : : ; An where Ai = (pi ; ti ), pi 2 Z+ is the number of points earned if you complete the assignment, and ti 2 R+ is the time required to complete the assignment. You also have a total time T 2 R+ available to complete all the assignments.

Find a subset of assignments that you can complete within your time limit and that maximizes the total number of points obtained. (Note: you cannot use arbitrary real numbers as array indices.)

Dept. of Computer Science, University of Toronto, St. George Campus page 2 of 2