Merge sort on linked list

How to apply Merge Sort to linked list?

• for more about Merge Sort, please refer to Merge Sort.
• Merge Sort works better on linked list than it does on arrays, in the sense of constant auxiliary space complexity.

A simple implementation in C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
public:
    // merge sort linked list
    ListNode* sortlist(ListNode* head){
        if(head != NULL)
            return mergeSort(head);
        return head;   
    }

    ListNode* mergeSort(ListNode* node){
        if(node->next != NULL){
            ListNode* firstHalf = node;
            ListNode* secondHalf = mergeSplit(node);
            firstHalf = mergeSort(firstHalf);
            secondHalf = mergeSort(secondHalf);
            ListNode* result = sortedMerge(firstHalf, secondHalf);
            return result;
        }
        return node;
    }

    // find the first&second half of the list
    ListNode* mergeSplit(ListNode* node){
        ListNode* secondHalf;
        ListNode* stepOne = node;
        ListNode* stepTwo = node->next;
        while(stepTwo != NULL && stepTwo->next != NULL){
            stepTwo = stepTwo->next;
            stepTwo = stepTwo->next;
            stepOne = stepOne->next;           
        }  
        secondHalf = stepOne->next;
        stepOne->next = NULL;
        return secondHalf;
    }

    // merge the sorted list
    ListNode* sortedMerge(ListNode* firstHalf, ListNode* secondHalf){
        //step1 - swap the new header
        //step2 - link the list
        ListNode* tmpf = firstHalf;
        ListNode* tmps = secondHalf;
        ListNode* tmp = new ListNode(99);
        ListNode* tmpHead = tmp;
        while(tmpf != NULL && tmps!= NULL){
            if(tmpf->val <= tmps->val){
                tmp->next = tmpf;
                tmp = tmp->next;
                tmpf = tmpf->next;
            }
            else{
                tmp->next = tmps;
                tmp = tmp->next;
                tmps = tmps->next;
            }
        }
        if(tmpf == NULL)
            tmp->next = tmps;
        if(tmps == NULL)
            tmp->next = tmpf;          
        return tmpHead->next;
    }
};

Monte Carlo method

What is Monte-Carlo simulation? How to use it to compute PI?

• Monte Carlo method is an algorithm which use random sampling to achieve some numerical results.
• Basic steps for Monte Carlo(from wiki):
1. Define a domain of possible inputs.
2. Generate inputs randomly from a probability distribution over the domain.
3. Perform a deterministic computation on the inputs.
4. Aggregate the results.     

Next is a simple example using Monte-Carlo to compute PI:

1. Draw a square with width 1,  a circle with radius 1.
2. Generate uniformly distributed random variables(x,y), red points represent points inside the circle, while blue color represents points outside.
3. Count the number of points inside the circle.
4. Divide the number of inside points by the total number of points, then multiplied by 4 gives the estimation of PI.

A simple example in matlab:

---

% Compute PI using Monte Carlo
% Copyright (c) Eric, CrazyQuant Fri Mar 15 14:10:12 SGT 2013
% Keywords: Monte Carlo

clear all;
close all;

numberOfTests = 20000;
numberInside = 0;
numberOutside = 0;

x = 0:0.01:1;
y = sqrt(1 - x.^2);
plot(x,y,'g');
hold on;

for number = 1 : numberOfTests
    x = rand();
    y = rand(); 
    if(x^2 + y^2 < 1)
        numberInside++;
        inside_x(numberInside) = x;
        inside_y(numberInside) = y;
    else
        numberOutside++;
        outside_x(numberOutside) = x;
        outside_y(numberOutside) = y;
    endif
end

plot(inside_x,inside_y,'ro');
plot(outside_x,outside_y,'bo');

PI = numberInside / numberOfTests * 4

---

Total points: 1000, PI = 3.1600

Total points: 5000, PI = 3.1552

Total points: 10000, PI = 3.1380

Total points: 20000, PI = 3.1366

Total points: 30000, PI = 3.1487

Volatility smile

Volatility smile

In finance, the volatility smile is the pattern in which in-the-money and out-of-the-money options are observed to have higher implied volatilities than at-the-money options. In the following, I will simulate a series of implied volatility using excel macros.

Implied volatility

Implied volatility of an option contract is the value of volatility of the underlying which is calculated from the pricing model after taking the observed market price as the input. Here the famous Black-Scholes formula will be used, and for simplicity vanilla Eur Call option is considered.

$$C(S,t) = N(d_1)S - N(d_2)Ke^{-r(T-t)}$$ with
$$d_1 = \frac{ln(\frac{S}{K})+(r+\frac{\sigma^2}{2})(T-t)}{\sigma\sqrt{T-t}}$$ $$d_2 = \frac{ln(\frac{S}{K})+(r-\frac{\sigma^2}{2})(T-t)}{\sigma\sqrt{T-t}}$$ then the problem becomes how to work out sigma from the above equation by taking the option's market price as input and Newton's method is used as follows:
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ which indicates that we need to calculate:
$$vega = \frac{\partial C}{\partial \sigma} = S\sqrt{T- t}N'(d1)$$ the iteration formula will be:
$$\sigma_{n+1} = \sigma_n - \frac{C(\sigma_n)}{vega(\sigma_n)}$$
a simple implementation in Excel macros:

Function impvol(MarketPrice As Double, StockPrice As Double, Strike As Double, 

                Interest As Double, Expiry As Double) As Double

Dim error As Double
Dim volatility As Double
Dim d1 As Double, d2 As Double
Dim vega As Double
Dim PI As Double
Dim dv As Double
Dim priceerror As Double

PI = 3.1415926
error = 0.001
volatility = 0.6
dv = 1

Do While Abs(dv) > error
d1 = Log(StockPrice / Strike) + (Interest + 0.5 * volatility ^ 2) * Expiry
d1 = d1 / (volatility * Sqr(Expiry))
d2 = d1 - volatility * Sqr(Expiry)
vega = StockPrice * Sqr(Expiry / 2 / PI) * Exp(-0.5 * d1 * d1)
priceerror = StockPrice * cdf(d1) - Strike * Exp(-Interest * Expiry) * cdf(d2) 

             - MarketPrice
dv = priceerror / vega
volatility = volatility - dv
Loop

impvol = volatility

End Function


Function cdf(x As Double) As Double

Dim a1, a2, a3, a4, a5 As Double
Dim d As Double
Dim dd As Double
Dim result As Double

a1 = 0.31938153
a2 = -0.356563782
a3 = 1.781477937
a4 = -1.821255978
a5 = 1.330274429

If x >= 0 Then
    d = 1 / (1 + 0.2316419 * x)
    dd = a1 * d + a2 * d ^ 2 + a3 * d ^ 3 + a4 * d ^ 4 + a5 * d ^ 5
    result = 1 - 1 / Sqr(2 * 3.1415926) * Exp(-0.5 * x ^ 2) * dd
    cdf = result
Else
    d = 1 / (1 + 0.2316419 * (-x))
    dd = a1 * d + a2 * d ^ 2 + a3 * d ^ 3 + a4 * d ^ 4 + a5 * d ^ 5
    result = 1 - 1 / Sqr(2 * 3.1415926) * Exp(-0.5 * x ^ 2) * dd
    cdf = 1 - result
End If

End Function

outcome: