Randomized Selection and Graph Intro

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.