No account? Create an account
 mrigmarichika [entries|archive|friends|userinfo]
viked

 [ userinfo | livejournal userinfo ] [ archive | journal archive ]

 Moved [Mar. 31st, 2008|03:40 pm] viked to http://gooeylumpdump.blogspot.com/. Will try to update both places for some time so that this blog gracefully goes into internet graveyard. Link 4 comments|Leave a comment

Random Surfing with a twist [Mar. 28th, 2008|09:51 pm]
viked
 [ Tags | algorithm maths puzzle ]

The famous random surfer model of pagerank (the not so secret sauce of google) is that you start surfing the net from a random point. Then every time you either follow one of the links on that page or you jump to another random page on the net. You keep on doing this indefinitely and probability of you landing on a particular page is its pagerank.
Now of course this intuition needs to be quantified and turned into mathematical equations to compute the pagerank. This is how it is quantified.

So let us assume Google uses this mathematical model, does heavy number crunching and computes the pagerank of each page. Now what your random surfer does is that he doesnt jump to a random page with equal probability. Instead whenever the coin lands tail, he goes to Google, enters a random query and goes to the first result shown by Google. Now what is the probability of jumping to a page. It clearly is not 1/n because a page with high pagerank would have migh higher chance of being jumped to. It also depends on the set of queries for which a page is returned. But to simplify our model we assume that jump probability to a page is proportional to its pagerank. So now our teleportation vector will have the ith entry as (pagerank of i) / (sum of all pageranks). Now Google uses this vector and recomputes to get a new set of pageranks. But this recomputation once again changes the teleportation vector thus changing the pagerank thus changing the teleportation vector thus changing the pagerank and so on.

So is there a fixed point for this iteration? Is this problem interesting? Is there some work on this?

Partitions and Compositions [Mar. 24th, 2008|09:26 pm]
viked
 [ Tags | math puzzle ]

A puzzle recently asked by a friend led me to consider various forms of partitioning a number. There are three ways essentially and for two of those I could find nice closed form solutions for number of partitions and for the third I could only find a recurrence.

1. Composition: A k-composition of a positive integer n is k positive integers which sum up to n. So for example a 2-composition of 4 would be 1+3 or 2+2 or 3+1. Notice that 3+1 and 1+3 are different compositions, so order of the k numbers matter. To find out the number of k-compositions, consider a scale on which we have marked numbers from 1 to n. Now we have to break the scale into k integral parts to form one composition. So a scale of length 4 can be broken at 1,2 or 3 to get different 2-compositions. Breaking the scale means selecting k-1 points at which we break out of n-1 possible break points. This can be done in (n-1)C(k-1) ways which is our desired answer.

2. Weak Composition: This is same as composition except that now some of the parts can be of 0 length. 3-Weak Compositions of 4 would be 0+1+3, 1+0+3, 2+0+2 and many more. Now how do we find number of k-weak compositions (referred as k-WC from here on). One natural way to think about this (the direction I first went in) is that removing all 0s from a k-WC would give k'-C where k'<=k. In fact for each k'-C we can put (k-k') 0s to form a k-WC. In how many ways can we insert these 0s. We have to pick (k-k') positions out of k positions where we will put zeros and this can be done in kCk' ways. There total number of k-WC formed from k'-C would be
kCk' * (n-1)C(k-1).
Adding this over all k' from 1 to k gives us
Sigma(i=1 to k) kCi*(n-1)C(i-1).

But this is not a satisfactory solution and I do not how to manipulate this summation to simplify it further. So I started looking for a different way to arrive at solution. After lots of head scratching, suddenly out of nowhere this fact hit me. If I add one to each number in k-WC of n I would get a k-C of n+k. This is because in total I am adding k and also none of the numbers would now be 0. For eg adding 1 to each number in 0+1+3 I get 1+2+4 which is 3-C of 7. After realising this fact it is not too difficult to prove that there is one to one correspondence between k-WCs of n and k-Cs of n+k. And we already know the formula fo k-Cs of n+k which is
(n+k-1)C(k-1).
This is also the formula for number of k-WCs of n.

3. Partition: This is same as composition except that now the order of numbers doesnt matter. So 1+3 and 3+1 are same partitions. I could not find a closed form solution for number of k-partitions but I could find a nice recurrence relation which can then be converted into dynamic programming algorithm. If 1 is the smallest  number in a partition then remaining k-1 numbers add to n-1. Therefore number of such partition is same as (k-1)-Ps of n-1. But if the smallest number is greater than 1 then what do we do. Well  we can subtract 1 from each number to get a valid k-P of n-k. For eg subtracting 1 from each number in 2+2 gives me 1+1 which is a 2-P of 4-2=2. Therefore number of such partitions would be same as number of (k)-Ps of n-k. So total number of k-Ps of n is
(k-1)-Ps of n-1 + k-Ps of n-k.
This could be easily converted to a DP algorithm with O(kn) space and time complexity.

a) Why wouldnt this same recurrence work for Compositions?
c) Can you find a better algorithm for Partitions?

Dependency Injection [Dec. 28th, 2007|02:45 pm]
viked
 [ Tags | java, programming, software ]

I have been reading a bit about Guice, a dependency injection framework by Google. Here is a small introduction of dependency injection in general which I thought of just to clear my own understanding. Most of the terms and concepts here have been borrowed from this Guice document just reworded.

1. Prelude
We have a class called Employees that return me the details of an employee with a particular Id. Now the employee details are stored in a database so Employees will need to open connection to database and fire a sql query. We might write it like this

public class Employees {
JdbcDriver driver;
public Employees() {
driver = new MysqlJdbcDriver();
}

Employee getEmployee(int id) {
driver.query("query to ger employee with id");
// populate Employee
return Employee;
}
}

On one hand this is a good design because it hides the fact that things are store in a database from its users. But this comes at the cost of flexibility. Tomorrow if my records are moved to a a different type of database then I will have to change the souce of Employees. Bigger pain this causes is in unit testing. Only way to test this class as it is now is to create a test database, populate it with some sample fields and then test it. But then my tests can fail due to database errors even though the logic in this class is fine and they will be slow because of database queries. Ideal way to unit test such classes is to mock all the dependencies on external factors such as database in this case.

2. Dependency Injection
That is possible only if the class allows us to set the driver either in its constructor or through some setter. Then we can pass it a dummy implementation of JdbcDriver. So we rewrite our constructor as

public Employees(JdbcDriver driver) {
this.driver = driver;
}

Now while creating Employees we can decide what kind of driver we want to pass to it. This is known as dependency injection where a class instead of creating its dependencies has them injected by the caller. Now this leads to two issues:

1. Lots of clutter in your caller such as
to create an object of type A we might have go write something like this:

C c = new CImpl();
D d = new DImpl();
E e = new EImpl();
B b = new BImpl(c, d, e);
A a = new AImpl(b);

2. Even though all we cared about is A we ended up knowing and importing B, C, D, E. This information should have been hidden from us.

3. Dependency Injection using Factory
One way to solve this problem is by using factory. Factory as the name suggests is a Class that knows how to manufacture objects of a certain type. So AFactory would know how to create objects of type A.

public static class AFactory {
public static A getInstance() {
B b = BFactory.getInstance();
A a = new AImpl(b);
return A;
}
}

This way all the clutter is moved to a different class away from your main logic. But well even though it is hidden the clutter is still there in your code leading to an indirect compile time dependency from Caller to B,C,D and E. And you might end up creating lots of these boiler plate factory classes. And if you look at the code of these factories they are all very similar and you would think it should be easy to automatically generate these.

4. Frameworks
This is where dependency injection frameworks come into picture. Essentially what a framework does is that it allows you to specify all the objects you require and there corresponding dependencies either outside of code in a format like XML (as in Spring, a popular framework) or inside code but still in more of a declarative manner using annotations etc (Guice). Then when you ask the framework to give you a particular object it will  first create all the dependencies for that object, then create that object and return it to you. Ofcourse to create dependencies, it might have to go one level further down and create dependencies of dependencies and so on recursively.
Using a framework I can layout my whole dependency tree in a separate place and ask the framework to give me any node of that tree and it will oblige. So you can say in a separate configuration file (similar to Spring's xml config file):

id = a class = AImpl
depends on b

id= b class = BImpl
depends on c,d,e

id = c class = Cimpl
id = d class = Dimpl
id = e class = EImpl

and then in your code say:
A a = MyDependencyframework.giveMe("a");

This will work like a charm. All you clutter has gone into a separate configuration file thus preventing any boilerplate from bloating your main logic. Also note that now your main class has to depend only on A at compile time.
Another way of thinking about the utility of dependency frameworks is thus. An elegant but extreme way to design any object oriented system would be to first have an initilisation or bootstrapping process where all the primary objects that will be required in the lifetime of of the system are created and kept in the memory. Then the main logic takes over which involves interaction between these myriad objects. Ofcourse there will be many temporary objects that will be created and destroyed during the main loop such as Strings, Callbacks, Exceptions, Filewriters/readers etc but all the bulky, juicy objects containing the meat of your logic are created in the bootstrapping stage. Dependency frameworks basically allow us to specify this bootstrapping process in a simple way, separate from the main logic and then make it happen.

Next time I will perhaps try to write brief introductions to Spring and Guice and there comparison.

A really nice puzzle [Jul. 16th, 2007|12:10 am]
viked
 [ Tags | puzzle maths ]

In a room, a row of 100 randomly ordered cards are placed with their face down, each has a unique number between 1 to 100 (= random permutation). 100 players (also numbered 1 to 100) are allowed to the room one at a time. Each player can peek at 50 cards - looking for his own number. The players can't communicate or transfer any kind of information after the game started, but they agree in advance on a strategy that will guaranty a surprisingly high probability that  *all* of them will see their numbers. What is the strategy?

Some clarifications:
1 Player who goes inside the room can only peek at 50 cards, but he must leave the room in the state as it was when he entered it. Which means that he cannot rearrange the cards or leave some card faced up.
2. This is not a trick question which means that there really cannot be any kind of information transferred between two players once the game has started. Which rules out all such solution as the time he spends inside the room gives some clue to others. You got the point.
3. I am not asking for a solution that will maximise the number of peaople who see there card. I am looking for a strategy that will give a high probability for all of them seeing there number. B high we mean something around 20-30%. Why is this high? Because just randomly opening cards will only give them a probability of (1/2^100) of all seeing there card.

It is quite amazing that just by cleverly peeking at the cards you can do so much better. A really Gem of a puzzle. Source “7 Puzzles You Think You Must Not Have Heard Correctly”. by Peter Winkler.

Generating the entire season of EPL with just the final League Table [Jun. 11th, 2007|09:41 pm]
viked
 [ Tags | algorithm puzzle probability ]

Football season has just ended and you are given the final league table which shows for each team how many matches it won and how many it lost (assume that there are no draws). What it doesn't show is the outcome of individual matches. So various question that arise are:

1. Generate a possible set of outcomes for all matches which result in this table.
2. Enumerate all such sets and/or number of such sets efficiently.
3. Given the table what is the probability that Arsenal beat Chelsea.

So for example if we had 3 teams each having won one match exactly then there would be two possible set of outcomes.
1. A beat B beat C beat A
2. A beat C beat B beat A
On the other hand if one team had won 2 matches and one had won 1 match then there would be only one possible set of outcome.

I dont know if these questions have interesting/elegant answers. I haven't been able to come up with anything good so far for questions 2 and 3. Question 1 though is easy.  I have also tried to formulate this in terms of some graph theroretical problem but no luck so far. I think these kind of constraints where you say exactly K events should happen (in this case Team A should win exactly K matches) are harder to model.

Any thought?