lgorithm Design Homework 05 Solution

(35 points) There are two unsigned integer lists X and Y with the same number of elements (N). The following relation exists among their ith elements:
≤ ≤




The cost (S) of a list X is defined as:

= ∑ | − − |

=2




Given a list Y, design and implement a dynamic programming algorithm in Python 3 that returns the maximum possible cost of list X.




Explain your algorithm and do worst case analysis as a comment block at the beginning of your implementation file, maximum_cost_StudentID.py




Your code will be tested with many different inputs as follows:




Y = [14,1,14,1,14]

cost = find_maximum_cost(Y)

print(cost)

#Output: 52

Y = [1,9,11,7,3]

cost = find_maximum_cost(Y)

print(cost)

#Output: 28

Y = [50,28,1,1,13,7]

cost = find_maximum_cost(Y)

print(cost)

#Output: 78




(35 points) A large amount of money was given to you and to protect, you split and buried it in a land with n*m cells (dimension is n row m column). Each cell in the land contains a positive integer which is the number of Turkish liras buried. A thief has learned your secret and going to steal maximum amount of money before the cops arrive. Initially the thief is at first column but can be at any row. He can move only 1 cell right, right-up or right-down from a given cell. When the thief arrives a new cell, he steals the money. Design and implement a dynamic programming algorithm in Python 3 to find out maximum amount of money he can steal when he reaches to the end (last column). Explain your algorithm and do worst case analysis as a comment block at the beginning of your implementation file, theft_StudentID.py. Your code will be tested with many different inputs as follows:

amountOfMoneyInLand= [[1,3,1,5], [2,2,4,1], [5,0,2,3], [0,6,1,2]] res = theft(amountOfMoneyInLand)




print(res)




#Output: 16




amountOfMoneyInLand= [[10,33,13,15], [22,21,4,1], [5,0,2,3], [0,6,14,2]] res = theft(amountOfMoneyInLand)




print(res)




#Output: 83







(30 points) A Decent Number having N digits has the following properties:

Its digits can only be 3's and/or 5's.
The number of 3's it contains is divisible by 5.
The number of 5's it contains is divisible by 3.
If there is more than one such number, we pick the largest one.



Design and implement a greedy algorithm to find the decent number having N digits. If there is not any decent number with N digits, return -1. Explain your algorithm and your greedy choice as a comment block at the beginning of your implementation file, decentNumber_StudentID.py. Your code will be tested with many different inputs as follows:




dn = decentNumber(1)




print(dn)




#Output: -1




dn = decentNumber(3)




print(dn)




#Output: 555




dn = decentNumber(5)




print(dn)




#Output: 33333




dn = decentNumber(11)




print(dn)




#Output: 55555533333







IMPORTANT NOTES




Codes will be written using Python 3 (not Python 2). Do not use any additional python libraries. You can only use sys library (import sys).



Do not use any global variables. Do not design brute force algorithms.



Homework’s will be submitted in ZIP format. There is no pdf in this homework. The file hierarchy will be this: CSE321_HW5_StudentID.zip



| maximum_cost_StudentID.py | theft_StudentID.py




| decentNumber_StudentID.py




Use homework question forum on Moodle if you have any questions about homework.



Cheating will be punished. Taking any code from internet is also forbidden. (Grade will be -100)



No late submissions.



This is the last homework, good luck!