Set Cover Algorithm :1Initialize the set cover C to be empty. Cphi. 2.

the set of
elements already covered from X is E. E phi.3 .repeat steps 4 and 5 while E!=X. 4.Select a
set Si that contains maximum numer of uncovered elements. add this set to set cover
C.CCUSi5. The set of uncovered elements from X is added to E each time a set is
selected.EEUSi6. Return C and exit Vertex Cover Problem :Find Vertex cover of
minimum size.Algorithm:1.Initialize the vertex cover C to be null. Cphi 2.The set of edges in
G is E. 3. Repeat steps 4 to 6 till the set of edges E is empty .4. Choose an arbitrary edge
(u,v) of E. 5.Add the endpoints u, v to vertex cover C. 6. Remove every edge incident on either
u or v from the set of edges E. 7.return C and Exit.

LCS DYANMIC PROGRSMMING: General Strategy:Used for optimization

problems: often minimizing or maximizing.Solves problems by combining solutions to sub-
problems.Sub-problems are not independent.Reduces computation bySolving sub-problems
in a bottom-up fashion.Storing solution to a sub-problem the first time it is solved.Looking up
the solution when subproblem is encountered again.Key: determine structure of optimal
solutionsLONGEST COMMON SUBSEQUENCE:A subsequence is a sequence that appears
in the same relative order, but not necessarily contiguous.In LSC, we have to find Longest
common Subsequence that is in same relative order.String of length n has 2^n different
possible subsequences.E.g.--Subsequences of "ABCDEFG"."ABC", "ABG", "BDF", "AEG",
""ACEFG", ...
Huffman Codes:are an effective technique of 'lossless data compression' which means
no information is lost.The algorithm builds a table of the frequencies of each character in a
fileThe table is then used to determine an optimal way of representing each character as a
binary stringTypically each character in a file is stored as a single byte. (8 bits)If we know we
only have six characters, we can use a 3 bit code for the characters instead:a = 000, b = 001,
c = 010, d=011, e = 100, f = 101This is called a fixed-length codeWith this scheme, we can
encode the whole file with 300,000 bits
(45000*3+13000*3+12000*3+16000*3+9000*3+5000*3)We can do betterBetter
compressionD More flexibilityVariable length codes can perform significantly better Frequent
characters are given short code words, while infrequent characters get longer code
wordsConsider this scheme: a= 0; b-101; c= 100; d=111; e- 1101; 1-1100How many bits are
now required to encode our file?a45,000*1+13,000*3+12,000*3+ 16,000*3+9,000'4+ 5,000*4:
-224,000 bits. This is in fact an optimal character code for this file.Both the encoder and
decoder make use of a binary tree to recognize codes.The leaves of the tree represent the
unencoded characters Each left branch indicates a "O" placed in the encoded bit string.Each
right branch indicates a "1" placed in the bit string. Steps to build Huffman Tree:Input is
an array of unique characters along with their frequency of occurrences and output is Huffman
Tree.1. Create a leaf node for each unique character and build a min heap of all leaf nodes
(Min Heap is used as a priority queue. The value of frequency field is used to compare two
nodes in min heap. Initially, the least frequent character is at root) 2. Extract two nodes with
the minimum frequency from the min heap.create a 3. Create a new internal node with a
frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its
left child and the other extracted node as its right child. Add this node to the min heap.4.
Repeat steps #2 and #3 until the heap contains only one node. The remaining node is the root
node and the tree is complete.To encode:Search the tree for the character to encode. As you
progress, add "0" or "1" to right of codeCode is complete when you findcharacter . To decode
a code:Proceed through bit string left to right For each bit, proceed left or right as indicated
When you reach a leaf, that is the decoded character
Spanning tree is a subset of graph G = (V,E) which has all vertices covered with minimum
number of edges. (n-1) edges. If graph is complete then n^n-2 spanning trees.Number of V
and E are same in all spanning trees. No cycle in spanning tree.Minimum Spanning Tree
(MST)Let G = (V, E) be an undirected connected graph.A sub graph T = (V, E') of G is a
spanning tree of G iff T is a tree.. It is a tree (i.e., it is acyclic)It covers all the vertices V•
contains |V| - I edgesA single graph can have many different spanning treesA minimum cost
spanning tree is a spanning tree which has a minimum total cost.A minimum spanning tree
(MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal
to the weight of every other spanning tree.. Addition of even one single edge results in the
spanning tree losing its property of acyclicity and removal of one single edge results in its
losing the property of connectivity.It is the shortest spanning tree.The length of a tree is equal
to the sum of the length of the arcs on the tree.• If we have a connected undirected graph with
a weight (or cost) associated with each edgeThe cost of a spanning tree would be the sum of
the costs of its edges. A minimum-cost spanning tree is a spanning tree that has the
lowest.Applications of minimum spanning trees• Consider an application where n stations
are to be linked using a communication network.. The laying of communication links between
any two stations involves a cost.. The problem is to obtain a network of communication links
which while preserving the connectivity between stations does it with minimum cost. The
ideal solution to the problem would be to extract a sub graph termed minimum cost spanning
tree.. It preserves the connectedness of the graph yields minimum cost. The phone company
task is to provide phone lines to a village with 10 houses, each labeled Hi through Hio.A single
cable must connects each home. The cable must run through houses H1, H2, and so forth, up
through Hio. Each node is a house, and the edges are the means by which one house can
be wired up to another. The weights of the edges dictate the distance between the homes.
Their task is to wire up all ten houses using the least amount of telephone wiring possible.
GREEDY ALGORITHM:(Optimization Problems):A problem that may have many
feasible solutions.Each solution has a value• In maximization problem, we wish to find a
solution to maximize the value• In the minimization problem, we wish to find a solution to
minimize the value.GREEDY ALGORITHM:Many optimization problems can be solved using
a greedy approach• The basic principle is that local optimal decisions may be used to build an
optimal solution• But the greedy approach may not always lead to an optimal solution overallfor
all problemThe key is knowing which problems will work with this approach and which will not
Greedy Technique: Greedy algorithms are simple and straightforward.• They are
shortsighted in their approach in the sense that they take decisions on the basis of information
at hand without worrying about the effect these decisions may have in the future.• They are
easy to invent, easy to implement and most of the time quite efficient. Many problems cannot
be solved correctly by greedy approach. Greedy algorithms are used to solve
optimization problems
Algorithm: Algorithm Greedy (a, n) {for i=1 to n do ,X = Select (a); If feasible (x) then,
,Solution= Solution + x;}

Knapsack Problem Statement A thief robbing a store and can carry a maximal weight of
w into their knapsack. There are n items and ith item weigh w, and is worth v, dollars. What
items should thief take?• There are two versions of problem. Objects(0)1,2,3,4,5,6,7Profits
(P)10,5,15,7,6,18,3Weight (W),2,3,5,7,1,4.1
Ford Fulkerson algorithm: 1)for each edge (u, v) in E[G]. 2).do f[u, v] = 0. 3)
f[v, u] = 0. 4) while there exists a path p from s to t in the residual network Gf 5) do Cf(p) =
min [ Cf(u, v) |(u,v) is in p}. 6) for each edge (u, v) in p. 7)do f[u, v] = f[u, v] + c_{f}(p)8)f[v,
u] =- hat f [u,v] pseudo code 1)iniitlaoze flow f to0 .2)while there exits an augmenting path
p 3)do augment flow f along p. 4)return f. Introduction network Practical examples of
a network- liquids flowing through pipes- parts through assembly lines current through
electrical network- information through communication network - goods transported on the
road...1.Sink:node with net inflow consumption point.2.capecity:maximum flow on an
edge.3.sporce: node with net outflow production pointFlow propertiesFlow in G = (V, E)
f / V * V -> R with 3 properties:1) Capacity constraint: For all u .v belong to V: f(u, v) <= c(u,
v)2) Skew symmetry:For all u ,v beong to V f(u, v) = - f (v, u)3) Flow conservation: For all u
belong to V backslash\ s.t\ \ s .t\ : Sigma f(u, v) = 0The max-flow problemInformal
definition of the max-flow problem:What is the greatest rate at which material can be shipped
from the source to the sink without violating any capacity contraints?Formal definition of the
max-flow problem:The max-flow problem is to find a valid flow for a given weighted directed
graph G, that has the maximum value over all valid flows.
Bubble Sort Algorithm :Input is the array A with n elementsStep 1. Read the
array AStep 2. Repeat steps 3 to 4 for i = 1 to n-1Step 3. Repeat step 4 for j= 0 to n-i-
1Step 4. If A [j] > A[j+1] then interchange A[j] and A[j+1] using temporary variable.Step 5.
Return A and Exit
SELECTION SORT Algorithm :Input is the array A of n elements.Step 1. Read the array A
Step 2. Repeat steps 3 to 6 for i = 0 to n-1Step 3. Set min = A[i] and set loc = I
Step 4. Repeat step 5 for j = i + 1 to N – 1, Step 5. If min > A[J] then, set min = A[J], set loc =
JStep 6. Interchange A[i] and A[loc] using temporary variable Step 7. Return A and exit

Radix Sort Complexity Analysis of:Radix sort is a non-comparative integer sorting

algorithm that sorts data with integer keys by grouping the keys by the individual digits which
share the same significant position and value. It has a time complexity of O(d * (n + b)),
where d is the number of digits, n is the number of elements, and b is the base of the
number system being used.in practical implementations, radix sort is often faster than other
comparison-based sorting algorithms, such as quicksort or merge sort, for large datasets,
especially when the keys have many digits. However, its time complexity grows linearly with
the number of digits, and so it is not as efficient for small datasets.Radix sort also has a
space complexity of O(n + b), where n is the number of elements and b is the base of the
number system. This space complexity comes from the need to create buckets for each digit
value and to copy the elements back to the original array after each digit has been sorted.

ALGORITHM
code obtained from http://www.geeksforgeeks.org/radix-sort/ */static void countSort(int arr[],
int n, int exp){int output[] = new int[n]; int i;int count[] = new int[10]; Arrays.fill(count,0); for (i
= 0; i < n; i++) count[ (arr[i]/exp)%10 ]++; for (i = 1; i < 10; i++)count[i] += count[i - 1]; for (i =
n - 1; i >= 0; i--) {
HEAPSORT
ALGORITHM:BUILD-MAX-HEAP(A)2.for i<-length downto 2 3.do exchange A[i]<->A[i]
4.heap-size[A]<-heap-size[A]-1. 5.Max-heapify(A,1)