2016

Gate Video Lectures for CSe

Theory of computation

Hacker Rank Solutions for Gem-Stones

Hacker Rank Solutions for Gem-Stones

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.

Input Format

The first line consists of N, the number of rocks.

Each of the next N lines contain rocks' composition. Each composition consists of lowercase letters of English alphabet.

Output Format

Print the number of gem-elements that are common in these rocks.

Constraints

1 ≤ N ≤ 100

Each composition consists of only small latin letters ('a'-'z').

1 ≤ Length of each composition ≤ 100

Sample Input

3
abcdde
baccd
eeabg

Sample Output

2

Explanation

Only "a", "b" are the two kind of gem-elements, since these are the only characters that occur in each of the rocks' composition.

Solutions

#include<stdio.h>

#include<string.h>

main(){

int n,i,j, ans=0;

int count[26]={0};

char s[100][100];

char *p;

scanf("%d",&n);

for(i=0;i<n;i++){

scanf("%s",s[i]);

}

j=1;

int t, index;

int l = strlen(s[0]);

for(i=0;i<l;i++){

t=0;

for(j=1;j<n;j++){

if(strchr(s[j],s[0][i])!='\0'){

t++;

}

if(t==n-1){

index= s[0][i] - 'a';

count[index]=1;

}

for(i=0;i<26;i++){

if (count[i]==1)

ans++;

}

printf("%d",ans);

}

HACKER RANK SOLUTON FOR GAME OF ROTATION

HACKER RANK SOLUTON FOR GAME OF ROTATION

Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.

There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.

PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.

Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.

PMEAN=∑i=1ni×a[i]

where a represents the configuration of conveyor belt when it is stopped. Indexing starts from 1.

Input Format

First line contains N denoting the number of elements on the belt.

Second line contains N space separated integers.

Output Format

Output the required PMEAN

Constraints

1 ≤ N ≤ 106

-109 ≤ each number ≤ 109

For any rotation, PMEAN will always lie within the range of 64-bit signed integer.

Sample Input

3

20 30 10

Sample Output

140

Explanation

Number on top can be written in these manners.

Initial numbers on belt, 20 30 10 PMEAN = 1x20 + 2x30 + 3x10 = 110

After first rotation, 30 10 20 PMEAN = 1x30 + 2x10 + 3x20 = 110

After second rotation, 10 20 30 PMEAN = 1x10 + 2x20 + 3x30 = 140

So maximum possible value will be 140.

Solution

#include <stdio.h>

int main() {

int n,i,k;
scanf("%d",&n);
long long int a[n],sum[n], ans, s=0,temp;
sum[0] =0;
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[0]+=(i+1)*a[i];
s+= a[i];
}
ans = sum[0];
for(k=1;k<n;k++){
temp = n*a[k-1];
sum[k]= sum[k-1] - s + temp;
if(ans<sum[k])
ans = sum[k];
}

printf("%lld",ans);
return 0;
}

HACKER RANK SOLUTION FOR Counting-Sort-2

HACKER RANK SOLUTION FOR COUNTNG SORT-2

Often, when a list is sorted, the elements being sorted are just keys to other values. For example, if you are sorting files by their size, the sizes need to stay connected to their respective files. You cannot just take the size numbers and output them in order, you need to output all the required file information.

However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don't need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.

Challenge

Given an unsorted list of integers, output the integers in order.

Hint: You can use your previous code that counted the items to print out the actual values in-order.

Input Format

There will be two lines of input:

n - the size of the list

ar - n space separated numbers that belong to the list

Output Format

Output all the numbers of the list in-order.

Constraints

1 <= n <= 1000000

0 <= x < 100 , x ∈ ar

Sample Input

100

63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

Sample Output

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

Explanation

In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.

Solution

#include<stdio.h>

main()

{

int n,i,j;

scanf("%d",&n);

int ar[n];

int count[100] = {0}; //for 0 to 100

for(i=0;i<n;i++)

{

scanf("%d",&ar[i]);

count[ar[i]]++;

}

for(i=0;i<100;i++)

{

if(count[i]>0)

{

for(j=0;j<count[i];j++)

{

printf("%d ",i);

}

Hacker Rank Solution for Counting-Sort1

Hacker Rank Solution for Counting-Sort1

Comparison Sorting

Quicksort usually has a running time of n*log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e., they sort a list just by comparing the elements with one another. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since n log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

Alternative Sorting

However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.

Challenge

Given a list of integers, can you count and output the number of times each value appears?

Hint: There is no need to sort the data, you just need to count it.

Input Format

There will be two lines of input:

n - the size of the list

ar - n space separated numbers that makes up the list

Output Format

Output the number of times every number from 0 to 99 (inclusive) appears in the list.

Constraints

100 <= n <= 106

0 <= x < 100 , x ∈ ar

Sample Input

100

63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

Sample Output

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

Explanation

the output states that 0 appears 0 times.

1 appears 2 times.

2 appears 0 times.

and so on in the given input array.

Solution

#include<stdio.h>

main()
{
int n,i;
scanf("%d",&n);
int ar[n];
int count[100] = {0}; //for 0 to 100
for(i=0;i<n;i++)
{
scanf("%d",&ar[i]);
count[ar[i]]++;
}
for(i=0;i<100;i++)
{
printf("%d ",count[i]);
}

}

Hacker Rank soluton for Correctness-and-the-Loop-Invariant

Hacker Rank soluton for Correctness-and-the-Loop-Invariant

In the previous challenge, you wrote code to perform an Insertion Sort on an unsorted array. But how would you prove that the code is correct? I.e. how do you show that for any input, your code will provide the right output?

Loop Invariant

In computer science, you could prove it formally with a loop invariant, where you state that a desired property is maintained in your loop. Such a proof is broken down into 3 parts:

Initialization - It is true (in a limited sense) before the loop runs.

Maintenance - If it's true before an iteration of a loop, it remains true before the next iteration.

Termination. It will terminate in a useful way, once it is finished.

Insertion Sort's Invariant

Say you have some InsertionSort code, where the outer loop goes through the whole array A:

for(int i = 1; i < A.length; i++){

//insertion sort code

You could then state the following loop invariant:

At the start of every iteration of the outer loop (indexed with i), the subarray until ar[i] consists of the original elements that were there, but in sorted order.

To prove Insertion Sort is correct, you will then demonstrate it for the three stages:

Initialization - The subarray starts with the first element of the array, and it is (obviously) sorted to begin with.

Maintenance - Each iteration of the loop expands the subarray, but keeps the sorted property. An element V gets inserted into the array, only when it is >= to the element to the left of it. Since the elements to the left have already been sorted, it means V >= all the elements to the left, so the array remains sorted. (In InsertionSort2, we saw this by printing array each time an element was 'inserted' into it.)

Termination - The code will terminate after i has reached the last element in the array, which means the sorted subarray has expanded to encompass the entire array. So the array is now fully sorted.

Loop Invariant Chart

You can often use a similar process to demonstrate the correctness of many algorithms. You can see these notes for more information.

Challenge

In the InsertionSort code below, there is an error. Can you fix it? Print the array only once, when it is fully sorted.

Details

The Input format and the constraints are the same as the previous challenges and are presented below.

Input Format

There will be two lines of input:

s - the size of the array

ar - the list of numbers that makes up the array

Output Format

Output the numbers in order, space-separated.

Constraints

1<=s<=1000

-1500<=x<= 1500 , x ∈ ar

Sample Input

6

1 4 3 5 6 2

Sample Output

1 2 3 4 5 6

Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <stddef.h>
void insertionSort(int ar_size, int * ar) {
int i,j;
int value;
for(i=1;i<ar_size;i++)
{
value=ar[i];
j=i-1;
while(j>=0 && value<ar[j])
{
ar[j+1]=ar[j];
j=j-1;
}
ar[j+1]=value;
}

for(j=0;j<ar_size;j++)
{
printf("%d",ar[j]);
printf(" ");
}
}

int main(void) {
int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
scanf("%d", &_ar[_ar_i]);
}

insertionSort(_ar_size, _ar);

return 0;
}

HAcker Rank Solutiom for Closest-Numbers

HAcker Rank Solutiom for Closest-Numbers
Problem Statement

Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.

Challenge

Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.

Input Format

There will be two lines of input:

n - the size of the list

array - the n numbers of the list

Output Format

Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times (see sample case #3 for explanation).

Constraints

2 <= n <= 200000

-(107) <= x <= (107), where x ∈ array

array[i] != array[j], 0 <= i, j < N, and i != j

Sample Input
#1

10

-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854

Sample Output
#1

-20 30

Explanation

(30) - (-20) = 50, which is the smallest difference.

Sample Input #2

12

-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470

Sample Output #2

-520 -470 -20 30

Explanation

(-470) - (-520) = 30 - (-20) = 50, which is the smallest difference.

Sample Input #3

4

5 4 3 2

Sample Output #3

2 3 3 4 4 5

Explanation

Here, the minimum difference will be 1. So valid pairs are (2, 3), (3, 4), (4, 5). So we have to print 2 one time, 3 and 4 two times, and 5 one time.

Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++){
a[i] = in.nextInt();
}
int min=0, temp=0;
HashMap<Integer, ArrayList<Integer>> minMap = new HashMap<Integer,ArrayList<Integer>>();
Arrays.sort(a);
for(int i=0; i<n-1; i++){
temp = a[i+1] - a[i];
if(!minMap.containsKey(temp))
minMap.put(temp, new ArrayList<Integer>());
minMap.get(temp).add(a[i]);
minMap.get(temp).add(a[i+1]);
if(min>temp || i==0)
min = temp;
}

for(int i=0; i<minMap.get(min).size();i++)
System.out.print(minMap.get(min).get(i)+" ");
}
}

Hacker rank solution for Bus-Station

Hacker rank solution for Bus-Station
There are n groups of friends, and each group is numbered from 1 to n. The ith group contains ai people.

They live near a bus stop, and only a single bus operates on this route. An empty bus arrives at the bus stop and all the groups want to travel by the bus.

However, group of friends do not want to get separated. So they enter the bus only if the bus can carry the entire group.

Moreover, the groups do not want to change their relative positioning while travelling. In other words, group 3 cannot travel by bus, unless group 1 and group 2 have either (a) already traveled by the bus in the previous trip or (b) they are also sitting inside the bus at present.

You are given that a bus of size x can carry x people simultaneously.

Find the size x of the bus so that (1) the bus can transport all the groups and (2) every time when the bus starts from the bus station, there is no empty space in the bus (i.e. the total number of people present inside the bus is equal to x)?

Input Format

The first line contains an integer n (1≤n≤105). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤104).

Output Format

Print all possible sizes of the bus in an increasing order.

Sample Input

8

1 2 1 1 1 2 1 3

Sample Output

3 4 6 12

Sample Explanation

In the above example, a1 = 1, a2 = 2, a3 = 1, a4 = 1, a5 = 1, a6 = 2, a7 = 1, a8 = 3.

If x = 1 : In the first trip, a1 go by the bus. There will be no second trip because the bus cannot accommodate group 2. Hence "x = 1" is not the required answer.

If x = 2 : No bus trip is possible. That's because a1 cannot go alone, as one seat will be left vacant in the bus. And, a1 & a2 cannot go together, because the bus is cannot accommodate both the groups simultaneously.

If x = 3 : In the first trip, a1 & a2 go by the bus. In the second trip, a3, a4 & a5 go by the bus. In the third trip, a6 & a7 go by the bus. In the fourth trip, a8 go by the bus.

If x = 4 : In the first trip, a1, a2 & a3 go by the bus. In the second trip, a4, a5 & a6go by the bus. In the third trip, a7 & a8 go by the bus.

Similarly you can figure out the output for x= 5, 6 & 7.

SOLUTION

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void quicksort(int * A, int p, int r){
if(p<r){
int q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}

int partition(int *A, int p, int r){
int x,i,j,temp;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
if(A[j]<=x){
i++;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i+1;
}

int main() {

int n,i,g, l=1,sum = 0;
scanf("%d",&n);

int a[n];

for(i=0;i<n;i++){
scanf("%d",&a[i]);
sum+= a[i];
if(g>a[i] || i==0)
g = a[i];
}

int k=0,m,d[n];

m = sqrt(sum);

while(l<= m){
if(sum % l == 0){
if(l>=g){
d[k] = l;
k++;
}

if(l != sum/l && (sum/l)>=g){
d[k] = sum/l;
k++;
}
}
l++;
}

int e[k];

l = 0;
int t = 0;
while(l<k){
m = d[l];
i = 0;
while(m>0){
m-= a[i];
i++;
if(m==0 && i<n)
m = d[l];
}
if(m==0 && i==n){
e[t] = d[l];
t++;
}
l++;

}
quicksort(e,0,t-1);
for(i=0;i<t;i++)
printf("%d ",e[i]);
return 0;
}

Hacker rank solution for Bigger-is-Greater

Hacker rank solution for Bigger-is-Greater
Please note that this is a team event, and your submission will be accepted only as a part of a team, even single member teams are allowed. Please click here to register as a team, if you have NOT already registered.

Given a word w, rearrange the letters of w to construct another word s in such a way that, s is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one.

Input Format

The first line of input contains t, number of test cases. Each of the next t lines contains w.

Constraints

1≤t≤105

1≤|w|≤100

w will contain only lower case english letters and its' length will not exceed 100.

Output Format

For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one and if no answer exists, print no answer.

Sample Input

3

ab

bb

hefg

Sample Output

ba

no answer

hegf

Explanation

Testcase 1 : There exists only one string greater than ab which can be built by rearranging ab. That is ba.

Testcase 2 : Not possible to re arrange bb and get a lexicographically greater string.

Testcase 3 : hegf is the next string ( lexicographically greater ) to hefg.

SOLUTION

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void solve (char str[])
{
int i, flag=0;
loop:
for(i=str.length-1; i>0; i--)
{

if(str[i]>str[i-1])
{
int j = str.length-1;
while(flag==0 && j!=i-1){
if(str[i-1]<str[j])
{
char t = str[j];
str[j] = str[i-1];
str[i-1] = t;
flag = 1;
break loop;
}
j--;
}
}

}

Arrays.sort(str,i,str.length);

if(flag==0)
System.out.println("no answer");
else
System.out.println(str);

}

public static void main(String[] args) {
char name[];
int t;
Scanner in = new Scanner(System.in);
t = in.nextInt();
for(int i=0; i<t; i++)
{
name = in.next().toCharArray();
solve(name);
}
}

}

C program for Merge Sort

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;

// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

Output:
Given array is
12 11 13 5 6 7

Sorted array is
5 6 7 11 12 13

Dynamic Programming 0/1 Knapsack Using C/C++

Dynamic Programming 0/1 Knapsack Using C/C++

/* A Naive recursive implementation of 0-1 Knapsack problem using c*/
#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;

// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);

// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}

// Driver program to test above function
int main()
{
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

OUTPUT:
220

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()

{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
//clrscr();
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
//f1 = fopen("Input","r");
if(f1==NULL)

{
printf("file not found");
exit(0);
}
while((ch=fgetc(f1))!=EOF)

{
for(j=0;j<=14;j++)

{
if(ch==oper[j])

{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)

{
if(i==-1)
break;
if(ch==seps[j])

{
if(ch=='#')

{
while(ch!='>')

{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')

{
do

{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)

{
str[i]=ch;
i++;
}
else
i=0;
}
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
//getch();
}
void keyw(char *p)

{
int k,flag=0;
for(k=0;k<=31;k++)

{
if(strcmp(keys[k],p)==0)

{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)

{
if(isdigit(p[0]))

{
printf("%s is a number\n",p);
num++;
}
else

{
//if(p[0]!=13&&p[0]!=10)
if(p[0]!='\0')

{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}
output

LEXICAL ANALYZER USING C
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()

{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
//clrscr();
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
//f1 = fopen("Input","r");
if(f1==NULL)

{
printf("file not found");
exit(0);
}
while((ch=fgetc(f1))!=EOF)

{
for(j=0;j<=14;j++)

{
if(ch==oper[j])

{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)

{
if(i==-1)
break;
if(ch==seps[j])

{
if(ch=='#')

{
while(ch!='>')

{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')

{
do

{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)

{
str[i]=ch;
i++;
}
else
i=0;
}
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
//getch();
}
void keyw(char *p)

{
int k,flag=0;
for(k=0;k<=31;k++)

{
if(strcmp(keys[k],p)==0)

{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)

{
if(isdigit(p[0]))

{
printf("%s is a number\n",p);
num++;
}
else

{
//if(p[0]!=13&&p[0]!=10)
if(p[0]!='\0')

{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}
output

LEXICAL ANALYZER USING C

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

C PROGRAM TO CALCULATE LEXICAL ANALYZER

C PROGRAM TO CALCULATE LEXICAL ANALYZER
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void keyw(char *p);
int i=0,id=0,kw=0,num=0,op=0;
char keys[32][10]={"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
main()

{
char ch,str[25],seps[15]=" \t\n,;(){}[]#\"<>",oper[]="!%^&*-+=~|.<>/?";
int j;
char fname[50];
FILE *f1;
//clrscr();
printf("enter file path (drive:\\fold\\filename)\n");
scanf("%s",fname);
f1 = fopen(fname,"r");
//f1 = fopen("Input","r");
if(f1==NULL)

{
printf("file not found");
exit(0);
}
while((ch=fgetc(f1))!=EOF)

{
for(j=0;j<=14;j++)

{
if(ch==oper[j])

{
printf("%c is an operator\n",ch);
op++;
str[i]='\0';
keyw(str);
}
}
for(j=0;j<=14;j++)

{
if(i==-1)
break;
if(ch==seps[j])

{
if(ch=='#')

{
while(ch!='>')

{
printf("%c",ch);
ch=fgetc(f1);
}
printf("%c is a header file\n",ch);
i=-1;
break;
}
if(ch=='"')

{
do

{
ch=fgetc(f1);
printf("%c",ch);
}while(ch!='"');
printf("\b is an argument\n");
i=-1;
break;
}
str[i]='\0';
keyw(str);
}
}
if(i!=-1)

{
str[i]=ch;
i++;
}
else
i=0;
}
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n",kw,id,op,num);
//getch();
}
void keyw(char *p)

{
int k,flag=0;
for(k=0;k<=31;k++)

{
if(strcmp(keys[k],p)==0)

{
printf("%s is a keyword\n",p);
kw++;
flag=1;
break;
}
}
if(flag==0)

{
if(isdigit(p[0]))

{
printf("%s is a number\n",p);
num++;
}
else

{
//if(p[0]!=13&&p[0]!=10)
if(p[0]!='\0')

{
printf("%s is an identifier\n",p);
id++;
}
}
}
i=-1;
}
output

implementing first of a given grammar using c

implementing first of a given grammar using c

#include<stdio.h>
#include<ctype.h>
void FIRST(char[],char );
void addToResultSet(char[],char);
int numOfProductions;
char productionSet[10][10];
main()
{
int i;
char choice;
char c;
char result[20];
printf("How many number of productions ? :");
scanf(" %d",&numOfProductions);
for(i=0;i<numOfProductions;i++)//read production string eg: E=E+T
{
printf("Enter productions Number %d : ",i+1);
scanf(" %s",productionSet[i]);
}
do
{
printf("\n Find the FIRST of :");
scanf(" %c",&c);
FIRST(result,c); //Compute FIRST; Get Answer in 'result' array
printf("\n FIRST(%c)= { ",c);
for(i=0;result[i]!='\0';i++)
printf(" %c ",result[i]); //Display result
printf("}\n");
printf("press 'y' to continue : ");
scanf(" %c",&choice);
}
while(choice=='y'||choice =='Y');
}
/*
*Function FIRST:
*Compute the elements in FIRST(c) and write them
*in Result Array.
*/
void FIRST(char* Result,char c)
{
int i,j,k;
char subResult[20];
int foundEpsilon;
subResult[0]='\0';
Result[0]='\0';
//If X is terminal, FIRST(X) = {X}.
if(!(isupper(c)))
{
addToResultSet(Result,c);
return ;
}
//If X is non terminal
//Read each production
for(i=0;i<numOfProductions;i++)
{
//Find production with X as LHS
if(productionSet[i][0]==c)
{
//If X → ε is a production, then add ε to FIRST(X).
if(productionSet[i][2]=='$') addToResultSet(Result,'$');
//If X is a non-terminal, and X → Y1 Y2 … Yk
//is a production, then add a to FIRST(X)
//if for some i, a is in FIRST(Yi),
//and ε is in all of FIRST(Y1), …, FIRST(Yi-1).
else
{
j=2;
while(productionSet[i][j]!='\0')
{
foundEpsilon=0;
FIRST(subResult,productionSet[i][j]);
for(k=0;subResult[k]!='\0';k++)
addToResultSet(Result,subResult[k]);
for(k=0;subResult[k]!='\0';k++)
if(subResult[k]=='$')
{
foundEpsilon=1;
break;
}
//No ε found, no need to check next element
if(!foundEpsilon)
break;
j++;
}
}
}
}
return ;
}
/* addToResultSet adds the computed
*element to result set.
*This code avoids multiple inclusion of elements
*/
void addToResultSet(char Result[],char val)
{
int k;
for(k=0 ;Result[k]!='\0';k++)
if(Result[k]==val)
return;
Result[k]=val;
Result[k+1]='\0';
}

Output

SOM code in MATLAB

SOM code in Matlab

Below is the code of applying SOM on handwritten digits recongnition. It was implemented for a homework assignment in a course offered by professor Paul Gader. I used only ten handwritten digits images provided by Dr. Gader. Each image is resized to 30×30 and reshape to a 900×1 column vector. data in the code below is the training set. It’s a coolection of 900-dimensional column vectors.
%//Matlab script
%//-- 10 x 10 map

data = double(data);
%// toal number of nodes
totalW = 100;
%//initialization of weights
w = rand(900, totalW);
%// the initial learning rate
eta0 = 0.1;
%// the current learning rate (updated every epoch)
etaN = eta0;
%// the constant for calculating learning rate
tau2 = 1000;

%//map index
[I,J] = ind2sub([10, 10], 1:100);

N = size(data,2);

alpha = 0.5;
%// the size of neighbor
sig0 = 200;

sigN = sig0;
%// tau 1 for updateing sigma
tau1 = 1000/log(sigN);

%i is number of epoch
for i=1:2000
%// j is index of each image.
%// it should iterate through data in a random order rewrite!!
for j=1:N
x = data(:,j);
dist = sum( sqrt((w - repmat(x,1,totalW)).^2),1);

%// find the winner
[v ind] = min(dist);
%// the 2-D index
ri = [I(ind), J(ind)];

%// distance between this node and the winner node.
dist = 1/(sqrt(2*pi)*sigN).*exp( sum(( ([I( : ), J( : )] - repmat(ri, totalW,1)) .^2) ,2)/(-2*sigN)) * etaN;

%// updating weights
for rr = 1:100
w(:,rr) = w(:,rr) + dist(rr).*( x - w(:,rr));
end
end

%// update learning rate
etaN = eta0 * exp(-i/tau2);
%// update sigma
%sigN = sigN/2;
sigN = sig0*exp(-i/tau1);

%//show the weights every 100 epoch
if mod(i,200) == 1
figure;
axis off;
hold on;
for l = 1:100
[lr lc] = ind2sub([10, 10], l);
subplot(10,10,l);
axis off;
imagesc(reshape(w(:,l),30,30));
axis off;
end
hold off;
end
end
Result:
See the transition between different numbers

FIRST AND FOLLOW OF A GIVEN GRAMMAR USING C

c program to implement first of a given grammar

/* Author : karthik Alapati
* mail: saikarthik002@gmail.com
*Modified on : 14/03/2016
*/
#include<stdio.h>
#include<ctype.h>
void FIRST(char[],char );
void addToResultSet(char[],char);
int numOfProductions;
char productionSet[10][10];
main()
{
int i;
char choice;
char c;
char result[20];
printf("How many number of productions ? :");
scanf(" %d",&numOfProductions);
for(i=0;i<numOfProductions;i++)//read production string eg: E=E+T
{
printf("Enter productions Number %d : ",i+1);
scanf(" %s",productionSet[i]);
}
do
{
printf("\n Find the FIRST of :");
scanf(" %c",&c);
FIRST(result,c); //Compute FIRST; Get Answer in 'result' array
printf("\n FIRST(%c)= { ",c);
for(i=0;result[i]!='\0';i++)
printf(" %c ",result[i]); //Display result
printf("}\n");
printf("press 'y' to continue : ");
scanf(" %c",&choice);
}
while(choice=='y'||choice =='Y');
}
/*
*Function FIRST:
*Compute the elements in FIRST(c) and write them
*in Result Array.
*/
void FIRST(char* Result,char c)
{
int i,j,k;
char subResult[20];
int foundEpsilon;
subResult[0]='\0';
Result[0]='\0';
//If X is terminal, FIRST(X) = {X}.
if(!(isupper(c)))
{
addToResultSet(Result,c);
return ;
}
//If X is non terminal
//Read each production
for(i=0;i<numOfProductions;i++)
{
//Find production with X as LHS
if(productionSet[i][0]==c)
{
//If X → ε is a production, then add ε to FIRST(X).
if(productionSet[i][2]=='$') addToResultSet(Result,'$');
//If X is a non-terminal, and X → Y1 Y2 … Yk
//is a production, then add a to FIRST(X)
//if for some i, a is in FIRST(Yi),
//and ε is in all of FIRST(Y1), …, FIRST(Yi-1).
else
{
j=2;
while(productionSet[i][j]!='\0')
{
foundEpsilon=0;
FIRST(subResult,productionSet[i][j]);
for(k=0;subResult[k]!='\0';k++)
addToResultSet(Result,subResult[k]);
for(k=0;subResult[k]!='\0';k++)
if(subResult[k]=='$')
{
foundEpsilon=1;
break;
}
//No ε found, no need to check next element
if(!foundEpsilon)
break;
j++;
}
}
}
}
return ;
}
/* addToResultSet adds the computed
*element to result set.
*This code avoids multiple inclusion of elements
*/
void addToResultSet(char Result[],char val)
{
int k;
for(k=0 ;Result[k]!='\0';k++)
if(Result[k]==val)
return;
Result[k]=val;
Result[k+1]='\0';
}

Output

FOLLOW OF A GIVEN GRAMMER USING C

#include<stdio.h>
#include<string.h>
int n,m=0,p,i=0,j=0;
char a[10][10],followResult[10];
void follow(char c);
void first(char c);
void addToResult(char);
int main()
{
int i;
int choice;
char c,ch;
printf("Enter the no.of productions: ");
scanf("%d", &n);
printf(" Enter %d productions\nProduction with multiple terms should be give as separate productions \n", n);
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
// gets(a[i]);
do
{
m=0;
printf("Find FOLLOW of -->");
scanf(" %c",&c);
follow(c);
printf("FOLLOW(%c) = { ",c);
for(i=0;i<m;i++)
printf("%c ",followResult[i]);
printf(" }\n");
printf("Do you want to continue(Press 1 to continue....)?");
scanf("%d%c",&choice,&ch);
}
while(choice==1);
}
void follow(char c)
{
if(a[0][0]==c)addToResult('$');
for(i=0;i<n;i++)
{
for(j=2;j<strlen(a[i]);j++)
{
if(a[i][j]==c)
{
if(a[i][j+1]!='\0')first(a[i][j+1]);
if(a[i][j+1]=='\0'&&c!=a[i][0])
follow(a[i][0]);
}
}
}
}
void first(char c)
{
int k;
if(!(isupper(c)))
//f[m++]=c;
addToResult(c);
for(k=0;k<n;k++)
{
if(a[k][0]==c)
{
if(a[k][2]=='$') follow(a[i][0]);
else if(islower(a[k][2]))
//f[m++]=a[k][2];
addToResult(a[k][2]);
else first(a[k][2]);
}
}
}
void addToResult(char c)
{
int i;
for( i=0;i<=m;i++)
if(followResult[i]==c)
return;
followResult[m++]=c;
}
RESULT
:

Karthik Alapati's Blog

HOME

Gate Video Lectures for CSe

Theory of computation

Hacker Rank Solutions for Gem-Stones

HACKER RANK SOLUTON FOR GAME OF ROTATION

HACKER RANK SOLUTION FOR Counting-Sort-2

Hacker Rank Solution for Counting-Sort1

Hacker Rank soluton for Correctness-and-the-Loop-Invariant

HAcker Rank Solutiom for Closest-Numbers

Hacker rank solution for Bus-Station

Hacker rank solution for Bigger-is-Greater

C program for Merge Sort

Dynamic Programming 0/1 Knapsack Using C/C++

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

LEXICAL ANALYZER USING C

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

C PROGRAM TO CALCULATE LEXICAL ANALYZER

implementing first of a given grammar using c

SOM code in MATLAB

SOM code in Matlab

FIRST AND FOLLOW OF A GIVEN GRAMMAR USING C

FIRST AND FOLLOW OF A GIVEN GRAMMAR USING C

Featured post

C PROGRAM TO IMPLEMENT LEXICAL ANALYZER

Popular Posts