Kosaraju's SSC algorithm is used to find the strongly connected components(SSC) in a directed graph. What are SSC? An intuitive definition is that SSC's are parts of the graph where you can move from one node to any other node in that part. Kosaraju's devious algorithm works by using two passes of DFS. In the … Continue reading Finding strongly connected component’s using Kosaraju’s SSC algorithm

# Author: Ninad Phalak

# Karger’s algorithm for finding minimum graph cut

Karger's algorithm is used for finding the minimum cut in a graph, i.e it cuts the graph into two halves such that the number of crossing edges across the two halves is minimum. Karger Algorithm is given as: 1) Initialize contracted graph G as copy of original graph 2) While there are more than 2 … Continue reading Karger’s algorithm for finding minimum graph cut

# Quicksort

Note: Github link for below code is here Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore three different pivoting rules. You should not … Continue reading Quicksort

# MergeSort and counting inversions

Below is an implementation of MergeSort and which also counts the number of Inversions. I'm assuming you are already familiar with Mergesort. Definition of an inversion is that If i < j and A[i] > A[j] then we have one inversion. The trick to calculate the number of inversions in O(nlogn) time is piggy back … Continue reading MergeSort and counting inversions

# Using Remote Desktop Connection( RDC) to connect to RedHat( RHEL)

I have a Linux workstation and a Windows laptop and I thought it might handy to be able to connect remotely from my laptop to my Linux workstation if I'm working from home. One way to do this is to setup TightVNC server on your workstation and then install a client on your laptop, but … Continue reading Using Remote Desktop Connection( RDC) to connect to RedHat( RHEL)

# Multiplying two very large integers with Karatsuba algorithm

So: what's the product of the following two 64-digit numbers? 9251592653589793238462643383279502884197169399375105820974944456 8978281828459045235360287471352662497757247093699959574966967789 You are given two 64 digit numbers and are asked to find the result. Our grade school multiplication takes O(n2) time. We can do better than this using the Karatsuba multiplication technique. Googling Karatsuba will give you plenty explanations to this algorithm, so … Continue reading Multiplying two very large integers with Karatsuba algorithm

# Git cherry-picking multiple commits from one branch into another branch

How do you move an entire feature you worked on in git to another branch( e.g. the master branch)? For that you would need to pick multiple commits to git from an older feature branch, say 6.1 to an.other branch, say master. Use the git cherry-pick command to pick your earlier commits from your 6.1 … Continue reading Git cherry-picking multiple commits from one branch into another branch

# My mini interpreter using Prolog

One of my projects while doing my masters in CS at UT Dallas was creating an interpreter in Prolog that can parse a custom set of instructions(like if conditions, loops, arithmetic etc.) . So let's say the user input to the interpreter will consist of two inputs that are provided in variables x and y. If we … Continue reading My mini interpreter using Prolog

# Things to come

This is my very first post! My intention is to use this site like a scratch pad for publishing my very own technical posts. Ciao for now..