Tuesday, June 29, 2010

Bubble sort -c++


It works by repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and swapping
them if they are in the wrong order. The pass through the list is
repeated until no swaps are needed, which indicates that the list is
sorted. 


Worst case performance O(n2)
Best case performance O(n)
 
-------------------------------------------------------------
#include <stdio.h>
#include <iostream>

using namespace std;

void bubbleSort(int *array,int length)//Bubble sort function


{
int i,j;
for(i=0;i<10;i++)
{

for(j=0;j<i;j++)
{
if(array[i]>array[j])
{

int temp=array[i]; //swap
                                array[i]=array[j];

array[j]=temp;
}

}

}

}

void printElements(int *array,int length) //print array elements

{
int i=0;
for(i=0;i<10;i++)

cout<<array[i]<<endl;
}


int main()
{

int a[]={9,6,5,23,2,6,2,7,1,8};   // array to sort

    bubbleSort(a,10);                 //call to bubble sort 
        printElements(a,10);               // print elements

  return(0);
}

linked list -C++

 A linked list is a data structure that consists of a 
sequence of data records such that in each record there 
is a field that contains a reference (i.e., a link) to 


the next record in the sequence. 
----------------------------------------------------
#include <iostream>
using namespace std;

struct node
{  char name[20];    // Name of up to 20 letters
     int age;          // D.O.B. would be better

     float height;     // In metres
     node *nxt;// Pointer to next node
  };


node *start_ptr = NULL;
node *current;           // Used to move along the list

int option = 0;

void add_node_at_end()
{  node *temp, *temp2;   // Temporary pointers

// Reserve space for new node and fill it with data

     temp = new node;
cout << "Please enter the name of the person: ";

cin >> temp->name;
cout << "Please enter the age of the person : ";
cin >> temp->age;

cout << "Please enter the height of the person : ";
cin >> temp->height;
temp->nxt = NULL;


// Set up link to this node
     if (start_ptr == NULL)
{ start_ptr = temp;

current = start_ptr;
} 
else
{ temp2 = start_ptr;

// We know this is not NULL - list not empty!
         while (temp2->nxt != NULL)
{  temp2 = temp2->nxt;

// Move to next link in chain
           }
temp2->nxt = temp;
}
}

void display_list()
{  node *temp;

temp = start_ptr;
cout << endl;
if (temp == NULL)

cout << "The list is empty!" << endl;
else
{ while (temp != NULL)
{  // Display details for what temp points to

              cout << "Name : " << temp->name << " ";
cout << "Age : " << temp->age << " ";

cout << "Height : " << temp->height;
if (temp == current)

cout << " <-- Current node";
cout << endl;
temp = temp->nxt;

}

cout << "End of list!" << endl;
}
}


void delete_start_node()
{ node *temp;

temp = start_ptr;
start_ptr = start_ptr->nxt;

delete temp;
}

void delete_end_node()
{ node *temp1, *temp2;

if (start_ptr == NULL)
cout << "The list is empty!" << endl;

else
{ temp1 = start_ptr;
if (temp1->nxt == NULL)
{ delete temp1;

start_ptr = NULL;
}
else
{ while (temp1->nxt != NULL)
{ temp2 = temp1;

temp1 = temp1->nxt;
}
delete temp1;
temp2->nxt = NULL;
}
}
}

void move_current_on ()
{ if (current->nxt == NULL)

cout << "You are at the end of the list." << endl;
else
current = current->nxt;
}

void move_current_back ()
{ if (current == start_ptr)

cout << "You are at the start of the list" << endl;
else
{ node *previous;     // Declare the pointer

        previous = start_ptr;

while (previous->nxt != current)
{ previous = previous->nxt;
}

current = previous;
}
}


int main()
{  start_ptr = NULL;

do
{
display_list();
cout << endl;

cout << "Please select an option : " << endl;
cout << "0. Exit the program." << endl;

cout << "1. Add a node to the end of the list." << endl;
cout << "2. Delete the start node from the list." << endl;

cout << "3. Delete the end node from the list." << endl;
cout << "4. Move the current pointer on one node." << endl;

cout << "5. Move the current pointer back one node." << endl;
cout << "6. Display the list. " << endl;

cout << endl << " >> ";
cin >> option;

switch (option)
{
case 1 : add_node_at_end(); break;

case 2 : delete_start_node(); break;
case 3 : delete_end_node(); break;

case 4 : move_current_on(); break;
case 5 : move_current_back(); break;

case 6 : display_list();
}
}
while (option != 0);

return(0);
}

quick sort -C++

 
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
  4. Worst case performance O(n2)
    Best case performance O(nlogn)


---------------------------------------------------
#include<iostream>
#define N 10
using namespace std;

class QuickSort
{
private:
int low,high;

double *Plist;
public:
QuickSort(int,int,double *,int);

void qkSort();
int part();
void prnt(int);
~QuickSort();
};

QuickSort::QuickSort(int l, int h,double *list, int ListLong)
{

low = l;
high = h;
Plist = new double[ListLong];

for(int i=0;i<ListLong;i++) Plist[i]=list[i];
}

int QuickSort::part()
{
int i,j;
double p;

i=low; j=high;
p=Plist[low];


while(i<j)
{
while(i<j &&Plist[j]>=p)
{

j--;
}
Plist[i]=Plist[j];
while(i<j &&Plist[i]<=p) i++;

Plist[j]=Plist[i];
}
Plist[i] = p;

return(i);
}
void QuickSort::qkSort()
{
int i;

if(low<high)
{
i =part();
high=i-1;

qkSort();
low = i+1;
qkSort();
}

else
return;
}
void QuickSort::prnt(int N)
{
cout<<"Sort sequence is "<<endl;

for(int i=0;i<N;i++)
cout << Plist[i] <<endl;
}

QuickSort::~QuickSort()
{
delete []Plist;
}

double a[]={3.0,3.7,3.5,2.9,2.7,2.3,3.3,2.5,3.1,3.9};

int main()
{
int m=0, n=N-1;

QuickSort qs(m,n,a,N);
qs.prnt(N);

qs.qkSort();
qs.qkSort();
qs.prnt(N);

return(0);
}

Binary Search-C++

 Compare the target to the middle item in the list. If the target is the
same as the middle item, you've found the target. If it's before the
middle item, repeat this procedure on the items before the middle. If
it's after the middle item, repeat on the items after the middle
 
Worst case performance O(log n)
Best case performance O(1) 
Code: 
#include<iostream>
#include<stdlib.h>

using namespace std;

class BinSearch
{
private:
double *Plist;


public:
BinSearch(double *,int);
void BinSrch(int, int, double);
~BinSearch();
};

BinSearch::BinSearch(double *list, int ListLong)
{
Plist = new double[ListLong];

for(int i=0;i<ListLong;i++) Plist[i]=list[i];
}

BinSearch::~BinSearch()
{
delete []Plist;
}

void BinSearch::BinSrch(int s, int r, double x)
{

int m;
m=(s+r)/2;
if(Plist[m]==x)
{


cout<< "The order of " <<x<<" is "<<m+1<<" in this sequence."<<endl;
return;
}

else if (s>=r)
{
cout<<x<<"does not exist in the sequence"<<endl;
exit(-1);
}

else if (x>Plist[m])
BinSrch(m+1,r,x);

else
BinSrch(s,m-1,x);
}


int main()
{
//a should be in the order of increasing
        double a[]={2.1,2.3,2.5,2.7,2.9,3.1,3.3,3.5,3.7,3.9};

double x=2.3;
int s=0, r=9;

BinSearch bs(a,10);
bs.BinSrch(s,r,x);

return(0);
}

openmp in westgrid

1. Example:
------------------------------------------------------
#include<iostream>
#include<iomanip>

#include<ctime>
using namespace std;

int
main()
{


double
sum=0;

double
w =0;
double
startime,endtime;
startime = clock();

int
nsim =1.234e6;
//#pragma omp parallel for private(w) reduction(+:sum) schedule(static,1)
#pragma omp parallel for

for
(int i = 0; i <=nsim; i++)
{


w = i*i;
sum = sum + w;
}


endtime = clock();
cout<<"sum="<< setprecision(5)<<sum<<endl;

cout<<"time pass "<<(endtime - startime)/CLOCKS_PER_SEC<<"second"<<endl;
return
(0);
}

---------------------------------------
2. Makefile in glacier.westgrid.ca
--------------------------------------
CC = icpc
CFLAGS = -g -O3 -openmp
OBJECTS = *cpp

main.exe : $(OBJECTS)
$(CC) $(CFLAGS) $(OBJECTS) -o main.exe

%.o : %.c
$(CC) $(CFLAGS) -c $<
----------------------------------------------
3. submit to the queue:
-------------------------------------

#!/bin/bash
#PBS -S /bin/bash
#PBS -l nodes=1:ppn=2
#PBS -l mem=2000mb
#PBS -l walltime=120:00:00
#PBS -M jiansen@triumf.ca
# Script for running OpenMP sample program main.exe on 2 processors on glacier


# If this file is "run_main.pbs", submit with "qsub run_main.pbs"

# Check on some basics:

echo "Running on host: " `hostname`
echo "Changing to directory from which PBS script was submitted."
cd $PBS_O_WORKDIR
echo "Current working directory is now: " `pwd`
# Note: The OMP_NUM_THREADS should match the number of processors requested.

echo "Node file: $PBS_NODEFILE :"
echo "---------------------"
cat $PBS_NODEFILE
echo "---------------------"
echo "JOb name: $PBS_JOBNAME"

NUM_PROCS=`/bin/awk 'END {print NR}' $PBS_NODEFILE`
echo "Running on $NUM_PROCS processors."
echo "Starting main.exe at `date`"


main.exe > run-main-pbs.out$PBS_JOBID


echo "main.exe run completed at `date`"

Monday, June 28, 2010

Symbolic calculation in Matlab

1) Solve equations:
example 1
--------------------------------
syms x % define x is symbol
y=x^3-8
Solve(y,x)
----------------------
example 2
-----------------------
syms x y
S = 2*x + 4 - y; %S is the 'dummy'
solve(S, x)
(ans = -2 + 1/2*y)
--------------------------
example 3
-----------------------
syms a b
f(1) = a + b - 3;
f(2) = a + 2*b - 6;
[A,B] = solve(f(1), f(2)) %solve f(1) = 0, f(2)=0
(A = 0 B = 3)

2. Differentiation and integration:
example
--------------------------------------
syms x
f = x^2 - 3*x + 4;
diff(f) % or diff('x^2 - 3*x + 4'), differentiation
(ans =2*x-3)
int(f) %integration
(ans = x^3/3-3*x^2/2)
int(f,0,1) % definite integral
(ans = 17/6)
3. Solve ODE
example 1
----------------------------------
syms x
dsolve('D2x = -x')
(ans = C1*sin(t)+C2*cos(t) )
-----------------------------------
example 2
-----------------------------------
syms x
f=dsolve('D2x = -x', 'Dx(0) = 2', 'x(0) = 4')
(f = 2*sin(t)+4*cos(t))
subs(f, 't', 5) %calculate f(5)
ezplot(f, [-2:0.1:2]) % plot f(t) vs t



curve fit in Matlab

1) Polynomial fit:
in polynomial.m
----------------------------------------
function polynomial
c=[1 2 -1] % for x*x+2*x-1
x=-1:0.1:1
y=polyval(c,x) % y=x*x+2*x-1
noise = rand(1, size(y,2)) %create some noise
newy=y+noise
newc=polyfit(x, newy,2) % get fit parameter
yc=polyval(newc,x)
hold on % plot all plots in 1 figure
plot(x, y, 'b--') % plot original blue --
plot(x, newy, 'r+') %plot new data with noise red ++
plot(x, yc, 'g') % plot fit curve green
legend('original curve','Data','Polynomial Fit','Location','NW')
---------------------------------------------------------
2. Non linear fit, for example Gaussian fit
define gauss.m
-----------------------------
function f=gauss(a,x)
f=a(1)*exp(-(((x-a(2))/a(3))/a(3)).^2)
-------------------------------------------------
then
-----------------------------------------
a=[2 0.5 1] % guess a
a=nlinfit(x,newy,'gauss',a) % find fit parameters for data [x, newy]
plot(x,gauss(a,x),'k') % plot fitted Gaussian curve in black

Saturday, June 26, 2010

random number generator -C++

#include<iostream>
#include<ctime>

#include<cmath>

using namespace std;


class rand_gen{
public:

rand_gen();
double uniform_dist(double a, double b);

double exponential_dist(double lamda);
double powerlaw_dist(double alpha, double lamda);

int binomial_dist(int n, double p);
int poisson_dist(double lambda);

double normal_dist(double sigma, double mu);
};


rand_gen::rand_gen(){

srand(time(NULL));
}
double rand_gen::uniform_dist(double a, double b){

double r=rand()/(RAND_MAX+1.0);
return a+(b-a)*r;
}

/*
To simulate exponential distribution exp(-lambda*x), the inverse
 method is used.
The cumulative distribution function for the exponential
distribution is:1-exp(-lambda*x). The inversion function
is  -log(1-U)/lambda. The simplified form is -log(U)/lambda,
where U is a uniform [0,1] random variable.
 http://cg.scs.carleton.ca/~luc/rnbookindex.html
*/
double rand_gen::exponential_dist(double lambda){
return(-1*log(uniform_dist(0.,1.))/lambda);
}

/*
Simulate power law with cut-off x^(-alpha)*exp(-lambda*x)
To simulate power-law with cutoff , one can generate an
exponentially distributed random number using the formula
above     (as k>0 and integer, so k start at 1)
and then accept or reject it with probability p or 1 - p 
respectively (i.e accept U1 <p or reject U1>p, and
 U1 is a uniform [0,1] random variable),
where p = (x/x_min)^(-alpha)  and  x_min=1.

http://www.santafe.edu/~aaronc/powerlaws/
*/
double rand_gen::powerlaw_dist(double alpha, double lamda)
{

double x;
do{
x = exponential_dist(lamda);
} while (pow(x,-1*alpha) < uniform_dist(0.,1.));

return (x);

}
int rand_gen::binomial_dist(int n, double p){

int m=0;
for( int i=0;i<n;i++){

if(uniform_dist(0.,1.)<p) m++;
}
return m;
}

/*
Poisson distribution
f(n, lambda) = lambda^n exp(-lambda)/n!
Algorithm Poisson random number (Knuth):
init:          Let L =exp(-lambda), k=0 and p =1
do:          k = k+
Generate uniform random number u in [0,1]
and let p =p*u
while p > L.
return k - 1.
*/
int rand_gen::poisson_dist(double lambda){

double L=exp(-1*lambda);


int k;
double p=1.;
k = 0;

do{
k = k + 1;

p = p*uniform_dist(0.,1.);
} while (p > L);

return k - 1;
}
double rand_gen::normal_dist(double sigma, double mu)
{

double V1, V2, S;
double X;

do {
double U1 = uniform_dist(0.,1.);

double U2 = uniform_dist(0.,1.);

V1 = 2 * U1 - 1;

V2 = 2 * U2 - 1;
S = V1 * V1 + V2 * V2;
} while(S >= 1 || S == 0);

X = V1 * sqrt(-2 * log(S) / S);

return sigma*X+mu;
}

int main(){

rand_gen myrand_gen;
cout<<"uniform distribution between 0 and 4"<<endl;
for(int i=1; i<10; i++) {

cout <<myrand_gen.uniform_dist(0.,4.)<<endl;
}
cout<<"exponential distribution exp(-2*x)"<<endl;

for(int i=1; i<10; i++) {

cout <<myrand_gen.exponential_dist(2.)<<endl;
}
cout<<"power law distribution x^-2*exp(-2*x)"<<endl;

for(int i=1; i<10; i++) {

cout <<myrand_gen.powerlaw_dist(2.,2.)<<endl;
}
cout<<"binomial distribution"<<endl;

for(int i=1; i<20; i++) {

//   flip the coin 4 times, count number of heads
         cout <<myrand_gen.binomial_dist(4,0.5)<<endl;
}
cout<<"Poisson distribution"<<endl;

for(int i=1; i<20; i++) {


         cout <<myrand_gen.poisson_dist(4)<<endl;
}
cout<<"Normal distribution"<<endl;

for(int i=1; i<20; i++) {

//   flip the coin 4 times, count number of heads
         cout <<myrand_gen.normal_dist(1.,0.)<<endl;
}
return(0);
}

Friday, June 25, 2010

Solve SIR model -C++/MatLab/Python

1) C++
------------------------------------------------------
/* Solve simple SIR Model
Author: Jiansen Lu
Date: June 25, 2010
Description:
dS/dt = - beta*S*I
dI/dt = beta*S - gamma*I
dR/dt = gamma*I
where S: Susceptibel
I: Infectious
R: Recovered
beta: transmission rate
gamma: recover rate:
set initial condition S(0)=1e-6, I(0)=1.0-S(0)
beta = 1.5, gamma = 0.2
Algorithm: using Runge-Kutta method
dy/dt = f(t,y), y(t_0) = y_0
t_(n+1) = t_n+h
y_(n+1) = y_n + (k_1+2*k_2+2*_k3+k_4)/6
where: k_1=f(t_n,y_n), k_2=f(t_n+h/2,y_n+h*k_1/2)
k_3=f(t_n+h/2,y_n+h*k_2/2), k_4=f(t_n+h,y_n+h*k_3)
*/

#include<iostream>

#include<cmath>

using namespace std;

class SIR{
private:

double t,S,I,R,Pop[3];
double dPop[3],step;

double beta, gamma;
double tmax;
public:


SIR();
SIR(double beta0, double gamma0, double step0, double S00, \
          double I00, double tmax0);
~SIR();

void Diff(double Pop[3]);
void Runge_Kutta();

void Solve_Eq();
};
// Initialise the equations and Runge-Kutta integration
SIR::SIR(double beta0, double gamma0, double step0,double S00, \
       double I00, double tmax0)
{

beta = beta0;
gamma =gamma0;
step = step0;

S =S00;
I = I00;
R = 1 - S - I;

tmax = tmax0;
}
SIR::~SIR(){
cout <<"delete SIR"<<endl;
}

void SIR::Diff(double Pop[3])
{

// The differential equations


dPop[0] = - beta*Pop[0]*Pop[1];              // dS/dt

  dPop[1] = beta*Pop[0]*Pop[1] - gamma*Pop[1];   // dI/dt

  dPop[2] = gamma*Pop[1];                    // dR/dt

}

void SIR::Runge_Kutta(){
int i;
double dPop1[3], dPop2[3], dPop3[3], dPop4[3];

double tmpPop[3], initialPop[3];

/* Integrates the equations one step, using Runge-Kutta 4
Note: we work with arrays rather than variables to make the
coding easier */

initialPop[0]=S; initialPop[1]=I; initialPop[2]=R;

Diff(initialPop);
for(i=0;i<3;i++)
{

dPop1[i]=dPop[i];
tmpPop[i]=initialPop[i]+step*dPop1[i]/2;
}

Diff(tmpPop);
for(i=0;i<3;i++)
{


dPop2[i]=dPop[i];
tmpPop[i]=initialPop[i]+step*dPop2[i]/2;
}

Diff(tmpPop);
for(i=0;i<3;i++)
{

dPop3[i]=dPop[i];
tmpPop[i]=initialPop[i]+step*dPop3[i];
}

Diff(tmpPop);

for(i=0;i<3;i++)
{

dPop4[i]=dPop[i];
tmpPop[i]=initialPop[i]+(dPop1[i]/6 + dPop2[i]/3 + dPop3[i]/3 + dPop4[i]/6)*step;
}


S=tmpPop[0]; I=tmpPop[1]; R=tmpPop[2];


}

void SIR::Solve_Eq(){
t=0;
cout <<"t    S    I       R"<<endl;

do
{
Runge_Kutta();
t+=step;
cout<<t<<"   "<<S<<"   "<<I<<"   "<<R<<"   "<<endl;
}

while(t<tmax);


}
int main(int argc, char** argv)
{

double beta0 = 1.5;
double gamma0 =0.2;

double I00 = 1e-6;
double S00 =1-I00;

double tmax0 = 50;
/* Find a suitable time-scale for outputs */

double step0=0.01/((beta0+gamma0)*S00);

SIR mySIR(beta0, gamma0,step0,S00,  I00,  tmax0);

mySIR.Solve_Eq();
return(0);

}

2) Matlab
in SIR.m
--------------------------------------------------------
function [t,S,I,R] =SIR()
%Solve SIR equation in Matlab

beta=1.5; gamma=0.2; I0=1e-6;
S0=1-I0; tmax=50;
S=S0; I=I0; R=1-S-I;

% The main iteration
[t, pop]=ode45(@Diff_SIR,[0 tmax],[S I R],[],[beta gamma]);

S=pop(:,1); I=pop(:,2); R=pop(:,3);

% plots the graphs with scaled colours
subplot(2,1,1)
h=plot(t,S,'-g',t,R,'-k');
xlabel 'Time';
ylabel 'Susceptibles and Recovereds'

subplot(2,1,2)
h=plot(t,I,'-r');
xlabel 'Time';
ylabel 'Infectious'

% Calculates the differential rates used in the integration.
function dPop=Diff_SIR(t,pop, parameter)
beta=parameter(1); gamma=parameter(2);
S=pop(1); I=pop(2); R=pop(3);
dPop=zeros(3,1);
dPop(1)= -beta*S*I;
dPop(2)= beta*S*I - gamma*I;
dPop(3)= gamma*I;
-------------------------------------------------
3. Python
in SIR.py (chmod  +x SIR.py, ./SIR.py)
------------------------------------------------
#!/usr/bin/env python



import scipy.integrate as spi
import numpy as np
import pylab as pl

beta=1.5
gamma=0.2
TS=1.0
tmax =50
I0=1e-6
S0=1-I0
INPUT = (S0, I0, 0.0)

def diff_eqs(INP,t):
'''The main set of equations'''
Y=np.zeros((3))
V = INP
Y[0] = - beta * V[0] * V[1]
Y[1] = beta * V[0] * V[1] - gamma * V[1]
Y[2] = gamma * V[1]
return Y   # For odeint

t_start = 0.0; t_end = tmax; t_inc = TS
t_range = np.arange(t_start, t_end+t_inc, t_inc)
RES = spi.odeint(diff_eqs,INPUT,t_range)
print RES #Ploting pl.subplot(211) pl.plot(RES[:,0], '-g', label='Susceptibles') pl.plot(RES[:,2], '-k', label='Recovereds') pl.legend(loc=0) pl.title('SIR.py') pl.xlabel('Time') pl.ylabel('Susceptibles and Recovereds') pl.subplot(212) pl.plot(RES[:,1], '-r', label='Infectious') pl.xlabel('Time') pl.ylabel('Infectious') pl.show()

Thursday, June 24, 2010

Using Newton method find root - C++/Matlab

1) C++
--------------------------------------------------------------------------------
/* An example of Newton's method
Author: Jiansen Lu
Created: June, 24, 2010
___________________________________

Purpose: This program estimates the root of the function f(x)


Algorithm:   The improvements to our initial guess x0  are obtained by
repeated  use of the formula:

x_new = x_old - ( f(x_old) / f'(x_old) ).

The initial guess ( x0 ), the maximum number of iterations(nmax),
the root tolerance (xtol), the function value tolerance (ftol)
are all inputed through the keyboard.

The root tolerance is defined as follows:
The iterations will stop if

| x_new - x_old | / | x_old | < xtol.


The function value tolerance is defined as follows:
The iterations will stop if

| f( x_new) | < ftol.

For accuracy all variables will be declared as double.
*/

#include <iostream>
#include <iomanip>
#include <cmath>
 using namespace std;

double fun(double x);
double funprime(double x);

int main()
{
double x_old = 0.6, x_new = 0 ;  //  estimates of the root

 double xtol = 1e-5 , ftol = 1e-5 ;  // tolerances

 double f = 0. , fprime = 0. ;   // values of the function and of its derivative

 int nmax = 1000 ;                  // max number of iterations
 int n = 0 ;                     // running index



// Prepare the heading of the table


cout <<"\n\n    x_old          f(x_old)       f'(x_old)           x_new   \n\n";
cout<< setiosflags(ios:: scientific);

cout<< setprecision(10);

//    START THE LOOP

for( n = 1; n <= nmax ; n++ )
{

f = fun(x_old);
fprime = funprime(x_old);

x_new = x_old - f / fprime ;

cout<<setw(20)<< x_old << setw(20) << f << setw(20) << fprime;

cout<<setw(20)<< x_new << endl;

if( fabs((x_new - x_old ) / x_old ) < xtol )   break;

if( fabs(f) < ftol )  break;

x_old = x_new ;
}
cout<<endl<<endl;
return (0);
}

double fun(double x){
return 2*x*x -x;
}

double funprime(double x){
return 4*x-1;
}
-----------------------------------------------------------------
2) Matlab:
f = @(x)2*x.^2-x;
Then find the zero near 0.6:
z = fzero(f,0.6)

Matlab summary

1. Building matrix:
>>rand(7) %7*7 matrix
>>rand(2,5) % 2*5 matrix
>>normrnd(0,1,[1 5])% random number 1*5 matrix from normal
%distribution with mean 0, standard deviation 1.
>> help rand %help manual
>>a=eye(6) %6*6 unit matrix
>>zeros(2,5) % 2*5 matrix with all elements 0
>>ones(7) % 7*7 matrix with all elements 1
>> b=[1; 2; 3;4;5;6] % a column vector with length 6
>> x=a\b % solve a*x = b

2. function
in stat.m
----------------------------------------
function [mean,stdev] = stat(x)
% to calculate mean and standard
%deviation of vector x
n = length(x);
mean = sum(x)/n;
stdev = sqrt(sum((x-mean).^2/n));
-----------------------------------------
>> b=[1; 2; 3;4;5;6]
>>[mean, stdev]=stat(b)

3. Format and misc
Matlab is case sensitive.
Matlab only display only 5 digits, using
>>format long
to display all 16 digits.
>>x=1; y=2; z=3
>>save filename
%will save x, y, z values to filename.mat
>>clear % clear x, y,z
>>load filename % will load filename.mat
>>whos % list x, y, z
>>save -ascii mydata.dat % save x, y and z in ascii
>>! vi mydata.dat % see what is inside mydata.dat
>>diary mydiary.out %will create diary to mydiary.out
>>diary on
>>diary off

4. Colon: create arrays or select a column from a matrix
>> x=-2:1 % -2 -1 0 1
>>x=-2:.5:1 % from -2 to 1 interval 0.5
>>a=rand(2,5)
>> a(2,:) % second row of a
>>a(:,3) % third column of a
>>a([1 2],:) %first and second column of a
>>[eye(2);zeros(2)] % combination of two matrices

5. if ... elseif ... else...end
in even.m
------------------------------
function b=even(n)
% b=1, even, b=0, odd
if mod(n,2)==0,
b=1;
elseif mod(n,2) ==1,
b=0;
else b=0;
end
--------------------------------
6. For loops: for i=1:n, , end
in addmatrix.m
----------------------------------------------------------
function c=addmatrix(a,b)

% This is the function which adds
% the matrices a and b. It duplicates the MATLAB
% function a+b.

[m,n]=size(a);
[k,l]=size(b);
if m~=k | n~=l,
r='ERROR using add: matrices are not the same size';
return,
end
c=zeros(m,n);
for i=1:m,
for j=1:n,
c(i,j)=a(i,j)+b(i,j);
end
end
-----------------------------------------------------------
7. While loops: while , , end
in twolog.m
-------------------------------------------------
function l=twolog(n)

% l=twolog(n). l is the floor of the base 2
% logarithm of n.

l=0;
m=2;
while m<=n   l=l+1;  m=2*m;
end
----------------------------------------------------
8. Plot
x=-pi:0.1:pi y=sin(x)
plot(x,y, 'Color','g') %color green
hold on % show two plots in the same window
y1=cos(x)
plot(x,y1,'Color','r') %color red
xlabel('-\pi \leq \Theta \leq \pi') % x label theta between -pi and pi
ylabel('sin(\Theta)') % put ylabel
title('Plot of sin(\Theta)') % put title
------------------------------------------
in plotbar.m, plot data in bar
--------------
function plotbar
hold on;
x=35:1:47;
y1=[33,89,105,163,153,419,842,1197,1237,1144,641,269,117];
y2=[2,4,3,1,12,14,33,88,162,240,154,103,99];
h1=bar(x,y1,'g'); xlabel('weeks');
ylabel('cases');
h2=bar(x,y2,'b');
set(h1,'Displayname','confirmed'); % legend
set(h2,'Displayname','hospitalized'); %legend
set(get(gca,'YLabel'),'Rotation',0.0);

hold off;
--------------------------------------------------

Wednesday, June 23, 2010

C++ interview Questions (1)

1) Using for loop, print out even number between 1 and 50.


#include<iostream>
using namespace std;

int main()
{


for (int i=1; i<=50;i++)

if(i%2==0) cout <<"even i="<<i<<endl;

return(0);
}

2)How do you know what shell you are running?
echo $0

3) What is object-oriented design?
In object-oriented design, an object is a fundamental entity.
The three basic principles of object-oriented are as follow:
a) Encapsulation-The ability to combine data, and operations on that
data, in a single unit.
b) Inheritance -The ability to create new objects from existing objects.
c) Polymorphism-The ability to use the same expression to denote
different operations.




4) Write a program to input 5 number between 1 and 10 and output average.
#include<iostream>
using namespace std;

int main()
{
double number;
double total = 0;

for(int i=1; i<=5;i++)
{
cout <<"please input a number between 1 and 10"<<endl;

cin>>number;
while(number<1 ||number>10)
{
cout<<"you number is not between 1 and 10, enter again"<<endl;

cin>>number;
}
total = total + number;

}

cout<<"the average of your 5 inputs are "<< total/5<<endl;
return(0);

}

~                    

5. Reverse a linked list
node * reverse(node *head)
{

node *curr = *head, *prev = NULL, *nxt_fwd = NULL;

while(curr)
{
nxt_fwd = curr->link;
curr->link = prev;

prev =curr;
curr=nxt_fwd;
}
head = prev; /*save the new head */

return head;
}

A linked list is a data structure that consists of a sequence of 
data records such that in each record there is a field that contains 
a reference (i.e., a link) to the next record in the sequence. 
 
6. What is difference between #define and const?

#define is macro and don't need to state the data type,
const is a modifier and need to state the data type.

7. What is difference between public, private and protected variables?
private variables can only be accessed by member functions and
friends of that class.
protected variables can be accessed by member fucntions and friends of
that class and its derived class.
public variables can be accessed by anyone.

8. What is difference between pointer and reference?
Reference is the other name given to the same variable. Pointer is used to
contain address of another variable. For pointer
a) Its not necessary to initialize the pointer at the time of declaration.
b) You can create the array of Pointer.
c) You can assign NULL to the pointer
d) You can use pointer to pointer.
But reference can not.

9. What C++ library are you proficient with?
STL, Boost and openmp.



10. What is virtual basic class and friend class?
Virtual Base Class: Used in context of multiple inheritance in C++. If
you plan to derive two classes from a class, and further derive one
class from the two classes in the second level, you
need to declare the uppermost base class as 'virtual' in the inherited classes.
This prevents multiple copies of the uppermost base class data members when
an object of the class at the third level of hierarchy is created.


Friend class: When a class declares another class as its friend, it is
giving complete access to all its data and methods including private
and protected data and methods to the friend
class member methods.



11. What is the difference between a .lib and .dll? 



DLL : as the name states is a dynamic link library, that can allows functions/

classes/ implmented within XXX.dll to be called at run time. Hence the calling

.exe or .dll links with XXX.dll at run time.



LIB : is static linking. I.e when the calling exe or dll calls the XXX.lib

the exporting functions/classes etc are pulled in at compile time, opposed

to run time.