Principles of Programming Languages - Blog

Savitribai Phule Pune University

Second Year Computer Engineering

2015 Pattern

 Syllabus, Notes, PPT,  Question Bank ..... click on link https://principalsofprogramminglanguagesse.wordpress.com/

 

Write a function to get the number of vertices in an undirected graph and its edges. You may assume that no edge is input twice. i. Use adjacency list representation of the graph and find runtime of the function ii. Use adjacency matrix representation of the graph and find runtime of the function

/*  C++ Program to Implement Graph using Adjacency List, Adjacency matrix, Traverse using BFS nd DFS  */

#include <iostream>
#include <cstdlib>
#include<stdlib.h>
#include<list>
using namespace std;


int visited[20],visit[20],stk[20],top=0,qu[12],front,rear;

/* Adjacency List Node */
struct AdjListNode
{
    int dest;
    struct AdjListNode* next;
};


/*  Adjacency List */ 
struct AdjList
{
    struct AdjListNode *head;
};


/* Class Graph */
class Graph
{
    private:
        int V,k;
        struct AdjList* array;
        int adjM[10][10];   
        list<int>* adj;
       
    public:
        Graph(int V)
        {
            this->V = V;
            array = new AdjList [V];
            for (int i=1;i<=V; ++i)
            {
                      array[i].head = NULL;
                for(int j=1; j<=V; ++j)   
                {
                adjM[i][j]=0;       
                }
            }
            adj = new list<int>[V];
            for (int i=1; i<=V; ++i)
            visited[i]=0;
        }

        /* Creating New Adjacency List Node  */

        AdjListNode* newAdjListNode(int dest)
        {
            AdjListNode* newNode = new AdjListNode;
            newNode->dest = dest;
            newNode->next = NULL;
            return newNode;
        }

        /*Add Edge to Graph */

   void addEdge()
        {
            int src,des;
            cout<<"\n Enter Edge ";
            cout<<"\n From -> ";
            cin>>src;
            cout<<"\n To -> ";
            cin>>des;
            adjM[src][des]=1;
            adjM[des][src]=1;
            adj[src].push_back(des);
            adj[des].push_back(src);
            AdjListNode* newNode = newAdjListNode(des);
            newNode->next = array[src].head;
            array[src].head = newNode;
            newNode = newAdjListNode(src);
            newNode->next = array[des].head;
            array[des].head = newNode;
        }

/* Print the graph*/

  void printGraph()
        {
            int v;
        cout<<"\n Adjucency Matrix is : \n ";
        for (int i=1; i<=V; ++i)
        {
           for(int j=1; j<=V; ++j)   
            {
               cout<<adjM[i][j]<<" ";       
            }
        cout<<"\n";
        }
            for (v=1; v<=V;++v)
            {
                AdjListNode* p = array[v].head;
                cout<<"\n Adjacency list of vertex "<<v<<"\n head ";
                while(p)
                {
                   cout<<"-> "<<p->dest;
                    p = p->next;
                }
               cout<<endl;
            }
        }

/*   Traverse using DFS   */
  void DFS(int u)
    {
    for (int i=0;i<=V; ++i)
            visited[i]=0;
    int j;
    cout <<"ORDER OF VISITED VERTICES";
    cout << u <<" ";
    visited[u]=1;
    k=1;
    while(k<V)
    {
    for(j=V;j>=1;j--)
    {
     if(adjM[u][j]!=0 && visited[j]!=1 && visit[j]!=1)
      {
       visit[j]=1;
       stk[top]=j;
       top++;
      }
    }
    u=stk[--top];
    cout<<u << " ";
    k++;
    visit[u]=0; visited[u]=1;
    }
      }
/*   Traverse using BFS   */
void bfs(int v)
{
for (int i=0;i<=V; ++i)
            visited[i]=0;
cout <<"Visitied vertices\n";
cout << v;
visited[v]=1;
k=1;
while(k<V)
{
for(int j=1;j<=V;j++)
if(adjM[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rear++]=j;
}
v=qu[front++];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}


};



/* * Main */

int main()
{
    int ver,ed,ch,i,j,s;
    cout<<"Enter Count of No of Vertices";
    cin>>ver;
   
    cout<<"Enter Count of No of Egdes";
    cin>>ed;
    Graph gh(ed);
    do
    {
    cout<<"\n Select option :";
    cout<<"\n\t 1. Create graph \n \t2.Display graph \n\t3.DFS \n \t 4.BFS \n \t 5.Exit";
    cin>>ch;
    switch(ch)
    {
    case 1:
    for(i=0;i<ed;i++)
    gh.addEdge();
    break;
    case 2:
        // print the adjacency list representation of the above graph
            gh.printGraph();
        break;
    case 3:
            cout<<"\n select Initial Vertex";
            cin>>s;
        // print the adjacency list representation of the above graph
            gh.DFS(s);
        break;
    case 4:
            cout<<"\n select Initial Vertex";
            cin>>s;
        // print the adjacency list representation of the above graph
            gh.bfs(s);
        break;
    default : cout<<"\n Enter correct choice";
     }
    }while(ch!=5);

    return 0;
}

About The Great Worrier "Shivaji Maharaj"

Shivaji Bhonsle (19 Feb 1630 – 3 April 1680), also known as Chhatrapati Shivaji Maharaj, was an Indian warrior king and a member of the Bhonsle Maratha clan. Shivaji carved out an enclave from the declining Adilshahi sultanate of Bijapur that formed the genesis of the Maratha Empire. In 1674, he was formally crowned as the Chhatrapati (Monarch) of his realm at Raigad.

Shivaji Maharaj established a competent and progressive civil rule with the help of a disciplined military and well-structured administrative organisations. He innovated military tactics, pioneering the guerrilla warfare methods (Shiva sutra or ganimi kava), which leveraged strategic factors like geography, speed, and surprise and focused pinpoint attacks to defeat his larger and more powerful enemies. He revived ancient Hindu political traditions and court conventions and promoted the usage of Marathi and Sanskrit, rather than Persian, in court and administration.

Shivaji Maharaj's legacy was to vary by observer and time but began to take on increased importance with the emergence of the Indian independence movement, as many elevated him as a proto-nationalist and hero of the Hindus. Particularly in Maharashtra, debates over his history and role have engendered great passion and sometimes even violence as disparate groups have sought to characterise him and his legacy.

Shivaji Maharaj was born in the hill-fort of Shivneri, near the city of Junnar in Pune district on 19 Feb. 1630. The Government of Maharashtra accepts 19 February 1630 as his birthdate; other suggested dates include 6 April 1627 or other dates near this day. Per legend, his mother named him Shivaji in honour of the goddess Shivai, to whom she had prayed for a healthy child. Shivaji was named after this local deity. Shivaji's father Shahaji Bhonsle was a Maratha general who served the Deccan Sultanates. His mother was Jijabai, the daughter of Lakhujirao Jadhav of Sindkhed (Sindkhed Raja). At the time of Shivaji's birth, the power in Deccan was shared by three Islamic sultanates: Bijapur, Ahmednagar, and Golconda. Shahaji often changed his loyalty between the Nizamshahi of Ahmadnagar, the Adilshah of Bijapur and the Mughals, but always kept his jagir (fiefdom) at Pune and his small army with him.

How to write Research Paper

1. STEP 1. CHOOSE A TOPIC
2. STEP 2. FIND INFORMATION
3. STEP 3. STATE YOUR THESIS
4. STEP 4. MAKE A TENTATIVE OUTLINE
5. STEP 5. ORGANISE YOUR NOTES
6. STEP 6. WRITE YOUR FIRST DRAFT
7. STEP 7. REVISE YOUR OUTLINE AND DRAFT


1. Checklist One


1. 1. Is my thesis statement concise and clear?
2. 2. Did I follow my outline? Did I miss anything?
3. 3. Are my arguments presented in a logical sequence?
4. 4. Are all sources properly cited to ensure that I am not plagiarizing?
5. 5. Have I proved my thesis with strong supporting arguments?
6. 6. Have I made my intentions and points clear in the essay?
1. Checklist Two
1. 1. Did I begin each paragraph with a proper topic sentence?
1. 2. Have I supported my arguments with documented proof or examples?
1. 3. Any run-on or unfinished sentences?
1. 4. Any unnecessary or repetitious words?
1. 5. Varying lengths of sentences?
1. 6. Does one paragraph or idea flow smoothly into the next?
1. 7. Any spelling or grammatical errors?
1. 8. Quotes accurate in source, spelling, and punctuation? 
1. 9. Are all my citations accurate and in correct format?
1. 10. Did I avoid using contractions? Use "cannot" instead of "can't", "do not" instead of "don't"?
1. 11. Did I use third person as much as possible? Avoid using phrases such as "I think", "I guess", "I suppose"
1. 12. Have I made my points clear and interesting but remained objective?
1. 13. Did I leave a sense of completion for my reader(s) at the end of the paper?


1. 1. Is my thesis statement concise and clear?
   Re-read your paper for grammatical errors. Use a dictionary or a thesaurus as needed. Do a spell check. Correct all errors that you can spot and improve the overall quality of the paper to the best of your ability. Get someone else to read it over. Sometimes a second pair of eyes can see mistakes that you missed.
8. STEP 8. TYPE FINAL PAPER

Guassian membership Function in NN

%inputs
% XOR input for x1 and x2
input = [0 0; 0 1; 1 0; 1 1];
% Desired output of XOR
output = [0;1;1;0];
% Initialize the bias
bias = [-1 -1 -1];
% Learning coefficient
coeff = 0.7;
% Number of learning iterations
iterations = 10000;
% Calculate weights randomly using seed.
rand('state',sum(100*clock));
weights = -1 +2.*rand(3,3);

%with back propogation
for i = 1:iterations
   out = zeros(4,1);
   numIn = length (input(:,1));
   for j = 1:numIn
      % Hidden layer
      H1 = bias(1,1)*weights(1,1)     
          + input(j,1)*weights(1,2)
          + input(j,2)*weights(1,3);

      % Send data through sigmoid function 1/1+e^-x
      % Note that sigma is a different m file
      % that I created to run this operation
      x2(1) = sigma(H1);
      H2 = bias(1,2)*weights(2,1)
           + input(j,1)*weights(2,2)
           + input(j,2)*weights(2,3);
      x2(2) = sigma(H2);

      % Output layer
      x3_1 = bias(1,3)*weights(3,1)
             + x2(1)*weights(3,2)
             + x2(2)*weights(3,3);
      out(j) = sigma(x3_1);
     
      % Adjust delta values of weights
      % For output layer:
      % delta(wi) = xi*delta,
      % delta = (1-actual output)*(desired output - actual output)
      delta3_1 = out(j)*(1-out(j))*(output(j)-out(j));
     
      % Propagate the delta backwards into hidden layers
      delta2_1 = x2(1)*(1-x2(1))*weights(3,2)*delta3_1;
      delta2_2 = x2(2)*(1-x2(2))*weights(3,3)*delta3_1;
     
      % Add weight changes to original weights
      % And use the new weights to repeat process.
      % delta weight = coeff*x*delta
      for k = 1:3
         if k == 1 % Bias cases
            weights(1,k) = weights(1,k) + coeff*bias(1,1)*delta2_1;
            weights(2,k) = weights(2,k) + coeff*bias(1,2)*delta2_2;
            weights(3,k) = weights(3,k) + coeff*bias(1,3)*delta3_1;
         else % When k=2 or 3 input cases to neurons
            weights(1,k) = weights(1,k) + coeff*input(j,1)*delta2_1;
            weights(2,k) = weights(2,k) + coeff*input(j,2)*delta2_2;
            weights(3,k) = weights(3,k) + coeff*x2(k-1)*delta3_1;
         end
      end
   end  
end

Activation Function in NN

% Illustration of various activation functions used in NN's
x = -10:0.1:10;
tmp = exp(-x);
y1 = 1./(1+tmp);
y2 = (1-tmp)./(1+tmp);
y3 = x;
subplot(231); plot(x, y1); grid on;
axis([min(x) max(x) -2 2]);
title('Logistic Function');
xlabel('(a)');
axis('square');
subplot(232); plot(x, y2); grid on;
axis([min(x) max(x) -2 2]);
title('Hyperbolic Tangent Function');
xlabel('(b)');
axis('square');
subplot(233); plot(x, y3); grid on;
axis([min(x) max(x) min(x) max(x)]);
title('Identity Function');
xlabel('(c)');
axis('square');

Implement defuzzyfication (Max-membership principle, Centroid method, Weighted average method)

clc;
clear all;
close all;

ip=11;
a1=1;
a2=5;
b1=4;
b2=7;
c1=7;
c2=9;
d2=11;
s1=0;
s2=0;

%Triangular function

for u=1:ip
    if(u<=a1)
        t(u)=0;
    elseif((u>a1)&&(u<=b1))
        t(u)=((u-a1)/(b1-a1));
    elseif((u>b1)&&(u<=c1))
        t(u)=((c1-u)/(c1-b1));
    else
        t(u)=0;
    end
end

subplot(221)
plot(t);
title('Triangular Function');

%Pie function

for u=1:ip
    if(u<=a2)
        p(u)=0;
    elseif((u>a2)&&(u<=b2))
        p(u)=((u-a2)/(b2-a2));
    elseif((u>b2)&&(u<=c2))
        p(u)=1;
    elseif((u>c2)&&(u<=d2))
        p(u)=((d2-u)/(d2-c2));
    else
        p(u)=0;
    end
end

subplot(222)
plot(p);
title('Pie Function');

z=t+p;
subplot(223);
plot(z);

%Using Centroid Method
for i=1:11
    s1=s1+(z(i)*i);
    s2=s2+z(i);
end

op1=s1/s2;
disp('Using Centroid Method:');
disp(op1);


%Using Weighted average method
a=mean(ip);
s1=s1+t(a)*(a)+p(a)*(a);
s2=s2+z(a)+p(a);
op1=s1/s2;
disp('Using Weighted Average MEthod');
disp(op1);

%Using Max-Membership Principle
k=z(1);
m=1;
for i=2:ip
    if(k<z(i))
    k=z(i);
    m=i;
    end
end
disp('Using Max Membership principle');
disp(m);