Towards the end of last year, a few friends and I decided to explore the South Indian state of Karnataka. Some folks in the group were planning to migrate to other countries, and others going back to school. This was the one big party before we all went our separate ways. There was little hope of meeting everyone together again and very little hope of traveling together for 10 days. The trip began with almost zero planning. The idea was to figure out the travel plans along the road.
We rented two cars and started our ride on a Saturday evening, three days before Christmas. The first stop in our journey was Kodagu, better known as Coorg. Kodagu is a hill district on the Western Ghats, with thick forests, rich wildlife, and world-famous coffee. Madikeri is the district capital and the principal town. The district lies between the state of Kerala on the south and Karnataka on the north. We reached our Airbnb around 2 in the night and crashed on whatever we found.
The next day started with a heavy breakfast, complemented with some of the best coffee I have ever had. Our first stop in our "itinerary" was Abbey Falls. It's a cliched waterfall, which gets a lot of tourists every year. We spent the afternoon exploring the areas surrounding the waterfalls. The aim was to get away from the crowds. The evening plan was a night trek, which involved a 3 km trek in a thick forest in complete darkness. Of course, we had a guide with us. It wouldn't be wise to let loose a bunch of concrete jungle citizens in an actual forest. The night trek ended with some rabbit hunting. Most of us choose to avoid, more so because of fatigue rather than any love for animals.
On the morning of Christmas Eve, we resumed our expedition. We checked out some other places around Madikeri. One of the prominent places in Kodagu is Raja's seat, a beautiful garden on a hilltop. The view from atop is very beautiful and one can see all the different hills that make up the Kodagu district. By afternoon, we started the journey to our next destination, Mangalore. The drive down from Kodagu mountain ranges was beautiful. It started raining too, disturbing the serenity of the hills, and creating an aesthetic marvel. So much so, that even the lazy ones started to volunteer to drive. -:)
Mangalore is a port city in the Arabian Sea. It is one of the earliest places where European merchants landed via sea, the first being Vasco Da Gama in 1498. Unlike him, we reached Mangalore, via road, at around 6 in the evening. And this is the place beyond which we had no plans. We spent some time looking for hotels, till we found a cheap hostel for the night. At 200 a night, it wasn't all bad. For starters, we had running water in the bathroom. But that's where the luxury ended.
We spent Christmas Eve at St Aloysius Chapel. Italian Jesuits built St Aloysius Chapel in 1880 and painted the interiors in 1899. The upper arches depict the saints of the Church. The lower arches depict Jesuit saints and the sloping ceilings depict the Apostles. Some of us attended the Christmas service, while others were busy devouring the rum cakes.
The next day, on Christmas day, we traveled to St Mary's Islands. St Mary's Islands are a set of islands in the Arabian Sea, off the coast of Udupi in Karnataka. The subvolcanic activity led to the formation of the island more than 88 million years ago. The only way to get to the islands is via a 6 km ferry service from Malpe. The ferry ride is a different experience altogether. One can find people partying and dancing on the boats. We joined the people dancing at the deck and did not shy away at all. We spent the afternoon at the Island's before resuming our nomadic voyage on four wheels. Our stop for the night was at a hotel 20 km south of a small town called Bhatkal.
Next day, Boxing Day, we started early for the temple town of Murudeshwar. Murudeshwar is a temple town from Hindu mythology. It is famous for it's Shiva temple and the world's second-tallest Shiva statue. The statue depicts Shiva sitting in meditation, with his back to the Arabian Sea. Some devout believers went inside the temple. By afternoon, we were traveling again, this time towards the coastal town of Gokarna.
The drive to Gokarna was scenic, the roads sandwiched between the rocky Western Ghats and the Arabian Sea. We reached Gokarna around 2pm and spent the rest of the day at the different beaches around Gokarna. Gokarna is another temple town, and a popular holiday destination, with many isolated and unexplored beaches. We spent some time at Om Beach, named so because of the protruding land mass giving it an "Om" shape. Some of us bought some cheap souvenirs, before proceeding to Half Moon Beach. The only way to reach Half Moon Beach from Om Beach is by navigating a tricky climb over a small hill.
It was every bit worth it though. We were all alone at this beach, left with the vast sea all for ourselves. If you have been to other Indian beaches (I look at you, Goa and Kovalam), this is a pristine experience. We spent the evening playing frisbee volleyball at the beach and floating in the ocean. It was only after sunset that we realized we had to navigate back the treacherous terrain, in the dark! Thankfully we found some fishermen, who gave us a ride on the motorboat after some haggling over the fare. The dinner was at Kudle Beach, with some wonderful seafood and some fine quality rare herbs (wink wink). The dinner went late, very late into the night and by the time we came back to our rooms, sleep was the only thing on our minds.
Next stop in our journey was Dandeli. Dandeli is a town famous for its Dandeli Wildlife Sanctuary and the Kali Tiger Reserve. The Wildlife Sanctuary is home to Panthers, Elephants and various species of birds. We had planned to visit the Kavala Caves. Kavala Caves are tiny in dimensions. One has to climb around 400 steps to reach the entrance and then climb down. There are prior permissions required from the Forest Department for visiting the caves. We had to skip it and move to the next item in our "agenda" - rafting in the Kali river. The usual rafting trail stretches for about 12 km which starts at around 9 am. We missed it, so we had to settle for the smaller trail of about 5 km. The trail has grade 2 and grade 3 rapids.
Three of my mates bounced out from the raft, and we sprang into action. One of the fellow rafting groups caught hold of one of them. We chased down the other guys, one of whom was floating on his back as per the instructions. The last guy found a rock and climbed on top of it and stayed there till we reached him much later. The rest of the day was quite uneventful. Nothing could follow this.
We left Dandeli late in the afternoon for our final stop at Hampi. We stopped at a small town called Haliyal for our dinner at a roadside hotel named Hotel Baburao. Baburao is one place with some amazing food and the world's best lime soda. After a ravishing meal, we resumed our journey towards Hampi. We reached Hubli at around 11 pm and decided to stop at Hubli for the night. After searching for a hotel for some time, we found a place, and we decided to end our quite eventful day.
The next morning we resumed our voyage to our final destination. We reached Hampi by 3pm in the afternoon. Hampi is a beautiful ancient city from the Vijayanagara Empire. At the height of its fame in 1500 CE, it was the world's second largest city after Beijing. In 1565, a coalition of Muslim cities attacked the Vijayanagara empire. They destroyed the city and it has been a ruin ever since. UNESCO declared it a World Heritage Site in 1986. The Tungabhadra river separates the city into two areas- the older ruins and the new "Hippy Island".
We spent the evening exploring the newer part of the city and then climbing the Anjaneya Hill. There is a temple on top of the hill and it has a breath-taking view. The climb to the top is about 600 steps. We enjoyed the sunset and took some mandatory wanderlust pictures before coming down. Our Saturday plan was to explore the ruins of Hampi. The plan included the Virupaksha temple, Underground Shiva temple, and the Vittala temple. Vittala temple is famous for its musical pillars. The pillars produce the seven musical notes when hit at the right spots. It is also famous for the stone Chariot which is also found on the back of a fifty rupee note.
We left Hampi by 6 in the evening. We stopped at Anantapur for our dinner. We were famished and devoured the food like hungry animals much to the amusement ( or derision?) of the hotel staff. We reached our homes late Saturday night, exhausted by an arduous trip. Along the way, I found out that Liverpool thumped Arsenal 5-1. What a way to end the year!
Monday, 3 June 2019
Thursday, 14 February 2019
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.
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.
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 :-
- Run BFS from any node to find the farthest leaf node. Label that node T.
- Run another BFS to find the farthest node from T. Label it as U
- 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.
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).
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.
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.
Subscribe to:
Posts (Atom)