Strongly Connected Graph
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
A strongly connected graph is a graph such that there is a path connecting each vertex in the graph to another vertex in the graph.
The strongly connected components (SCCs) of a directed graph G are the equivalence classes of the relation: u~v <-> path u->v AND path v->u. The ~ relation is an equivalence class, that is, ~ is reflexive, symmetric, and transitive. (Reflexive => everybody is related to itself, symmetric => if u is related to v, then v is related to u and Transitive => if u is related to v, v to w then w is related to u )
[Read More]Topological Sorting
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Definition
Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering.
A topological ordering of a directed graph G is a labeling f of G’s nodes (1…n) such that:
(1) the f(v)’s are the set {1, 2, … , n}
(2) if (u, v) in G, then f(u) < f(v) … the graph should move in forward direction.
[Read More]Minimum Cut Problem
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Input - An undirected graph G = (V,E) (note that parallel edges are allowed)
Goal - Tom compute a cut with fewest number of crossing edges (a min cut) The minimum cut problem or min-cut problem is to determine the cut which has the least number of crossing edges.
Please note that to understand mincut, you have to first read what is cut, if you don’t alreadyy know that. So, consider the following graph -
[Read More]Closest Pair Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Here we will discuss about the closest pair algorithm.
Input : A set p = { p1,p2, … pn} of n points in the plane (R2)
Notation d(pi , pj) = Euclidean distance.
d = x
Assumption - All points have distinct x-coordinates distinct y-coordinates.
Brute force method
Say you are given a set of points in the plane and you want to find the two points closest to one another.
[Read More]Randomized Selection : Selecting the i'th smallest element
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Input - array A with n distinct numbers and a number i ∈ {1,2,…,n}
Output : ith order statistic i.e. ith smallest element of the input array
O(n log n) algorithm
Apply mergesort/quicksort Return the ith element of sorted array So, we used reduction via taking the help of sorting algorithm. So this was the naive way as we would be to say, “Hey let’s sort it and then we can just pick out the ith one!
[Read More]Meaning behind Master Method
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
After establishing what the running time of an algorithm based on three variables a, b, d, we might be wondering what is the meaning behind this method. Where do these logs and exponents come from?
If we look at the amount of work done at a single level of the recursion tree, we get that it is,
where aj is the number of level-j subproblems and the rest is the amount of work per level-j subproblem.
[Read More]Master Method for Solving Recurrences
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Why Master method ? - Master method helps us analysing algorithms with their running time.
So, lets consider the integer multiplication - here.
Now we get equation 1.
The way we reason about recursive algorithm like these is with the help of recurrence. Recurrences
What is recurrence?
T(n) = max number of operations this algorithm needs to multiply 2 n digit numbers. Recurrence is to express T(n) in terms of recursive calls.
[Read More]Strassen's Subcubic Matrix Multiplication Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
A Review on Matrix Multiplication
Given two 2 nxn matrices X, Y and their product matrix Z,
X.Y = Z
we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y.
zij = ∑xik . ykj where k is 1 < k < n.
For eg. : Let
X = a b and Y = e f
[Read More]Inversions
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This was taught in Algorithms: Design and Analysis Part I on coursera - how to count inversions.
What is an inversion? An inversion is a pair of objects that are out of order. If we are given an array and our goal is to sort from low to high, an inversion would be two items ai and aj such that ai > aj, but i < j. We can see that they are misplaced.
[Read More]BFS and Undirected Connectivity
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Let G=(V,E) be an undirected graph (Note - for directed graph, better algorithms are available)
Connected Components - the pieces of G, where graphs are connected in equivalence class.
Formal definition of max connectivity - Equivalence relation between 2 vertices u and v for every u to v path in G.
Equivalence relation between 2 vertices means they have to satisfly 3 conditions of equivalence
Reflexive - Everything has to be related to itself Symmetric - If u is related to v, then v is related to u, which is not a problem for undirected graph Transitive - If u and v are related and v and w are related, then u and w are related Application
[Read More]