Thursday, 12 December 2013

Check if graph is semiconnected

›
22.5-7 A directed graph G=(V,E) is semiconnected if, for all pairs of vertices (u,v) we have u to v or v to u. Give an efficient a...

Check if graph is singly connected

›
A directed graph G = (V,E) is singly connected if there is at most one directed path from u to v for all vertices u, v  in V . Give an effi...
1 comment:

DFS using stack not recursion.

›
s[x] = start time of x; f[x]= finish time of x color[x] - stores the state of the vertex WHITE: undiscovered GRAY: still processing BL...

Check if a graph is bipartite/ determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy.

›
Algorithm: Perform as many BFS's as needed to cover all vertices. Assign all wrestlers whose distance is even as good guys and all w...
Tuesday, 10 December 2013

Show that determining whether a directed graph G contains a universal sink – a vertex of indegree |V| - 1 and outdegree 0 – can be determined in time O(V ).

›
How many sinks could a graph have? 0 or 1 How can we determine whether a given vertex u is a universal sink? The u row must co...
Tuesday, 22 October 2013

Matrix exponentiation

›
The Tribonacci Numbers: F(n) = F(n-1) + F(n-2) + F(n-3), F(1) = 1; F(2) = 1; F(3) = 2   * for N as large as 10^15, using dp will alwa...
Sunday, 1 September 2013

Median of medians

›
Median of Medians Algorithm Quickselect is linear-time on average, but it can require quadratic time with poor pivot choices. This is ...
3 comments: