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

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

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