A few simple graph problems, and their interestingly cute solutions!

Recently, I was solving a few graph problems from here, and I found the questions to be simple yet challenging! By this, I just mean that the questions didn't ask for any advanced knowledge from my side, and yet it was a challenge to come up with simple solutions for them.

There were many questions, for which I too came up with my answers, but they were complex. On the other hand, the given solutions were quite simple, and they had an aesthetic beauty that only an algorithmist can understand. Hence, the cuteness.

I am just providing the questions here in brief, and the underlying thought process that led to those cute solutions. For a detailed study, which you must do, go here.

1. Design an algorithm that finds all bridges in undirected, connected graph G in O(V · E) time.
   
   Actually this is the third part of one question. They beautifully and thoroughly made the students think over the solution. The key idea is to think of the BFS tree of the graph.
   
   First, they asked to prove that all the bridges will be present in the BFS tree of the graph. Then, to examine the running time of checking whether a given edge is a bridge or not. And finally they stated the problem that I mentioned.
   
   What an amazing way to teach students how to solve problems!
   
   
2. To find an efficient algorithm to find the number of paths in directed acyclic graph G from s to t.
   
   Topological sorting, and storing the number of paths to all the vertices, using the previous counts to build the next ones!
   
   
3. Suppose you are given a city map with unit distance between each pair of directly connected locations. Design an O(V + E)-time algorithm that finds the number of shortest paths between the source vertex s and the target vertex t.
   
   Always remember, BFS finds the shortest path to all the vertices in an unweighted graph. And then again, we can store the number of shortest paths to all the vertices, using the previous counts to build the next ones.
   
   But remember, we are finding the number of shortest paths in an unweighted graph!
   
   
4. Consider a connected weighted directed graph G = (V, E, w). Define the fatness of a path P to be the maximum weight of any edge in P. Give an efficient algorithm that, given such a graph and two vertices u, v ∈ V , finds the minimum possible fatness of a path from u to v in G.
   
   Amazing question, and what a cute solution! A good reminder to self regarding what value does d[u] store for all the vertices. A simple change in RELAX method of Dijkstra's algorithm. Seriously, this never crossed my mind before I read the solution.
   
    
5. Given four vertices u, v, s, and t in a directed weighted graph G = (V, E) with non-negative edge weights, present an algorithm to find out if there exists a vertex vc ∈ V which is part of some shortest path from u to v and also a part of some shortest path from s to t. The algorithm should run in O(E + V log V ) time.
   This is my favourite of all. The solution just requires understanding the basic definition
   d[u,v] = d[u,vc] + d[vc,v]. And there you have it.
   

I found all these questions to be quite mind-stretching, and yet looking out for only the elements of understanding in me!

 

Lakes in Berland : Why coding your solution is a good idea?

I write about my solutions to the coding competition problems only for myself. For the problems that stretched my mind a little more. To bring myself a clarity of thought of what i did in the code. To understand my mistakes. Do not read it unless you have really nothing else to do in this awesome universe!

The question : Lakes in Berland. As simple as it could it be. I guess it didn't take me more than 10 minutes to figure out how to solve it. But there awaits the demon. The one everyone talks of. The implementation.

There is a reason why great programmers ask to code your solution. Because just knowing the solution isn't enough! And that is what happened in my case.

It took me quite a good long time, almost a day to get to a working solution! And no, it wasn't anything hard to code. It just reflects my weakness in implementing a solution.

..

While coding the solution, I was noting down all the mistakes that I did, due to which my test cases failed. Here they are in a proper format just to make myself realize my fallacies, and why I need to think a little more before submitting my solution all over again.

MIstake #0 : It took a lot of time to implement the dfs, and the lines of code that I wrote was way more than for the accepted code in C++; always a red signal.

Mistake #2 : I made a very big mistake as my code was allowing the non-starting vertices to be on the border, had to refactor my code to find the connected components!

Polycarp At The Radio - Importance of maths in programming!

Many people argue among themselves whether maths is important or not, when it comes to programming. I don't indulge in these arguments, neither this post is going to do anything similar.

But recently I tried to solve a problem which made me realize the importance of mathematical intuition when it comes to programming.

I started to solve this problem on Codeforces, Polycarp At the Radio, and hit sort of a dead end for more than a day.  But something got me hooked to this question. There was nothing special about it. No difficult algorithm tags. And still I was finding it difficult to code.

But I went on to code what I thought to be a good enough code to pass all the test cases. And no, I just didn't start monkey-typing on my keyboard. Yet the end result was around 200 lines of python code, with a lot of comments and debugging statements hidden within it.

And it doesn't stop there. My code still failed on a test case I knew of, I wasn't sure if there still exist other test cases it might fail upon, and just when things seemed to make sense, I realized I had no idea in hell or heaven how to change my code to pass this particular test case.

..

Finally, I gave up, and read the tutorial given for the same. And I just couldn't express how beautiful the solution is. So simple, so intuitive. I can't even say it to be mathematical. But something definitely mathematically intuitive.

And the code was just 40 lines long, with complete surety that it will work for all the test cases, whatever it may be! And this is why, my boy, mathematical intuition is important in programming.

I am linking a github gist here, containing both the buggy and the correct codes, to show how complex a program can get because of the lack of simple mathematical intuition.

Just give this puzzle a try before you hop on to another post of someone else! :)

Learning the open source way at dgplug!

I still remember a first-year college student who, in 2014, somehow got to know of dgplug through Quora, and just jumped on the ship.

I still have that post that I wrote that time just like this one! https://thisisashwanipandey.blogspot.in/2014/07/my-experience-with-dgplug-summer.html

But I couldn't attend more than 5-6 sessions as I had to go to college then, and I was using chatzilla, and I got stuck with proxy problems. And that was a very big problem for that kid. I tried it a few times, but by then a lot had already happened in the training sessions. I have to leave it then!

Fast forward 2 years, and here you see the same boy writing this post while determined enough to not leave in between this time whatsoever!  And yes, to learn a lot more this time.

..

Regarding the current session going on, I got to have a virtual session with one core python developer, and I got to know about rst, bash and sphinx. I already was a little bit familiar with rst, but sphinx and bash are totally new and cool things for me. I would be reading and learning more about them as many related things are not yet clear to me!

Many other things did happen too in the sessions, and you can read about them at the link that I gave at the very starting.

..

I am really excited to see and learn the upcoming things in the training session. If all this excite you too, do join us at dglpug. And a big thanks to the dgplug team, who take out their precious time to teach others all this exciting stuff.

IITH Internship Diary - Week 2 : Troublesome Implementation

Week 2 passed by like a flash with nothing much done from my side. And if this continues on, I guess I would have achieved at the end of my internship.

On Monday, I met my PhD mentor Aarghya sir, and he made a lot of basics clear, and also made me understand the basics of research paper, and what actually I need to do on the implementation side. And it was followed by a short meet with Vineeth sir on Wednesday, with almost nothing done from my side in between these two meetings.

Then, I started with the basics of Lua, followed by that of Torch. I am currently reading and trying to understand ML implementation with Torch from these two sources.

• https://github.com/soumith/cvpr2015/blob/master/Deep%20Learning%20with%20Torch.ipynb
• https://web.archive.org/web/20160216003701/http://code.madbits.com/wiki/doku.php?id=tutorial_basics

On weekend, I went to visit Hyderabad, but due to such long commute to reach there, I probably won't be going anywhere in the city for the next few weeks. It was tiring.

For the next week, I would mainly continue with the above mentioned links and speed up my work with my main focus on this only, which I wasn't able to give for the past week.

IITH Internship Diary - Week 1 : Getting the basics slowly

Well, the week started with a meeting with my mentor professor Dr. Vineeth sir for the first time on Tuesday. I was really excited about it, and my excitement for the project and machine learning in general only increased after meeting. He is really an enthusiastic person to meet. He basically told all of the interns more about their work, and what all new things are happening in the field of ML.

After that day, I started with learning logistic regression from the Ng's course. But then switched on to learning the basics of neural networks from here. Michael Nielsen really made the concepts very clear in the first go! But somehow, it still took me around three days completing the first chapter only. Later I also saw his TED talk on open science.

I guess it took me three days because I was not having any feedback loop to tell myself what all I have achieved everyday. I have already included this thing in my list from now on, so things will hopefully speed up from now on.

On Saturday, I raced through the later end of the first chapter. I would come back to the implementation discussion that he did, later on.

Sunday was a day well spent, learning about LSTMs. Christopher Olah has a really awesome blog. You must definitely check that out. And later part of the day was spent reading research paper. Although only bits of the paper were clear, I was happy that atleast something was clear this second time.

Also, I somehow landed on some of the amazing pages on the web, and I have saved all those links and I am definitely gonna read all of them soon. I would share them as I go on reading them one by one!

Bye!

Resources for loads of Linux fun

I am very weak as of now in my understanding of Linux, but I am hell bent to be awesome at it.

Lately, on my exploration of the net, I stumbled on a few great resources, and I am saving them for the upcoming summer or whenever I want to have some fun while learning Linux!

• http://eudyptula-challenge.org/
• https://practicalunix.org/ : I will only touch any of the other listed links once I finish this one!
• http://linuxsurvival.com/linux-tutorial-introduction/
• file:///home/little_pirate/Documents/TLCL-13.07.pdf
• There were some pretty good questions here
  
  http://web.eecs.utk.edu/~plank/plank/classes/cs360/lecture_notes.html
  
  http://web.eecs.utk.edu/~plank/plank/classes/cs360/

Resources for Capture The Flag

Just two days ago, I didn't even know what CTFs are. But after reading about them I am really excited to go on and solve the puzzles in this new arena!

This post is live and resources will keep on adding as I work through this :

• https://trailofbits.github.io/ctf/index.html
• https://www.hackthissite.org/

Useful resources I found while making a web spider

For the past few days, I have been trying to implement a javascript-enabled web spider, and finally I successfully implemented it yesterday.

Actually, it was an internship challenge task given by SocialCops, and I finally submitted it today. Fingers crossed for the results !

This post is not about how to make web spider or any resource provider of some sort for the same. Sorry if you landed here because of the misleading title!

I am writing this post, so as to keep a list of all the great links that I found while making the web spider, the ones that I would visit frequently from now on. Almost all of them are programming related, and I assure you that they are just awesome!

Have a look on them!

• **https://www.reddit.com/r/dailyprogrammer/ ~ lots of interesting programming challenges
• https://opensource.com/life/15/6/2015-summer-reading-list ~ a great list of interesting books
• http://www.obeythetestinggoat.com/ ~ a great blog and book on test driven development, understood its importance while making the web spider
• **http://newcoder.io/tutorials/ ~ superb tutorials on interesting projects
• https://jeffknupp.com/ ~ again, a great book cum blog on Python !
• **https://automatetheboringstuff.com/ ~ hands down, a very interesting book to read !
• http://simplystatistics.org/ ~ a great blog on statistics, even I don't remember how I landed on this while making the spider
• **http://effbot.org/zone/about.htm ~ a blog with lots of new and great python stuff !
• http://blog.stephenwolfram.com/2012/03/the-personal-analytics-of-my-life/ ~ a great blog post by Stephen Wolfram on how he use data analytics in his life!
• ***https://www.recurse.com/ ~ a great place I would love to be someday!
• https://www.recurse.com/blog ~ a nice blog to hang around, for sure!!
• http://szeliski.org/Book/ ~ haven't read it yet, but will read it to get some understanding of computer vision
• http://www.kristenwidman.com/blog/33/how-to-write-a-bittorrent-client-part-1/ ~ a nice place to start with the basics!!

Too many of them, but all of them are kind of gems!

Started with my first "real" django project

Django. I first saw it and used it when I went for my internship at IITB in the summer of 2015. I started with it, and learn pieces of info regarding web frameworks, and django. But I couldn't understand much, and after a while the internship came to an end.

Next time I used it when building a basic chat application, but it was too high a level for me, and I miserably failed in that too.

This time I have started with http://www.tangowithdjango.com and I would be making the web application with the design described on the site. This would surely make me sound with django.

So, that's the task at hand. Get, set , go.

This week of mine : Goldman Sachs internship preparation ends

Okay, so a few hours before, the result for the aptitude test of Goldman Sachs was given, and I couldn't clear that. And yeah, that's bad and I can spend a good amount of time from now on, sitting idle and feeling bad about that, or I could just focus on what went wrong, and deliver my best to be much better the next time.

So, what went wrong? Well, everything. I couldn't solve more than 5 questions out of the given 15 general aptitude questions on my own, and that's really bad. And I mean it.

But there is no point being sad about that. The thing is such aptitude tests have always given me hard time when given to solve in a restricted amount of time. It's not like that I can't solve that. The problem with me is to have the speed and accuracy at the same time, where my speed has always knocked me down.

And the other thing, for which I guess I am pretty much upset from myself, is that only 4 out 20 test cases could pass for the only coding question that was given to us. The problem I see here is I need to be faster. Faster in coming up with a good algorithm, faster in implementing that. Because the problem is I had no time to generate my own test cases, which might have reflected why my answer was failing for so many test cases.

So, finally all boils down to practice, practice and practice.

To prepare for aptitude tests, I was looking at the answers given here.

And the answers seems to point to good resources. Do comment if you know of some other awesome resources to prepare for general aptitude tests.

Then remains the part of coding questions. Well, I think I am doing good in this area. I regularly solve questions, and in some time I will be fast enough to have spare time to have a good look at it once again.

At last I am ending this post with a part of one quote that happens to be my inspiration all the time.

If you know what you're worth, then go out and get what you're worth.

And I know what I'm worth of :)
    

What computer science things I am going to learn in the next 2 years ?

Although I study in a college, but most of the times, I consider myself as a self-taught programmer, who learns from the net along with his friends, and don't bother to depend on the boring college classes.

This answer on Quora made me realise how awesome and vast the field of computer science is, and hopefully I will get my hands dirty in these subjects in the next two years.

Thanks Ryan Witt.

Read Ryan Witt's answer to What skills do self-taught programmers commonly lack? on Quora

09.06.2015 : Attending Jeff Ullman's talk on MapReduce algorithms

I had this moment while doing my internship in IITB and I couldn't resist writing a post regarding this.

Here it is : 09.06.2015 : Attending Jeff Ullman's talk on MapReduce algorithms

Life always amaze me with its randomness!!