C Programmes

Problem :- The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem. Idea:-  Place the queens column wise, start from the left most column If all queens are placed. return true and print the solution matrix. Else Try all the rows in the current column. Check if queen can be placed here safely if yes mark the current cell in solution matrix as 1 and try to solve the rest of the problem recursively. If placing the queen in above step leads to the solution return true. If placing the queen in above step does not lead to the solution , BACKTRACK, mark the current cell in solution matrix as 0 and return false. If all the rows are tried and nothing worked, return false and print NO SOLUTION. Algo :-  NQueen(k,n) { for(i=1 to n) do { if(place(k,i)) then { x[k]=i; if(k==n) then write (x[1:n])...

Problem :-  the  largest increasing subsequence  problem is to find a subsequence of a given  sequence  in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example :- Input : arr[] = {3, 10, 2, 1, 20} Output : Length of LIS = 3 Algo : - Input : arr[] Output : Length of LIS for(i=1 to n) LIS[i]=1 for(i=2 to n) for(j=i-1 to 1) if(LIS[i]<LIS[j]+1) && (A[j]<A[i]) LIS[i]=LIS[j]+1 Programme :-  Download the programme #include<stdio.h> main() { int n,i,j; printf("ENTER THE SIZE OF ARRAY:"); scanf("%d",&n); int a[n],lis[n]; printf("ENTER ARRAY ELEMENTS:"); for(i=0;i<n;i++) { scanf("%d",&a[i]); lis[i]=1; } int max=0,maxInd; for(i=1;i<n;i++) { for(j=0;j<i...

Problem  :-    Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.  Example :-    s1=Howard s2=Hogwartz s(Ans)=Howar  |s|=5 Use Desktop Version Of This Site For Better View. Idea :-  LCS[m][n] stores the solution of first m chars of s1 and first n chars of s2(sub problem). LCS[m][n] = LCS[m-1][n-1]    if s1[m]=s2[n]                              =  max(LCS[m-1][n] , LCS[m,n-1])   otherwise              where m is the no. of chars to be consider of s1(substring) and n is no. of chars to be consider of s2(substring). Programme :-  Download The Programme #include<stdio.h>  char s1[20],s2[20]; int findmax(int x,int y) { ...

➤ Greedy algo does not give optimal solution everytime.       Exa. Consider  n=3 and Capacity W=30               w={20,10,5}               p={180,80,50}               p/w={9,8,10}               greedy solution={1,0,1} ➝ profit =180+50=230               optimal solution={1,1,0} ➝ profit=180+80=260 Algo :-  w[i] gives weight of ith item. p[i] gives value(profit) of ith item. sol[i][j] gives the maximum profit for i items and j capacity(sub problem) Use Desktop Version Of This Site For Better View. for(j=0 to m) ➝ No Capicity No Packets      sol[0][j]=0 for(i=0 to m) ➝ No Items      sol[i][0]=0 for(i=1 to n)       for(j=1 to m)           if(w[i] > j)      ...

Greedy may not give optimal solution everytime. Make change Problem - Greedy Algo Example : Coins  : { 1 ,  3 , 4  } Amount : 6 Solution Given By Greedy : { 4 , 1 , 1 } Optimal Solution : { 3 , 3 } Dynamic Programming : Algo : fun makechange(N) { array d[1...n]=[1,4,6]; array c[1...n,0...N] for i=1 to n do c[i,0]=0 for j=1 to N do c[i,j] = if i=1 & j<d[i] then +  ∞ else if i=1 then 1+c[1,j-d[1]]; else if j<d[i] then c[i-1,j] else min(c[i-1][j] ,1+c[i,j-d[i]]); return c[n,N]; } Programme : Download Programme #include<stdio.h> #include<stdlib.h> #include<limits.h> int min(int x,int y) { int min; if(x>y) { min=y; } else { min=x; } return min; } void make_change(int N) { int i,j; int d[4]={0,1,4,6}; int c[4][N+1]; printf("...

Djikstra's algorithm   solves the problem of finding the shortest path from a point in a graph (the  source ) to a destination. It turns out that one can find the shortest paths from a given source to  all  points in a graph in the same time, hence this problem is sometimes called the  single-source shortest paths  problem. This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G = (V,E) where V is a set of vertices and E is a set of edges. Dijkstra's algorithm keeps two sets of vertices: S    the set of vertices whose shortest paths from the source have already been determined  and V-    S :   the remaining v...

Dynamic Systems Development Method(DSDM) :- Dynamic system development method is approach to system development which as the name suggests develops the system dynamically it is a Rapid application development that uses incremental Prototyping. The DSDM philosophy is borrowed from a modified version of " Pareto Principle " Pareto Principle :-  80% of an application can be delivered in 20% of the time it would take to deliver the complete(100%) application. DSDM is an iterative software process in which each iteration follows 80% rule. That is only enough work is required for each increment to start next increment The remaining work can be completed later when more requirements are known or changes have been requested. DSDM life cycle defines 3 different cycles preceded by 2 additional life cycle activities ( FBFDI ) Feasibility Study :-  establishes the basic business requirements and constraint associated with the application to be built. and Identifie...

Adaptive Software Development (ASD) :- Adaptive Software Development(ASD) has been proposed by Jim High smith as technique for building complex software and system. ASD focus on human collaboration and team self-organization. Jim High smith defines an ASD "Life Cycle" that consist of three phases  Speculation Collaboration learning  During speculation, the project is initiated and adaptive cycle planning is conducted. Adaptive cycle planning uses project Initiation information,the customer's mission statement ,basic requirements and project constraint to define the set of release cycles that will be required for the project. Collaboration encompasses communication and team-work but it also enphasizes individualism because individual creativity plays an important role in collaborative thinking.It is all above all,a matter of trust. people working together must trust one another to comment without war help without irritation work as hard as ...

PROBLEM :                  Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. To understand Kruskal's algorithm let us consider the following example − Step 1 - Remove all loops and Parallel Edges Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and ove all others. Step 2 - Arrange all edges in their increasing order of weight The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost). Step 3 - Add the edge which has the least weightage Now we start adding edges to the graph beginning from the one which has the least weight. Th...