Antonio Gulli's coding playground

List of Best Paper Awards in Computer Science

2012-02-11T14:09:00.000-08:00

(seen this in my social graph of friends)

By Conference: AAAI ACL CHI CIKM CVPR FOCS FSE ICCV ICML ICSE IJCAI INFOCOM KDD NSDI OSDI PLDI PODS SIGIR SIGMOD SOSP STOC UIST VLDB WWW

Microsoft Research is the Top Institution.

Institutions with the most Best Papers

Institutions with Best Papers
Microsoft Research	22.9
Carnegie Mellon University	20.8
Stanford University	19.8
University of Washington	19.0
Massachusetts Institute of Technology	15.3
University of California Berkeley	13.5
Cornell University	10.9
University of Toronto	10.4
University of Illinois at Urbana-Champaign	9.3
University of British Columbia	8.8
University of Texas at Austin	8.4
IBM Research	8.0
University of Oxford	6.2
Georgia Institute of Technology	5.8
University of Maryland	4.8
AT&T Laboratories	4.8
Weizmann Institute of Science	4.5
Yahoo! Research	4.4
McGill University	4.4
University of California San Diego	4.1
University of California Irvine	4.0
Rice University	3.5
École Polytechnique Fédérale de Lausanne	3.5
Princeton University	3.4
Google	3.4
University of Massachusetts Amherst	3.4
Brown University	3.3
Bell Labs	3.3
Technion	3.1
Columbia University	3.1
University of Michigan	3.0
University of Alberta	3.0
Hewlett-Packard Labs	3.0
ETH Zurich	2.8
University of Wisconsin	2.7
Max Planck Institut	2.6
Ohio State University	2.4
University of Nottingham	2.4
Duke University	2.3
University of Pennsylvania	2.3
Université Paris-Sud	2.1
Tel-Aviv University	2.1
Saarland University	2.1
National University of Singapore	2.0
Polytechnic Institute of New York University	2.0
University College London	2.0
University of Cambridge	2.0
Universidade Técnica de Lisboa	2.0
Indiana University at Bloomington	2.0
DePaul University	2.0
BBN Technologies	2.0
NASA Ames Research Center	2.0
NEC Labs America	2.0

Calculate x^y in optimal time

2012-02-08T06:59:00.001-08:00

You have to store a huge graph of 1billion of nodes

2012-02-07T07:01:00.000-08:00

How?

order by RAND()

2012-02-06T07:28:00.000-08:00

mysql allows to perform an "order by rand()" any idea of how this can be useful?

Search is so boring, what if we stop sending queries?

2012-01-30T23:34:00.000-08:00

First search engine I ever saw was Lycos pursuit back in 1994 (wow long time ago!). The key idea in pursuit was to have a crawler collecting documents, and a search form where you had the opportunity to submit queries/keywords for retrieving relevant results. Now, after 17 years search paradigm is ,,, still the same! just more relevant and working on a larger scale. Anyway, the paradigm is still the same. Really?

So that's boring. I don't like being bored.

After leaving Ask.com and before joining Microsoft, I had this idea of a new startup. One of those ideas I have every 4-5 weeks. I never realized it, so now I put it here for free and if you want you can pick it and make money out of it. After all, ideas are for free but the execution is not.

Imagine you visit a place and prepare a video guide about this place you are visiting. You go on your favorite restaurant and you record a video with your impressions and comments. You go in an hotel and you record another video. You go to the visit a shopping area and you record another video. You record your own videos pretty much in every location and your mobile will upload them in my server.

Then every time someone will come closer to that location my service will push your content to those people.

No queries, just the location. Searches will happen on your behalf.

Relevance can leverage a ranking on the video contributors, their social network, how much their contribution was appreciated in the past, and many other factors that I will not discuss here
Monetization can leverage the location and it will have several opportunities.

So this is an idea for you to pick and execute.

Search, with no queries.

Books: "Cracking the coding interview"

2012-01-24T23:37:00.000-08:00

Cracking the coding interview is one book you should definitively have in your bookshelf, and you should keep reading it now and then.

I have a passion for reading and solving coding interview questions and never found such a detailed source of information.

The book starts with several suggestions on how preparing yourself for an interview. This is an aspect that many people underestimate, whilst having a well-written CV, a personal blog, and possibly a number of open source projects is definitively important. This book gives you a number of good suggestions.

Then there is long part discussing interview questions with a broad coverage of basic data structures, algorithms, programming languages, databases and threads and some advanced coding questions.

The style is concise and you can read each Chapter in isolation. Gayle made an amazing job in illustrating not just the solutions, but several techniques that you can use for solving new problems. Plus, those interview questions, the solutions and the techniques, are not just hypothetical but are very useful in your day by day life as Dev or Researcher.

I would suggest the author splitting the Chapter 7 "Mathematics and Probability" into two separate parts and expand both of them because they are very important during interviews and the current description is probably too synthetic. Also, a Chapter on String algorithms and another one on Parallel programming would be probably useful to have because people will look for them elsewhere.

Having said that, this is definitively a must have book and the money you spend will definitively generate a great return on the investment.

Thanks Gayle for writing it.

Compute if a number is a multiple of 5

2012-01-07T23:33:00.000-08:00

You can use just bit operations

Discuss memory layout for C programs

2012-01-07T00:11:00.000-08:00

Ideally you should discuss all the different areas that are used

Find if there is a number duplicated in an array

2012-01-06T23:24:00.000-08:00

Good collection of different techniques. useful to know.

Let's talk about C++ const

2012-01-05T23:13:00.000-08:00

when and where do you use it?

Sphinx: open source search

2012-01-04T10:45:00.000-08:00

Sphinxsearch is a scalable open source search server that seamlessly integrates with Mysql. Documents are stored in mysql and the server creates its own external indices. The index and search performance are quite good (60+ MB/sec per server, 500+ queries/sec), and the server allows to easily extend your own ranking functions. A sql-like language is supported for searching. Apparently, the largest cluster of sphinx servers is currently indexing 3billions of documents and it serves 50M queries per day. An interesting feature I am going to use is the ability to search all the geo-points within a fixed radius.

News dataset

2012-01-03T11:26:00.000-08:00

Republishing my link to the open collection of news articles.

AG's corpus of news articles

Openlayer: an example of geo-location

2012-01-02T22:03:00.000-08:00

Openlayer an example of map switching

2012-01-01T21:56:00.000-08:00

Openlayer

2011-12-17T21:23:00.000-08:00

Openlayer offers a programmatic way for accessing bing, google, yahoo and other maps system with one javascript api. I am using it for my next playground project.

Points of Interest

2011-12-16T21:09:00.000-08:00

Openstreetmap has a collection of 2.5M points of interest distributed world wide. I am using them for my next playground project.

(n & (n-1)) =- 0

2011-12-15T05:59:00.001-08:00

Check if a list of characters is palidrome

2011-12-14T13:30:00.000-08:00

It would be easy to compare it if you have an array, some additional difficulties because you have a list. Not that much.

Given a string s and a regular expression r match the regular expression

2011-12-14T09:41:00.000-08:00

Supported operators :

^, match the beginning of the string
$, match the end of string
* match a sequence of characters
[a-z][A-Z] matches the correspondent character
Assume that there are no parenthesis

Solution

this is an interesting application of recursion

Subsequence

2011-12-13T10:49:00.000-08:00

Find the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence

Solution
Max(i) = max(Ni + Max(i+2), Max(i + 1)) foreach i

Compute n to the power of m

2011-12-12T17:20:00.000-08:00

You can make it in log (m) and that's a nice thing. X^8= (X^2)^4 so i can actually reduce the size by half at each step. Anyway if n is odd there is the need of an additional multiplication X^9=X * (X^8).

Compute (n k)

2011-12-12T15:47:00.000-08:00

The solution to this should be recursive and similar to the classical fibonacci one,
given that (n k) = (n-1 k-1) (n-1 k)

A couple of new features to PicPlacer

2011-12-11T06:39:00.000-08:00

Mario added a couple of new features to PicPlacer (I wanted to have more time to work on this myself). Now it's possible to tag a whole album with a location and to search locations.

A robot is moving in a rectangular board

2011-12-10T06:40:00.000-08:00

It can move either down or right and the board is N x M. How many path does the robot have?

Solution:

Steps are N+M and we can chose N, so ( N+M N) is the binomial factor we are looking for.

A children can hop either 1, 2, or 3 steps in a stairway of N steps.

2011-12-09T06:40:00.000-08:00

How many combinations do you have?