Job scheduling problem

Well,

This problem was written on whiteboard by manoj for others to solve and finally arpita solved it for the most part with me chipping in at the end.

Problem : There are n jobs to be done and 2 processor available.  Each job take the same amount of time ( so for simplicity one can assume it takes unit time ). Both processor have the same capabilities.  A job may depend on other jobs, for example if job A is dependent on B and C then A can not be scheduled before B and C both  are finished.  Dependancies amogst jobs are given.  Give an algorithm to find the optimum schedule ( in terms of time to finish all jobs ).

Solution ; Because dependacies are given, one can generate a dependacy graph. This graph is a DAG ( Directed Acyclic Graph ). Because if there is a cycle then all jobs which participate in the cycle can never be scheduled. Now, compute the transitive closure, in a sense that if there are edges A -> B and B -> C, then add an edge A -> C.

This way we have obtained all dependencies, direct as well as indirect, in this graph G. Forget about the direction of the edges for a moment and compute a complement graph G’. It is easy to see two jobs can be scheduled in parallel if and only if there is an edge between them in G’. Find a maximum matching ( 1-factor ) of G’.  Minimum time taken would

# of edges in G’ + # of unmatched nodes in G’.

Of course, the ordering is still needs to be decided.

Let’s get back to G now.  We will merge nodes which were matched in G’, that will give us another DAG.  Topological sort on this DAG would give us the order in which we should schedule the jobs.

Though I am not fully confident, I believe that this method would give us the optimum schedule. One more point to ponder is that whether this can be generalized for k-processors.

— Saurabh Joshi

Puzzle : Death Defying Duck!!

So I am back after a long time with an interesting puzzle. The credit for giving this puzzle goes to Sameer and in turn to microsoft for askim him this puzzle in their placement interview. ( By the way, sameer got selected in microsoft ).

Problem : There is a circular lake of radius . A duck is there at the center of the lake and a dog at the perimeter. Dog is intelligent and so is duck ( Actually none of them are, but this is added to make sure that reder is intelligent enough not to give any stupid answer ). Dog desperately wants to eat the duck. Now that the duck has finished fishing, it wants to escape. The only way it can escape is to reach the perimeter of the lake and fly away.  ( For some unknown reason, this duck can fly very well, but can’t do so when in the water ). Swimming speed of the duck is while dog can run at a speed of . What stretagy/path the duck should follow to guarantee a safe escape??

Solution : When sameer asked me this question, my initial thought was to try if duck can escape swimming diagonally opposite to the dog. But alas!! so while duck has to swim , dog has to run which is easy for the dog to accomplish. So it does not work!!

Anyways, we will assume now on that without loss of generality. So the next thing I thought of what if the duck starts moving in the diagonally opposite direction only for some distance . After that, duck again changes the velocity so that the direction will be towards the digonally opposite point from the dog. I imagine that this will lead to some kind of a spiral like path. However, evaporation of integration and differentiation happened years ago from my brain, I could not prove or disprove whether this stretagy would work.

So finally, I came up with the solution from other direction. Look at the figure below.

Distances AB=1/4, AD=AC=1, BC=3/4. What if the duck can be at B while the dog is at D? Duck can now straight away go to C safely. Why? Well, think about it for a moment. BC=3/4, so dog can cover at most distance upto 3 unit of distance in that time. But to catch the duck, dog has to cover . Poor dog!!!

Next thing is to make this situation happen. Notice that when duck circles around the lake at radius 1/4, dog can run along the perimeter with the same angular velocity. For all circles with radius less than 1/4, angular speed of the duck is greater than the dog. So duck chooses to circle around at a radius where, is very very small. Duck now keeps circling around which gives him positive phase difference with respect to dog. When the phase difference becomes 180 degree, at that point duck can straight away go diagonally opposite to the dog and escape.  Here, is small enough to exploit the difference of .

It was an interesting exercise going through all that. Thanks to sameer for bringing this to me.

— Saurabh Joshi