Very quick summary of Union-Find or Disjoint Set data structure

# Tag: algorithms

Kosaraju’s vs Tarjan’s Kosaraju’s algorithm finds the Topological Sorting of the original directed graph. For this, it uses DFS. Next it reverses the graph and runs DFS on the topologically sorted vertices. So it takes two DFS though the time complexity is O(|V|+|E|). Tarjan’s algorithm, on the other hand, only uses one DFS but uses […]

This is a array/string problem and you can look up this problem on HackerRank. To solve this one, it can not theoretically be any better than O(n) time complexity. Here I convert the string to character array, then for each character and if this is a small ASCII character between a-z, then subtract the value […]

This LeetCode problem is a great practice problem to implement a binary search for a value in a sorted array with duplicate values. It asks to find the indices of the first and start the occurrence of a value in the sorted array with possibly duplicate values. It can be solved in a naive manner […]

The Sort Color problem expects to sort the array with values {0, 1, 2}. This can be done in a typical sorting algorithm in O(nlogn) time. A better approach is to use three-way partitioning of the array. Generic three-way partitioning Below the threeWayPartitionSort() method splits the given an array, [3,2,0,2,1,1,0,-1], into three parts, where values […]

This class implements a QuickSort algorithm using Hoare Paritioning scheme. This partitionining scheme is slightly harder to implement but is more efficient than the Lamuto partitioning scheme as it does three times fewer swaps on average [Wikipedia]. Avg Time-Complexity: O(nlogn) Worst Time-Complexity: O(n^2) Space complexity: O(1) Understanding Hoare Partition Intuitively After spending quite some on […]

## Merge Sort (Draft)

First check out the problem description here on LeetCode. The Solution This is marked as a medium difficult problem. However if you know what in-order traversal does, it is a very simple problem. Here I just added a helper traverse() method. All the trick is done in the few lines inside the function. It checks […]

Quick introduction to basic Reinforcement Learning algorithms including Bellman Equation, Policy Iteration, Value Iteration, and Q-Learning

Random Projection is an interesting Dimensionality Reduction technique. You may choose to create a random projection for 1,2,3,..,n dimensional projections. Now how to tell which one is best? So you would need to calculate loss of data due to this reduction in data size. # data has this shape: row, col = 4898, 11 random_projection […]