Ravindra Ranwala's Blog

Red-black trees are one of many search-tree schemes that are balanced in order to guarantee that basic dynamic-set operations take $Θ(log_2 \;n)$ time in the worst case. [1] A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. Every red-black tree should satisfy the following red-black properties: [1] Every node is either red or black. The root is black. Every leaf ( NIL ) is black. If a node is red, then both its children are black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. As a matter of convenience in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. Its color attribute is BLACK , and its other attributes - p, left, right, and key—can take on arbitrary values. Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, t...

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Given a string $s$, find the longest palindromic substring in $s$. You may assume that the maximum length of $s$ is $1000$. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb" Let $p[i][j]$ be a table that states whether the substring $s_i\ldots s_j$ is a palindrome or not. Note that any substring of $length = 1$ can be considered as a palindrome. The following equation describes  the recurrence. $p[i][j] = \begin{cases} true ,  & \text{if $l = 1$} \\[2ex] s_i == s_j,   & \text{if $l = 2$} \\[2ex] p[i+1][j-1]\; and \; s_i == s_j, & \text{if $len \gt 2$} \end{cases}$ Procedure LONGEST-PALINDROME-SUBSTRING takes a String as it’s input. It stores $p[...

Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t...

Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how similar the two strands are, as some measure of how closely related the two organisms are. However we can, and do, define similarity in many different ways. The way which we use to measure the similarity of strands $S1$ and $S2$ is by finding a third strand $S3$ in which the bases in $S3$ appear in each of $S1$ and $S2$, these bases must appear in the same order, but not necessarily consecutively. The longer the st...

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...