Archive

Archive for the ‘algorithms’ Category

Basic Data Structures and Algorithms in the Linux Kernel

November 24, 2013 Leave a comment

Algorithm Complexity Analysis

A Gentle Introduction to Algorithm Complexity Analysis

However, theoretical computer science has its uses and applications and can turn out to be quite practical. In this article, targeted at programmers who know their art but who don’t have any theoretical computer science background, I will present one of the most pragmatic tools of computer science: Big O notation and algorithm complexity analysis. As someone who has worked both in a computer science academic setting and in building production-level software in the industry, this is the tool I have found to be one of the truly useful ones in practice, so I hope after reading this article you can apply it in your own code to make it better. After reading this post, you should be able to understand all the common terms computer scientists use such as “big O”, “asymptotic behavior” and “worst-case analysis”.” (source)

Dictionary of Algorithms and Data Structures

April 11, 2013 Leave a comment
Categories: algorithms

Generate random numbers deterministically and non-deterministically

Problem
I wanted to compare the efficiency of some sorting algorithms. For this, I wrote a simple program that accepts a command-line parameter (the name of a sorting algorithm) and calls the specified algorithm on a large array containing random integers. Using the Unix “time” command I could do my tests.

However, if the array is filled up with different random numbers each time, the tests wouldn’t be fair. Thus, the array should contain random numbers that are generated in a deterministic way, i.e. each time I execute my little program, the array should be filled with the same numbers in the same order.

Generate random numbers deterministically
C snippet:

int UPPER = 10;

for (i = 0; i < 10; ++i) {
    printf("%d ", (int)(random() % UPPER + 1));
}

Full source code is here.

Python snippet:

UPPER = 10
random.seed(0)  # use a constant seed

for _ in range(10):
    print random.randint(1, UPPER),

Full source code is here. Doc on random.seed is here.

Sample output:

$ ./det.py
4 7 8 6 4 6 7 3 10 2
$ ./det.py
4 7 8 6 4 6 7 3 10 2

Generate random numbers non-deterministically
Now let’s see how to generate random numbers non-deterministically.

Note that this method is still deterministic since it uses the current time as its seed. If someone knows the time when you launched your program, (s)he could reproduce your “random” numbers. As John von Neumann said: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.

C snippet:

int UPPER = 10;

srand((unsigned)time(NULL));   /* use current time as seed */

for (i = 0; i < 10; ++i) {
   printf("%d ", (int)(random() % UPPER + 1));
}

Full code is here.

Python snippet:

UPPER = 10

for _ in range(10):
    print random.randint(1, UPPER),

Full code is here.

Sample output:

$ ./non-det.py
2 4 4 10 6 9 4 3 2 7
$ ./non-det.py
5 8 10 2 10 10 1 10 4 5

Note
Notice the different behaviors of C and Python. By default, C uses the same seed, thus if you want “true randomness”, you must call srand. On the other hand, Python generates “true random” numbers by default and you must provide a constant seed if you want a determinsitic behavior.

Thanks to Temia E. for his (her?) help.

Books on graphs and graph algorithms

October 26, 2011 Leave a comment
Categories: algorithms, graphs
Follow

Get every new post delivered to your Inbox.

Join 61 other followers