Quoting from Dasgupta, Papadimitrou, and Vazirani textbook: “Trees A tree is an undirected graph that is connected and acyclic.” p.135 Trees have these properties, quoting from DPV again: A tree on n nodes has n − 1 edges Any connected, undirected graph G = (V, E) with |E| = |V| − 1 is a tree. […]
A directed graph without any cycle is a Directed Acyclic Graph (DAG). If there is a cycle, then there will be a back edge, which goes backwards. For such edge(u,v), postorder number for u will be smaller than that of v, i.e. post(u) < post(v). So after DFS, if any edge satisfies post(u) < post(v) […]
There can be three types of graphs here. 1. Undirected Graph For undirected graphs, we can use Depth First Search (DFS) to find the connected component number for each vertex. The runtime is O(|V|+|E|). 2. Directed Graph Directed graphs can be of two types. Directed Acyclic Graphs (DAG) and General Directed Graphs. DAGs’s do not […]
In Directed Acyclic Graphs (DAG), there are no cycles. So it is simple to find the connected components just by sorting the vertices by post-order visit number in decreasing order after one run of DFS. The run time for DFS is again O(|V|+|E|)
To find a viable business idea, one needs to delve into one domain of life. Over time, deficiencies in the current status quo becomes visible and opportunities to offer a drastically better solution presents itself. If it does not happen, one needs to seek into a different domain. There is a great essay by YCombinator […]
This is a programming problem where the given array A is of infinite length and we have to find the position of a value x in it. The first n values are sorted and after n-th number, all remaining values in the array are None. For example: A= [1, 3, 5, 100, 102, 1050, 1061, […]
“The more you sweat in peace, the less you bleed in war” “Too bad! Same old story! Once you’ve finished building your house you notice you’ve accidentally learned something that you really should have known—before you started.”– Friedrich Nietzsche, Beyond Good and Evil “if you don’t know where you are going you’ll end up someplace else”
An important Machine Learning concept is Reinforcement Learning which is different from the more common Supervised or Unsupervised Learning models. In Supervised learning, you have the labels for training, in Unsupervised learning, there is no labeled data. Reinforcement Learning falls in between the two because it does not have a label but it learns from […]
Since early on, I was a hardworking student. So my parents continued investing in my education. When I was in grade 8, I convinced my parents to let me go to Dhaka Residential Model College for grade 9-10 because I thought my father will get transferred for his job away from the capital city and […]
Work-in-progress. I will write more about each approach later in details. Just summarizing the tools for connecting to Hadoop and running geospatial processing on a large dataset. I am working on a ~100 GB Hive Table which is just a small subset of the original dataset http://geospark.datasyslab.org/ https://pypi.org/project/geopyspark/ https://github.com/Esri/gis-tools-for-hadoop/wiki Kinetica GPU Database – Graph solver […]