QUICKSORT:
Pick pivot. All left of pivot should be less than the pivot, same for the right.
Partitioning can be done in O(n) time.
Reduces problem size. Doesn't need extra memory.
- Choose pivot element.
- Rearrange such that everything left of it is smaller.
PARTITION SUBROUTINE:
If not element, chose another element and swap with the first element for the pivot.
Divide into two- what we have seen and what we haven't seen. First part will be partitioned the right way. ie: Everything smaller than the pivot will be left of the pivot.
j - Boundary point between what we have seen and what we haven't.
i - Boundary between less than pivot and more than pivot. Hence, it points to the last element smaller than pivot.
QUICKSORT (Array, N){
if n=1 return;
P = choose_Pivot(A,n);
Partition A around p;
Recursively call first part;
Recursively call second part.
}
Running time depends on how well the pivot element is chosen.
NOTE: If a sorted array is passed to QuickSort, the running time will be O(N^2).
For every array size n for QuickSort, the average running time will be O(NlogN).
Best case would be to choose the median everytime, but a 25-75 split is good enough to get O(nlogn) time.
-----------------------------------------------------------
MASTER THEOREM:
Recursive Algo:
Base case, Work done in recursive call, work done outside the recursive call.
Assumptions :
All subproblems have the same size.
n is a power of b.
Master Format: T(N) <= aT(N/b) + O(N^d) or T(N) <= aT(N/b) + cN^d.
- a-> No of recursive calls. or RATE OF SUBPROBLEM PROLIFERATION (RSP). (Evil)
- b-> input size shrinkage factor
- d->Exponent of work done outside recursive calls.
- b^d -> RATE OF WORK SHRINKAGE (RWS). (Good)
T(N) <= cN^d[a/b^d]^j. (Use merge sort to come to this conclusion) ie:Total work <= cn^d(Work outside recursion) * (sigma from 0 to logba)(a/b^d)^j.
- RSP = RWS : Same amount of work done at each level. Like merge sort. Hence, expect O(nlogn).(Because in the equation, a/b^d =1)
- RSP < RWS: Less and less work with every level. Hence, max work is done at root. Hence, we consider only root time as it will dominate over the rest. Expect O(n^d).
- RSP > RWS: More work done with each level. hence, max work is at leaves. Then leaves time will dominate. Hence, consider only that. Depth of leaves will be O(log(base b)N).
a^(log(base b)N) = No of leaves in a recursion tree.
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.
