Amortized Analysis : Accounting Method

Amortized Analysis : Introduction and Aggregate analysis

Graph coloring using backtracking

 

C pointers

                                         C pointers

 C pointers are a powerful tool that gives strength to the C language more than others.

What is the output?

#include<stdio.h>

void crazy(int,int);

void crazy(int m, int n)

 {

int *ptr;

m=0;

ptr=&m;

n=*ptr;

*ptr=1;

printf("%d %d",m,n);

}

void main()

{

            crazy(2,2);

}

O/p:

C programming

                                                           Structure in C

struct add                                         //abstract data type

{

    int A,B;

 }x,sum;

int main()

{

   printf("Enter first no\n");

   scanf("%d", &x.A);

   printf("Enter second no \n");

   scanf("%d", &x.B);

                                                                                    // adding nos

   sum.A=x.A+x.B;

   printf("Sum is = %d", sum.A);

  return 0;

}

Webmining

Web scraping in python

1. Write a program (using nltk toolkit in python environment) to tokenize

a) Sentence

b) Multiple sentences

c) A paragraph

d) Information of a complete web page

Python code

import nltk 

from nltk.tokenize import word_tokenize

from nltk.text import Text

mystring = "I am currently studying in XYZ UNIVERSITY atDELHI. Cuurently in 4th year studying placements and tyring for the masters too as i was tooearly to start the programming. Currently tyring to ops as datascientist at any product based copany as a data scientist i need to learn all the python programmming at the professionally and we have to be good at statistics and the machine learnng models which model will suit for which problem"

tokens = word_tokenize(mystring)

tokens

O/p:

['I', 'am', 'currently', 'studying', 'in', 'XYZ', 'UNIVERSITY', 'at', 'DELHI', '.', 'Cuurently', 'in', '4th', 'year', 'studying', 'placements', 'and', 'tyring', 'for', 'the', 'masters', 'too', 'as', 'i', 'was', 'too', 'early', 'to', 'start', 'the', 'programming', '.', 'Currently', 'tyring', 'to', 'ops', 'as', 'datascientist', 'at', 'any', 'product', 'based', 'copany', 'as', 'a', 'data', 'scientist', 'i', 'need', 'to', 'learn', 'all', 'the', 'python', 'programmming', 'at', 'the', 'professionally', 'and', 'we', 'have', 'to', 'be', 'good', 'at', 'statistics', 'and', 'the', 'machine', 'learnng', 'models', 'which', 'model', 'will', 'suit', 'for', 'which', 'problem']

Python code

nltk.download('punkt')

O/p:

[nltk_data] Downloading package punkt to

[nltk_data]     C:\Users\Viru\AppData\AMK\nltk_data...

[nltk_data]   Package punkt is already up-to-date!

True

 

Tokenizing multiple sentences

Python code

print("Enter multiple sentences: ")

lines = []

tok = []

while True: 

    line = input() 

    if line: 

        lines.append(line) 

    else:

        break

        

    for t in lines:

        t = word_tokenize(t)

        tok.append(t)

print("Tokens for multiple sentences are as follows: ",tok)

 

O/p:

Enter multiple sentences:

Modern humans arrived on the Indian subcontinent from Africa no later than 55,000 years ago

Their long occupation, initially in varying forms of isolation as hunter-gatherers, has made the region highly diverse, second only to Africa in human genetic diversity.

In the early medieval era, Christianity, Islam, Judaism, and Zoroastrianism became established on India's southern and western coasts

 

Tokens for multiple sentences are as follows:  [['Modern', 'humans', 'arrived', 'on', 'the', 'Indian',…

 

Tokenizing the Paragraph

Python code

##Information of a complete web page

#bs4 module to crawl webpage

from bs4 import BeautifulSoup

import urllib.request

#requesting php.net for information

 

response = urllib.request.urlopen('https://en.wikipedia.org/wiki/India')

html = response.read()

#cleaning grabbed text

soup = BeautifulSoup(html,"html5lib")

text = soup.get_text(strip=True)

tokens_web = word_tokenize(text)

print("Tokens for this web page are: ",tokens_web[:])

#declare a dictionary

word_freq = {}

for tok in tokens_web:

    tok = tok.split()

    for t in tok:

        if t in word_freq:

            word_freq[t] += 1

        else:

            word_freq[t] = 1

 

 

O/p:

Tokens for this web page are:  ['India', '-', 'Wikipediadocument.documentElement.className=', "''", 'client-js', "''", ';', 'RLCONF=', '{', '``', 'wgBreakFrames', "''", ':', 'false', ',', "''", 'wgSeparatorTransformTable', "''", ':', '[', '``', "''", ',', "''", "''", ']', ',', "''", 'wgDigitTransformTable', "'

 

Numpy tutorial

 Numpy tutorial

NumPy is the fundamental package for scientific computing in Python. It is a Python library that provides a multidimensional array object, various derived objects (such as masked arrays and matrices), and an assortment of routines for fast operations on arrays, including mathematical, logical, shape manipulation, sorting, selecting, I/O, discrete Fourier transforms basic linear algebra, basic statistical operations, random simulation and much more.

The following tutorial will help you to learn Numpy.

1. Create an array of 6 zeros

import numpy as np np.zeros(6)

 O/p:

array([0., 0., 0., 0., 0., 0.])

Data Structures and Algorithms[CODES]

 

Stack using array in C

 #include<stdio.h>

#include<stdlib.h>

#define Size 4

int Top=-1, inp_array[Size];

void Push();

void Pop();

void show();

int main()

{

    int choice;

     while(1)   

    {

        printf("\nOperations performed by Stack");

        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");

        printf("\n\nEnter the choice:");

        scanf("%d",&choice);

        switch(choice)

        {

            case 1: Push();

                    break;

            case 2: Pop();

                    break;

            case 3: show();

                    break;

            case 4: exit(0);

            

            default: printf("\nInvalid choice!!");

        }

    }

}

 void Push()

{

    int x;

     if(Top==Size-1)

    {

        printf("\nOverflow!!");

    }

    else

    {

        printf("\nEnter element to be inserted to the stack:");

        scanf("%d",&x);

        Top=Top+1;

        inp_array[Top]=x;

    }

}

  void Pop()

{

    if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nPopped element:  %d",inp_array[Top]);

        Top=Top-1;

    }

}

 void show()

{

     if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nElements present in the stack: \n");

        for(int i=Top;i>=0;--i)

            printf("%d\n",inp_array[i]);

    }

}

Dynamic programming

Greedy algorithm

Dynamic Programming in C

 

Longest Common Subsequence in C

 #include<stdio.h>

#include<string.h>

 int i,j,m,n,c[20][20];

char x[20],y[20],b[20][20];

 void printFunction(int i,int j)

{

                if(i==0 || j==0)

                                return;

                if(b[i][j]=='c')

                {

                                printFunction(i-1,j-1);

                                printFunctionf("%c",x[i-1]);

                }

                else if(b[i][j]=='u')

                                printFunction(i-1,j);

                else

                                printFunction(i,j-1);

}

 

void LongComSub()

{

                m=strlen(x);

                n=strlen(y);

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

                                c[i][0]=0;

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

                                c[0][i]=0;

                                

 //c, u and l denotes cross, upward and downward directions respectively

                for(i=1;i<=m;i++)

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

                                {

                                                if(x[i-1]==y[j-1])

                                                {

c[i][j]=c[i-1][j-1]+1;

                                                                b[i][j]='c';

                                                }

                                                else if(c[i-1][j]>=c[i][j-1])

                                                {

                                                                c[i][j]=c[i-1][j];

                                                                b[i][j]='u';

                                                }

                                                else

                                                {

                                                                c[i][j]=c[i][j-1];

                                                                b[i][j]='l';

                                                }

                                }

}

int main()

{

                printf("Provide first sequence:");

                scanf("%s",x);

                printf("Provide second sequence:");

                scanf("%s",y);

                printf("\nThe LongComSub is ");

                LongComSub();

                printFunction(m,n);

return 0;

}

Recursion in C

Find the output of the following recursive algorithm.

 #include<stdio.h>

  int counter = 0;

  int calc(int a, int b) {

  int c;

  counter++;

  if (b==3) {

  return (a*a*a);

          }

  else {

    c = calc(a, b/3);

    return (c*c*c);

 }

}

int main (){

  calc(4, 81);

  printf ("%d", counter);

  }

Output: 4

C codes for Greedy Algorithms

                        

              Job Sequencing using Greedy method in C

 

#include<stdio.h>

#define MAX 100

typedef struct Job {

  char id[6];

  int deadline;

  int profit;

} Job;

void JobSeq(Job jobs[], int n);

// minimum of two jobs.

int Min(int x, int y) {

  if(x < y) return x;

  return y;

}

int main(void) {

  /*variables*/

  int i, j;

  /*jobs with deadline and profit*/

  Job jobs[6] = {

    {"j1", 60,  200},

    {"j2", 40,  180},

    {"j3", 30,  190},

    {"j4", 20,  300},

    {"j5", 40,  120},

    {"j6", 70,  120},

  };

  /*need one temp variable*/

  Job temp;

  //total  jobs

  int n = 6;

   /*sort profit  in descending order*/

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

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

      if(jobs[j+1].profit > jobs[j].profit) {

        temp = jobs[j+1];

        jobs[j+1] = jobs[j];

        jobs[j] = temp;  //

      }

    }

  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

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

    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);

  }

  JobSeq(jobs, n);

  return 0;

}

void JobSeq(Job jobs[], int n) {

    /*variables*/

  int i, j, k, maxprofit;

  //free time slots

  int timeslot[MAX];

  //filled time slots

  int filledTimeSlot = 0;

  //find max deadline value

  int dmax = 0;

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

    if(jobs[i].deadline > dmax) {

      dmax = jobs[i].deadline;

    }

  }

  //Initially let us keep all free empty slot as -1

  for(i = 1; i <= dmax; i++) {

    timeslot[i] = -1;

  }

  printf("dmax: %d\n", dmax);

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

    k = Min(dmax, jobs[i - 1].deadline);

    while(k >= 1) {

      if(timeslot[k] == -1) {

        timeslot[k] = i-1;

        filledTimeSlot++;

        break;

      }

      k--;

    }

    //if all time slots are filled then stop

    if(filledTimeSlot == dmax) {

      break;

    }

  }

   /*Sequenced jobs*/

  printf("\nSequenced Jobs: ");

  for(i = 1; i <= dmax; i++) {

    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax) {

      printf(" --> ");

    }

  }

  // profit

  maxprofit = 0;

  for(i = 1; i <= dmax; i++) {

    maxprofit += jobs[timeslot[i]].profit;

  }

  printf("\nMax Profit: %d\n", maxprofit);

}