Description
For each dynamic programming question below, write the corresponding recurrence relation, and how you obtained it. Explain the
algorithm you propose, and analyze its complexity.
1. Profit rates of many companies have changed due to the pandemic. XYZ
is a retail company with many branches on the Marmaray line. The management of the company is trying to identify the regions where they make
the most profit. For this purpose, they gather the profit-loss rates of their
retail shops to the table. Entries on the table are sorted in Marmaray
station order.
A B C D E F G
3 -5 2 11 -8 9 -5
(a) Design a dynamic programming algorithm that finds the maximum profit belonging to the most profitable cluster (the cluster
must contain a consecutive region). For example, the maximum profit
is 14 (C-D-E-F) on the table above.
(b) This question was asked in one of your homework before. Compare
the algorithm with the algorithms you previously proposed in terms
of complexity. Explain your arguments.
2. There is a candy shop, and candies are produced as a stick of length n cm.
They can cut and sell candies in different lengths, and there is a price list
that shows prices of all pieces of size smaller than n. For example, if the
length of the candy is 8 cm and the values of different pieces are given as
in the following, then the maximum obtainable value is 22 (by cutting in
two pieces of lengths 2 and 6)
length 1 2 3 4 5 6 7 8
price 1 5 8 9 10 17 17 20
Design a dynamic programming algorithm that finds the maximum obtainable value.
1
For each problem below, propose a greedy algorithm and describe
it in detail. Analyze the complexity of the algorithm.
3. There is a store where dairy products like milk and cheese are sold. There
exist n different types of cheese in the store, and each cheese type has
a price pi and a weight wi
. The owner wants to put a combination of
different cheeses in a box, and sell it. The box has a weight capacity W,
and you are allowed to cut cheeses and put any portion of it in the box
to maximize the total price without exceeding the box weight capacity.
Design a greedy algorithm that finds the maximum price you can get.
4. A group of gifted students will be prepared for an intelligence contest. In
order to prepare them, a program has been designed where each student
can take courses among n courses, and the start and end times of the
courses are given. A table is given below as an example.
Course Start Finish
English 1 2
Mathematics 3 4
Physics 0 6
Chemistry 5 7
Biology 8 9
Geography 5 9
A student can attend at most 4 of the above courses . The maximum
set of courses that can be attended is {English, Mathematics, Chemistry,
Geography}. Design a greedy algorithm to find the maximum number of
courses a student can attend among n courses.
Notes
1. Late submissions will not be accepted.
2. No collaboration is allowed, the homework must be done individually.
3. The homework will be submitted in ZIP format. The file hierarchy will
be like:
CSE321 HW5 [StudentID].zip
| → CSE321 HW5 report [StudentID].pdf
| → cluster [StudentID].py
| → candy [StudentID].py
| → cheese [StudentID].py
| → courses [StudentID].py
2
