In the previous programming assignment you priced European- and American-Options using a memoized-Trinomial Models. You would have clearly seen the bene ts, in terms of computation-time, of memoization. In this programming exercise, you are going to explore if memoization has similar bene ts when it comes to pricing European-Options using Linear-Programs (LPs).
Section 8 of Lesson 6 of my notes contains the necessary theoretical back-ground for pricing European Options using LPs. I want you to take the C++ code European Option Pricing via LPs.cpp on Compass, which prices an European-Option using LPs, and modify it to include memoization.
More speci cally, in the un-memoized version of the code in European Op-
tion Pricing via LPs.cpp on Compass, we are being very ine cient by adding
the same set of self- nancing-constraints when we repeatedly visit the same
Binomial Lattice State (k; i) many times in course of the recursive functions cre-
ate LP for european put option(int k, int i) and create LP for european call option(int
k, int i). In the memoized-version, which you are going to write as a part of
this assignment, you will do the needful to ensure the constraints are not un-
necessarily repeated when a state (k; i) has been visited earlier.
I want you to compare the running times of your (memoized) code against European Option Pricing via LPs.cpp on Compass. From the programming as-signment on Repeated-Squaring, you know how to measure the time it takes to compute the price of the options (i.e. you have to insert the appropriate code to do this).
The code you write will produce an output that looks like what is shown in gure 1, I have intentionally blanked-out the runtime information to make you think about what you are getting in your experiments. To keep the running-times reasonable, I suggest you try Number of Divisions to be in the set f10; ; 15g. Do you see any bene ts to memoization here? Explain your results (i.e. provide a justi cation for whatever you observe in course of your experiments).
What I need from you:
1. Upload the C++ code on Compass, and
2. Upload a short explanation for what you see in your experiments.
1
Figure 1: Comparing the Runtimes with-and-without memoization for an algo-rithm that prices European-Options using Linear Programs.
2
