Blog Feed: Analysis and Design of Algorithms

Back tracking:

Published on 2009-03-17 06:13:00

N-queue:Description: The objective is to place the n queens in each row in the n*n matrix such that no two queens attack each other. Algorithm:Data structures used: n- Hold the no of queens. k – Hold the track of the row. x > read more

Kruskal’s Algorithm

Published on 2009-03-17 06:11:00

Description: For the given connected ,undirected graph G=(v,e),determine the weighted acyclic minimum spanning tree but are not necessarily connected, where weight is defined as the sum of the weights on all its edges. Algorithm:Data structures > read more

Prim’s Algorithm:

Published on 2009-03-17 06:08:00

Description: For the given connected, undirected graph G=(v,e),determine the connected weighted acyclic minimum spanning tree, where weight is defined as the sum of the weights on all its edges. Algorithm:Data structures used: n- Hold the n > read more

Dijikstra’s Algorithm (single source shortest paths problem):

Published on 2009-03-17 05:47:00

Description: For the given weighted connected graph G(v, e) and given vertex(source),find the shortest paths from source vertex to all its other vertices. Example: Consider a directed graphCost matrix V0 V1 V2 V3 V4 V5 > read more

Published on 2009-03-16 08:51:00

2.KNAPSACK:Description: For the given n objects and k knapsack (container).Each object has a weight w and capacity of the knapsack is M. Each object is associated with a profit p that is earned when it is placed in the knapsack.Algorithm:Dat > read more

Greedy algorithms

Published on 2009-03-16 08:47:00

1. Job scheduling:Description: For the set of ‘n’ jobs, each job is associated with a deadline’ di’ and profit ‘pi’,for any job ‘i ‘profit ‘pi’ is earned with the constraintsa.The job is completed by its deadlineb.Only one mac > read more

Depth First Search (DFS):

Published on 2009-03-16 08:41:00

DFS Description: In the DFS the vertex u is picked as source vertex and is visited. A vertex v adjacent to u is picked and is visited and search begins at the vertex v. There may still some nodes which are adjacent to u but not visited. The searc > read more

Graph Traversals

Published on 2009-03-16 08:37:00

1. Breadth First Search (BFS): Description: The technique of visiting all the vertices and identifying the vertices which are reachable from a source vertex is called breadth-first search and in this technique, the vertices are visited in the ord > read more

0/1 knapsack program

Published on 2009-03-16 08:31:00

Program: #define max 30 int knapsack(int ,int ); int maxi(int ,int ); int p[max],w[max],n; void main() { int m,opsol,i; clrscr(); printf("enter the no of objectsn"); scanf("%d",&n); printf("enter d weightsn"); > read more

0/1 knapsack

Published on 2009-03-16 08:28:00

2. 0/1 knapsackDescription: For the given n objects and knapsack (container), each object has a weight w and capacity of the knapsack is M.Each object is associated with a profit p that is earned when it is placed in the knapsack with the cons > read more