My Tryst with CS

Detecting the starting point of a loop in a linked list is a very popular problem. In fact most you reading this might already be knowing the algorithm to solve this. However understanding why that algorithm works is a separate challenge altogether. I was in the same state and decided to find an explanation of why it works. I could not find convincing explanations by simple google searches and hence decided to right this blog. Hopefully, this will satisfy the curiosity of people trying to understand the reasoning behind this algorithm. I believe coming up with this algorithm in the first place is an even bigger challenge. You will have to stay with this problem a lot longer if you want to do that. For now let's assume we have the algorithm and let's try to prove why it should work. The Algorithm The key insight of the algorithm is that we need to maintain two pointers: Slow and Fast, Slow pointer: Moves one node at a time. Fast pointer: Moves two nodes at a tim...

In my post on RSA encryption system I mentioned the use of Fermat's little theorem. In this post I am going to give a formal proof (and explain in simple terms) the theorem itself. This will also give you a chance to boast among your friends (possibly nerdy) that you know the proof to one of Fermat’s theorem ;) THE STATEMENT Fermat's little theorem states that: For any integer a not divisible by p and any prime p, the following always holds: a (p-1) ≡ 1 (mod p) The reason why the theorem states that a should not be divisible by p is very clear. Let us assume that a was divisible by p, then obviously p will divide a (p-1) . So this means that a (p-1) ≡ 0 (mod p) when p | a. So this is an exception and is separately mentioned in the theorem. PROOF Now coming to the actual proof of the theorem. If we see the left hand side of the equation in the statement, we have the term a (p-1) . So it is clear that this was obtained by multiplying a, p-1 times. Now let us ...

In this post I would like to talk about the Chinese Remainder Theorem. You might have heard this problem as a kid: There are x number of things. When taken in groups of 5, they leave a remainder 1. When taken in groups of 7, they leave a remainder 2. When taken in groups of 9, they leave a remainder 3. And when taken in groups of 11, they leave a remainder 4. Find the value of x. We will see how such problems can be solved using the Chinese Remainder Theorem(CRT). LINEAR CONGRUENCES Lets talk about linear congruences. You might have already encountered them informally in my previous post on the RSA encryption system. Here I would like to introduce it a bit more formally. ax ≡ b (mod n) Abusing the use of notation, we can express this equation into a form which might look more familiar, i.e ax%n = b. In other words, the integer ax when divided by n leaves a remainder equal to b. Lets say that we find a solution to the above equation, say x = x 0 . => ax 0 ≡ b (...

THE NEED OF ENCRYPTION In today's world where a lot of secured information like our credit card number, passwords etc., travel around the web, the presence of a secure encryption system is almost inevitable. We want a method to encrypt a message, send it over the insecure internet connection and allow only the receiver to be able to decrypt and read the original message. This exact problem was solved by R ivest, S hamir and A dleman(RSA) in the year 1978, in their paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. In this post, I will try to explain the method they adopted to create a secure encryption system. PUBLIC KEY CRYPTOSYSTEM A public key cryptosystem has the following properties: 1) D(E(M)) = M, if we decrypt an encrypted message, we should get back the message. 2) Both E and D should be easy to compute, if it takes days to encrypt or decrypt the message, then the cryptosystem is not very useful. 3) By publicly revea...

MIN CUT We have already talked about the maximum flow problem. Now is a good time to talk about a seemingly different but actually quite similar to the maximum flow problem, i.e the min-cut problem. A cut is defined on two vertices A and B such that we can partition all the vertices of the graph into two sets such that A and B do not belong to the same set. Going by this definition an s-t cut can be defined as a partition of the vertices of a graph such that the source and the sink are not in the same partition. Now we associate with a cut, what is called the capacity of the cut . It is defined as the sum of the flow of edges that go out of the cut. We do not consider the edges coming back into the cut as we want an upper bound on the amount of flow that can go out of the cut. Formally the capacity of a s-t cut is defined as:  where δ + (A) is used to denote the set of edges sticking out of A. (Similarly we will use δ - (A) to denote the set of edges sticking into A...

PROBLEM DESCRIPTION The problem of finding the maximum flow in a network, has a history which dates back to the second world war. Practically the maximum flow problem can be stated as:  “A list of pipes is given, with different flow-capacities. These pipes are connected at their endpoints. What is the maximum amount of water that you can route from a given starting point to a given ending point?” or equivalently “A company owns a factory located in city X where products are manufactured that need to be transported to the distribution center in city Y. You are given the one-way roads that connect pairs of cities in the country, and the maximum number of trucks that can drive along each road. What is the maximum number of trucks that the company can send to the distribution center?” Formally stated the problem is: We are given a network - a directed graph, in which every edge has a certain capacity c associated with it, a starting vertex (called the source), and an ending...