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 Data Science

Stock Prediction Using Deep Learning

Recently have been looking into some stock market prediction libraries and repositories for our group project for CS7643 Deep Learning at Georgia Tech. Previously I worked on traditional Machine Learning algorithms and Q-Learning algorithm from Reinforcement Learning for CS7646: Machine Learning for Trading commonly known as the “ML4T course”. My codes for ML4T is locked […]

Categories
Algorithms

LeetCode: Find Peak Element Solution

The Find Peak Element problem can be solved using a linear search in O(n) time and O(1) space. but it can be even better to solve it by binary search in O(log n) time complexity. But there can be two cases for binary search solution, the recursive solution creates stacks for each call and thus […]

Categories
Algorithms

LeetCode: Kth Largest Element in an Array using QuickSelect with Hoare Partition

Find Kth Largest Element in an Array is a problem which can be solved using e.g. QuickSort in O(nlogn) time and then pick the k-th element in the sorted array. Another way is to sort it using QuickSelect in O(n) times. The solution below beats 100% Java submissions on LeetCode for runtime. QuickSelect QuickSelect is […]

Categories
Algorithms Data Science

Resources to Understand Transformer Architecture in NLP

Posting some great resources to understand the Transformer architecture for NLP presented in the paper “Attention is All You Need” (Vaswani et al. 2017). This website by J Al-Ammar is excellent The next best resource is this annotated implementation of Transformer in PyTorch from Harvard University Second, read this article called “Attention! Attention!” by Lilian […]

Categories
Data Science

SQL Notes for Data Science

SQL is one of the most widely used programming language but yet it remains too much undervalued. Here is some quick SQL query snippets for refreshing the memory. Introductory Concepts Optional: Learn about FOREIGN KEY and PRIMARY KEY and the different Database Normalization types from this Wikipedia page. Probably you will need only up to […]