Categories
Algorithms

Union-Find (aka Disjoint Set) Data Structure

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

Categories
Algorithms

Strongly Connected Component using Tarjan’s Algorithm

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 […]

Categories
Algorithms

Hacker Rank: Caesar Cipher aka Rotational Cipher

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 […]

Categories
Algorithms

LeetCode#34: Find First and Last Position of Element in Sorted Array

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 […]

Categories
Algorithms

LeetCode#75: Sort Color using Three-way Partitioning

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 […]

Categories
Algorithms

Understanding Quick Sort and QuickSelect using Hoare Partition

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 […]

Categories
Uncategorized

Merge Sort (Draft)

Categories
Algorithms

LeetCode#94: Binary Tree Inorder Traversal

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 […]

Categories
Algorithms Data Science

Policy Iteration, Value Iteration, and Q-Learning

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

Categories
Algorithms OMSCS

How To Compute Reconstruction Error for Random Projection

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 […]