Algorithm Design Homework 5 Solution

For each dynamic programming question below, write the corre-sponding 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 man-agement 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 maxi-mum 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 ob-tainable 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