Rapa nui and the mohais

The inhabitants of the remote Rapa Nui island want to build a pyramid of mohais. There are K mohais in the island and each of them has a weight wi and a strength si. The i-th mohai can tolerate a weight no larger than si on his shoulders. What is the maximum height of the pyramid? (PS: there are two options either you subtract the weight of the mohai from his strength, or you don't subtract it).

a rant to the academic community

I like to serve conferences as PC member or to review journal papers. Anyway, I keep seeing papers with elegant theoretical solutions and very poor experimental settings. For instance, you can see a new elegant text clustering algorithm tested in an unrealistic environment such as "Let's suppose we take this collection of 4000 articles and cluster them in just 5 clusters, well then my algorithm is better than the state-of-art of about 3% in precision".

Please, do not accept this type of papers. Web reality is different you have hundred thousands or millions or more documents and, certainly, you don't have just 5 clusters. Plus, data is evolving and you may want to consider temporal constrains, as well.

Size of the web: how many servers to store the whole web?

Back in 2005 someone said that the web is more than 11.5 billion of pages. Maybe it is a bit larger now.

• Can you estimate what is the amount of disk storage for storing it?
• Can you estimate what is the amount of disk storage for storing different snapshots (see thewaybackmachine)
  

Magy!: how can we monitors most frequent queries?

Magy! receives a huge amount of queries everyday. They don't want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don't want to store all the queries.

Magy!: how many servers for a video search engine?

Magy! is the ultimate search engine. It won all the battles and survived. They have an ultra-social video search engine, which receives 500 new videos per second. Videos are user-contributed.

• Can estimate what is the disk space needed to store one year of videos?
• Can you propose a server infrastructure for storing the videos?
• What about caching.

Yet another back of the envelope computation.

Random samples and permutations (which terminate)

I am enjoying Jon Bentley's book. And well... I always made the same mistake he made for generating random samples and permutations (see Programming pearls: a sample of brilliance). Floyd's algorithms are pretty and elegant solution to the problem. Here you have a C++, STL implementation.

Back of the envelope computation: how large should be an hash table?

Jon Bentley's More Programming Pearls: Confessions of a Code has a nice chapter about back of the envelope computations. It is amazing how many people are having difficulties with simple math, while they know about algorithms and design patterns. So here is one simple problem:

• You have a collection of 50Millions words and you want to hash them into an hash table. How large the hash table should be?

More problems to follow.

Problem solving: bridges

Four guys are on the left side of a bridge and they need to go to the right side. It is night and the guys have just one electric torch light. Each guy has a different walking time. Namely, 10 second, 5 second, 2 second, and 1 second. At most 2 guys can be on the bridge at the same time, and when they walk in pair they have the speed of the slowest guy.

What it the minimum time to have the four guys on the right side of the bridge?

Problem solving: Light bulbs and switches

In a R1 room there are three switches and in another separate room R2 there are three light bulbs. The three switches control the light bulbs, but you cannot see the lights in R2 from R1.

You need to discover what switch controls each bulb, but you can enter in the room R2 only one time.

Generic Skip list (skiplist)

Skip lists are an interesting randomize data structure for storing pairs of . Skip lists have logaritmic search and insertion time. Here I sketch a generic skip list code

Problem solving: Array of bits, and their state

Suppose to have an array of k bits. At step 1 all the bits are set to 1, at step 2 all the even bits change their state, at step 3 all the bits which are multiple of 3 change their state, at step k all the bits which are a multiple of k change their state. How many bits will be set to 1 at step k?

There is a simple quadratic algorithm, but it turns out that there is a closed formula to compute the number of bits set to 1 at step k.

Bits, endianess, and stack growing

Here some little bit oriented tricks.

• How to discover if your server is little endian or big endian?

bool endianess(){
int test_num = 1;
char *ptr = (char *) &test_num;          // this will return a byte
return (*ptr)
}

• How to count the number of bits set to 1 in the internal representation of a number?

int num_ones_in_binary_representation(int num){
 int num_ones = 0;
 while (num){
 if (num & 1)
    num_ones++;
 num = num >> 1;
 }
 return num_ones;
}

A more elegant solution:

int num_ones_in_binary_representation(int num){
 int num_ones = 0;
 while (num){
  num = num & (num - 1);  // consider the binary representation of num - 1 and subtract them
  num_ones++
 }
}

• Is your stack growing up or down?

Call two functions and take the address of their arguments, or consider the address of two consecutive variables within a function.

Generic Graph search

Two classical graph search algorithms. DFS and BFS.

Generic Graph

Another generic data structure. This time a labeled direct graph. Labels can be associated to nodes and to edges with different types. Nodes are stored in an STL vector and new nodes can be dynamically added to the collection. Edges are stored in STL vectors, one vector for each different node.

Generic list and list iterators

Iterators are a nice paradigm for traversing a collection of elements. In C++ they can easily be expressed by using suitable struct contained within a class. STL's iterators are implemented this way (It is a useful reading to study the code in your distribution). Here I present a generic list implementation which supports list iterators.

Generic heap

I believe that heap is one of the most fascinating basic data structure. It's simple and yet elegant. Here you have a generic implementation, which also provides generic heapsort.

Generic Hash_Map

This example is an extension of previous hash_set. Here I implemented an hash_map, which stores a pair into and chained hash. Data structure is based on generic programming.

Chained hash and hash function

This example leverages the generic list for building an array of lists. In turn, this is used for building a generic chained hash_set. My hash_set implementation is a subset of STL's hash_set extension. User can provide their own custom hash function by inheriting from STL's unary_function.
I suggest evaluating boost::unoderder, If you want to play with a more complete implementation.

Generic list and mergesort

Generic programming is very powerful. You can write an ADT such as a list and don't care about the internal item. This example deal with lists and generic mergesort. A classical one.

Threads, Shared Lock, Unordered map

Boost is the C++ swiss knife. Here I play a bit with Threads, Shared Lock (a.k.a read/write locks) and hash map. In this example, multiple threads are writing (reading) data in an hash_map, synchronizing by using write lock (read lock).