Given an array A of predicted prices for bitcoin, you are asked to buy bitcoin a
ID: 3743930 • Letter: G
Question
Given an array A of predicted prices for bitcoin, you are asked to buy bitcoin at some time i and sell it at a future time j > i, such that both A[j] > A[i] and the corresponding profit of A[j] A[i] is as large as possible.
For example, let A = [7,6,1,11,10,13,8,20,19,9,10]. If you buy bitcoin at time i = 2 with A[i] = 1 and sell at time j = 7 with A[j] = 20, you make the maximum profit of 20 1 = 19 megabucks.
(a) Consider the pseudocode below that takes as input an array A of size n:
1
CSCI 3104, Algorithms Chen, Hoenigman Assignment 1 - Due Sept. 7 by 5pm Fall 2018, CU-Boulder
Use one or two sentences to explain under what circumstances the algorithm will return a profit of 0.
(b) The algorithm makeMaxProfit is not efficient. You can compute the maximum profit more efficiently by keeping track of the following when scanning from A[0] to A[i]:
TheminimumpricesofarMinPSoFar=min0ji A[j]. Writepseudocode that finds MinPSoFar recursively.
The “current profit” CurrentProfit = A[i] MinPSoFar if you purchase at the minimum price so far and sell at price A[i].
Write pseudocode that finds the “maximum profit so far” recursively based on CurrentProfit. Here, the maximum profit so far is the maximum profit that can be obtained if you purchase and sell by time i.
(c) Implement the algorithm outlined in (3b) in Python, and run it using an array of 50 prices. Submit the Python code and report the input array and the maximum profit.
Explanation / Answer
a)-->In the following cases the maximum profit will be zero :
i)-->If the array size is one - you cannot sell the stock
ii)--> If the bitcoin price for each day is at less than or equal to its price in the previous day. Example - A = [20, 17, 13, 13, 11, 10, 5, 3, 3, 3, 1]. In this case there is no profitable way to buy at a lower price and sell at a higher price. So, the algorithm will return the default price, which is 0.
b)-->Pseudocode:
maxProfit = 0
Index = 1
maxDay = len(A) ##The last day till which you want to consider
maxProfitSoFar(A, maxProf, index, maxDay){
if(index + 1 ==maxDay){
return maxProf
}
minPrice = A[index - 1]
currentProf = A[index] - minPriceSoFar(minPrice, index - 1)
if (currentProf > maxProf){
maxProf = currentProf
}
return maxProfitSoFar(A, maxProf, index + 1, maxDay)
}
minPriceSoFar(minPrice, index){
if index == 0{
return minPrice
}
prevIndex = index - 1
if minPrice > A[prevIndex]{
minPrice = A[prevIndex]
}
return minPriceSoFar(minPrice, prevIndex)
}
c)-->I am providing 2 different solutions:
i)-->The first program is according to the question number 3b. Both maxProfitSoFar and minPriceSoFar are implemented recursively :
A = [34, 11, 95, 95, 98, 49, 45, 38, 89, 16, 28, 29, 13, 48, 85, 37, 37, 96, 25, 53, 26, 84, 30, 81, 46, 54, 79, 35, 71, 99, 42, 19, 11, 72, 43, 58, 36, 95, 29, 96, 45, 93, 27, 10, 91, 17, 11, 13, 1, 47]
maxProfit = 0
maxDay = len(A)
def maxProfitSoFar(A, maxProf, index, maxDay):
if index + 1 == maxDay:
return maxProf
minPrice = A[index - 1]
currentProf = A[index] - minPriceSoFar(minPrice, index - 1)
if currentProf > maxProf:
maxProf = currentProf
return maxProfitSoFar(A, maxProf, index + 1, maxDay)
def minPriceSoFar(minPrice, index):
if index == 0:
return minPrice
prevIndex = index - 1
if minPrice > A[prevIndex]:
minPrice = A[prevIndex]
return minPriceSoFar(minPrice, prevIndex)
print(maxProfitSoFar(A, maxProfit, 1, maxDay))
Answer = 88
ii)-->The second program only computes maxProfitSoFar recursively. It keeps track of minPriceSoFar non-recursively. The reason for providing this solution is that recursion increases time complexity of a program. This program will be much faster for larger inputs :
A = [34, 11, 95, 95, 98, 49, 45, 38, 89, 16, 28, 29, 13, 48, 85, 37, 37, 96, 25, 53, 26, 84, 30,
81, 46, 54, 79, 35, 71, 99, 42, 19, 11, 72, 43, 58, 36, 95, 29, 96, 45, 93, 27, 10, 91, 17, 11, 13, 1, 47]
maxProfit = 0
minPrice = A[0]
maxDay = len(A)
def maxProfitSoFar2(A, maxProf, minPriceSoFar, index, maxDay):
if index + 1 == maxDay:
return maxProf
if minPriceSoFar > A[index - 1]:
minPriceSoFar = A[index - 1]
currentProf = A[index] - minPriceSoFar
if currentProf > maxProf:
maxProf = currentProf
return maxProfitSoFar2(A, maxProf, minPriceSoFar, index + 1, maxDay)
print(maxProfitSoFar2(A, maxProfit, minPrice, 1, maxDay))
Answer = 88
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.