There are n trading posts numbered 1 to n, as you travel downstream. At any trading...

Transcribed Image Text:

There are n trading posts numbered 1 to n, as you travel downstream. At any trading post i, you can rent a canoe to be returned at any of the downstream trading posts j> i. You are given a cost array R(i, j) giving the cost of these rentals for 1i j n. We will have to assume that R(i,i) = 0 and R(i, j) = if i > j. For example, with n = 4, the cost array may look as follows: The rows are the sources (i-s) and the columns are the destinations (j's). 1 2 1 2 3 4 20 0 2 3 7 2 4 234 4 02 0 The problem is to find a solution that computes the cheapest sequence of rentals taking you from post 1 all the way down to post n. In this example, the cheapest sequence is to rent from post 1 to post 3 (cost 3), then from post 3 to post 4 (cost 2), with a total cost of 5 (less than the direct rental from post 1 to post 7, which would cost 7). 3 YOUR TASKS 3.1 BRUTE FORCE (4 points): Design a brute force solution to solve this problem. You need to print the cheapest solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.2 DIVIDE AND CONQUER (7 points): Express the problem with a purely divide-and-conquer approach. Implement a recursive algorithm for the problem. Be sure to consider all sub-instances needed to compute a solution to the full input instance in the self-reduction, especially if it contains overlaps. As before, you need to print the solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.3 DYNAMIC PROGRAMMING (7 points): Design a dynamic programming table for this problem. How is the table initial- ized? In what order will the table be filled? How would you use the table to find the cheapest sequence of canoe rentals from post 1 to post n? Implement the corresponding dynamic programming solution. Question 3: (20 marks) A person is trading his money in the stock exchange market. Assume that the daily price of a specific market along a certain period of time is given as follows: Price [200, 500, 800, 100, 300, 50] all in Dollar. This means that the price of the stock in the first day is 200$ and the day after which is mean the second day the price is going up to be $500 and so on until the end of the week or the list you are given. You are allowed to buy and sell the stock only once, which means that if you buy it on the first day then you will pay 200$ then if you decided to sell it on the third day then you will get $800 the your profit will be $600. Another example: prices (300, 450, 720, 90, 30, 50, 900, 500, 70% Output: Buying date: day 5, at the price of $30 selling date: day 7, at the price of $900 Maximum Profit: $870 1. You are requested to develop an algorithm to maximize the profit in single buy and sell. 2. Build your algorithm by using OUBUILD 3. Provide two screenshots with different outputs. Proof of correctness: stability Claim. In Gale-Shapley matching M*, there are no unstable pairs. Pf. Suppose that M* does not contain the pair h-s. Case 1: h never proposed to s. h prefers its Gale-Shapley partners' to s. h-s is not unstable, pair Case 2: h proposed to s. - hospitals propose in decreasing order of preference =>> s rejected h (right away or later) =>>> s prefers Gale-Shapley partner h' to h. h-s is not unstable pair students only trade up h-s' h'-s In either case, the pair h-s is not unstable. Gale-Shapley matching M* 12 There are n trading posts numbered 1 to n, as you travel downstream. At any trading post i, you can rent a canoe to be returned at any of the downstream trading posts j> i. You are given a cost array R(i, j) giving the cost of these rentals for 1i j n. We will have to assume that R(i,i) = 0 and R(i, j) = if i > j. For example, with n = 4, the cost array may look as follows: The rows are the sources (i-s) and the columns are the destinations (j's). 1 2 1 2 3 4 20 0 2 3 7 2 4 234 4 02 0 The problem is to find a solution that computes the cheapest sequence of rentals taking you from post 1 all the way down to post n. In this example, the cheapest sequence is to rent from post 1 to post 3 (cost 3), then from post 3 to post 4 (cost 2), with a total cost of 5 (less than the direct rental from post 1 to post 7, which would cost 7). 3 YOUR TASKS 3.1 BRUTE FORCE (4 points): Design a brute force solution to solve this problem. You need to print the cheapest solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.2 DIVIDE AND CONQUER (7 points): Express the problem with a purely divide-and-conquer approach. Implement a recursive algorithm for the problem. Be sure to consider all sub-instances needed to compute a solution to the full input instance in the self-reduction, especially if it contains overlaps. As before, you need to print the solution, as well as the sequence. What is the asymptotic complexity of this algorithm? 3.3 DYNAMIC PROGRAMMING (7 points): Design a dynamic programming table for this problem. How is the table initial- ized? In what order will the table be filled? How would you use the table to find the cheapest sequence of canoe rentals from post 1 to post n? Implement the corresponding dynamic programming solution. Question 3: (20 marks) A person is trading his money in the stock exchange market. Assume that the daily price of a specific market along a certain period of time is given as follows: Price [200, 500, 800, 100, 300, 50] all in Dollar. This means that the price of the stock in the first day is 200$ and the day after which is mean the second day the price is going up to be $500 and so on until the end of the week or the list you are given. You are allowed to buy and sell the stock only once, which means that if you buy it on the first day then you will pay 200$ then if you decided to sell it on the third day then you will get $800 the your profit will be $600. Another example: prices (300, 450, 720, 90, 30, 50, 900, 500, 70% Output: Buying date: day 5, at the price of $30 selling date: day 7, at the price of $900 Maximum Profit: $870 1. You are requested to develop an algorithm to maximize the profit in single buy and sell. 2. Build your algorithm by using OUBUILD 3. Provide two screenshots with different outputs. Proof of correctness: stability Claim. In Gale-Shapley matching M*, there are no unstable pairs. Pf. Suppose that M* does not contain the pair h-s. Case 1: h never proposed to s. h prefers its Gale-Shapley partners' to s. h-s is not unstable, pair Case 2: h proposed to s. - hospitals propose in decreasing order of preference =>> s rejected h (right away or later) =>>> s prefers Gale-Shapley partner h' to h. h-s is not unstable pair students only trade up h-s' h'-s In either case, the pair h-s is not unstable. Gale-Shapley matching M* 12

Answer rating: 100% (QA)

Here are the solutions to the questions 1 Brute Force Algorithm 4 points Pseudocode bruteForceR n mi... View the full answer