Archive for the ‘Programming’ Category

Complex number in OpenCL - cl_complex

Recently I've been involved in the developing of a library OpenCAL capable of  parallel execution of cellular automata  and finite differences models.

I though it could have been fun to render some huge fractal with it and so I ended up writing some OpenCL code for the generation of Julia sets. Unfortunately OpenCL does not provide support for complex number (CUDA does, check the following link out: CUDA complex number example)  so I had to write it myself.

The following might be useful to anyone with need of support for complex number operations as exponentiation, argument, modulus etc. in OpenCL.

Here is a link to a 324 Megapixels Julia set Rendered image (warning, size >150 MB)

Weighted Tree Vertex Cover Problem

Vertex cover of graph  is defined as  s.t.  . In other word a subset of the vertices such that all vertices are incident to a vertex in the vertex cover.
We will derive an algorithm for finding the weight of a minimal (yes is not unique) vertex cover for a subclass of graphs i.e. tree (which are acyclic graphs with the property that only one path between each vertex exists).

Remember that vertex cover for graphs is an NP-Complete (NP-hard and NP, hard at least as all NP problems and it is an NP problem itself) problem i.e. no deterministic polynomial tyme algorithm was discovered (if you discover one, contact me, we will be millionaire).

Tree Vertex Cover - Problem Definition

Given a weighted tree  with  write an algorithm for computing a vertex cover with minimum weight i.e. V' is a vertex cover and the sum of the weight of its element is minimal.

The following is the tree structure that we will use throughout the article.

template<typename T,int DEGREE>
struct node{
array<node*,DEGREE> children;

T data;
int weight;

node(const T& v , int _weight) : weight(_weight){
data=v;
mincover=0;
}
};



What if the weight is equal to the degree of the node?

The first observation we can make is that the root node can weather be or not be in the vertex cover. If we include it in the solution then we are sure that all the edges from it to its children have been covered and to solve the problem we need only to compute the cover of its children (which is a simpler problem). Read On…

Programming Interview Question - Merge Intervals

This post will explore the solutions to the question #4 of the famous website cakeinreview (here the link).

Programming Interview Question - Merge Intervals - Problem Statement

Given a list of pair of integers return a list of merged or condensed intervals.

Given for instance the following input list

Your function should take care of corner cases like merging two intervals like the following in . Give a solution first. Then try to solve it in .

List Cycle Detection

Linked list cycle detection problem is a very instructive and fun problem to reason about. This article will state the problem first and then explains how we can solve it efficiently while giving some insight on the underlying math.

A list can gets corrupted and some node can be linked by more than one node, as in the following figure. This could lead to never ending traversal of the list. So it make sense to solve the following problem:

Cicular List

List Cycle Detection - Problem Statement

1. Given  a linked list, detect if the list is circular i.e. contains a cycle
2. Find the starting node of the cycle (the node with two inward arrows in the figure)

The problem is easily solvable in time and space considering that we can visit the list from the head and store in a separate list the visited nodes. As the visit continues we check if the node we are examining was previously visited (for each node we visit we asks the following question: is that node contained in the support list already?). If yes the list is circular and that node is the start point of the cycle. If we reach the tail of the list then the list is not circular.

We can lower the complexity of this approach down to time using a more efficient support (set) data structure (like a tree set). But we can do much better, and the rest of the article will show how to obtain time and space complexity.

List Cycle Detection - Floyd’s algorithm

This algorithm uses the fact that, like clock's hands, things iterating on a cycle at different speed will eventually meet at some point in the future. Consider two runner with velocities respectively, starting running from the same point in a circular stadium. They will meet again when the slower runner reach the starting point for the second time. Why? By the time the slower one has completed half circle the faster has completed a complete cycle and by the time the slower finishes his run, arriving at the starting point again, the faster has completed a second entire cycle.

Things are a bit more complicated in the list cycle detection problem because the iterators (the two runners) do not necessarily start they race from the circular part of the list

Consider two iterators with velocities  respectively. Suppose the cycle has length and that it starts at node number . When the slower iterator reaches the faster is at location . How many iteration it will take before they meet? And at which node?

The situation is described by the following congruence:

which has solution . This means that they will meet after iteration of the slower iterator. This means that they will meet at nodes before the beginning of the cycle and we can use this fact to count nodes from the beginning of the list to deduce the starting point of the cycle. Once the iterators meet in the cycle, we can move the fast iterator back to the beginning of the list and iterate forward one node per step with both iterators until they match again. When we move the fast iterator back at the head of the list, both iterators are nodes away from the beginning of the cycle. Because of this when we move both of them by one,  they will eventually meet exactly at that node .

Let's consider now the case when . This means that by the time the slower iterator reaches the beginning of the cycle the faster one has completed more that a cycle. What will be the starting point for the faster one? We argue that once reaches , is at node but since , this means that it will be at position . We can now use similar argument to the previous case and write:

• since

which has solution . This means that the meeting point is nodes before the beginning of the cycle. If we do the same operations as the previous case, , we obtain the same result. Iterators will meet at the beginning of the cycle. Why? Well advancing makes cycles possibly several times ( remember that  ) and it will clearly stops at .

In other words the slower pointer is at first  at node number . We can write where . After advancing steps it will be at location   Since the result follows.

As an example consider a list with a cycle of length starting at node number . The first part of the algorithm tells us that the nodes will meet at node . Moving the fast pointer back to the head of the list and iterating one node per time both iterators will lead the slower point to node:

• 12 again after advancing of 4 nodes
• 12 again after advancing of 4 nodes
• 10 advancing of the remaining 2 nodes.

The following illustration depict how the algorithm would work on a list of 8 nodes with a cycle of length 4 starting at node number 4. After 5 steps the slow (blue) and fast (red) iterator points to the same node i.e. node number 6.

After that the fast pointer is moved to the head of the list and both iterator are incremented by 1 until they meet again. When they do, they will meet at the beginning of the cycle.

Execution of the Floyd's algorithm on a list of 8 nodes with a cycle of length 4 starting at node 4.

HOW-TO: Dynamic Message of the day

The final result will be something like the following:

It mixes a fun message using fortune and cowsay which you can install using


sudo dnf install fortune-mod cowsay



utility and some informative info about the status of the system as:

• Ram and Swap available and used
• Disk space

The script file can be easily configured and extended to suits the your needs. Colors can also be easily customized.

Distributed  Hadoop and HBase installation - Fedora Linux

In this post I will describe how to get started with the latest versions of hadoop and hbase describing all the step to obtain a working hadoop installation. The steps described here can be easily used to perform a working installation on a large cluster (even tough it can requires additional steps as shared filesystem for instance).

Prerequisites

 sudo dnf install openssh openssh-askpass openssh-clients openssh-server

Don't forget to start the ssh service using the following command:

 sudo service sshd start

Programming Interview Question

Question: given two string write a method to decide if one is a permutation of the other.

This is a common question that could be easily solved if we know in advance which is the size of the alphabeth. A straightforward approach could be to sort both strings and then compare them. This approach has complexity  due to sorting. We can do better and lower the complexity to  if we reason as follows: given a boolean sequence of the same size of the alphabet  initially false initialized.  Then what happen if  for each char we found in the  string  we negate the value of the correnspoding bool in the sequence? We end up having the  at position  if the char  appeared an odd number of times and  otherwise. Now if the other string  is a permutation of the first one, we all agree that for each char in  it contains the same number of occurrences. This means that if we apply the same process as before on the boolean sequence using as input the string  each bool is being negated an even number of times and this means that its value would be the same as the beginning of the process (all ). So if the sequence does not contains any true value, than it means that the strings contains the same elements i.e. they are permutation of each other.

Example:

1. "abbccd" ,  "cbdabc" , 
2. Apply negation using s
• 
3. Apply negation using v
• 

A possible C++ implementation is shown here

Programming Intervew Question: Unique Characters in a String

Question: implement an algorithm to determine if a string has all unique characters

The idea behing this (fairly easy) question is that whenever we found that any chars is repeated at least twice we should return false. In order to do that we have to look at each char we are loloking for a solution which complexity is at least . We are free to use any support data structure. is the size of the ASCII charset.

Byte Number Conversion

For a project I'm working on these days I was forced to convert raw byte to several numerical values ( to and from binary format).

Bytes are represented in C/C++ as  unsigned char, and std::string are often used as byte buffer as well as old well known raw arrays. I wrote a simple struct that relieve the pain in performing such conversions. It exposes two functions: fromBytes and toBytes.fromBytes takes an additional boolean parameter that takes care of different endianness.

/*
Author: Davide Spataro 2016

Converts byte buffer to type T
*/
typedef unsigned char byte;

template <class T>
struct converter{

static const size_t size = sizeof(T);

union conv{
T value;
byte bytes[ sizeof( T ) ];
} c ;

T fromBytes( const  byte *bytes, bool endianness = false){

if(endianness)
#pragma unroll
for(int i=0;i<size;i++)
c.bytes[size-1-i] = bytes[i];
else
#pragma unroll
for(int i=0;i<size;i++)
c.bytes[i] = bytes[i];

return c.value;
}

byte* toBytes(const T& value,bool endianness = false){
c.value =value;
if(endianness)
reverse();
return c.bytes;
}

void reverse(){
#pragma unroll
for(int i=0;i<size/2;i++){
byte tmp = c.bytes[i];
c.bytes[i]=c.bytes[size-1-i];
c.bytes[size-1-i] = tmp;
}

}

};

template<class T>
void printHex(const T& key, size_t size){
std::cout.setf(std::ios::hex, std::ios::basefield);
for (int i = 0; i < size; i++){ if (i > 0) printf(":");
printf("%02X", (unsigned char)key[i]);

printf("\n");
}



Usage is very simple: let's say for instance you have the following 8 bytes into an unsigned long long

00:00:00:00:00:00:00:5E


converter<int64_t> c;
//binary value is 00:00:00:00:00:00:00:5E (8 bytes)
int64_t res =  c.fromBytes(reinterpret_cast<const unsigned char*>(binary.c_str()),true);
std::cout <<res<< " \n";



this will output clearly output 94.

It works with almost all numerical types (float, all int flavors and floating points)

Programming Question: Given an integer, compute its parity(easy)
The parity of an integer is true iff number of set bits (1) is odd, false otherwise. Example: has 5 set bits and hence its parity is true.