Friday 26 June 2015

Delta Algorithmic Contest


I recently came up with two problems for a programming contest organized by Delta , the premier programming club in NIT Trichy (and the coolest thing that I am part of).

The contest link :
Delta Algorithmic Contest 

You can find both my problems here:

Count Bus Stops
Dependency


In this we will be discussing a solution to the first problem.

 A given set of locations are connected such that there is a unique path from each location to every other location. There are bus services from different places.
The problem is to find the maximum number of bus stops possible between any two locations.

The main idea here is to model the locations and roads as a tree with the locations as nodes and roads as edges. Since the roads are bi-directional one can model the problem efficiently using an undirected unweighted tree. The problem to find maximum number of bus stops then is essentially finding the diameter of tree.


The simplest way to do it is :-

  1. Run BFS from any node to find the farthest leaf node. Label that node T.
  2. Run another BFS to find the farthest node from T. Label it as U
  3. The path you found in step 2 is the longest path in the tree and the diameter of the tree is dist between U and T.
The running time of the algorithm is same as running time of BFS. So the running time is O(N), where N is the number of nodes.

Delta Algorithmic Contest - 2

This post is a continuation to this.

In this post we will be discussing the solution to the second problem. You can find it here.

There are N files in a package. To compile them you need to compile each file individually. However some of these files require other files to be compiled first. Given N files and M relations denoting dependencies of one file on other, you need to find order of compiling the files. If there are more than one orders , find the one which is lexicographically largest.

The key to solving this problem is to model the given input as a proper data structure.

The given files can be considered as nodes of a graph with the dependency relations as edges. The dependency relations are not symmetric i.e if x requires y to compile then y would not require x to compile. Thus the graph is unweighted, acyclic and directed.

The order in which the files must be compiled is now simply a topological ordering of the graph. A topological ordering T of a directed acyclic graph (DAG), is ordering of vertices such that for every edge from any vertex v to any other vertex u , v appears somewhere before u.

However a DAG can have any number of topological orderings. The question asks for the one which is lexicographically largest.

There are many ways to do this, however the below mentioned one is very easy to implement for our case.

As the given graph is acyclic there exists at least one vertex with in-degree 0. The following algorithm constructs a topological ordering:

While there are vertices in graph:
     Pick a vertex with in-degree 0, add it to the required order and remove the vertex from the graph along with all its out going edges.

In case there are more than one vertices with 0 in-degree pick the one which is represented by a bigger number.

To implement this one can use a priority queue with vertices ordered in the increasing order of in-degree and if the vertices have equal in-degree then the one denoted by a bigger number has a higher priority. At every step remove the top element from the priority queue and decrease the in-degree of all vertices to which the removed vertex has an edge by one.

Time Complexity:
For the graph with N vertices and M edges
We pick the top priority element from the queue N times and decrease the in-degree a total  M times.
Getting the top element from a priority queue is O(logN) and decreasing an element is also O(logN), if the queue is implemented as a heap.

So the time complexity is O((N+M).logN).

Wednesday 24 June 2015

Hello World

Hello World!

These lines are so special to any programmer. For some it is a ritual that anything new must start with these lines. I am one of those.

I am Sam Radhakrishnan and I spend most of time coding. I'm a Computer Science and Engineering student in my sophomore year at the National Institute of Technology, Tiruchirapalli (sane people call it NIT Trichy).

I contribute to various open source projects and maintain a few of my own. I also take part in coding competitions.

When I am not doing any of these, I do my bit to change the world.