4. Let x be a positive integer. Prove that gcd (4x + 1, 2x + 1)...

Transcribed Image Text:

4. Let x be a positive integer. Prove that gcd (4x + 1, 2x + 1) = 1. Hint: Use polynomial division to fill in the box: 4x + 1 = (2x+1) +2 Then gcd (4x + 1, 2x + 1) = gcd(2x + 1,2). This is true by the key step of Euclid's algorithm, where you trade off your original pair for the pair consisting of the smaller number and the remainder. Now explain why gcd(2x + 1,2) = 1. Remember that 2x + 1 is always an odd number. Why? Question 2: (9 Marks) A broker is trading his money in the stock market. Assume that the daily price of a specific stock along a certain period of time is given as follows: Price [200, 500, 800, 100, 300, 50] all in $. This means that the price of the stock is $200 in the first day, $500 in the second day, and so on. You are allowed to buy and sell the stock only once, which means that if you buy it on the 1st day (i.e. $200) and then sell it on the 3rd day (i.e. $800) a profit of $600 will be gained. You are requested to develop an algorithm to maximize the profit in single buy and sell. Another example: int 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$ Answer the following questions: Short Term Exit Long Term Buy a) Design a brute force algorithm (pseudocode) to solve the above problem (1 mark), and determine its complexity (1 marks). b) Design an efficient algorithm (pseudocode) to solve the above problem (2 marks), and determine its complexity (1 marks). c) develop a brief report to explain the difference between the two algorithms and explain why one of them is more efficient than the other. (2 marks) d) Implement the efficient algorithm using Python (2 marks) 4. Let x be a positive integer. Prove that gcd (4x + 1, 2x + 1) = 1. Hint: Use polynomial division to fill in the box: 4x + 1 = (2x+1) +2 Then gcd (4x + 1, 2x + 1) = gcd(2x + 1,2). This is true by the key step of Euclid's algorithm, where you trade off your original pair for the pair consisting of the smaller number and the remainder. Now explain why gcd(2x + 1,2) = 1. Remember that 2x + 1 is always an odd number. Why? Question 2: (9 Marks) A broker is trading his money in the stock market. Assume that the daily price of a specific stock along a certain period of time is given as follows: Price [200, 500, 800, 100, 300, 50] all in $. This means that the price of the stock is $200 in the first day, $500 in the second day, and so on. You are allowed to buy and sell the stock only once, which means that if you buy it on the 1st day (i.e. $200) and then sell it on the 3rd day (i.e. $800) a profit of $600 will be gained. You are requested to develop an algorithm to maximize the profit in single buy and sell. Another example: int 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$ Answer the following questions: Short Term Exit Long Term Buy a) Design a brute force algorithm (pseudocode) to solve the above problem (1 mark), and determine its complexity (1 marks). b) Design an efficient algorithm (pseudocode) to solve the above problem (2 marks), and determine its complexity (1 marks). c) develop a brief report to explain the difference between the two algorithms and explain why one of them is more efficient than the other. (2 marks) d) Implement the efficient algorithm using Python (2 marks)