Not P==NP for now..

Some time ago (January 19, 2011), Vladimir Romanov announced that he had found a polynomial time solution for the 3-SAT NP-Complete problem. As I mentioned on the first related post, if this was true it would immediately suggest that P==NP.. A nice article about what would be the implications of this equality can be found in Wikipedia.

The time for such a proof (or the opposite one, which is consider to be more probable) has not come yet. Yesterday, with a comment to his blog, Vladimir Romanov announced that there is a problem with the solution that need to be corrected:

Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.

Best regards,
V. R.

Introduction to Erlang post series

This entry is part 1 of 16 in the series Introduction to Erlang

While I was writing my first actual (and extremely delayed :-S) article for the Parallelizing simple algorithms series, I realized that since Erlang is not a popular programming language it would be nice to start an Introduction to Erlang post series. I consider Erlang as a must-know language for an engineer that works with distributed systems and parallel programming. Believe me, in several cases, Erlang is a problem solver!

I will try to keep the posts short and example based. An approximation of the posts that I intend to write is:

1. Basics: how to get a working Erlang environemt
2. Basic Types: integers, floats, …
3. Modules and Compiling: how to write and compile a module
4. Functions: how to delcare functions
5. Library Functions & BIFs
6. Lists: list manipulation
7. Processes: how to create new processes
8. Message Passing: how to send messages between processes
9. Debugging: how to debug Erlang programms
10. Records: how to use records

I will keep this list updated in case that I come up with new ideas!

I hope I will convince you that Erlang worths every software engineer’s attention..

Parallelizing simple algorithms : Fibonacci

This entry is part 2 of 2 in the series Parallelizing simple algorithms

Fibonacci Blocks

It took me a little more than I expected, but finally I managed to write the first post for the Parallelizing simple algorithms series.

As I “promised”, I will start these series by parallelizing the Fibonacci Number sequence generation. As you probably already know, Fibonacci numbers are the integer sequence produced by the following relationship:

```   F`0` = 0
F`1` = 1
F`n` = F`n-2` + F`n-1````

The resulting sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

Removing the SVN metadata files (.svn/) in Linux

If you ever want to remove a folder from SVN control (clean the folder by removing the .snv metadata folders) in Linux, you can simply run the following command:

`rm -rf \$(find path/to/the/CORRECT/folder -type d -name .svn)`

where:

• `rm -rf` is remove recursive force. Recursive for deleting the directories and their contents recursively and force for no prompting (for example, for write protected files)
• `\$(..)` is the command substitution, that takes the output of a command and uses it as input for another
• `find path/to/the/CORRECT/folder -type d -name .svn` is searching (recursively) for folders (d for directory) with the name .svn1 in the directory pointed by `path/to/the/CORRECT/folder`

Be careful to use the correct path, else you can remove the svn metada for the wrong folder! A good approach can be to execute the `find` command without the `rm`, check the output, and then proceed to the remove :-).

1case sensitive, use `-iname` for insensitive

Extracting citations from a BibTex file using Linux terminal

I had a big (around 40 entries) BibTex file with the references of some papers I studied and I wanted to extract the citations in the format used for citing in Latex (`\cite{AuthorYear}`). Just today I read some tutorials about `awk`, so I thought “Let’s use it!!”.

An example BibTex file:

```@article{Kotselidis2010, author = {Kotselidis, Christos and Lujan, Mikel and Ansari, Mohammad and Malakasis, Konstantinos and Kahn, Behram and Kirkham, Chris and Watson, Ian}, doi = {10.1109/IPDPS.2010.5470460}, isbn = {978-1-4244-6442-5}, journal = {2010 IEEE International Symposium on Parallel \& Distributed Processing (IPDPS)}, pages = {1--12}, publisher = {Ieee}, title = {{Clustering JVMs with software transactional memory support}}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5470460}, year = {2010} } @phdthesis{Zhang2009c, author = {Zhang, Bo}, keywords = {cache-coherence,contention manager,distributed transactional memory}, title = {{On the Design of Contention Managers and Cache-Coherence Protocols for Distributed Transactional Memory}}, year = {2009} }```

Solution

`awk 'BEGIN{FS="[{,]"} /@/ {print "\\cite{"\$2"}"}' filename.bib`

\cite{Zhang2009c}
\cite{Kotselidis2010}

In order to save the output in a file named `cites.txt`:

`awk 'BEGIN{FS="[{,]"} /@/ {print "\\cite{"\$2"}"}' filename.bib > cites.txt`

Hint: Use “`>>`” if you want to append the output. Single `>` creates a new file (if not existing), or empties the existing one and then appends the content..

If you want to know my “implementation” process, continue reading 😉
Read the rest of this entry »

Netbeans 6.9.1 on Ubuntu 10.10 Installation – OpenJDK problem

I wanted to install Netbeans IDE 6.9.1 (C/C++ version, but I believe that the problem is generic) on my Ubuntu 10.10 laptop, so after downloading the latest version from netbeans.org, I tried to install it:

```\$ ls -l netbeans-6.9.1-ml-cpp-linux.sh -rw-r--r-- 1 ** ** 36699136 2011-02-06 00:58 netbeans-6.9.1-ml-cpp-linux.sh \$ chmod +x netbeans-6.9.1-ml-cpp-linux.sh \$ sudo ./netbeans-6.9.1-ml-cpp-linux.sh```

and got the following output:

```Configuring the installer... Searching for JVM on the system... Extracting installation data... Running the installer wizard... null```

The installation wizard (GUI) did not appear at all.

Luckily, I “immediately” thought “hmm, I re-installed Ubuntu quite recently, did I install JRE?”
So, I checked if I had “Java” installed and checked that everything is “good”:.

```\$java -version java version "1.6.0_20" OpenJDK Runtime Environment (IcedTea6 1.9.5) (6b20-1.9.5-0ubuntu1) OpenJDK Client VM (build 19.0-b09, mixed mode, sharing)```

As you can see, I had OpenJDK installed..
For some reason, which I don’t know, I had already installed the Sun JDK, but not removed the OpenJDK, or at least set the `java` to point to the Sun version.

So, using synaptic, I unistalled OpenJDK (you can (un)install OpenJDK and Sun JDK from the Software Center also):

```\$java -version java version "1.6.0_22" Java(TM) SE Runtime Environment (build 1.6.0_22-b04) Java HotSpot(TM) Server VM (build 17.1-b03, mixed mode)```

And then, everything worked fine..

Linux Commands: a useful article

Yesterday, I found an article called “A Practical Guide to Linux Commands“; a compact guide to several linux command use cases, such as backup and compression, searching the filesystem, etc. I have to admit that it was one of the most interesting/useful articles I have ever read, thus I share it with you.

The article is posted on linuxconfig.org and you can access it here.

Pointers and Arrays in C

As anyone who had programmed in C knows, pointers can be (also) used to access the data of an array.

From the Wikipedia article about C language:

C supports the use of pointers, a very simple type of reference that records, in effect, the address or location of an object or function in memory. Pointers can be dereferenced to access data stored at the address pointed to, or to invoke a pointed-to function. Pointers can be manipulated using assignment and also pointer arithmetic. The run-time representation of a pointer value is typically a raw memory address (perhaps augmented by an offset-within-word field), but since a pointer’s type includes the type of the thing pointed to, expressions including pointers can be type-checked at compile time. Pointer arithmetic is automatically scaled by the size of the pointed-to data type.

Series