Under Graduate

Copy code Algorithm Input An array of numbers Output Min and max Complexity O(n) Minmax (A) 1 set n=number of element in array; 2 initialize min=max=a[1]; 3 for i=1 to n 4 if (A[i]<min) 5=”” then=”” min=”A[i];” 6=”” if=”” (a[i]=””>max) 7 Then max =A[i]; 8 print min and max; Algorithm Description A is the array […]

Copy code Algorithm Input n=No of element in the series Output Sum of series of n elements Complexity O(nlogn) Fibonacci(fib,n) 1. Set sum=0; 2. If (n==0 or n==1) then 3. fib=n; 4. Sum=sum+fib; 5. Return fib.; 6. Call Fibonacci(fibA,n-2); 7. Call Fibonacci(fibB,n-1); 8. Set Fib=fibA+fibB; 9. Sum=sum+fib; 10. Return Fib; 11. Outside the function print […]

Copy code Algorithm Input An integer and number of digits in the integer Output Number is Armstrong or not. Complexity O(d) where d is the number of digits in the integer Armstrong(num,digits) 1 n=num 2 while(num>0) do 3 digit =n%10; 4 sum=sum+pow(digit,digits) 5 n= n/10; 6 if (sum =num) 7 print it is an Armstrong […]

Copy code Algorithm Input Lower case character Output Uppercase character. Complexity O (n). Upper to lower case (char[]) 1. Set n=number of character in char[]; 2. For i=1 to n 3. Do if (95 <=char[i] <=122) 4. Then char[i]=(char[i]-32); 5. Print char[i]; Algorithm Description 1. Chat[] :character array; 2. For loop for each element in […]

Copy code Algorithm Input The probabilities p1, …, pn and q0, …, qn and the size n, and it returns the tables e and root. Output It returns the tables e and root. Complexity O(n^3). OPTIMAL-BST(p, q, n) 1 for i = 1 to n + 1 2 do e[i, i – 1] = qi-1 […]

Copy code Algorithm Input Uppercase character. Output Lower case character. Complexity O (n). Upper to lower case (char[]) 1. Set n=number of character in char[]; 2. For i=1 to n 3. Do if (65 <=char[i] <=90) 4. Then char[i]=(char[i]+32); 5. Print char[i]; Algorithm Description Char[] :character array; For loop for each element in the array. […]

Copy code Algorithm Copy code C Code //WAP to implement Depth First Search #include<stdio.h> #include<conio.h> int n,adj[10][10],visited[10]; void input(); void dfs(int); int main() { int s; printf(“Enter no. of nodes in a Graph “); scanf(“%d”,&n); input(); printf(“From which node u wanna start dfs “); scanf(“%d”,&s); if(s>n) printf(“Invalid node “); else { printf(“DFS output is :\n”); […]

Copy code Algorithm Input No. of nodes in graph (tested for 10 nodes) and its adjacency matrix Output Breadth First traversal of Graph Complexity O(V+E) BFS(G) 1. Initialize all vertices to the ready state (STATUS = 1) 2. Put the starting vertex A in QUEUE and change the status of A to the waiting state […]

Copy code Algorithm Input Graph (G). Output Sorted path from source to destination . Complexity O(vlogv+E). Initialize (G, s) 1 for each vertex v in V[G] 2 do d[v]= ∞ 3 parent[v] =NIL 4 d[s] =0 Relax (u, v, w) 1 if d[v] > d[u] + w (u, v) 2 then d[v] = d[u] + […]

Copy code Algorithm Input Adjacent vertices of every node. Output Euler path exist or not. complexity O (1). Eular_path (G); For Each Vertex v ϵ V (G) Enter No. of Adjacent Vertex. If (vertex % 2=1) Count++; If (count=2) Print Graph contains Euler path. Else Print Euler path doesn’t exist. Algorithm Description G: graph, v: […]

Copy code Algorithm Randmized select(a,p,r,i) 1. If(p=r) then Return a[p]; 2. q=randomized partition(a,p,r) k=q-p+1; 3. if (i=k)then return a[q]; 4. else if (i<k)then return randmized select(a,p q-1,i); 5. else return randomized select (a,q+1,r,i-k) randomized partition(a,p,r) 1 x=a[r]; 2 i=p-1; 3 for j=p to r-1 4 do if (a[j]<=x) then i=i+1; exchange a[i+1] and a[j]; 5 […]

Copy code Algorithm Input An integer to be enqueue. Output An integer to be dequeue. Complexity O(n). Enqueue() 1. Top1= Top1 +1; 2. A1[Top1]=item; Dequeue() 1. If(Top=-1)then Print queue is empty; 2. While(top1>=0) Do Top2=Top2+1; A2[Top2]=A1[Top1]; Top1=Top1-1; End of loop. 3. Print A2[Top2]; 4. Top2=Top2-1; 5. While(Top2>=0) Top1=Top1+1; A1[Top1]=A2[Top2]; Top2 =Top2-1; Algorithm Description We are […]

Copy code Algorithm [This algorithm takes a graph G as an input and w is the weight. Here V[G] are the set of vertices of a graph. (u,v) is an edge between any two vertices u and v. Finally it returns a set A having edges for Minimum spanning tree of G] Input No. of […]

Copy code Algorithm Input Two Strings (tested for 20 character string) Output Longest Common Subsequence Complexity O(mn) LCS(X, Y) [length[X] counts the length of String X. b and c matrix is maintained in which information about longest common subsequence is stored using dynamic programming.] 1 m ← length[X] 2 n ← length[Y] 3 for i […]

Copy code Algorithm Input No. of Vertex , Edges weights between vertices Output Minimum spanning tree of graph Complexity O(E + V lg V) MST-PRIM(G, w, r) [This algorithm takes a graph G as an input and w is the weight. Here V[G] are the set of vertices of a graph. (u,v) is an edge […]

Copy code Algorithm Input Array of integers (tested for 20 inputs) Output Sorted sequence Complexity Worst case : Θ(n2) QUICKSORT(A, p, r) [Quicksort is based on the divide-and-conquer paradigm which takes an array A to sort. Here the initial call is QUICKSORT(A, 1, length[A]) so p is the first element and r is the last […]

Copy code Algorithm input Number of disk output Print: disk moved successfully complexity O(n). Tower(n , beg , aux , end) 1. If (n=1) then Beg = end; Return; 2. Call Tower(n-1 , beg ,end , aug ); 3. Call Tower (1 ,beg ,aux ,end ); 4. Call Tower (n-1,aux ,beg ,end); Algorithm Description Copy […]

This problem discusses all the implementation of the linked list functions Copy code Algorithm Getnode()//creates node 1. [allocate memory for node] Set temp:=(node *)malloc(sizeof(node)); 2. If (temp==NULL) then: return “error” and exit 3. Else return temp; 4. Exit Insert_beg(x)//inserts element x at beginning of list 1. Call getnode(); 2. [store value in newly created node] […]

Copy code Algorithm Push(stack, top, maxstk, item)// inserts an item onto the stack 1. [stack already filled?] If top = maxstk then : print : OVERFLOW and return. 2. Set top : = top +1 . [increases top by 1] 3. Set stack[top] := item [inserts item in new TOP position] 4. Return. Pop(stack, top, […]

Copy code Algorithm Enqueue(queue, n, front, rear, item)//inserts item into a queue 1. [queue already filled?] If front := 1 and rear := n or front := rear +1 then: Print OVERFLOW and return 2. [find new value of rear] If front : =NULL , then [Q initially empty] Set front := 1 and rear […]

Copy code Algorithm Input Array of integers Output Loc of searched element. Complexity O(logn). Binary_search(a,n) 1. [initialize segment variables] Set beg:=0,end:=n and mid:=int((beg+end)/2); 2. Repeat steps 3 to 6 while beg<= end and a[mid]!=item 3. If item<a[mid] then : set end := mid-1; 4. Else Set beg:= mid+1; 5. Set mid := int((beg+end)/2) 6. [end […]

Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Bubble_sort(A,n)//here A is an array with n elements and this algorithm sorts the element in A. 1. Repeat steps 2 -5 for i=1 to n-1 2. Set j := 1;[initializes pass pointer j] 3. Repeat while (j<= n-i):[executes passes] 4. If A[j]>A[j+1] then: […]

Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Min_val(a,I,n) This procedure finds the location loc of the smallest element in array a of size n 1. Set min = a[I] and loc = I [Initializes pointers] 2. Repeat step 3 for j = I+1 to n 3. If min>A[j] then: a. […]

Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Insertion_sort(a,n) 1. Set n=Input size of array; 2. Repeat steps 4-10 for i=1 to n 3. Set temp = a[i]; 4. Set j = i-1; 5. Repeat steps 7-9 while( temp<a[j]) 6. Set a[j+1] = a[j]; 7. [decrease j] j= j-1; 8. If […]

Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n). COUNTING-SORT(A, B, k) 1 for i ← 0 to k 2 do C[i] ← 0 3 for j ← 1 to length[A] 4 do C[A[j]] ← C[A[j]] + 1 5 C[i] now contains the number of elements equal to i. 6 for i […]

Copy code Algorithm An array contains n-1 unique integers in the range [0,n-1]that is there one number from the range that is not in A. Design an O(n) time algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself Missing number (A,size)//returns the missing element in […]

Copy code Algorithm Suppose each row of an nXn array A consists of 1’s and 0’s such that in any row I of A all the 1’s come before any 0’s in that row. Suppose further that the number of 1’s in the row I is atleast the number in row I+1,for I=0,1….n-2.Assuming A is […]

Solve Josephus permutation problem which is defined as: Suppose n people are arranged in a circle & we are given a positive integer m n) { System.out.println(“\n m should be less than n… Enter m again :”) ; m = Integer.parseInt(br.readLine()); } int a[] = new int[10]; for(i=0;i<n;i++) a[i] = 0; m1 = m; System.out.print […]

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately they don’t know which one. To make the matter worse the poison the spy […]

Copy code Algorithm Insert(n) //creates BST and inserts node n 1. [initialize pointer] *t := root; 2. Check if (root==NULL) then: a. Allocate memory for root node. b. Set root->data := n and root->r:=root->l:=NULL; 3. Else a. Repeat steps b, c, and d while(t) b. If (n<t->data) then: i. If(t->l!=NULL) then : Set t := […]

Copy code Algorithm Input Number of voter .leader id Output Winner of the election. complexity O(n). Election() 1. Set n=Input number of candidates participating in election. 2. Set b[X] //input vote from X number of voters where X is unknown 3. for j=1 to n. 4. do Initialize candidate array a[j] = 0 5. for […]

To find the order of the four railroad cars moving-in and moving out on the tracks numbered 1-4. Copy code Algorithm Input Order of car. Output Order is possible or not Complexity O(c). Algo_car() 1. i=j=k=flag=0 and top=-1 //Initialize segment variables; 2. For i=0 to 3. 3. do perm[i] //input the order in which railroad […]

Copy code Algorithm Input Number of parking slots and wake up sequence. Output Parking order. Complexity O(m). Parking() 1. Set m= number of parking slots. 2. Set A[] wake up sequence. 3. Set b[i] = stores the parking order. 4. Repeat for i=1 to m. Do If ( b[a[i]]==0 ) then Set b[a[i]] = i. […]

Copy code Algorithm Input Two string s1 and s2. Output S1 is anagram of s2 or not. complexity O(n). Anagram(s1,s2) 1. [Initialize segment variables] MAX_ASCII := 127, TRUE := 1 and FALSE :=0. 2. Set freq[i] : = 0 for i=0 to MAX_ASCII 3. Repeat while(*s1) Set freq[(INT) *s1++]++. 4. Repeat while(*s2) Set freq[(INT) *s2++]–. […]

Copy code Algorithm Input inputs polynomial expression in terms of coefficient and power Output Sum of two polynomial expressions Complexity O(n). create()// inputs polynomial expression in terms of coefficient and power 1. Repeat while(1) a. [Input the coff and pow]. b. if (node→pow==0) then: i. Set ptr=node, node=NULL, ptr→link:=node and break. c. [whether to input […]

Copy code Algorithm Input Number of rows and columns Output Sparse matrix Complexity O(n). create(h)//Creates sparse matrix using linked list 1. [Input number of rows(r) and columns(c)] 2. [ create the head node]. 3. [initialize row & col no and rw & col ptrs] h→r=r, h→c=c, h→rptr=h, h→cptr=h; 4. Set h→data=0; 5. [ create column […]

Copy code Algorithm odd_num(n)//creates magic square for odd number n 1. [initialize segment variables] num=1 and nn=n*3/2; 2. Repeat for i=0 to n a. Repeat for j=0 to n i. Set m[(j-i+nn)%n][(i*2-j+n)%n]=num++; 3. [End] even_num( n)//creates magic square for even number n 1. [initialize segment variables] num:=1, nminus:=n-1,nmiddle:=n/2,nn=n*n+1 and osl:=0. 2. Set first_block:=(n-2)/4, second_block=nminus-first_block. 3. […]

Copy code Algorithm Input An integer Output Sum of digits. complexity O(d).[no. of digit in the number] Sod(a) 1. [Initialize sum] sum := 0. 2. Repeat while(n>0) Set d=n%10 ; sum=sum+n; Set n=n/10 ; 3. return sum. Algorithm Description Copy code C Code #include<stdio.h> #include<conio.h> int main() { int n,i,d,sum=0; printf(“\n enter any integer number […]

Copy code Algorithm Input An integer Output Palindrome or not complexity O(d).(number of digit) Palindrome(n) 1. [initialize segment variables]m := n, i:=n. 2. Repeat while(m>0) Set i:=i%10; rev:=i+rev*10; m:=m/10 ; i:=m; 3. if(rev==n)then print : “Number is palindrome”. 4. Else print: “Number is not a palindrome”. 5. Exit Algorithm Description Palindrome(n) checks whether given number […]

Copy code Algorithm Input Coefficient of quadratic equation Output Roots complexity O(n). Roots (a,b,c) 1. Initialize root1:=root2:=0. 2. Set cal := (sqrt((b*b)-(4*a*c)))/(2*a). 3. Set root1 : = -b + cal. 4. Set root2 : = -b – cal. 5. If(root1<0 or root2<0) then print : “Imaginary roots” 6. Else return 7. end Algorithm Description Roots() […]

Copy code Algorithm Input A string; Output Reverse of string complexity O(n). Reverse(s1)//reverses string s1 1. Initialize ctr := 0. 2. while(s1!=’\0’) 3. [increment ctr] ctr++, 4. Repeat for i=ctr to 0 print : *(s1+i) 5. [end] Algorithm Description Ctr :counter; Ctr count the number of elements in the string. For loop for print the […]

Copy code C++ Code /* program to heap sort array elements */ #include<iostream> #include<math.h> using namespace std; int b[100],ptr=0,tn; //function to form heap of a given tree void heapify(int n,int a[]) { //if no node left if(n==0) { return; } int l,r,tmp,curr; //decrease current node number curr=n-1; l=(curr+1)*2-1; r=l+1; //if parent if less then left […]

Copy code JAVA Code import java.io.*; class multiply { int a[][]=new int[16][16]; int b[][]=new int[16][16]; int c[][]=new int[16][16]; void input(int a[][],int n)throws IOException { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { System.out.println(“Input the element”+i+”,”+j); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); a[i][j]=Integer.parseInt(br.readLine()); } } void display(int a[][],int n) { int i,j; for(i=0;i<n;i++) { System.out.println(“”); for(j=0;j<n;j++) System.out.print(“\t”+a[i][j]); } System.out.println(“\n”); […]

Copy code C++ Code /* Program for integer multiplication */ #include<iostream> #include<cstring> #include<cmath> using namespace std; //function to calculate size of a given number in form of array int size(char a[]) { int length=0; //loop till end of the array while(a[length]!=’\0′) { length++; } return length; } //funtion to add bits of number void add(char […]

Copy code C++ Code /* program to implement fractional knapsack problem using greedy programming */ #include<iostream> using namespace std; int main() { int array[2][100],n,w,i,curw,used[100],maxi=-1,totalprofit=0; //input number of objects cout<<“Enter number of objects: “; cin>>n; //input max weight of knapsack cout<<“Enter the weight of the knapsack: “; cin>>w; /* Array’s first row is to store weights […]

Copy code JAVA Code

Copy code JAVA Code import java.io.*; class hash { public static void main(String args[]) throws Exception { int n=11,l,i,k,flag; int a[]=new int[11]; int hash[]=new int[11]; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); System.out.println(“Enter the elements “); for(i=0;i<n;i++) { a[i]= Integer.parseInt(cin.readLine()); hash[i]=0; } for(i=0;i<n;i++) { k=(2*a[i]+5)%11; flag=0; while(flag!=1){ if(hash[k]==0){ hash[k]=a[i]; flag=1; } else k=(k+1)%11;//linear probing } } […]

Copy code JAVA Code import java.io.*; class hash_quadratic{ public static void main(String args[]) throws Exception{ int n=11,i,k,j,flag; int a[]=new int[11]; int hash[]=new int[11]; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); System.out.println(“enter the elements to be sorted”); for(i=0;i<n;i++){ a[i]= Integer.parseInt(cin.readLine()); hash[i]=0; } for(i=0;i<n;i++){ flag=0; j=0; while(flag!=1){ k=((2*a[i]+5)%11+j*j)%11; if(hash[k]==0){ hash[k]=a[i]; flag=1;} else{ j++; } } } System.out.println(“hash table […]

Copy code JAVA Code

Copy code JAVA Code import java.io.*; class merge_sort { public static void main(String args[]) throws Exception { merge_sort m=new merge_sort(); int n,end,beg,i; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); int arr[]=new int[10]; System.out.println(“enter 10 elements to be sorted”); for(i=0;i<10;i++) { arr[i]= Integer.parseInt(cin.readLine()); } beg=0; end=9; m.mergesort(arr,beg,end); System.out.println(“THE ELEMENTS AFTER SORTING ARE:”); for(i=0;i<10;i++) System.out.println(arr[i]); } }

Copy code JAVA Code

Copy code JAVA Code import java.io.*; class queens{ int count=0; int x[]=new int[10]; boolean place(int k,int i) { int j; for(j=1;j<=k-1;j++) if((x[j]==i) || (Math.abs(x[j]-i)==Math.abs(j-k))) return false; return true; } void nqueens(int k,int n) { int r,i; for(i=1;i<=n;i++) { if(place(k,i)) { x[k]=i; if(k==n) { for(i=1;i<=n;i++) { for(r=1;r<x[i];r++) { System.out.print(” – “); } System.out.print(” * “); for(r=x[i]+1;r<=n;r++) […]

Copy code JAVA Code import java.io.*; class knapsack10 { public static void main(String args[]) throws IOException { int capacity,n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println (“\n Enter the number of items u want to enter:”); n= Integer.parseInt(br.readLine()); float p[]=new float[n+1]; float x[]=new float[n+1]; int i,j,k,w; int WEIGHT[]=new int[n+1],PROFIT[]=new int[n+1]; WEIGHT[0]=0; PROFIT[0]=0; for(i=1;i<=n;i++) { System.out.println (“\n Enter […]

Copy code JAVA Code /*To implement graph colouring*/ import java.io.*; class graph_colour { void colournext(int k,int colour[],int n,int m,int edge[][]) { int flag=0,j; do { flag=0; colour[k]=(colour[k]+1)%(m+1); if(colour[k]==0) return; for(j=0;j<n;j++) { if((edge[k][j]==1) && (colour[k]==colour[j])) flag=1; } }while(flag==1); } public static void main(String args[]) throws IOException { int i,t,j,h,n,m,k,flag=0,maxclique=0; System.out.println(“Enter the no. of vertices in the […]

Copy code JAVA Code

Copy code JAVA Code import java.io.*; class bishop { static int a[][]= new int[8][8]; static int pl[][]= new int[8][8]; static int row; static int placerook(int i,int j) { int i1,j1,flag=0; i1=i; j1=j; while(i1>=0) { if(a[i1][j1]==0) flag=1; i1–; } return(flag); } static int placebishop(int i,int j) { int i1,j1,flag=0; i1=i; j1=j; while((i1>=0)&&(j1>=0)) {if(a[i1][j1]==1) flag=1; i1–; j1–;} […]

A draft report has five chapters. The table shows the lengths of the chapters & their importance where the scale is from 1(low) to 10(high). The report must be at most 600 pages long. The problem is to edit the report so that the overall importance is maximized. Implement the fractional knapsack algorithm using Greedy […]