Graph Algorithms, Dynamic and Greedy Algorithms
Breadth First Search (BFS)
BFS (G, s) //Where G is the graph and s is the source node
let Q be queue.
Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = Q.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
Q.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges.
Depth First Search
DFS-iterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)Kruskal’s Algorithm
KRUSKAL(G): A = ∅ foreach v ∈ G.V: MAKE-SET(v) //make every independent set of an vertex foreach (u, v) in G.E ordered by weight(u, v), increasing:
//edges ko ascending order me lagao if FIND-SET(u) ≠ FIND-SET(v):
// if they found in diff set
A = A ∪ {(u, v)} // union karo A se.
UNION(u, v) // dono ko ek set me combine kardo
return A
Time Complexity :O(E log E)Prim's Algorithm
- MST-PRIM(G, w, r) //Where G is graph and r is source vertex w is the adjacent nodes for each u in V [G] // each vertex in graph do key[u] ← ∞ // set all vertex to infinity π[u] ← NIL // set parent to nil key[r] ← 0 //set source to 0 Q ← V [G] //put all vertex in Queue while Q ≠ Ø //while Q is not empty do u ← EXTRACT-MIN(Q) //Extract min vertex from queue
- for each v in Adj[u] // for each vertex in adj of u do if v in Q and w(u, v) < key[v] then
π[v] ← ukey[v] ← w(u, v)The time complexity is O(VlogV + ElogV) = O(ElogV)
Bellman Ford's Algorithm:
function bellmanFord(G, S) for each vertex V in G distance[V] <- infinite previous[V] <- NULL distance[S] <- 0 for each vertex V in G for each edge (U,V) in G tempDistance <- distance[U] + edge_weight(U, V) if tempDistance < distance[V] distance[V] <- tempDistance previous[V] <- U for each edge (U,V) in G If distance[U] + edge_weight(U, V) < distance[V} Error: Negative Cycle Exists return distance[], previous[]Time Complexity: O(V E)
Djikstra's algorithm
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]
Time Complexity: O(V^2) Floyd Warshall
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
for each vertex v
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
Time Complexity : O(n3)
Multistage Algorithm
To write a simple algorithm, assign numbers to the vertices so those in stage Vi have lower number those in stage Vi+1.
int[] MStageForward(Graph G)
{
// returns vector of vertices to follow through the graph
// let c[i][j] be the cost matrix of G
int n = G.n (number of nodes);
int k = G.k (number of stages);
float[] C = new float[n];
int[] D = new int[n];
int[] P = new int[k];
for (i = 1 to n) C[i] = 0.0;
for j = n-1 to 1 by -1 {
r = vertex such that (j,r) in G.E and c(j,r)+C(r) is minimum
C[j] = c(j,r)+C(r);
D[j] = r;
}
P[1] = 1; P[k] = n;
for j = 2 to k-1 {
P[j] = D[P[j-1]];
}
return P;
}
Time complexity of Multistage Graph is O(n2) or O(V2) Huffman coding
1. Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE).
2. Repeat until the OPEN list has only one node left:
(a) From OPEN pick two nodes having the lowest frequencies/probabilities, create a parent node of them.
(b) Assign the sum of the children's frequencies/probabilities to the parent node and insert it into OPEN.
(c) Assign code 0, 1 to the two branches of the tree, and delete the children from OPEN.
- HUFFMAN(C)
- n ← |C|
- Q ← C
- for i 1 to n - 1
- do allocate a new node z
- left[z] ← x ← EXTRACT-MIN (Q)
- right[z] ← y ← EXTRACT-MIN (Q)
- f [z] ← f [x] + f [y]
- INSERT(Q, z)
- return EXTRACT-MIN(Q)
Time Complexity O(nlogn).
Activity Selection problem :
Greedy-Iterative-Activity-Selector(A, s, f):Sort A by finish times stored in f
S = {A[1]}
k = 1
n = A.length
for i = 2 to n:
if s[i] ≥ f[k]:
S = S U {A[i]}
k = i
return S
The Time complexity of this problem is O(n log n) when the list is not sorted.
When the sorted list is provided the complexity will be O(n).
Job Selection problem :
Algorithm: Job-Sequencing-With-Deadline (D[1...n], J[1....n], n, p[1...n],list[1...n])
- initialize list to 0
- profit=0
- for i to n do:
- k = d[i];
- while(k>0)
- if list[k]=0 then
- list[k]=j[i];
- profit=profit+p[i]
- go to step 3;
- end if
- decrement k by 1
- end while
- end for
- print list
Time Complexity :O(N^2)
0 1 Knapsack problem :
Dynamic-0-1-knapsack (p, w, n, W) for w = 0 to W do c[0, w] = 0 for i = 1 to n do c[i, 0] = 0 for i to n
for w to W do
if w[i] ≤ w then
if p[i] + c[i-1, w-w[i]] then
c[i, w] = p[i] + c[i-1, w-w[i]]
else c[i, w] = c[i-1, w]
end for
print c[n][W]
i=n k=W
while (k>0 & i>0)
if (c[i][k]<>c[i-1][k])
print i
k = k - w[i]
end if
i = i-1
End while
// Input:
// Values (stored in array p ie profit)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "p" and array "w" are assumed to store all relevant values starting at index 1.
Time complexity of 0 1 Knapsack problem is O(nW)
Fractional Knapsack problem :
Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to n
if weight + w[i] ≤ W then
x[i] = 1
weight = weight + w[i]
else
x[i] = (W - weight) / w[i]
weight = W
break
return x
Time Complexity O(n logn).
Matrix chain :
/ Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n MatrixChainOrder(int dims[]) { // length[dims] = n + 1 n = dims.length - 1; // m[i,j] = Minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] // The cost is zero when multiplying one matrix for (i = 1; i <= n; i++) m[i, i] = 0; for (len = 2; len <= n; len++) { // Subsequence lengths for (i = 1; i <= n - len + 1; i++) { j = i + len - 1; m[i, j] = MAXINT; for (k = i; k <= j - 1; k++) { cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j]; if (cost < m[i, j]) { m[i, j] = cost; s[i, j] = k; // Index of the subsequence split that achieved minimal cost } } } } }
Time complexity O(n3)
Space Complexity O(n2)
karatsuba :
procedure karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /* calculates the size of the numbers */ m = min(size_base10(num1), size_base10(num2)) m2 = floor(m/2) /*m2 = ceil(m/2) will also work */ /* split the digit sequences in the middle */ high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(low1, low2) z1 = karatsuba((low1 + high1), (low2 + high2)) z2 = karatsuba(high1, high2) return (z2 * 10 ^ (m2 * 2)) + ((z1 - z2 - z0) * 10 ^ m2) + z0
Time Complexity : O(nlog23) ≈ O(n1.585)
space complexity : O(n)
Strassen's Multiplication :
p= (A11+A22) (B11+B22)
q= B11(A21+A22) //BAAB +--+
r= A11(B12−B22)
s= A22(B21−B11)
t= B22(A11+A12)
u= (A21−A11)(B11+B12) //s+t and exchange A & B
v= (A12−A22)(B21+B22) //r+s and exchange A & B
C11=p+s−t+v
C12=r+t //rat
C21=q+s //r-1 = q t-1=s
C22=p−q+r+u
Time Complexity :O(n^2.80)
Counting inversion :
def mergeSortInversions(arr):
if len(arr) == 1:
return arr, 0
else:
a = arr[:len(arr)/2]
b = arr[len(arr)/2:]
a, ai = mergeSortInversions(a)
b, bi = mergeSortInversions(b)
c = []
i = 0
j = 0
inversions = 0 + ai + bi
while i < len(a) and j < len(b):
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
inversions += (len(a)-i)
c += a[i:]
c += b[j:]
return c, inversions
Time Complexity : O(n * log n)
space complexity: o(n)
Optimal-Binary-Search-Tree(p, q, n)
e[1…n + 1, 0…n],
w[1…n + 1, 0…n],
root[1…n + 1, 0…n]
for i = 1 to n + 1 do
e[i, i - 1] := qi - 1
w[i, i - 1] := qi - 1
for l = 1 to n do
for i = 1 to n – l + 1 do
j = i + l – 1 e[i, j] := ∞
w[i, i] := w[i, i -1] + pj + qj
for r = i to j do
t := e[i, r - 1] + e[r + 1, j] + w[i, j]
if t < e[i, j]
e[i, j] := t
root[i, j] := r
return e and root
Time Complexity : O(n^3)
Longest Common Subsequence
MEMOIZATION(* Straightforward implementation of fib has exponential number of * recursive calls. Requires n non-negative *) let rec fib n = if n < 2 then 1 else fib (n-1) + fib (n-2) (* However most of these recursive calls share common subproblems - * there are only n distinct subproblems to solve, one for each value * of n. The idea of memoization is to keep track of these results so * they can be looked up rather than recomputed. *) let fibm n = let memo : int option array = Array.create (n+1) None in let rec f_mem n = match memo.(n) with Some result -> result (* computed already! *) | None -> let result = if n < 2 then 1 else f_mem (n-1) + f_mem (n-2) in memo.(n) <- Some result; (* record in table *) result in f_mem n
we are given a ground set of n elements E = {e1, e2, . . . , en} and a collection of m subsets of E: S := {S1, S2, · · · , Sm} and a nonnegative weight function cost : S → Q+. We will sometimes use wj = cost(Sj ). The goal is to find a minimum weight collection of subsets that covers all elements in E. Formally we want to find a set cover C that minimizes ΣSj∈C wj subject to S Sj∈C Sj = E. If wj = 1 for all j, then the problem is called the unweighted set cover problem. • Set Cover is a problem whose study has led to the development of fundamental techniques for the entire field of approximation algorithms [2]. • It is a generalization of many other important NPC problems such as vertex cover and edge cover. • It is used in the development of antivirus products, VLSI design and many other practical problems.
APPROXIMATION ALGORITHMS
vertex cover
Set Cover problem,
3.1 Algorithm 1. Initialize C ← φ. 2. While C does not cover all elements in E do (a) Define cost-effectiveness of each set S ∈ S as αS =cost(S)|S\C| (b) Find S, the most cost-effective set in the current iteration. (c) Pick S and for all newly covered elements e ∈ S \ C, set price(e) = αS. (d) C ← C ∪ S. 3. Output C.
Comments
Post a Comment