Stuff you might be interested in learning about.
I recently learned something fun: how to solve maze puzzles by using shortest path algorithms in graphs! First step is to convert the maze into a graph. Let me take this simple maze as an example.
(Pardon my awkward looking drawing. I can never seem to get these right.)
It has been some days since I wrote on the blog but that doesn’t mean I haven’t been writing! In fact I have co-authored two articles in this month so far: one is a brief introduction on lambda calculus and the other discusses recommender systems based on collaborative filtering. Both are inspired by random talks that I attended in the past. Go check them out! 🙂
Apart from this, I’ve been reading a lot lately. Technical papers, blogs, news pieces, and even novels. After all, reading a well written piece of work is one of the greatest source of inspiration for writing! Talking about inspiration, here’s something for you to check out – Brain Pickings. If you don’t already know about it, knock yourself out with their very interesting collection.
Ciao, till I post again!
Ever played one of those games where you are given two water containers/jugs of different sizes and the task is to fill one of the jugs with a certain amount of water? Here’s an android app (image below) for the game if you aren’t familiar. Play it all you want because now I’m going to ruin it for you! I’m going to tell you a general solution to this water jug riddle.
The only thing you need to know is: Greatest Common Divisor.
My Differential equation prof while making use of Pythagoras theorem in an equation drew these cute little visual proofs on the board:
The notion of dependent and independent events is a common one in probability theory and it’s applications.
This article has been published at Function Space.
(This is just my back up copy of the thing, do check this out on FS for better experience.)
Let’s say for an upcoming contest at a school, you form a team and decide to develop a software. Everything goes fine until you guys come to a stage when two or more of teammates work on the same piece of code! If you guys are working on disjoint set of files, the problem comes when you want to integrate the two modified code together manually.
Further, how would you handle a vast code distributed over several files and people working from different geographical locations? If one of the guy messed up the code, won’t all of the other teammates also suffer? The solution is a version control system. In this article, we will discuss about one of the widely used open-source version control system called git.
This article has been published at Function Space.
(This is just my back up copy of the thing, do check this out on FS for better experience.)
In this article, we dive into computational complexity theory. You might want to check out our previous article to get informally introduced to some of the concepts that we elaborate here, although it is not a strict requirement.
Let’s look at a few similar looking problems :
This article has been published at Function Space.
(This is just my back up copy of the thing, do check this out on FS for better experience.)
One of the most beautiful occurrences of mathematics in nature are Fibonacci numbers[1]. Named after Leonardo Fibonacci, this series dates back to ancient history with origins in Indian mathematics [2].
The beauty of the series is enhanced by it’s simple definition, x(n+2) = x(n+1) + x(n)
So starting from x(0) = 0 and x(1) = 1, the series progresses infinitely as: 0,1,1,2,3,5,8,13…
The problem we’ll be discussing in this article is: How do we go about finding the nth Fibonacci number?
This article has been published at Function Space.
(This is just my back up copy of the thing, do check this out on FS for better experience.)
Morpheus said Matrix is everywhere. He’s not very far from the truth! Every thing that we see can be considered a matrix, because image is nothing but a matrix!
And one of the most frequently used and computationally intensive matrix operation is Matrix Multiplication.
For the purpose of this article let’s stick with two square matrices A and B of order n each and take that as our running example.
Volker Strassen came up with a more efficient matrix multiplication algorithm in 1969 which runs in O(n^log7)≈O(n^2.807) time. From then on, many optimizations have been made in this area and the current best runs in O(n^2.3727)time. In fact, {what is the fastest algorithm for matrix multiplication} is still an unsolved problem in computer science.
This article has been published at Function Space.
(This is just my back up copy of the thing, do check this out on FS for better experience.)
Suppose you are a teacher of a class of 1000 students. There is a scholarship offer for the top 50 students of your class. Now, you as a teacher, want to find those top 50 students. How would you go about doing this?
A) There is an easy approach you could follow. You just sort the students according to their ranks and pick up the top 50 from this sorted list. But you will realize that you have wasted a lot of effort in sorting the other 950 students of your class. The best known sorting algorithm takes O(n∗log(n)), where n is the number of students in the class.
B) Another approach which is slightly clever is as follows. Pick up the student with highest rank from the list by going through all of them. Then, remove him from the list and find out the highest rank from the remaining students, which turns out to be the student with second highest rank. Repeat the process 50 times and you have the top 50 students with you. Upon trying to analyze the time complexity of this approach, it would take O(k∗n) time, where k is 50 in this case.
So, is this really better than the first? Continue reading
Aakritty 