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

Advertisements

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

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