Nth order statistic: The nth smallest element in the array.
Median : (n+1)/2 -> N is odd.
(n/2) -> N is even.
Randomized Selection( Array A, int N, order statistic i){
if n=1 return A[i];
Choose pivot p from A uniformly at random.
Partition A around p and let j be the index of p.
if j=i, return p;
if (j>i) RSelect(first half of A,j-1,i);
if(j
}
Average running time : O(n).
Expected running time: O(nlogn)
Worst Cse:O(n^2)
ANALYSIS:
RSelect is in phase j if the array size is between (0.75)^(j+1)N and (0.75)^(j)N.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
GRAPHS:
Remember the basic notations, V- vertices, E edges.
Parallel Edge: More than one direct connection between two nodes.
Connected: In one piece.
Fewest No of edges in a connected non-parallel graph: V-1.
Max : V(V-1)/2
MIN CUT PROBLEM: Cut a graph in two pieces such that they have the minimum number of crossing edges.
Basic Notation: N- no of vertices, M- no of edges.
SPARSH VS DENSE GRAPH:
In sparse, M is O(N) or close to it.
In Dense, M is O(N^2) or close to it.
ADJACENCY LISTS VS MATRICES: Usage depends on the graph density.
Ad Matrix Space : O(N^2).
Ad List Space: O(m+n)
RANDOM CONTRACTION ALGORITHM:
While there are more than two vertices:
Pick a remaining edge (u,v) at random.
Merge u and v into a single vertex.
Remove self loops.
Return cut represented by the final two vertices.
Conditions: Let\s say we want output as supernodes A and B with the interconnecting edges represented as F. We will only get the desired output if any edge from F is never contracted.
GRAPH CONNECTIVITY.
The goal of Searching in a graph: O(m+n) time.
Generic Search Algorithm (Given graph G, initial vertex S){
Initially, S explored, all other vertexes unexplored.
While possible:
Choose an edge(u,v) with one explored and one unexplored.
Mark the new vertex explored.
BFS: (Explores nodes in layers, Uses Queue)
- Can compute shortest paths.
- Can compute connected components of an undirected graph.
DFS:(Explores aggressively, uses stack)
- Compute topological ordering or a directed acyclic graph.
- Can compute connected components of a directed graph.
BFS:(Graph G, start vertex S):
Mark S explored.
Q= queue, initialized with S.
While(Q!=null):
Remove the first node of Q, call it v.
For each edge(v,w):
Mark w explored; add to Queue
COMPUTE SHORTEST PATH:
Use BFS only, add extra code:
Initialize dist(V) : 0 if V==s, infinite if V!=S.
When considering edge (v,w) : if W is unexplored, dist(w) = dist(v) +1;
UNDIRECTED CONNECTIVITY:
To compute all components:
All nodes unexplored.
for i =1 to n (n number of nodes):
if (i not explored): BFS(G,i);
Running Time : O(m+n).
----------------------------------------------------------------------------------------------------
DFS Algo:
mimics BFS, uses a stack; Can do the whole thing recursively too. Try it out.
DFS(Graph G , vertex S):
Mark S explored.
For every edge (S,v):
if V unepxlored:
DFS(G,v).
%f(v) = current_label--;% (F rom topological sort)
------------------------------------------------------------------------------------------------------------
Topological Ordering:
Let V be the sink vertex of graph G.
F(V) = n.
Delete that node and recurse on G-{v}
A topological ordering of a directed graph is a labelling F of G's nodes such that:
- F(v) belongs to the set of vertexes.
- (u,v) -> f(u)
If G is cyclic, there can be no topological sort.
Every directed acyclic graph has a sink vertex.
DFS_LOOP(GRAPH G):
mark all nodes unexplored.
current_label = n,
for each vertex v in G:
if v is not explored:
DFS(G,v).
---------------------------------------------------------------------------------------------------------
STRONGLY CONNECTED COMPONENTS:
A graph is strongly connected if you can get from any one point to any other point.
Problem: We can get an SCC only if we start from the right node.
KOSARAJU'S TWO PASS ALGORITHM:
1) Reverse all the paths of the graph. Represented by G^(rev).
2) Run DFS-LOOP n the reverse graph from the highest node to the lowest. (It will compute a magical ordering of nodes).
-Let f(v) be the finishing time of each vertex.
3) Run DFS-LOOP on the original graph. (Once it goes through the magical prdering, it will reveal the SCC's one by one).
-SCC's - All nodes which have the same leader.
DFS Loop(Graph G):
global variable t = 0 (# of nodes so far) (For first pass).
global variable s = NULL (most recent source vertex) (For second pass).
Assume nodes labelled 1 to n.
for i =1 to n:
if i unexplored:
S:=i;
DFS(G,i);
DFS(Graph G, vertex i):
mark i as explored.
set leader(i) = s; //second pass
for (each arc(i,j)):
if j unexplored.
DFS(G,j);
t++; //first pass
set (f(i) = t; //first pass
- SCC's can have complex structures but if we zoom out and treat every SCC as a single node, they have a simple directed acyclic graph.
- If SCC1 has an outer edge to SCC2, then max F(SCC2) > max F(SCC1).
- Leader is the same as the highest finishing time for that SCC.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
STRUCTURE OF THE WEB (OPTIONAL):
Vertices: Web Pages
Directed edges: Hyperlinks
