C Programmes

Problem Statement : -  Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’. Operations and their Cost which we can perform to achieve this goal Insert - 1 Delete - 1 Replace - 2 (Note : Delete The Element + Insert New Element) Example 1 : - Input : s1= Hogward , s2= Hogwartz Output : 4 E xplanation : 1. Insert 'g' at index 3 ; cost = 1 2. Replace 'd' with 't' at index 7; cost = 2 3. Insert 'z' at index 8 = 1; cost=1 Total cost = 1+2+1 = 4 Idea : - We create array MED of  Size M * N where M= length of s1 N= length of s2 To Solve This Problem We use Dynamic Approach. We solve All sub problem which is |sub1|=m , |sub2|=n  where m <=|s1| and n<=|s2| If last characters of two strings are same, nothing need to do. So we use Previous Solution and Recur for...

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) { ...