Description

CSE321 – Introduction to Algorithm Design
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.
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.
Notes
2. No collaboration is allowed, the homework must be done individually.
3. The homework will be submitted in ZIP format. The file hierarchy willbe like:
CSE321 HW5 [StudentID].zip
| → CSE321 HW5 report [StudentID].pdf
| → cluster [StudentID].py
| → candy [StudentID].py
| → cheese [StudentID].py
| → courses [StudentID].py
2