Ravindra Ranwala's Blog

Electronic circuit designs often need to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of $n$ pins, we can use an arrangement of  $n - 1$ wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable. We can model this wiring problem with a connected, undirected graph $G = (V, E)$, where $V$ is the set of pins, $E$ is the set of possible interconnections between pairs of pins, and for each edge $(u,  \;v) \in E$, we have a weight $w(u,  v)$ specifying the cost (amount of wire needed) to connect $u$ and $v$. We then wish to find an acyclic subset $T \subseteq E$ that connects all of the vertices and whose total weight is minimized. $$\LARGE w(T) = \sum_{(u, \;v) \in T} w(u, \;v)$$ Since $T$ is acyclic and connects all of the vertices, it must form a tree, which we call a spanning tree since it “spans” the graph $G$. We call the problem of...

This article shows how we can use depth-first search to perform a topological sort of a directed acyclic graph, or a “dag” as it is sometimes called. A topological sort of a dag $G = (V, E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u, v)$, then $u$ appears before $v$ in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) We can view a topological sort of a graph as an ordering of its vertices along a horizontal line so that all directed edges go from left to right. Topological sorting is thus different from the usual kind of “sorting”. [1] The following simple algorithm topologically sorts a dag: Now let’s take a look at a real world application of the Topological sort algorithm. Course Schedule There are a total of $n$ courses you have to take, labeled from $0$ to $n-1$. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: $\left[ \b...

RSA Introduction Most of us know RSA cryptosystem which is the most widely spread cryptosystem even today. The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem. In RSA, the process of encryption and decryption is depicted in the following illustration. RSA Algorithm Now let’s drill down this $encryption (E)$ and $decryption (D)$ process furthermore. As we all know the RSA algorithm [1] works as follows: Choose two prime numbers $p$ and $q$, Compute the modulus in which the arithmetic will be done: $N = pq$, Pick a public encryption key $e \in Z_n$, Compute the private decryption key as $d$ such that $ed = 1\; mod\; \phi(N)$, Encryption of message $m: c = m^e\; mod\; N$, Decryption of ciphertext $c: m=c^d\; mod\; N$. Proof Our simple proof  uses the Euler-Fermat Theorem. Let’s first have a look at it. Euler-Fermat Theorem Let $n$ be a positive integer, and let $a$ be an...