CSE321-Homework 5 Solved

1.   Profit rates of many companies have changed due to the pandemic. XYZis 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 ncm. 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. Thereexist 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. Inorder 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.