Ravindra Ranwala's Blog

Exercise 7.4-1 Show that the recurrence $T(n) = max\{T(q) + T(n - q - 1): 0 \le q \le n - 1\} + \Theta(n)$ has a lower bound of $T(n) = \Omega(n^2)$. [1] Inductive hypothesis: $T(n) \ge n^2$ $T(n) = max\{q^2 + (n - q - 1)^2: 0 \le q \le n - 1\} + \Theta(n)$ $f(q) = q^2 + (n - q - 1)^2: 0 \le q \le n - 1$ By expanding the expression we obtain $f(q) = q^2 + (n - q)^2 - 2 \cdot (n - q) + 1$ $f(q) = 2 \cdot q^2 + n^2 - 2nq - 2n + 2q + 1$ Now let’s find the local maxima of the function using its first derivative. Taking the first derivative with respect to $q$ we obtain: $f'(q) = \frac {d}{d q}2q^2 + \frac {d}{d q} n^2 + \frac {d}{d q} -2nq + \frac {d}{d q}-2n + \frac {d}{d q} 2q + \frac {d}{d q} 1$ Since we are looking for a critical point in the graph, $f'(q) = 4q - 2n + 2 = 0$ $q = \frac{n - 1}{2}$ This can be either a local minima or a maxima of our function. Let’s determine it next. Let $q = 1$ for sufficiently large $n$, plugging in the values in the above equation we get: $4 ...

Today, we are going to establish a lower bound for searching and prove that binary search is optimal, and no comparison based search in this universe would be better than that by more than a constant factor. Let’s define our problem more formally first. Theorem Let us assume that we have $n$ pre-processed items in the array. Finding a given item among them in a comparison model requires $\Omega(log_2 n)$ in the worst case. Computation Model Let’s try to model the situation using a decision tree. In this decision tree, an internal node represents a decision that our algorithm makes and a leaf represents an answer. Here’s our representation of the problem using a decision tree computation model for $n = 3$ element array for the sake of simplicity. I mentioned here that the Items are preprocessed to mean you could do whatever you want with items ahead of time. For instance, I can sort them, build them into an AVL tree et.al. Proof Let $n$ be the number of items in the input array. Then, w...

 We return today to graph search. Last time we saw breadth-first search, today we're going to do depth-first search. It's a simple algorithm, but you can do lots of cool things with it. DFS is often used to explore the whole graph, and so we are going to see how to do that today. So high-level description is we're going to just recursively explore the graph, backtracking as necessary, kind of like how you solve a maze. Let’s now consider a real world application of the DFS algorithm. Number of Closed Islands - Problem Definition Given a 2D grid consists of $0s$ (land) and $1s$ (water).  An island is a maximal 4-directionally connected group of $0s$ and a closed island is an island totally (all left, top, right, bottom) surrounded by $1s$. Return the number of closed islands. Output: 5 Output: 4 Note that closed islands are colored in the tables above. Output: 2 Output: 1 Number of Closed Islands - Approach We use the table $d$ to keep track of the discovery state of each bl...

A word, phrase, or sequence that reads the same backwards as forwards is a palindrome. For example the sequence "Step on no pets" is a palindrome. Today, let's focus on converting a sequence into a palindrome by inserting characters at arbitrary positions in the original input sequence. Minimum Insertion Steps to Make a String Palindrome - Problem Statement Given an input sequence $s$, in one step you can insert any character at any position of the input sequence. Return the minimum number of steps to make $s$ palindrome. For example, given the input sequence "leetcode", inserting five characters the string becomes "leetcodocteel". This is the minimum number of insertions required to make the input sequence a palindrome. Minimum Insertion Steps to Make a String Palindrome - Definition Let $s$ be an input sequence, $i$ and $j$ denote the start and end positions of a subsequence. Let $p[i][j]$ be the minimum number of insertions required to make subseque...

Graph problems pervade computer science, and algorithms to working with them are fundamental to the field. Hundreds of interesting computational problems are couched in terms of graphs. In this part, we touch the Breadth First Search. Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Given a graph $G = (V, E)$ and a distinguished source vertex $s$, breadth-first search systematically explores the edges of $G$ to discover every vertex that is reachable from $s$. It computes the distance (smallest number of edges) from $s$ to each reachable vertex. [1] Now let’s consider a real world application of the BFS algorithm.  Treasure Island - Problem Definition You have a map that marks the location of a treasure island. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in. There are other explorers trying to find the treasure. So you must figure out a shortest route to th...

 Today, let’s focus on a very good application of the famous algorithm binary search. Most of you may be familiar with binary search since it is widely used to implement different algorithms. In fact, I have used it in a few articles before.  Minimum capacity to ship within given days - Problem statement A conveyor belt has packages that must be shipped from one port to another within $d$ days. The $i^{th}$ package on the conveyor belt has a weight of $w[i]$. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within $d$ days. Also note that we are not allowed to split the items apart and then ship. Minimum capacity to ship within given days - Definition We first need to define the window of possible capacities. Let $w$ be the weight array of item...