FOSDEM 2019

I recently had the opportunity to attend FOSDEM. If you haven't heard of FOSDEM, it is a two-day conference held in the beautiful city of Brussels, Belgium. The goal is to promote free and open source software. FOSDEM brings together people from diverse FOSS projects. And unlike other open source conferences, FOSDEM is completely free to attend.

It was my first time attending FOSDEM and I was unsure of what to expect. And if I am being completely honest, I was a tad sceptical as to whether it would be worth travelling to Brussels all the way from Bangalore. I am glad that I was wrong. Along with attending some high-quality talks, I spent 3 wonderful days in the city of Brussels, visited the nearby city of Bruges and spent a couple of days at Amsterdam.

I met some very interesting people and talked to some very interesting projects. There were some very cool stands from some very popular projects like Apache and Mozilla. Being extremely popular, these were extremely crowded. I met some folks from the PostGraphile project, a really wonderful project that allows one to create a GraphQL API server instantly by pointing to an existing PostgreSQL. How cool is that! There were some guys who maintain the super impressive game 0AD. 0AD is a free and open source game like Age of Empires, only better. It's completely built by game developers all over the world. Imagine playing a strategy game written by yourself! There were some other popular projects too like GlusterFS by RedHat, a distributed open source file system. 

But the most interesting of all was the XMPP project. The XMPP project is aimed at building a set of open technologies for instant messaging, multi-party chat and a lot of other things. If one could send instant messages to other people, much like how we send emails now, without ever having to worry if the receiver is on a different email provider. So I could send a message over one of my messaging apps to a person on some other messaging app. The folks at XMPP were kind enough to answer the numerous ignorant questions that I asked.

I spent a lot of time in the open media dev-room. Dev-rooms are where people with a specific set of interests come together to talk about interesting projects in the domain. That is where I discovered GStreamer, an open source multimedia framework for building multimedia applications on top of it. There were interesting talks, with one in particular about using Rust to build multimedia applications. I also spoke there about combining OpenCV and CUDA to build video analysis tools. 

FOSDEM is a really special conference in that it is run by volunteers and donations alone. Brussels is a really nice place to visit, maybe February is not the best time. Here is a picture of ULB Solbosch, the venue.

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

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.