## Basic Data Structures and Algorithms in the Linux Kernel

## 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)

## 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

http://stackoverflow.com/questions/510758/can-you-suggest-a-good-book-on-graphs-and-graph-algorithms

**Links**

- Graph Theory with Applications by J.A. Bondy and U.S.R. Murty (in HTML and PDF)
- Introduction to Algorithms
- Graph Theory
- Programming Challenges
- Introductory Graph Theory
- Data Structures and Network Algorithms