CSE321-Homework 5 Solved

Suppose that you are running a lightweight consulting business - just you, two associates, and some rented equipment. Your clients are distributed between the East Coast and the West Coast of USA, and this leads to the following question. Each month, you can either run your business from an office in New York (NY) or from an office in San Francisco (SF). In month i, you will incur an operating cost of Ni if you run the business out of NY; you will incur an operating cost of Si if you run the business out of SF. (It depends on the distribution of client demands for that month.) However, if you run the business out of one city in month i, and then out of the other city in month i + 1, then you will incur a fixed moving cost of M to switch base offices.  

Given a sequence of n months, a plan is a sequence of n locations - each one equal to either NY or SF - such that the ith location indicates the city in which you will be based in the ith month. The cost of a plan is the sum of the operating costs for each of the n months, plus a moving cost of M for each time you switch cities. The plan can begin in either city. 

The problem: Given a value for the moving cost M and sequences of operating costs N1 ..... Nn and S1 ..... Sn, find a plan of minimum cost. (Such a plan will be called optimal.) 

For example, suppose that n=4, M=10 and the operating costs are given by the following table:

 

# 
Month 1 
Month 2 
Month 3 
Month 4 
NY 
1 
3 
20 
30 
SF 
50 
20 
2 
4 
 

Then the plan of minimum cost would be the sequence of locations:

[NY, NY, SF, SF]
with a total cost of 1 + 3 + 2 + 4 + 10 = 20, where the final term of 10 arises because you change locations once.

 

Design a dynamic programming algorithm that takes values for n, M, and sequences of operating costs N1 ..... Nn and Sl .....Sn, and returns the cost of an optimal plan. Implement your algorithm and analyze its worst-case running time. Explain your algorithm in your report file.  2-) Suppose that you attend a symposium which has many simultaneous sessions. The lengths of the sessions are not fixed and they begin at various times. As a curious student, you want to join as much sessions as possible. Design a greedy algorithm that finds the optimal list of sessions with the maximum number of sessions. Remember that you can be at only one session at the same time and you cannot leave any session before it is over. Implement your algorithm and analyze its worst-case running time. Explain your algorithm in your report file.  

3-) You are given a set of integers S = [-1, 6, 4, 2, 3, -7, -5]. Design a dynamic programming algorithm to check whether there is a subset with the total sum of elements equal to zero. If the algorithm finds such a subset, then print the elements of that subset and terminate the algorithm. Implement your algorithm and analyze its worst-case running time. Explain your algorithm in your report file.   

4-) Design a dynamic programming algorithm to find an alignment between two strings with minimum cost. The cost of the alignment is calculated using the following equation:

𝐶𝑜𝑠𝑡 = 𝑁 ∗ 𝑚𝑎𝑡𝑐ℎ_𝑠𝑐𝑜𝑟𝑒 + 𝑀 ∗ 𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ_𝑠𝑐𝑜𝑟𝑒 + 𝐾 ∗ 𝑔𝑎𝑝_𝑠𝑐𝑜𝑟𝑒

The match, mismatch and gap scores in the equation are the weights for the matching, mismatching and indent operations, respectively.  N, M and K are the count of matches, mismatches and gaps in the alignment, respectively. For example;

 

𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝐴 = 𝐴𝐿𝐼𝐺𝑁𝑀𝐸𝑁𝑇, 𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝐵 = 𝑆𝐿𝐼𝑀𝐸

 

                     𝑚𝑎𝑡𝑐ℎ_𝑠𝑐𝑜𝑟𝑒 = 2,            𝑚𝑖𝑠𝑡𝑚𝑎𝑡𝑐ℎ_𝑠𝑐𝑜𝑟𝑒 = −2,           𝑔𝑎𝑝_𝑠𝑐𝑜𝑟𝑒 = −1  

 

𝐴 𝐿 𝐼 𝐺 𝑁 𝑀 𝐸 𝑁 𝑇 

                                        𝐴𝑙𝑖𝑔𝑛𝑚𝑒𝑛𝑡 𝑜𝑓 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝐴 𝑎𝑛𝑑 𝐵: { | | | | |       |    |           

𝑆 𝐿 𝐼 − − 𝑀 𝐸

 

𝐶𝑜𝑠𝑡 = (4 ∗ (+2)) + (1 ∗ −2) + (2 ∗ −1) = 4

Implement your algorithm and analyze its worst-case running time. Explain your algorithm in your report file.   

5-) Suppose that you have an ancient computer system that needs to do 𝐴 + 𝐵 operation to add numbers 𝐴 𝑎𝑛𝑑 𝐵.  For example, the computer does 13 operation to add 5 and 8. You are given an array of integers to calculate the sum of its elements. Design a greedy algorithm to calculate the sum of the array with the minimum number of operations. Implement your algorithm and analyze its worst-case running time. Explain your algorithm in your report file.