## Sunday, January 5, 2014

### Comparison of iterative and recursive way of Fibonacci Sequence calculation

The Fibonacci numbers are the sequence of numbers

$\{F_n\}_{n=1}^\infty$

defined by the linear recurrence equation

$$F_n = F_{n-1} + F_{n-2}$$

with $F_1 = F_2 = 1$, and conventionally defining $F_0 = 0$.

We can implement Fibonacci numbers by iteratively or by using recursion. These two functions are implemented in Matlab to compare the running time of the algorithms.

function [result] = fibonacciRecursive(n)
%calculates the fibonacci output in recursive way
if n==0 || n==1
result=1;
else
result=fibonacciRecursive(n-1)+ fibonacciRecursive(n-2);
end
end


function [result] = fibonacciIterative( n )
%calculates the fibonacci output in iterative way
y1=1;
y2=2;
for i=2:n
result=y1+y2;
y2=y1;
y1=result;
end
end
For testing:

N=10;

fibonacciIter=zeros(N,1);
fibonacciRecur=zeros(N,1);

for i=1:N
tic
for j=1:25
fibonacciIterative(i);
end

fibonacciIter(i)=toc;

tic
for j=1:25
fibonacciRecursive(i);
end
fibonacciRecur(i)=toc;
end
X=1:N;
plot(X,fibonacciIter,X,fibonacciRecur);
legend('Iterative', 'Recursive')
xlabel('input size');
ylabel('time(seconds)');
The plot is:

As shown in plot recursive implementation is increasing exponentially in time with the given input size

## Wednesday, December 11, 2013

### Implementing Principle Component Analysis (PCA) in Python

i take a look at PCA (principle component analysis). i'm not sure this is implemented somewhere else but a quick review of my collage notes (reference needed) lead me the code below, and  data is (reference needed):
x y
2.5 2.4
0.5 0.7
2.2 2.9
1.9 2.2
3.1 3.0
2.3 2.7
2 1.6
1 1.1
1.5 1.6
1.1 0.9

'''
*@author beck
*@date Sep 14, 2012
*PCA with Python
*bekoc.blogspot.com
'''
import numpy as np
import matplotlib.pyplot as plt
import pylab

xs= np.loadtxt("pcaData",delimiter=" ", skiprows=1, usecols=(0,1)) # numpy array - similar to C array notation.
#get mean
meanx=np.average(xs[:,0])
meany=np.average(xs[:,1])

correctedX=[value-meanx for value in (xs[:,0])] #X data with the means subtracted
correctedY=[value-meany for value in (xs[:,1])] #Y data with the means subtracted
data= np.array([correctedX,correctedY])
print data.shape
covData=np.cov(data)#calculate covariance matrix

eigenvalues, eigenvectors = np.linalg.eig(covData)

print eigenvectors
print eigenvectors #eigenvectors are both unit eigenvectors
print eigenvectors
x= [n for n in range (-2,3)]
y=  [eigenvectors*i/eigenvectors for i in x ]
y1=  [eigenvectors*i/eigenvectors for i in x ]

print x
print y
plt.plot(x, y,linestyle='--', label='eigenvector1')
plt.plot(x, y1, linestyle='--', label='eigenvector2')
plt.plot(data[0,:],data[1,:], marker='+', linestyle=' ',  label= "Normalized data" )

#plt.plot(xs[:,0],xs[:,1],marker='+',linestyle=' ')
pylab.ylim([-2,2])
pylab.xlim([-2,2])
plt.title('PCA example')
plt.legend()
plt.show()

The code includes step 1 to 5
PCA summary :
1- Given a dataset calculate normalized data (mean substructed data), let's say n dimension (feature) data
2-calculate covariance matrix of normalized data
3-calculate eigenvalues and eigenvectors of the covariance matrix
4-eigenvector with the largest eigenvalue is the principal component
5-choose p eigenvectors and multiply with your data
6-now your data is p dimension. The green dotted plot of the eigenvector shows the most significant relation between dimensions Please refer to simple and consise tutorial at georgemdallas blog

## Saturday, November 2, 2013

### how to implement two stacks in one array

My friend came up with a new question  that he is asked in his interview,

Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The code is implemented in C++.

/*
* File:   main.cpp
* Author: bekoC
*/

#include <cstdlib>
#include<stdio.h>
#include <stdlib.h>
#include<iostream>

#define N 10

struct Stacks {
char charArray[N];
int top1, top2;
void olustur();
bool Insert(int stackNumber, char veri);
char deleteFromStack(int stackNumber);
bool isEmpty(int stackNumber);
void printStack(int stackNumber);
};

bool Stacks::Insert(int stackNumber, char newChar) {
if (top1 == top2)
{
return false;
}
if (stackNumber == 1)
charArray[top1++] = newChar;
else
charArray[top2--] = newChar;
return true;
}

char Stacks::deleteFromStack(int stackNumber) {
if (stackNumber == 1)
return charArray[--top1];
else
return charArray[++top2];
}

bool Stacks::isEmpty(int stackNumber) {
if (stackNumber == 1)
return (top1 == 0);
else
return (top2 == N - 1);
}

void Stacks::create() {
top1 = 0;
top2 = N - 1;
}

void Stacks::printStack(int stackNumber) {

if (stackNumber == 1 && !isEmpty(stackNumber)) {
{
for (int i = 0; i <= top1; ++i) {
printf("%c", charArray[i]);

}
}
} else if (isEmpty(stackNumber)) {
printf("Stack 1 is empty");
}
if (stackNumber == 2 && !isEmpty(stackNumber)) {
for (int i = N - 1; i >= top2; i--) {
printf("%c", charArray[i]);
}
} else if (isEmpty(stackNumber)) {
printf("Stack 2 is empty");
}
}

int main() {
Stacks myStack;
myStack.create();
myStack.Insert(1, 'A');
myStack.Insert(1, 'B');
myStack.Insert(1, 'C');
myStack.Insert(1, 'D');
myStack.Insert(1, 'E');
myStack.Insert(1, 'F');

myStack.Insert(2, 'W');
myStack.Insert(2, 'X');
myStack.Insert(2, 'Y');
myStack.Insert(2, 'Z');
myStack.printStack(1);
myStack.printStack(2);
if (!myStack.isEmpty(1))
myStack.deleteFromStack(1);
if (!myStack.isEmpty(2))
myStack.deleteFromStack(2);
return 0;
}


Recently, my friend asked me to write a basic program in C to add a indicator (e.g. any number or char) between the two nodes of the given linked list. He is asked this question in one of the job interviews.
The output of the program with the indicator of  99 is shown as below.

The code
/*
* File:   main.cpp
* Author: bekoC
*/

//Some notes about my compilation errors:
//There are many ways to get a segfault,
//at least in the lower-level languages such as C(++).
//A common way to get a segfault is to dereference a null pointer:
//int *p = NULL;
//*p = 1;

#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct Node {
int data;
struct Node *next;
};

struct Node* insert(struct Node *head, int data) {
struct Node *temp = (struct Node*) malloc(sizeof (struct Node)); // for the new node address is taken by malloc in heap
temp->data = data;
temp->next = NULL;
} else {
while (temp1->next != NULL) {
temp1 = temp1->next;
}
temp1->next = temp;
}
}

struct Node *newNode, *scan;
while (temp1 != NULL && temp1->next != NULL) {
newNode = (struct Node*) malloc(sizeof (struct Node));
newNode->data = indicator;
newNode->next = temp1->next;
temp1->next = newNode;
temp1 = newNode->next;
}
}

//using recursion
return;
}
}

int main(int argc, char** argv) {
printf("\n");
//Adding a indicator which is 99
int indicator = 99;
return 0;
}


## Sunday, October 6, 2013

### Yet another another language for scientific computing

i have written a post about which programming  language to use for the implementation of algorithms in machine learning, yet i have came across another scientific computing language while i was searching about recurrence. It's called Julia:
Julia is a high-level, high-performance dynamic programming language for technical computing, with syntax that is familiar to users of other technical computing environments. It provides a sophisticated compiler, distributed parallel execution, numerical accuracy, and an extensive mathematical function library. The library, largely written in Julia itself, also integrates mature, best-of-breed C and Fortran libraries for linear algebra, random number generation, signal processing, and string processing. In addition, the Julia developer community is contributing a number of external packages through Julia’s built-in package manager at a rapid pace. IJulia, a collaboration between the IPython and Julia communities, provides a powerful browser-based graphical notebook interface to Julia.
i'm not sure that i need to use it but it desires to look at it because it is stated in official release that Julia beats all other high-level systems (i.e. everything besides C and Fortran) on all micro-benchmarks.

you can read  more detailed post "MATLAB, R, and Julia: Languages for data analysis" if you'd like to give a decision of using it or not. In addition, i'd like to recommend reading the post "A Matlab Programmer's Take On Julia",which  criticizes Matlab. Finally, take a look at some benchmark results of fibonacci and matrix multiplication computations implemented with Julia.

## Sunday, September 29, 2013

### Understanding thread basics with Python

Recently, I needed to use the threads in order to increase the CPU efficiency in terms of idle time in Python. I came a cross great examples from agiliq's blog. I have reimplemented his code and add some minor comments.
You can refer the original post with more details.

'''
Created on Sep 29, 2013
@author: Bekoc::algorithms
'''

import time
import urllib2

def __init__(self, url):
self.url = url

def run(self):
resp = urllib2.urlopen(self.url)
print self.url, resp.getcode()

def get_responses():
urls = ['http://www.google.com', 'http://www.amazon.com', 'http://www.ebay.com', 'http://www.alibaba.com', 'http://www.reddit.com']
start = time.time()
for url in urls:
print ('Thread %s is calling %s' %(t.getName(), url))
t.start()
t.join()
print "Elapsed time: %s" % (time.time()-start)

get_responses()


Race Condition example without use of lock.acquire and lock.release:

'''
Created on Sep 30, 2013
@author: Bekoc::algorithms
'''
import time
#define a global variable
some_var = 0

def run(self):
#we want to read a global variable
#and then increment it
global some_var
time.sleep(.001)
print "some_var in %s is %d" % (self.name, read_value)
print "some_var in %s after increment is %d" % (self.name, some_var)

for i in range(50):
t.start()

t.join()
print "After 50 modifications, some_var should have become 50"
print "After 50 modifications, some_var is %d" % (some_var,)



in order to prevent the race condition change the run function  and import Lock:

from threading import Lock

def run(self):
#we want to read a global variable
#and then increment it
global some_var
lock.acquire()