Ravindra Ranwala's Blog

Introduction 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. Today let’s discuss graph algorithms. In fact, I like this problem so much because it reminds me of my childhood. We were playing this game during our school holidays with our friends and it was fun. Let us get into the details next. Problem Statement You are given an $n \times n$ integer matrix board where the cells are labeled from $1$ to $n^2$ in a Boustrophedon style starting from the bottom left of the board (i.e. $board[n - 1][0]$) and alternating direction each row. You start on square $1$ of the board. In each move, starting from square curr, do the following: Choose a destination square next with a label in the range $[curr + 1, min(curr + 6, n^2)]$ This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the siz...

Today, let’s go to the forest and conduct a survey. This would be an interesting task. We specifically choose rabbits and when we meet one, we ask him, hey How many rabbits of your color have you seen in this forest? In a hypothetical world where you know how to communicate with a rabbit, it would be an amazing activity. Now, let’s get into the problem first. Problem Statement There is a forest with an unknown number of rabbits. We asked $n$ rabbits "How many rabbits have the same color as you?" and collected the answers in an integer array $answers$ where $answers[i]$ is the answer of the $i^{th}$ rabbit. Given the array $answers$, return the minimum number of rabbits that could be in the forest. [1] Example 1: Input: answers = [1,1,2] Output: 5 Explanation: The two rabbits that answered "1" could both be the same color, say red. The rabbit that answered "2" can't be red or the answers would be inconsistent. Say the rabbit that answered "2" ...

Finding the length of a longest wiggle subsequence is an interesting problem. We’ll solve it first using dynamic programming and then using a greedy algorithm. We’ll compare and contrast the two different approaches that we used to solve the problem towards the end of the article. Problem Statement A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences. For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative. In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero. A subsequence is obtained by deleting some elements (possi...

Exercise 9.3-1 asks you to show that the $SELECT$ algorithm still runs in linear time if the elements are divided into groups of 7. This problem asks about dividing into groups of 3. Show that $SELECT$ runs in linear time if you divide the elements into groups whose size is any odd constant greater than 3. Show that $SELECT$ runs in $O(n\; lg\; n)$ time if you divide the elements into groups of size 3 Because the bound in part (b) is just an upper bound, we do not know whether the groups-of-3 strategy actually runs in $O(n)$ time. But by repeating the groups-of-3 idea on the middle groups of medians, we can pick a pivot that guarantees $O(n)$ time. The $SELECT3$ algorithm on the next page determines the $i^{\;th}$ smallest of an input array of $n \gt 1$ distinct elements. Describe in English how the $SELECT3$ algorithm works.Include in your description one or more suitable diagrams. Show that $SELECT3$ runs in $O(n)$ time in the worst case. [1]   The worst-case linear-time median-f...

Problem statement Exercise 9.3-8 The $k$th quantiles of an $n$-element set are the $k$ - 1 order statistics that divide the sorted set into $k$ equal sized sets (to within 1). Give an $O(n \cdot lg k)$-time algorithm to list the $k$th quantiles of a set. [1] Definitions In statistics and probability, quantiles are cut points dividing the range of a probability distribution into continuous intervals with equal probabilities, or dividing the observations in a sample in the same way. There is one fewer quantile than the number of groups created. [2] Approach Let's write a divide and conquer algorithm using selection to solve this problem. What if we find the $l = \lfloor\frac{n \cdot \lfloor\frac{k}{2}\rfloor}{k}\rfloor$ th smallest number  and partition the array around it. Then, we can find the first $\lfloor\frac{k}{2}\rfloor$ cut points in the first half $l$ and the remaining $\lceil\frac{k}{2}\rceil$ cut points in the second half $n - l$. At each step, we keep on dividing $...

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

Today, let’s focus on implementing a regular expression engine. Matching a given input string against a regular expression pattern is a very common application in the real world. Most regular expression engines are far too complex, and are often based on Finite automata state machines. However, our naive implementation doesn’t use Finite automata state machines.  Regular Expression Matching - Problem Statement Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Regular Expression Matching - Definition For the input string $s$ and the pattern $p$, each with length $m$ and $n$ characters respectively, let $t[i][j]$ be the evaluation of the string $s_1 \ldots s_i$ against the pattern $p_1 \ldots p_j$ such that $0 \le i \le m$ and $0 \le j \le n$. H...

 Today, let’s take a look at another interesting exercise given in the CLRS book [1]. Problem Statement Exercise 15.4-6 Give an $O(n \cdot log_2 n)-$ time algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers. (Hint: Observe that the last element of a candidate subsequence of length $i$ is at least as large as the last element of a candidate subsequence of length $i - 1$. Maintain candidate subsequences by linking them through the input sequence.) Longest Monotonically Increasing Subsequence - Approach There may be many different approaches to solve this problem. However, we are going to describe one such approach that we came up with. Each approach has its own strengths and weaknesses. The book [1] suggests a different approach to what we are going to present here. Nonetheless, both the approaches have the same asymptotic time and space complexity. Our approach uses an auxiliary array $m$ to store intermediate results. Finally, this array ...

Introduction In the fractional knapsack problem, the setup is the same in the 0-1 knapsack problem, but the thief can take fractions of items, rather than having to make a binary (0, 1) choice for each item. You can think of an item in the 0-1 knapsack problem as being like a gold ingot and an item in the fractional knapsack problem as more like gold dust. [1] We can solve the fractional knapsack problem by a greedy strategy. To solve the fractional problem, we first compute the value per pound, $v_i/w_i$ for each item. Obeying a greedy strategy, the thief begins by taking as much as possible of the item with the greatest value per pound. If the supply of that item is exhausted, and he can still carry more, he takes as much as possible of the item with the next greatest value per pound, and so forth. [1] Now let’s draw our attention to an exercise in the CLRS book [1]. Exercise 16.2-6 Show how to solve the fractional knapsack problem in $O(n)$ time. [1] By sorting the items by value pe...

 Introduction Weighted interval scheduling is a variant of the Interval scheduling problem described under chapter 16 of our CLRS book [1]. If you are not familiar with the Interval scheduling problem, I would encourage you to read that in the book [1], before proceeding with the rest of this article. Recall that in the original problem we are given a set of $n$ activities, each with associated start time $s_i$ and finish time $f_i$. Our objective is to find the maximum subset of non-overlapping activities. Moreover, the problem of finding the maximum subset of compatible activities exhibits the greedy choice property. Now with this information in mind, let’s move on to our new variant.   Problem Statement Exercise 16.1-5 Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to start and finish time, a value $v_i$. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value...