Fast String Hashing

Gio introduced me to the magic of FNV Hash a special kind of hash function well suited for hashing strings. Operations used for FVN hashing are bit-shift and xor. So they are pretty fast and guarantee to have few collision. No code this time, since the above web page has it already.

A comprehensive list of hash function is available here.

Update: Gio introduce me to the ultra-fast HSIEH string hash functions, which outperforms FNV hash. Again the code is in the page.

Serializing a Generic Tree

Boost Serialization offers a flexible tool for generic serialization. What if you can serialize a whole tree T, with something as simple as

oa << root 

and library serializes single node in T regardless tree shape and the type of each generic. This code explain how to serialize a generic tree. (Thanks gio for fixing that nasty bug!)

Segment covering

Given several segments of line with coordinates [L_i,R_i], choose the minimal amount of them, such they completely cover the segment [0,M].

Generic Tree

Boost::ptr_container is the standard solution for containers of pointers of heap-allocated objects in an exception-safe manner and with minimal overhead.
The applications are very interesting. For instance, it is easy to write a Generic Tree code and use it as in:

 Inner<std::string> root("root");
 root.add_child(new Leaf<std::string>("test son of root"));
 Inner<int> * n1  = new Inner<int>(1);
 root.add_child(n1);
 n1->add_child(new Leaf<std::string>("test son of integer"));
 depth_first(root);

I'm working on a version of the Generic Tree which supports serialization, but this is hard to achieve according to this post

Pokemon

There are M^3 Pokemons characterized by three different skills ("attack", "defense", "beauty"), each ranging from 1 to M. A subset containing N of the Pokemon are the bad pets. We want to select one of the other Pokemon to be a Hero. The Hero must beat each of the bad pets in at least one skill (not necessarily the same skill for all the bad pets).

The task is to compute the number of Pokemon that can be selected to be the Hero.

Different sea shells

You are given 12 sea shells with same shape and colour. 11 of them have the same weight, while 1 has different weight. Can you identify the different one by using a scale balance just three times?

Memory Mapped files in Boost and C++

Memory Mapped I/O is a crucial methodology for increasing I/O performance. The standard I/O approach is costly due to system call overhead and memory copying. Anyway, the memory mapped approach has its cost in page faults which should be carefully handled.

Before BOOST there was no portable API for memory mapped I/O. POSIX-compliant systems, such as UNIX, Linux, Mac OS X or OpenVMS supports the Posix function mmap(), while Microsoft Windows supports CreateFileMapping().

Boost C++ provides a portable implementation of memory-mapped files for Microsoft Windows and POSIX-compliant platforms.

Here you have the code for portable memory mapped file reading in Boost.

Fibonacci, a mathematician from Pisa

Leonardo Pisano (Leonardo Fibonacci, or simply Fibonacci meaning "filius nacci", the son of Nacci) was born in Pisa, Italy in about 1170 (the place where I live). He is well known for his Fibonacci Numbers.

Can you compute the Fibonacci numbers in optimal time?

Beautiful C++ books

C++

• The C++ Programming Language: Special Edition (3rd Edition) by Bjarne Stroustrup
• C++ Common Knowledge: Essential Intermediate Programming by Stephen C. Dewhurst
• Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions by Herb Sutter
• More Exceptional C++: 40 New Engineering Puzzles, Programming Problems, and Solutions by Herb Sutter
• Efficient C++: Performance Programming Techniques by Dov Bulka and David Mayhew
• Practical C++ Programming, Second Edition by Steve Oualline

C++ STL and Boost

• STL Programming from the Ground Up by Herbert Schildt
• The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis
• The C++ Standard Library Extensions: A Tutorial and Reference by Pete Becker
• Generic Programming and the STL: Using and Extending the C++ Standard Template Library by Matthew H. Austern
• Extended STL, Volume 1: Collections and Iterators by Matthew Wilson
• Beyond the C++ Standard Library: An Introduction to Boost by Björn Karlsson

C++ Templates and Generic Metaprogramming

• Modern C++ Design: Generic Programming and Design Patterns Applied by Andrei Alexandrescu
• C++ Templates: The Complete Guide by David Vandevoorde and Nicolai M. Josuttis
• C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond (C++ In-Depth Series) by David Abrahams and Aleksey Gurtovoy

Stack of bits, what will remain?

You have a stack A of 256 bits, 13 are set to 0 and 243 are set to 1. In addition you have an additional stack B of 128 bits all of them set to 1. Until A is empty, you extract two bits from the top of the stack A:

• if the two extracted bits are different, then you discard the the bit set to 1 and push back the bit set to 0 into the stack A ;
• if the two extracted bits are equal, then you discard both of them and push into the stack A the a bit extracted by B;

What will be the last bit in the stack A?

An array of N bits, split in two parts with same amout of bits set to one

You are given an array A of N bits. I tell you that K << N are set to one, and the remaining are set to 0. You don't know what bits are set to one and what are not. You just know the amount.

What is the optimal time and space complexity to split the array in two parts such that the number of bit set to one are equal in both the parts? The two parts may be or many not be contiguous. In the latter case, you can provide two sets of indexes for A as answer.

A beautiful multi-core optimization

The article Fast String Search on Multicore Processors describes an interesting implementation of classical Aho-Corasick string matching algorithm on the top of the Many-core Cell processor.
It's impressing the speed-up improvement you can reach when you hash both the automata states and the input symbols ids. This reduces the contention in main memory access and it allows to leverage all the power of your playstation.

Beatiful Books in IR, Data Mining and Machine Learning

Information Retrieval & Web IR

• Introduction to Information Retrieval by Christopher D. Manning
• Managing Gigabytes: Compressing and Indexing Documents and Images by Alistair Moffat and Timothy C. Bell
• Mining the Web: Discovering Knowledge from Hypertext Data by Soumen Chakrabarti
  
• Google's PageRank and Beyond: The Science of Search Engine Rankings by Amy N. Langville
• Information Retrieval: Algorithms and Heuristics by David A. Grossman

Data Mining

• Data Mining: Practical Machine Learning Tools and Techniques, Second Edition by Ian H. Witten
• Data Mining: Concepts and Techniques, Second Edition by Micheline Kamber Jiawei Han
• Principles of Data Mining by David J. Hand, Heikki Mannila, and Padhraic Smyth

Machine Learning

• Machine Learning by Thomas Mitchel
  
• Introduction to Machine Learning by Ethem Alpaydin

Programming

• Programming Collective Intelligence: Building Smart Web 2.0 Applications by Toby Segaran

Hashing, Shingling and HashTrees

Hashing is my favorite methodology for data mining, machine learning and information retrieval. For computing “similarities” between a set of N objects (such as text, images, videos, web pages, etc), you need two steps:

1. define a distance metric among objects;
2. compute the matrix of distances in O(N^2);

In many situations, this is too expensive. Here it comes the magic of hashing. Each object is hashed to a bucket. The hash becomes the fingerprint of the object. Then, you can safely compare only to objects belonging to the same bucket. In many practical application you have a resulting complexity which is almost linear. The process becomes:

1. define the fingerprint of the object;
2. map the object to buckets; one different bucket for each different fingerprint;
3. compare directly the objects in the same bucket.

Shingling is one of my favorite hashing technique. Here a fragment of text (a shingle) is hashed with multiple hash functions. Intuitively, if you take two different fragments the more similar they are, the more frequently multiple hash functions will produce identical results (when they are applied to the fragments). Shingling has a rock solid mathematical foundation. In a previous post, I enclosed a C++ code for shingling.

Another interesting hash technique is the HashTree construction. Here an order set of items (itemset) is hashed with an hash function. The hash of item in position i-th is used to select a specific children of the node currently visited. In short, hashing is used to drive the visit of a path from the root to a leaf. Each leave of the HashTree contains a bucket, where similar itemsets are stored. The main difference with shingling is that order is preserved and that to items are considered as candidate for similarity if their hash collides in the first k positions. It turns our that this property if very useful for computing frequent itemsets in the Apriori algorithm. Here you have the C++ code for HashTree.

Tower of cubes

You have a set of solid 3-d cubes. Each cube has 6 faces, with different colors on each face. Cubes have different weights. One cube can be put on the top of the other if and only if (a) the two touching faces have the same color, and (b) the lighter cube is above the heavier one.

Find the height of longest tower that you can build, in optimal space and time.

Network of proxies

Suppose that you have N web clients connected on a network. The network is represented with a graph G = (N, E). A certain number of clients can cache a small amount of the content they download. In this case, they can act as proxies for other clients.

1. How do you choose the clients which are promoted to proxies?
2. How do they index their content?
3. What content do you prefer to cache?

Can you think about metrics to evaluate your proposed methodologies for (1, 2, 3)?

Myriad of virtues of Weka data mining toolkit

Weka is the swiss knife for data miners, with support for classification, clustering, regression, features selection and filtering. Data Mining book by Ian H. Witten and Eibe Frank discusses the 2005 version of Weka. I suggest using Weka for a rapid evaluation of your data mining protototypes and then a c++ robust implementation of the specific algorithm chosen.
Here you have the Weka documentation available on line with the Weka 3.6.0 manual.

Edit step ladder

Yet another edit step game. This time you have a dictionary of words D. A word wi can mutate into a word wj if a single character is added, deleted, or changed. This operation is called edit step. An edit step ladder is a lexicographically ordered sequence of words w1... wn, such as the transformation from wi to wi+1 is an edit step. Find the longest edit step ladder in D in optimal space and time.

Web mis-spell, edit distance and graph search

"Britnay spers" who is that girl? ... Hmm this name is a common misspell of the "Britney Spears". Misspelling is an important part of Web search. You may want to suggest the "correct" and "closer" alternative query, when a user submits the "wrong" one. Under certain conditions, you may want to re-write the query in a transparent way and provide directly search results for the "correct" alternative query.

Here it is a set of spelling related problems.

1. Given two strings s, t such that |s|=n, |t|=m, compute the edit distance(s, t). You may assume different costs for insert, delete, and substitution. You can make this in O(mn) and space O(min { m, n } )
2. Given a set of words S = { w1, ... wk } an accettable bidirectional mutation (wi <-> wj) for the word wi is a word wj, such that edit_distance(wi, wj) < T. Suppose you can access a large query log Q of queries previously submitted to a search engine. Suppose that a user rewrites the word wi into the word wj within a distance D of queries submitted during her search session. In this case, you call the mutation (wi -> wj) real. Note that this mutation is in one direction only. A real accettable mutation is an accettable mutation which is both real and acceptable. A frequent real mutation is a mutation which appears in at least F different users' sessions. Given a configuration (Q, T, D, F) find all the frequent, real and acceptables word mutations. What is the optimal complexity in time and space?
   
3. Find the diameter of the graph G formed considering all the frequent, real, acceptable word mutations (wi -> wj).
4. A sentence is an order sequence of words. For instance, "britney spears" is different from "spear britnery". How can you deal with mispelling in case of sentences?

Here you have the C/C++ code for edit distance.

K-means in C++

K-means is a classical clustering algorithm..
Here you have a C++ code for K-means clustering.

(Edit: 12/05/013)
See also my more recent posting A new lighter implementation of K-means

Strange equations

What solutions for?

Generate two greek crosses given a greek cross

Given a greek cross, generate two of them with the minimum amount of cuts.

You can solve Rubik in 25 moves

Tomas Rokicki has proved that Twenty-Five Moves Suffice for Rubik's Cube. Actually, he proved that no configuration takes 26. He also gives a nice greedy algorithm. My only perplexity is that a 180 degree rotation is considered a move. When I was young I thought they were two moves.

Viterbi Algorithm in Boost and C++

The Viterbi algorithm was conceived by Andrew Viterbi in 1967 as an error-correction scheme for noisy digital communication links. The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events.

In 2008, Viterbi won the Millennium Technology Prize "for the invention of the Viterbi algorithm, the key building element in modern wireless and digital communications systems, touching the lives of people everywhere.". It's interesting to note that in 1960s nobody could imagine a general application for the algorithm, so Viterbi followed his lawyer's advice and did not patent it. More information about Viterbi are given by this nice article by DrDobbs.

Here you have the Viterbi code in C++ adapted by the one of Božský Filip for using boost and a bit cleaner interface.

A beautiful solution to the ordered generation of hamming numbers

The hamming problem has an interesting variant. That is generating the numbers in ascending order (e.g. quoting wikipedia "regular numbers are often called Hamming numbers, after Richard Hamming, who proposed the problem of finding computer algorithms for generating these numbers in order.").

It turns out that a beautiful and compact solution is obtained by using 3 queues (Q2, Q3, Q5). The solution produces numbers in order and without duplicates. Time complexity is linear in the size output space. Hmm ... intuitively space should be constant in the output space, but still I need to think a bit about it... Here you have the C++ code for Hamming numbers in order and without duplicates. No need to explain the algorithm here since he code is self-explaining.

Myriad virtues of (Generic) Patricia Trees

Patricia Trees is a interesting variant of tries with a large range of applications ranging from IP lookup, to Web query suggestion, to word completion and spelling suggestion on your mobile phone. Anytime you have a string prefix and need to complete it with all the known variants available in your pre-built dictionary, well .. in this cases, you may want to consider Patricia trees.

Here I found a nice C++ generic implementation of patricia trees. This should be added to Boost template library!

Old but gold: Wavelet transform (and image clustering)

This series of three articles from DDJ are old, but still very interesting. The Fast Wavelet Transform (FWT) introduces this O(N) transformation which improves "old" FFT O(N logN). A Wavelet Analyzer introduces the recursive computation of wavelet coefficients tree. Here one of the most impressive property of wavelets is expressed in all its power. Each level of the tree is a more detailed approximation of the original data. The Wavelet Packet Transform is an interesting evolution of FWT. If you want to get more information, Wikipedia has more information on wavelets.

In short, wavelet transform enables analysis of data at multiple levels of resolution. This is useful in many contexts. For instance, it has been succesufully apploed to Similarity detection and clustering of images for fast ranking and clustering of similar images.

Web search ranking and spamming as Nash equilibrium game

The paper Network Reputation Games by Hopcroft, J. and Sheldon, D. October 2008 gives a nice interpretation of link creation process and Pagerank score as a game with Nash equilibrium.

Generalizing the above, I wonder if Web spam and search ranking process can be jointly modeled as a game with Nash equilibrium. In other words, let's suppose that search engines make public their search ranking algorithms (ehmm) together with their demotion strategies for web spammers.

The benefit for search engines can be measured in terms of increase of market share. The benefit for content providers can be measure in terms of positions in the ten blue links or in terms of referral traffic generated by search engines. There is a non zero probability that a spammer is identified. In this case, its ranking is demoted and the referral traffic will have a drammatic decrease.

Under what conditions this is a game with a Nash equilibrium?

Betting with advisors

There are 3 men/advisors: one of them always says the truth, while the other two can lie. A man writes either 0 or 1 on a piece of paper. Then, he shows the number to the other men who will tell to you the number.

You are given a fixed amount of money M. If you bet x money and you win you will increase your richness of x units, otherwise you will decrease your richness of x units.

What is the maximum amount of money you can guarantee to win?

Web search ranking and GPU Nvidia CUDA many core computation

Many search ranking algorithms involve a multiplication between a [very large and sparse] matrix and a full vector (e.g. PageRank with power method) or can be re-casted into this type of problem (e.g. HITS, some of the new learning to rank methodologies, etc).

GPU computation performs parallel blocks based multiplication, where each block is assigned to a grid of threads running on separate core. I have 18 cores on my sony notebook (16 on GPU and 2 on CPU) and that is a lot of power!

1. GPGPU: CUDPP provides a library for parallel multiplication based on classical parallel prefix approach. I tested some code (adapted to run on windows vista by myself) and this approach looks quite promising;
2. IBM proposes a closed-source solution for sparse matrix - vector multiplication. Declared performance is interesting but I don't know the internals of their proposed approach;
   
3. This technical report from NVIDIA tackles the problem with an interesting mix of algorithmic and engineering solutions: N. Bell and M. Garland. Efficient sparse matrix-vector multiplication on CUDA. NVIDIA Technical Report NVR-2008-004, December 2008. [PDF] [Online].

In short, I believe that having low cost GPUs open a new exciting scenario for linear algebra computations. This model can make search engines save a lot of money.

CUDA and Sony vaio FZ21M configuration (part II)

Many people sent me mails asking information about how to run CUDA on a sony vaio FZ21M. Here you have the requested steps:

1. Install Visual C++ Express 2005. Cuda 2.0/2.1 needs express 2005 in order to compile. If you have Express 2008 you need to install 2005 as well;
2. Install CUDA drivers from http://www.laptopvideo2go.com/. I installed 185.20 Vista 32bit - 2008-12-26 version with Modded INF;
3. Install CUDA toolkit and CUDA SDK. I run v2.0 because CUDPP does not run on 2.1;

When you compile deviceQuery you get the result shown in the picture.

Cuda: massive parallelism on my notebook sony vaio FZ21M

Cuda is a parallel computing architecture developed by NVIDIA. Nvidia GPUs have a parallel "many-core" architecture, each core capable of running thousands of threads simultaneously. I installed CUDA 2.1 on my Sony notebook Vaio FZ21M with Geoforce 8400M by using the modded drivers available at http://www.laptopvideo2go.com/

CUDA supports C, C++, Python, and Fortran. The paper Fast N-body Simulation with CUDA describes an a CUDA parallel program which runs 50 times as fast as a highly tuned serial implementation for the N-body simulation program. Wow! this is amazing. I still remeber my parallel implementation on Cray T3E, with 128 alpha processors. More than 10 years ago.

Well, now I have thousands of threads running on a multi-core GPU under my fingers (plus the dual-core CPU). Cuda documentation is pretty extensive. I am right now studying the CuBlas libraries for linear algebra and starting to code.

Here you have an introduction to cuda by the way of Dr. Dobbs

Optimal prefix-suffix matches

You are given a finite set of string S = { s1, s2, .... sn } over a finite alphabet Σ. Two strings s1 and s2 have a prefix-suffix match if s2 has a prefix α which is a suffix of s1 (i.e. s1 = φα, s2 = αλ ). In this case the strings can be joined in a superstring φαλ and the value of this join is | α |. In this case s1 is tail-joined and s2 is head-joined. If a string is tail(head)-joined, it can not be tail(head)-joined again with other strings. Find the combination of prefix-suffix matches in S with maximum value.

Cheating wifes

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Coin changes and dynamic programming

Coin Change is the problem of finding different ways of making changes for a particular amount of cents, n, having an infinite amount of coins available. For instance, how can you change 10 dollars having an infinite amount of nickels (1 cent), pennies (5 cents), quarter (10 cents), dimes (25 cents), one dollars?

Well this is the typical problem that you can solve by using dynamic programming.

Generating Web Graphs with RMAT and Eigen template c++ library

R-MAT: is a recursive model for graph mining. It has some useful properties:

1. On-line property. The number of nodes and edges can change with times;
   
2. Power law degree distribution property;
   
3. Small world property: diameter is much smaller than the order of the graph;
4. Many dense bipartite subgraphs. The number of distinct bipartite cliques is large when compared to a random graph.

RMAT recursively subdivides the adjacency matrix in four equal quadrants and selects one of the four quadrants with unequal probability (a, b, c or d). When the selected portion is a 1x1 cell, the corresponding direct edge is set.

Here you have the RMAT C++ code implemented with Eigen template library. As an example, I report the timings taken on my VMware virtual machine (guest: Linux Ubuntu with 1GB memory, host: Windows Vista Professional, core duo, 4Gb)

• 2^16 nodes, 8*2^16 edges; real 0m6.453s
  
• 2^18 nodes, 8*2^18 edges; real 0m53.253s
• 2^20 nodes, 8*2^20 edges; real 2m17.383s
• 2^21 nodes, 8*2^21 edges; real 7m26.611s
  

I believe that these performance can be further improved by adopting fixed-size matrices, with size defined at compile time. Well, running on a dedicated server and not a virtual machine may help as well. But this is not bad, the library is pretty good for rapid coding!

Eigen -- A generic matrix library for linear algebra computation

Eigen is an interesting library for Matrix computation in C++. It supports all the common operations for linear algebra with vectors, matrices, fixed-size (known at compile time) and dynamic (allocated at compile time), full or sparse. Coding with Eigen is pretty fast and intuitive. Implementing an algorithm on top of Eigen feels like just copying pseudocode. I think that it would be great to have it included in Boost. Benchmarks show that the resulting code is pretty fast and optimized at compile time.

I am currently coding a model for Web graph generation (see R-MAT: A recursive model for graph mining). I think that I will post the code pretty soon.

Overlapping rectangles

A set of rectangles has one border parallel to the x-axis of a Cartesian plan. Find the set of overlapping rectangles in optimal time.

Hamming numbers III

It is possible to generate the hamming numbers without duplicates. The key intuition it to generate the sets:

1. M2 = { h : h=2^l , l \in N, l < max }
   
2. M3 = { h : h=3^o , o \in N, o < max }
   
3. M5 = { h : h=5^p , p \in N, p < max }
   

Then we generate:

1. M23 = { i : i = h*k, h \in M2, k \in M3}
2. M25 = { i : i = h*k, h \in M2, k \in M5}
3. M35 = { i : i = h*k, h \in M3, k \in M5}
4. M235 = { i : i = h*k, h \in M23, k \in M5}

Here is the code. Let's have a look to the complexity in terms of analyzed numbers. Let P the maximum integer you can represent. Then, generating the sets M2, M3, M5 takes O(logP), since |M2| <= log2(P) , |M3| <= log3(P), |M5| <= log5(P). As a consequence, generating M23, M25, M35, M235 takes (log(P))^2. We are sub-linear in terms of input and cubic in terms of output.

Hammin numbers II

One problem with the previous solution is the amount of duplicates we generate. For instance, starting from 2 we can generate 2x3=6. Starting from 3 we can generate 3x2=6. We need to remove these duplicates as soon as possible to avoid unneeded elements in H. A solution is to use set operations, which is "logarithmic in general, but amortized constant if t is inserted right after p". So the complexity of this solution is O(nlogn) in worst case, and O(n) in average since hamming numbers are sparse among large integers.

#include <set>
#include <iostream>
#include <limits.h>

int main(){

 typedef unsigned long long num;
 typedef std::set<num> Nums;
 typedef std::set<num>::const_iterator Nums_iterator;
 Nums nums;
 Nums_iterator it;

 nums.insert(1);

 for (it = nums.begin(); it != nums.end(); ++it){

   nums.insert(nums.end(), *it*2);
   nums.insert(nums.end(), *it*3);
   nums.insert(nums.end(), *it*5);
   std::cout << *it << std::endl;
 }
}

Hamming numbers

The set of Hamming numbers H is defined recursively. 1 is in H. The numbers 2h, 3h, 5h are in H, if h is a number contained in H. The first few hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, ... Dijkstra put the problem of computing efficiently the hamming numbers. What is your proposal?

Generic programming and out-of-the core computation

STXXL is a C++ library for extra large data sets. The library allows to write generic programs, with an idiom typical of STL, and to leverage the power of out-of-the-core computations for massive data-sets. I played with the library and I loved it.

1. You have the STXXL containers, which are similar to STL containers. Anyway, an STXXL container can be mapped to (multiple) external file(s) in a transparent way. Files may have different implementations that might be bases on various file systems or even remote storage interface. Examples of containers are:
   


• vectors: example: stxxl::vector v(64 * int64(1024 * 1024));
• map: example: stxxl::map
  
• queue: example: stxxl:queue
• stacks and priority queues


2. You can access the containers with STXXL Iterators and the library is taking care of all I/O operation, supporting large files up to dozens of terabytes even if they are mapped on multiple physical disks.
   


• unsigned int big_size = 1024 * 1024 * 2 * 16 * 16;
  typedef stxxl::vector vec_big;
  vec_big my_vec(big_size);
  vec_big::iterator big_it = my_vec.begin();


3. You can use a collection of STXXL Algorithms, similar to STL ones but for external memory:


• stxxl::generate(v.begin(), v.end(), stxxl::random_number32(), 4);
• stxxl::for_each_m(v.begin(), v.end(), square(), 4);
• ...
  


4. A particular mention goes to sorting algorithms for external memory:
   


• typedef stxxl::vector vector_type;
  const stxxl::int64 n_records =
  stxxl::int64(384) * stxxl::int64(1024 * 1024) / sizeof(my_type);
  vector_type v(n_records);
  stxxl::random_number32 rnd;
  for (vector_type::size_type i = 0; i < v.size(); i++)
  v[i]._key = 1 + (rnd() % 0xfffffff);
  
• stxxl::sort(v.begin(), v.end(), cmp(), memory_to_use);


5. This paper describes the library Stxxl : Standard Template Library for XXL Data Sets ; R. Dementiev, L. Kettner, P. Sanders "STXXL: standard template library for XXL data sets" Software: Practice and Experience Volume 38, Issue 6, Pages 589-637, May 2008 DOI: 10.1002/spe.844. See also the technical report.
   


6. Here you have a collection of example codes; performance are pretty good, and some stxxl users have reported that stxxl sort is much faster than UNIX sort. In addition, i found this paper which reports very good performance (Breadth first search on massive graphs). Do not forget to consult the STXXL forum if you need any help.

Economy does not look good.

Off-topic: one picture is enough to explain current situation with the economy.

Banks Merging and Acquisition (M&A)

Bank system is going crazy. One solution is to merge all of them together under a central authority. You have N banks at the beginning and they are combined into a single bank at the end. How many different configurations of merging are possible?

Longest common substring, subsequences, increasing subsequences

String gurus are excited about long stuffs. It turns out that such theoretical researches have a lot of practical applications.

1. Longest Common Substring (LCS): it has applications in biology (gene analysis) and Web-IR (clustering, features' extraction) and many others. Given two strings S : | S | = n and T : | T | = m, finding the common substring has complexity O(nm) by using dynamic programming. In alternative, a generalized suffix tree (GST) can be built in linear time, if the size of the alphabet is constant. Once the GST is built, you can get the LCS by visiting GST bottom-up. You need to annotate each internal node with the strings that caused its creation. The visit is linear in the length of the strings.


2. Longest Common Subsequences (LCSseq): Substrings are made up of consecutive symbols, while subsequences are not. For instance with web clustering, you may want to "skip" some symbol. In this case, you have to use subsequences instead of substrings. If you have two documents, you may want to compare where they are different (have you ever used the diff program?). There are two interesting proprieties, which are useful for a dynamic programming solution with complexity O(nm)
   
   
   • LCS(X_n, Y_m) = (LCS( X_n-1, Y_m-1), x_n), if the string X_n, Y_m both ends with the symbol x_n
   • LCS(X, Y) = the longest sequences of LCS(X_{m – 1}, Y) and LCS(X, Y_{n – 1}), this is useful when X_n, Y_m do not end with the same symbol
   • LCS({}, {}) = 0
   
   Running time can be reduced by adopting memoization. Space can be reduced by using hashing.
   
   
3. Shortest Common Supersequence (SCS) is a common super-sequence of minimal length. Think about merging two documents. For two input sequences, an SCS can be formed from an LCS easily, by inserting the non-lcs symbols while preserving the symbol order


4. Longest Increasing Subsequence (LIS): Here symbols have an order (lexicographical, numerical, etc) and you want to find the longest common subsequence that respects this order. The longest increasing subsequence of a sequence S is the longest common subsequence of S and T, where T is the result of sorting of S. The algorithm is quadratic, but it is possible to give an O(nlogn) algorithm.
   

Magy! how to rank a web search result

Magy! engineers are trying to identify new methodologies for ranking web search results. After all, the academic literature has been evolved around three main ideas:

1. Web links
2. Text Score
3. Query logs

We saw my interesting developments, but no real break-trough in different directions. Do you have any additional idea to rank web search results?

Magy! search result clustering and the next search UI

Search UI is still the same since the beginning of search era. True: the 10 blue links model is a solid one, but is there any other innovation ?

Many people are thinking that blending is the next frontier, with champions such as Ask.com and Google. They mix and shake together results coming from different search domains, such as news, images, blogs, questions, products, and the like. The result is a sense of more variety, more freshness and, after all, a better user experience.

Personally, I do think that we need to try different UIs in response to different search queries. Back in 2000, I was a big fan of Northern Light folder's organization, which later on evolved into the Vivisimo's web hierarchies adopted by Clusty, and in a series or Academic reseach proposals about web snippet clustering.

I think that next UIs will be obtained (a) by leveraging cool graphical proposals and (b) by solving basic algorithm problems which apparently have no relationship with UI.

For instance, here it is one problem for our proud Magy! engineers.

• Given an array of strings, find the longest common substring in optimal time

It turns out that this the solution of this problem can be very useful for web snippet clustering. Yet another example where theoretical researches may have interesting pratical applications.

PS: you may be interested to have a look to suffix array and suffix tree data structures for solving this particular problem.

Dropping Swarovski Crystals

A building of 100 floors, there is a threshold N s.t. if a Swarovski Crystal from Nth floor and above it will break. If it's dropped from any floor below, it will not break. Given 2 Crystals, find this N, and minimize the number of drops for the worse case.

Maximum sub-array sum

Given an array of integers, find the sub-array of contiguous elements with maximal sum. In case of ties select the shortest sub-array.

Finding the the more frequent symbol in a stream of numbers

You are given an infinite stream of numbers, find the symbol that appears more frequently. At any instant, you are interested to symbols that appears more than 50% of times.

Happy or not?

A community of K people can be happy or not happy. Can you enumerate and generate all the possible states?

joining n segments

You are given n segments. In turn, you take each one of them and join it with one among those already selected, creating either a loop or a longer segment. How many loops there are in average, at every instant of time?

Covering a circle

You are given a circle and two players. When is his turn, each player will mark down a sign on cicle. Game stops when there is no more free space available on the circle. What is the winning strategy?

Find a number non in the sequence

You are given a sequence of m distinct numbers extracted by a set of 1...n numbers, with m < n. Can you give an efficient algorithm for identifying a number non in the sequence.

Boost::serialization for storing generic class

Boost serialization is a lovely collection for storing generic classes. Here you have example for serializing int, list of int, vectors of lists of floats (STL containers), and your own class.

Maximum sub-array product

Given an array of integers, find the proper sub-array with maximum elements' product, in linear time.

Bandwidth reduction, permutation of docs, fast pagerank

A common problem with research is that same results are achieved again and again with different names and in different contexts.

Matrix Bandwidth reduction is a well-known numerical analysis technique to reduce the bandwidth of a matrix. A quite famous method is the Cuthill-McKee algorithm. Other well-known techniques are the king ordering and the min degree ordering.

Recently, the similar techniques for bandwidth reductions have been studied in the context of document ids permutation for indexing compression (Index Compression through Document Reordering, Investigating the Effectiveness of Clickthrough Data for Document Reodering)

Lately, an interesting application has been suggested for Fast PageRank Computation

Boost provides an elegant and flexible support for Generic Graph representation. It also provides support for matrix bandwidth reduction.
Here you have the C++ code for boost matrix reodering.

Multiplying the other elements of an array in linear time

You are given an array X with n elements. Can you compute in linear time a new array A with n elements, where A[i] is the product of all elements in X, but X[i] is excluded. You cannot use division, you may use additional space

Magy: how can you improve the ranking time?

Magy!'s engineers are spending too much time in ranking search results. Their AlgoGuru said "well, we have n results for this search and this will cost us O(n * log n), we cannot be better than this. We must resort into heuristics and approximations such as stopwords, caching, index pruning, and the like".

A young and proud eng stood up and he said "Hey, I know that you are wrong. We can make this better from an algorithmic point of view and still get exact results".

Do you know why?

Finding a loop in a list

Suppose you have a list of integers and you don't want to use any additional storage.

1. Can you detect if the list has a loop?
2. If it has, can you identify the node with two incoming edges?
   

Counting frequent words in Boost

Counting frequent words contained in a file is a quite common operation.
It is surprisingly easy if you adopt Boost::Unordered_map and Boost::Tokenizer.
Here you have an example of code

Counting cubes and hypercubes

Consider a cube C1 (k=3 dimension) and suppose it has the length of a side n=3 (as the (g)old Rubik's cube).

• How many cubes there are on the surface of C1?

Now consider a cube C2 (k=3 dimension) and suppose it has the length of a side n (see Rubik Variations in wikipedia for examples of n=4, 5, 6, etc)

• How many cubes there are on the surface of C2?
  

Now consider an hypercube, a generalization of a cube in k dimensions.

• Let's start with k=4 dimensions. How many hypercubes there are on the surface of n * n * n * n hypercube with k=4?
• Now, generalize to k generic dimensions. How many hypercubes there are on the surface of n * n ..... n * n (k times) hypercube with k dimensions?

I like this problem since it's hard to guess a formula for the final question, but it is easy to derive it if you solve simpler problems first.

More than linear?

You have 10 bags full of colored balls. Nine bags contain N balls, and each ball weights 10 grams. One bag contains M balls, and here each ball weights 9 grams.

Can you identify the bag with M balls using a balance just one time?

Design Patterns : C++ full collection of Gamma's patterns

Full collection of Gamma's patterns in c++:

1. Creational: Abstract Factory, Builder, Factory, Prototype, Object Pool, Singleton,
2. Structural: Adapter, Bridge, Composite, Decorator, Facade, Flyweight, Proxy patterns,
3. Behavioral: Chain of Responsibility, Command, Iterator, Mediator, Memento, Observer, State, Strategy, Template, Visitor, and Interpreter

Better than logarithmic ?

You have 8 balls: 7 have the same weight, 1 has a different weight.

Can you identify the heavier ball by using a scale balance just two times?

Design Patterns: C++ Behavioral Design Patterns (part two)

Expand the collection of Behavioral Design Patterns in C++. Namely, Memento, Observer, State, Strategy, and Template

Magy! how can you identify adult images?

Magy! wants to launch an image search engine, where adult content is filtered.

Can you suggest few techniques for filtering adult images? Please, use your own fantasy ;-)

Design Patterns: C++ Behavioral Design Patterns (part one)

I continue my sum-up of design patterns. This time an initial collection of Behavioral Design Patterns in C++. Namely, Chain of Responsibility, Command, Iterator, and Mediator.

Bank system: better to conquer or to defend?

Bank system is having troubles. You are given a collection of K banks. Each bank has a certain amount of money (Mi). A bank i can decide to buy a bank j if its capital Mi is greater than the half of Mj (Mi > Mj/2). When a bank is controlled, its capital can be used by the controller.

A good CEO should decide what strategy to adopt for enlarging its control on other banks, and avoid to be controlled by other banks.

• Can you describe an (heuristic) algorithm for help the CEO?
• Given a solution, can you identify the best CEO (different criteria can be given: who has control on the largest number of banks, who has the largest amount of money, etc)?
  

Bill Gates ' paper on sort

Bill Gates published one academic paper on sort. You are given an array A of unsorted integers and the only allowed operation is to "flip" a sub-array. A flip(i) is an operation which reverses all the sub-array starting in position A[i]. Namely,

(A[1], .... A[i-1], A[i], A[i+1] ...., A[n-1], A[n])

is changed into

(A[1], .... A[i-1], A[n], A[n-1] ...., A[i+1], A[i])

Can you suggest a sorting algorithm based just on flip() operations?

PS: this sorting method has an impact on genetic studies and evolution of species.

PS: the paper is W. Gates and C. Papadimitriou, Bounds for sorting by prefix reversal (1976)

Design Patterns: C++ Structural patterns

I continue my sum-up of Design Patters. This time you have a collection of structural pattern skeletons.. Namely, Adapter, Bridge, Composite, Decorator, Facade, Flyweight and Proxy patterns.

Design Patterns : C++ creational patterns

Design Patterns are the swiss knife of any programmer. I read many times the book of the gang of four. Yes it is a seminal book, but there are too many words there and too little C++ code.

Therefore, I wrote sum up the patterns in c++ skeletons. Here you have the c++ skeletons for creational design patterns. Examples of Abstract Factory, Builder, Factory, Prototype, Object Pool, Singleton are given.

Dreaming a DARPA-like Obama plan for energy

I dreamed of a DARPA-like plan for energy. Obama has a great asset in Internet based technology companies. He can use this asset as one of the pillar for re-vitalizing the economy.

I hope that the other pillar will built as a result of a massive investment in energy innovation. I dream of seeing dozens of companies such as Tesla.

Data parallel multi-core C++ computations

Threading Building Blocks is a collection of generic containers and algorithms for performing data parallel multi-core computations. The key ideas is that the programmer should not deal with low-level thread and syncronization issues, but with an higher data-parallel paradigm. This reminds me somehow the old-time, old-school skeleton parallel computation, where the language gives a fixed number of parallel constructs which are optimized by the compiler.

TBB has a rich set of containers such as concurrent_vector, concurrent_queue, concurrent_hash_map, and data-parallel algorithms such as parallel_for, parallel_sort, parallel_while, parallel_scan, parallel_reduce, and compositions such as pipeline and task (see Tutorial | Reference Manual | Code Samples). I am playing with the library and I found it versatile enough.

C++ Multithread concurrent programming

Boost is my favorite choice and I suggest you to read the code of BOOST_THREAD class because it is very instructive. In version 1.36/37 there are some improvements. Here, I report the ones I like the most

1. You can create a thread and pass arguments to it (internally it uses boost::bind) as in

int k;
void thread_function   (int i, std::string s, int& j);
boost::thread t(thread_function, 10,"hello world", boost::ref(k));

Note that this is making a copy of the function, so any reference should be passed via boost::ref().

2. You can have a multiple-readers/one-writer lock which is useful in many situations, just have a look to shared_mutex class. Another useful features is boost::mutex::scoped_lock (which was already available in previous versions). It implements the RAII concept and therefore when the lock variable is out-of-scope, it is automatically unlocked.

3. You can try to lock up to five resources and if one of them is locked all the others are released. This is useful to avoid deadlocks. Have a look to try_lock()

4. Interruptions for threads

Other improvements are described here. Here you find a code that uses a number of these features.

Computing efficiently the Erdős numbers

From wikipedia: "In order to be assigned an Erdős number, an author must co-write a mathematical paper with an author with a finite Erdős number. Paul Erdős is the one person having an Erdős number of zero. If the lowest Erdős number of a coauthor is k, then the author's Erdős number is k + 1."

• You are given a collection of K papers, can you write an efficient algorithm for computing the Erdős number associated to each author?

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

Python web , rss, image crawler -- v2

Thanks for the comments to code v1. Here you have the Python web , rss, image crawler -- v2. Pylint 8.6 or something around that

A Python crawler for rss, html, and images

So I wanted to learn a bit of python. Well you know, I am used to script in Perl since 1997. Moreover, I am lazy. So why the heck I should learn a new language? Well let's say that the environment around me is full of these young and smart guys who love python. So I tried it. After all, it is nice to add another knife.

So where is the crawler? Here it is. Very compact. It uses Eventlet from SecondLife, a nice framework to support Async/IO and co-routines. The resulting code is very compact and it avoids all the pitfalls of calling a cascade of callbacks(). RSS/Atom feeds are parsed using feedparser.
Images are handled with PIL. HMTL pages are parser with Beautiful soap. Mysql is accessed with MySQLdb. Eventlet needs greenlet to run. The crawler downloads a bunch of rss/atom feeds, all the web pages referred by the postings, all the images contained in the web page. There is one single thread which performs all the network operations with pool of co-routines.

Boost::asio, Keep-alive, Boost::serialization

Boost::serialization is the ultimate solution if you want to send your objects trough a socket. I remember the old days when we were used to work with corba and similar stuff. Thanks to god this is not longer requested. This code is extending the async io server and serialize a test object. Ping messages are objects too. Generic programming is used to send as many different objects as you want. .. we are moving towards a full map reduce implementation

Boost::asio and Keep-alive

Boost::Asio is a very useful framework for portable networking. Same code can be used for all the unicies variants, macos and windows. Support for asynchronous IO is remarkable. It is possible to write a generic server and, then, specialize the framework for specific use. In this code, I experimented with portable keep-alive support using async no-op read() and asio timeout.