DumB-ShAre-ArtS

Is Google cheating on us

2011-02-11T03:00:00.000-08:00

Just observed something.you type any query in google and search for it and google returns result very quicly and says
About 4,850,000 results (0.11 seconds)

You can see that result on page 2 starts with result number 10 i.e start=10 u can watch that in url above.

Now when i change that start value to 500 i.e start=500 observe what happened

Number of result is reduced to 453 i.e About 4,850,000 results (0.11 seconds) is now changed to page 47 of 453 result.

Again when i changed start value from 500 to 1000 google reviles its secrete
watch out:-

"Sorry, Google does not serve more than 1000 results for any query. (You asked for results starting from 1000.)"
Then is message returned by google in first place that "about 4,850,000 results" found justified ?????

Isn't it a sort of cheating with its user, giving false impression that it is serving so fast for result set containing millions of items in-spite of fact that it is returning 1000 result at max for any query ...

---Regards
Sagar Sharma

How to not secure urself ...

2010-11-28T04:42:00.000-08:00

Seen it somewhere so thought abt posting it here ...

See n observer how much difficult is it to crack this 4 digit door lock code.. :D
with this lock someone secured his assets ... i m genuinely concerned if insurance company will pay for loss of his assets....well as a insurence inspector i must nt ..
wat say fellas ...
For more info on security issues goto :- http://securityresearch.in/

ARP poisoning attack and countermeasure (MAN IN THE MIDDLE ATTACK) MITM

2010-11-17T07:00:00.000-08:00

One of the active evesdropping attack in current scenario used against individual and organisational is MAN-IN-THE-MIDDLE often know as MITM attack.It is basically exploits the ARP(Address Resolution Protocol).This attack is categorized as Layer 2 attack ,i.e it works on layer -2(MAC Sublayer) of TCP/IP model most of u must be knowing.

MITM attack include: apr poisioning , DNS spoofing , http session hijaking

ARP

This protocol is made to facilitate layer-2(MAC) to layer-3(IP) address transaltion.APR is based on 2 packats ARP_REQUEST and ARP_RESPONSE

Aim of these 2 packats are to locate the hardware address associated with the provided IP-address.

ARP_REQUEST is like it says my IP is AA.AA.AA.AA ,and my MAC address is
AA:AA:AA:AA:AA:AA i want to send some data to destination whose IP is BB.BB.BB.BB i don't know the Hardware address pls tell me.depicted in pic given and similarly ARP_RESPONSE packet is generated answering the requested question.Once this transmission is over the transmitting device updates its ARP_CACHE_TABLE,and then the communication starts.

ARP POISIONING

ARP is insecured protocol,devices using ARP can take update at any time.This means that any host in network can reply with ARP_REPLY and force the another host to update its ARP_CACHE with new poisoned value.

This feature of ARP can be used in malicious manner that user thinks that it is communicating with intended user in spite of fact actually it is communicating with attacker.

Now i m gonna show you the demonstration for ARP_POSIONING. For recreating by demonstration u need
1)unix OS
2)ettrecap utility

there are many pluginswhich are provided by ettrecap.
that u can find using

$man ettrecap

use the command given below to start arp posoning n listening to private data,poior to that be sure to be in superuser mode .

#ettercap -T -q -M arp:remote -i etho -P repoison_arp // //

above command will scan all the host in ur subnet and will poison dere arp_cache.
-T -- this cap is for running ettrecap in text mode
-q -- this cap is for showing only usufull information not the entire packet
-M -- this cap is for starting MITM attack
-i   --this cap is for selection of netwrok interface on which MITM will work
         it can be eth0 or wlan0 or watever interface u are interested in
-P -- this is for using the plugin provided by the utility
// // --it is there for selecting the user range within subnet default is whole
         subnet

After executing this command u'll get the private data of users within subnet .
above tutorial was intended entirely for purpose of understanding.pls don't use them for malacious purpose .

it's awl for nw

For more info goto :- http://securityresearch.in/
Next post will be about DNS_SPOOFING till then tadasssssssss..

How to program for IP - resolver against a host-name

2010-10-31T10:09:00.000-07:00

For this matter u need to have some prerequisite :-
1)Knowledge of C language
2)Unix based system on ur Box

Now here we go is the code for resolving the IP address from given hostnames:
given program in line no 40 gets the address info with help of getaddrinfo( ) function line no. 46 to 61 prints the Ip addresses. Loop from 46 to 61 is for the case if server is having multiple Ip's .User can give n numbers of hostname and corresponding IP'll be resolved.
Explanation of program is described just after the program .

1:  //   Ipresolver.c  
2:  //     
3:  //   Copyright 2010 ananya <ananya@kgeek-laptop>   
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <stdio.h>  
20:  #include <string.h>  
21:  #include <sys/types.h>  
22:  #include <sys/socket.h>  
23:  #include <netdb.h>  
24:  #include <arpa/inet.h>  
25:  int main(int argc, char *argv[])  
26:  {  
27:    struct addrinfo hints, *res, *p;  
28:    int status,i;  
29:    char ipstr[INET6_ADDRSTRLEN];  
30:    if (argc == 1) {  
31:      fprintf(stderr,"usage: showip hostname[n]\n");  
32:      return 1;  
33:    }  
34:   for(i=1;i<argc;i++)  
35:   {  
36:    printf("************************************************\n");  
37:    memset(&hints, 0, sizeof hints);  
38:    hints.ai_family = AF_UNSPEC;   
39:    hints.ai_socktype = SOCK_STREAM;  
40:    if ((status = getaddrinfo(argv[i], NULL, &hints, &res)) != 0) {      //getaddrinfo() call goes here   
41:      fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(status));      //Ip and other info regarding hostname is stored in struct addrinfo res     
42:      return 2;  
43:    }  
44:    //printf("%d\n",status);  
45:    printf("IP addresses for %s:\n\n", argv[i]);  
46:    for(p = res;p != NULL; p = p->ai_next) {                  //Loop goes for different Ips if hostname has multiple Ip's  
47:      void *addr;  
48:      //in_port_t port;  
49:      char *ipver;  
50:      if (p->ai_family == AF_INET) {                    //If it is IPv4  
51:        struct sockaddr_in *ipv4 = (struct sockaddr_in *)p->ai_addr;     
52:        addr = &(ipv4->sin_addr);                     //Extracting Ip address in binary format   
53:        //port=ipv4->sin_port;  
54:        ipver = "IPv4";                            
55:      } else {                               //If it is IPv6                
56:        struct sockaddr_in6 *ipv6 = (struct sockaddr_in6 *)p->ai_addr;    
57:        addr = &(ipv6->sin6_addr);  
58:        ipver = "IPv6";  
59:      }  
60:      inet_ntop(p->ai_family, addr, ipstr, sizeof ipstr);          //convert binary Ip notation in text i.e dotted decimal form  
61:      printf(" %s: %s \n", ipver, ipstr);  
62:    }  
63:  }  
64:    freeaddrinfo(res);   
65:    return 0;  
66:  }

Compiling Info:-

$ gcc IPresolver.c -o Ipresolver.o

$ ./Ipresolver.o www.nitk.ac.in www.google.com www.slashdot.org

Corresponding Output:-

 ************************************************  
 IP addresses for www.nitk.ac.in:  
  IPv4: 210.212.194.8   
 ************************************************  
 IP addresses for www.google.com:  
  IPv4: 72.14.213.105   
  IPv4: 72.14.213.106   
  IPv4: 72.14.213.147   
  IPv4: 72.14.213.99   
  IPv4: 72.14.213.103   
  IPv4: 72.14.213.104   
 ************************************************  
 IP addresses for www.slashdot.org:  
  IPv4: 216.34.181.48

so here we go:-

Socket Descriptor it is of type int.

1:   struct addrinfo {  
2:          int       ai_flags;              // AI_PASSIVE, AI_CANONNAME, etc.  
3:          int       ai_family;             //AF_INET (IPv_4),AF_INET6 (IPV_6)  
4:          int       ai_socktype;          //SOCK_STREAM,SOCK_DGRM  
5:          int       ai_protocol;           //Usually "0"  
6:          size_t     ai_addrlen;           // size of ai_addr in bytes   
7:          struct sockaddr *ai_addr;         //struct sockaddr_in or _in6          
8:          char      *ai_canonname;       //full canonical hostname  
9:          struct addrinfo *ai_next;          //next node in lineked list  
10:        };

u can even get this struct info using konsole command :-

$ man getaddrinfo

1:  struct sockaddr {  
2:          sa_family_t sa_family;  
3:          char    sa_data[14];  
4:        }

the only purpose of above is to cast the structure pointer passed in addr in order to avoid compiler warnings.

u can even get this struct info using konsole command :-

$ man bind

To deal with struct sockaddr, programmers created a parallel structure: struct sockaddr_in ("in" for "Internet") to be used with IPv4. and sockaddr_in6 for IPv6

Structure sockaddr_in6

1:  struct sockaddr_in6 {  
2:          sa_family_t   sin6_family;  /* AF_INET6 */  
3:          in_port_t    sin6_port;   /* port number */  
4:          uint32_t    sin6_flowinfo; /* IPv6 flow information */  
5:          struct in6_addr sin6_addr;   /* IPv6 address */  
6:          uint32_t    sin6_scope_id; /* Scope ID (new in 2.4) */  
7:        };  
8:        struct in6_addr {  
9:          unsigned char  s6_addr[16];  /* IPv6 address */  
10:        };

u can even get this struct info using konsole command :-

$ man ipv6

similarly struct sockaddr_in for IPv4 cab b viewed .

First, let's say you have a struct sockaddr_in ina, and you have an IP address "192.168.0.48" or "2001:db8:63b3:1::3490" that you want to store into it. The function you want to use, inet_pton(), converts an IP address in numbers-and-dots notation into either a struct in_addr or astruct in6_addr depending on whether you specify AF_INET or AF_INET6. ("pton" stands for "presentation to network"—you can call it "printable to network" if that's easier to remember.) The conversion can be made as follows:

1:  inet_pton(AF_INET, "192.168.0.48", &(sa.sin_addr)); // IPv4  
2:  inet_pton(AF_INET6, "2001:db8:63b3:1::3490", &(sa6.sin6_addr)); // IPv6

u can get infomation about inet_pton() using following command in konsole:-

$ man inet_pton

getaddrinfo()

It used to be that you would use a function called gethostbyname() to do DNS lookups. Then you'd load that information by hand into a struct sockaddr_in, and use that in your calls.

In these modern times, you now have the function getaddrinfo() that does all kinds of good stuff for you, including DNS and service name lookups, and fills out the structs you need, besides!

1:   #include <sys/types.h>  
2:   #include <sys/socket.h>  
3:   #include <netdb.h>  
4:   int getaddrinfo(const char *node, const char *service,  
5:              const struct addrinfo *hints,  
6:              struct addrinfo **res);  
7:   void freeaddrinfo(struct addrinfo *res);  
8:   const char *gai_strerror(int errcode);

U can get hell lot of information about this function using konsole command:

$ man getaddrinfo

Enjoy Rest in peace

Solution of 8-Queen Problem

2010-10-25T15:20:00.000-07:00

Definition of problem :- Here is a very famous problem. How many ways are there to place 8 queens on a chess board so that
no two queens attack each other? A chess board is an 8x8 grid. Queens can be placed in the cells f
the grid. Two queens are under mutual attack if they share a row, a column or a diagonal. Here is one
possible solution:
We have to endure 4-things
1)No 2 Queens share same Column
2)No 2 Queens share same Row
3)No 2 Queens share / diagonal
4)No 2 Queens share \ diagonal
No. 1 is automatic because the way we store solution
No. 2 is done with used array
for 3 and 4 we do same thing we keep two array of size 15 to keep track which diagonals are occupied.,Consider the following trick.If we take a cell with coordinate (r,c) what are the values of (r+c) and (r+c-7) (indexing is from 0-7).

Let's call (r+c) the "Slash Code" of cell and (r-c+7) the "Backslash Code" .Then two queen which share a / diagonal has same "Slash code" and those who share a \ diagonal has same "Backslash Code" .

Solution O/P :-

For more info goto : http://securityresearch.in/beta
Code :-

1:  //   8_queen.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <vector>  
21:  using namespace std;  
22:  vector<int> row(8),used(8),slash(15),backSlash(15);  
23:  int total;  
24:  int queen(int i)  
25:  {  
26:       if(i==8)  
27:       {  
28:            return 1;  
29:       }  
30:       for(row[i]=0;row[i]<8;row[i]++)  
31:       {  
32:            if(used[row[i]]==1 || slash[row[i]+i]==1 || backSlash[row[i]-i+7]==1)  
33:                 continue;  
34:            used[row[i]]=1;  
35:            slash[row[i]+i]=1 ;  
36:            backSlash[row[i]-i+7]=1;  
37:            total=queen(i+1);  
38:            if (total==1)  
39:              return 1;  
40:            used[row[i]]=0;  
41:            slash[row[i]+i]=0 ;  
42:            backSlash[row[i]-i+7]=0;  
43:       }  
44:       return total;  
45:  }   
46:  int main(int argc, char** argv)  
47:  {  
48:       for(int i=0;i<8;i++)  
49:       {  
50:            row[i]=0;  
51:            used[i]=0;  
52:       }  
53:       for(int i=0;i<15;i++)  
54:       {  
55:            slash[i]=0;  
56:            backSlash[i]=0;  
57:       }  
58:       int k=queen(0);  
59:       k++;  
60:       /*for(int i=0;i<8;i++)  
61:       {  
62:            cout<<row[i]<<endl;  
63:       }*/  
64:    for(k=0;k<8;k++)  
65:        {  
66:        for(int l=0;l<8;l++)  
67:            cout<<" ----";  
68:        cout<<endl;  
69:        for(int j=0;j<9;j++)  
70:        {  
71:            cout<<"|  ";  
72:            if(row[k]==j)  
73:            cout<<"\b\bQ"<<k;  
74:        }  
75:        cout<<endl;  
76:     }  
77:       for(int l=0;l<8;l++)  
78:            cout<<" ----";       
79:       return 0;  
80:  }

Rest in Peace

Just Because Google Exists Doesn’t Mean You Should Stop Asking People Things

2010-10-24T09:55:00.000-07:00

I found a pretty interesting thing :- If you spend any amount of time online you’re probably very familiar with the above website,Let Me Google That For You LMGTFY is a super smug and hilarious site built for those sick of “all those people that find it more convenient to bother you with their question rather than google it for themselves.“

Also “Because of Google,” Mecurio said. “Everyone would call their friend and the friend would start Googling to get the answer. The contestant would be like, ‘Hey Joe, aspirin. A-S-P-I-R-I-N.’ We could hear them typing on their keyboard!”

Google has basically become an extension of our brain, as of Mr. Steve Jobs’ Bicycle for Our Mind

Twice this week I have asked questions that would be better suited to a human rather than an search engine algorithm and both times I’ve been met with a “just Google it”- Clumsy response [:x].

Implementation of Bellman_Ford in C++ Using STL

2010-10-21T07:32:00.001-07:00

For further info goto : http://securityresearch.in/beta/

1:  //   Bellman_Ford.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <stdio.h>  
21:  #include <limits.h>  
22:  #include <map>  
23:  #include <vector>  
24:  #include <string>  
25:  #include <list>  
26:  #include <functional>  
27:  using namespace std;  
28:  struct Vertex;  
29:  struct Edge  
30:  {  
31:       Vertex *dest;  
32:       double cost;  
33:       Edge(Vertex *d=0,double c=0.0)  
34:        : dest(d),cost(c){}  
35:  };  
36:  struct Vertex  
37:  {   
38:       string name;  
39:       vector<Edge> adj;  
40:       double dist;  
41:       Vertex *prev;  
42:       unsigned int scratch;  
43:       Vertex(const string &nam):name(nam)  
44:       {reset();}  
45:       void reset()  
46:       {  
47:            dist=3000000;  
48:            prev=0;  
49:            scratch=0;  
50:    }       
51:  };  
52:  class Graph  
53:  {  
54:       public:  
55:            Graph(){};  
56:         ~Graph();  
57:         void addEdge(const string & sourceName,const string & destName,double cost);  
58:         void printPath(const string & destName) const;  
59:         bool bellmanFord(const string & startName);  
60:         void printbellmanFord();  
61:       private:  
62:         Vertex * getVertex(const string & vertexName);  
63:         void printPath(const Vertex & dest) const;  
64:         void clearAll();  
65:         typedef map<string,Vertex *,less<string> > vmap;  
66:         vmap vertexMap;  
67:  };  
68:  Graph::~Graph()  
69:  {  
70:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
71:            delete (*itr).second;  
72:  }  
73:  Vertex * Graph::getVertex(const string & vertexName)  
74:  {  
75:       vmap::iterator itr=vertexMap.find(vertexName);  
76:       if(itr==vertexMap.end())  
77:       {  
78:            Vertex *newv=new Vertex(vertexName);  
79:            vertexMap[vertexName]=newv;  
80:            return newv;  
81:       }  
82:       return (*itr).second;  
83:  }  
84:  void Graph::addEdge(const string & sourceName,  
85:            const string & destName,double cost)  
86:  {  
87:       Vertex *v=getVertex(sourceName);  
88:       Vertex *w=getVertex(destName);  
89:       v->adj.push_back(Edge(w,cost));  
90:  }  
91:  void Graph::clearAll()  
92:  {  
93:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
94:            (*itr).second->reset();  
95:  }  
96:  void Graph::printPath(const Vertex & dest) const  
97:  {  
98:       if(dest.prev!=0)  
99:       {  
100:            printPath(*dest.prev);  
101:            cout<<" -->";  
102:       }  
103:       cout<<dest.name;  
104:  }  
105:  void Graph::printPath(const string &destName) const  
106:  {  
107:       vmap::const_iterator itr=vertexMap.find(destName);  
108:       if(itr==vertexMap.end())  
109:       {  
110:            cout<<destName<<" not Found in Graph"<<endl;  
111:            return;  
112:       }  
113:       Vertex & w =*(*itr).second;  
114:       if(w.dist==3000000)  
115:            cout<<destName<<" is not rechable"<<endl;  
116:       else  
117:       {  
118:            cout<<"(Cost is: "<<w.dist<< ")";  
119:            printPath(w);  
120:       }  
121:       cout<<endl;  
122:  }  
123:  void Graph::printbellmanFord()  
124:  {  
125:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
126:        {  
127:            cout<<(*itr).first;  
128:            printPath((*itr).first);  
129:        }  
130:  }  
131:  bool Graph::bellmanFord(const string & startName)  
132:  {  
133:       vmap::iterator itr=vertexMap.find(startName);  
134:       if(itr==vertexMap.end())  
135:         {  
136:          cout<<"Specified node not found in graph"<<endl;  
137:          return 0;  
138:         }  
139:       clearAll();  
140:       Vertex *start=(*itr).second;  
141:       list<Vertex *> q;  
142:       q.push_back(start);  
143:       start->dist=0;  
144:       start->scratch++;  
145:       while(!q.empty())  
146:       {  
147:            Vertex *v=q.front();  
148:            q.pop_front();  
149:            if(v->scratch++>2*vertexMap.size())  
150:            {  
151:                 cout<<"Negative Cycle detected"<<endl;  
152:                 return false ;  
153:            }  
154:            for(unsigned int i=0;i<v->adj.size();i++)  
155:            {  
156:                 Edge e=v->adj[i];  
157:                 Vertex *w=e.dest;  
158:                 double cvw=e.cost;  
159:                 if(w->dist>v->dist+cvw)  
160:                 {  
161:                      w->dist=v->dist+cvw;  
162:                      w->prev=v;  
163:                      if(w->scratch++ % 2==0)  
164:                           q.push_back(w);  
165:                      else  
166:                           w->scratch++;  
167:                 }  
168:            }  
169:       }  
170:       return true ;  
171:  }  
172:  int main(int argc, char** argv)  
173:  {  
174:       Graph g;  
175:       cout<<"Enter the Graph description in following format:->"<<endl;  
176:       cout<<"Edge_sourceName Edge_destName cost_of_Edge"<<endl;  
177:       cout<<"Enter the detail:-"<<endl;  
178:       int a,cost;  
179:       a=1;  
180:       string sName,dName;  
181:       while(a==1)  
182:       {   
183:        cin>>sName>>dName>>cost;  
184:        g.addEdge(sName,dName,cost);  
185:        cout<<"Wanna Continue(press 1/0):";  
186:        cin>>a;   
187:    }  
188:    cout<<"Enter the source node:";  
189:    cin>>sName;  
190:    if(g.bellmanFord(sName)==true)  
191:    {  
192:       cout<<"Shortest path to Distinct nodes are :-->"<<endl;  
193:       g.printbellmanFord();  
194:    }  
195:    else  
196:    {  
197:    }   
198:    return 0;  
199:  }

Implementation of Floyd Warshall in C++ Using STL

2010-10-21T07:29:00.001-07:00

1:  //   Floyd_Warshall.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <vector>  
21:  #include <stdio.h>  
22:  using namespace std;  
23:  int path(int x,int y,vector<vector<int> > & par)  
24:  {  
25:       if(x!=y)  
26:       {  
27:            path(x,par[x][y],par);  
28:            cout<<"-->"<<y;  
29:       }  
30:       return 0;  
31:  }  
32:  int main(int argc, char** argv)  
33:  {  
34:       int n;  
35:       cout<<"Enter the Number of nodes : ";  
36:       cin>>n;  
37:       vector<vector<int> > g(n+1,vector<int> (n+1));  
38:       vector<vector<int> > d(n+1,vector<int> (n+1));  
39:       vector<vector<int> > p(n+1,vector<int> (n+1));  
40:  /*     vector<vector<int> > Temp(n,vector<int> (n));  
41:       vector<vector<int> > pTemp((n,vecor<int> (n));  
42:  */       
43:       cout<<"use 3000 for INFINITY"<<endl;  
44:       cout<<"Enter the graph discription in row-major fashion:"<<endl;  
45:       for(int i=1;i<n+1;i++)  
46:            {  
47:                 for(int j=1;j<n+1;j++)  
48:                      {  
49:                           cin>>g[i][j];  
50:                      }  
51:            }  
52:       for(int i=1;i<n+1;i++)  
53:            {  
54:                 for(int j=1;j<n+1;j++)  
55:                      {  
56:                           d[i][j]=g[i][j];  
57:                           if(g[i][j]==0 || g[i][j]==3000)  
58:                                p[i][j]=0;  
59:                           else   
60:                                p[i][j]=i;  
61:                      }  
62:            }  
63:       for(int k=1;k<n+1;k++)  
64:       {  
65:            for(int i=1;i<n+1;i++)  
66:                 {  
67:                      for(int j=1;j<n+1;j++)  
68:                      {  
69:                           if(d[i][j] > d[i][k]+d[k][j])  
70:                           {  
71:                                d[i][j]=d[i][k]+d[k][j];  
72:                                p[i][j]=p[k][j];  
73:                           }  
74:                      }  
75:                 }  
76:       }  
77:       cout<<"Modified ASSP MATRIX is:->";  
78:       for(int i=1;i<n+1;i++)  
79:    {  
80:            std::cout<<endl;  
81:            for(int j=1;j<n+1;j++)  
82:            {  
83:                printf("%5d",d[i][j]);  
84:            }  
85:    }  
86:    cout<<endl<<"Parent MATRIX is:->";  
87:    for(int i=1;i<n+1;i++)  
88:    {  
89:            std::cout<<endl;  
90:            for(int j=1;j<n+1;j++)  
91:            {  
92:                printf("%5d",p[i][j]);  
93:            }  
94:    }  
95:    cout<<endl<<endl;  
96:    for(int i=1;i<n+1;i++)  
97:    {  
98:            for(int j=1;j<n+1;j++)  
99:            {  
100:                 if(i!=j)  
101:                 {  
102:                      cout<<"Shortes Path from node "  
103:                        <<i <<" to node "<<j  
104:                        <<" :- cost= "<<d[i][j];  
105:                      cout<<"::path is "<<i;  
106:                      path(i,j,p);  
107:                 }  
108:                 cout<<endl;  
109:            }  
110:       }  
111:       /*cout<<endl;  
112:       cout<<"1";  
113:    path(1,2,p);*/  
114:       return 0;  
115:  }

For Further info goto :- http://securityresearch.in/beta/

Implementation of Jhonson's APSP in C++ Using STL

2010-10-21T07:26:00.001-07:00

1:  //   Johnson_mod.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <stdio.h>  
21:  #include <limits.h>  
22:  #include <map>  
23:  #include <vector>  
24:  #include <string>  
25:  #include <list>  
26:  #include <functional>  
27:  #include <queue>  
28:  using namespace std;  
29:  struct Path;  
30:  struct Vertex;  
31:  struct Edge  
32:  {  
33:       Vertex *dest;      
34:       double cost;      
35:       Edge(Vertex *d=0,double c =0.0)  
36:        : dest(d),cost(c) {}  
37:  };  
38:  struct Vertex  
39:  {  
40:       string name;      
41:       vector<Edge> adj;    
42:       double dist;      
43:       Vertex *prev;      
44:    unsigned int scratch;  
45:    double h;  
46:    unsigned int hash;    
47:    Vertex(const string & nam):name(nam)  
48:      {reset();}  
49:    void reset()  
50:     {  
51:             dist=3000000;  
52:             prev=0;  
53:             scratch=0;  
54:        }  
55:  };  
56:  struct Path  
57:  {  
58:       Vertex *dest;  
59:       double cost;  
60:       Path(Vertex *d=0 ,double c=0)  
61:        : dest(d),cost(c){}  
62:       bool operator>(const Path &rhs) const  
63:       {return (cost > rhs.cost);}  
64:       bool operator<(const Path &rhs) const  
65:       {return (cost < rhs.cost);}  
66:  };  
67:  class Graph  
68:  {  
69:       public:  
70:         Graph(){};  
71:        ~Graph();  
72:         void addEdge(const string & sourceName,const string & destName,double cost);  
73:         void printPath(const string & destName) const;  
74:         void dijkastra(const string & startName);  
75:         bool bellmanFord(const string & startName);  
76:         bool jhonson();  
77:         void printDijkastra();  
78:         int getNodeCount();  
79:         void calcHash();  
80:    private:  
81:      Vertex * getVertex(const string & vertexName);  
82:      void printPath(const Vertex & dest) const;  
83:      void clearAll();  
84:      typedef map<string,Vertex *,less<string> > vmap;  
85:      vmap vertexMap;     
86:  };  
87:  Graph g,g1;  
88:  Graph::~Graph()  
89:  {  
90:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
91:           delete (*itr).second;  
92:  }  
93:  Vertex * Graph::getVertex(const string & vertexName)  
94:  {  
95:       vmap::iterator itr= vertexMap.find(vertexName);  
96:       if(itr==vertexMap.end())  
97:       {  
98:            Vertex *newv=new Vertex(vertexName);  
99:            vertexMap[vertexName]=newv;  
100:            return newv;  
101:       }  
102:       return (*itr).second;  
103:  }  
104:  void Graph::addEdge(const string & sourceName,  
105:            const string & destName,double cost)  
106:  {  
107:       Vertex * v =getVertex(sourceName);  
108:       Vertex * w =getVertex(destName);  
109:       v->adj.push_back(Edge(w,cost));  
110:  }  
111:  void Graph::clearAll()  
112:  {  
113:       for(vmap::iterator itr= vertexMap.begin();  
114:         itr!=vertexMap.end();++itr)  
115:         (*itr).second->reset();  
116:  }  
117:  void Graph::printPath(const Vertex & dest) const  
118:  {  
119:       if(dest.prev !=0)  
120:       {  
121:            printPath(*dest.prev);  
122:            cout<<" --> ";  
123:       }  
124:       cout<<dest.name;  
125:  }  
126:  void Graph::printPath(const string & destName) const  
127:  {  
128:       vmap::const_iterator itr= vertexMap.find(destName);  
129:       if(itr==vertexMap.end())  
130:       {  
131:            cout<<"Destination not found "<<endl;  
132:            return ;  
133:       }       
134:       const Vertex & w =*(*itr).second;  
135:       if(w.dist==3000000)  
136:         cout<<destName<<" not reachable "<<endl;  
137:       else  
138:       {  
139:            cout<<"(Cost is: "<< w.dist << ")";  
140:            printPath(w);  
141:       }  
142:       cout<<endl;  
143:  }  
144:  void Graph::printDijkastra()  
145:  {  
146:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
147:        {  
148:            cout<<(*itr).first;  
149:            printPath((*itr).first);  
150:        }  
151:  }  
152:  int Graph::getNodeCount()  
153:  {  
154:       return vertexMap.size();  
155:  }  
156:  void Graph::calcHash()  
157:  {  
158:       unsigned int i =1;  
159:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
160:       {  
161:            (*itr).second->hash=i++;  
162:       }  
163:  }  
164:  void Graph::dijkastra(const string & startName)  
165:  {  
166:       priority_queue< Path,vector<Path>,greater<Path> > pq;  
167:       Path vrec;  
168:       vmap::iterator itr=vertexMap.find(startName);  
169:       if(itr==vertexMap.end())  
170:         {  
171:          cout<<"Specified node not found in graph"<<endl;  
172:          return ;  
173:         }  
174:       clearAll();  
175:       Vertex *start= (*itr).second;  
176:       pq.push(Path(start,0));  
177:       start->dist=0;  
178:       unsigned int nodesSeen=0;  
179:       for(;nodesSeen<vertexMap.size();nodesSeen++)  
180:       {  
181:            do  
182:            {  
183:                 if(pq.empty())  
184:                   return;  
185:                 vrec=pq.top();  
186:                 pq.pop();  
187:            }while(vrec.dest->scratch!=0);  
188:            Vertex *v =vrec.dest;  
189:            v->scratch=1;  
190:            for(unsigned int i=0;i<v->adj.size();i++)  
191:            {  
192:                 Edge e=v->adj[i];  
193:                 Vertex *w=e.dest;  
194:                 double cvw=e.cost;  
195:                 if(cvw<0)  
196:                 {  
197:                  cout<<"Negative Weight Edge seen"<<endl;  
198:                  return;  
199:                 }  
200:                  if(w->dist>v->dist+cvw)  
201:                  {  
202:                       w->dist=v->dist+cvw;  
203:                       w->prev=v;  
204:                       pq.push(Path(w,w->dist));  
205:                  }  
206:             }  
207:        }  
208:  }  
209:  bool Graph::bellmanFord(const string & startName)  
210:  {  
211:       vmap::iterator itr=vertexMap.find(startName);  
212:       if(itr==vertexMap.end())  
213:         {  
214:          cout<<"Specified node not found in graph"<<endl;  
215:          return 0;  
216:         }  
217:       clearAll();  
218:       Vertex *start=(*itr).second;  
219:       list<Vertex *> q;  
220:       q.push_back(start);  
221:       start->dist=0;  
222:       start->scratch++;  
223:       while(!q.empty())  
224:       {  
225:            Vertex *v=q.front();  
226:            q.pop_front();  
227:            if(v->scratch++>2*vertexMap.size())  
228:            {  
229:                 cout<<"Negative Cycle detected"<<endl;  
230:                 return false ;  
231:            }  
232:            for(unsigned int i=0;i<v->adj.size();i++)  
233:            {  
234:                 Edge e=v->adj[i];  
235:                 Vertex *w=e.dest;  
236:                 double cvw=e.cost;  
237:                 if(w->dist>v->dist+cvw)  
238:                 {  
239:                      w->dist=v->dist+cvw;  
240:                      w->prev=v;  
241:                      if(w->scratch++ % 2==0)  
242:                           q.push_back(w);  
243:                      else  
244:                           w->scratch++;  
245:                 }  
246:            }  
247:       }  
248:       return true ;  
249:  }  
250:  bool Graph::jhonson()  
251:  {  
252:       g.calcHash();  
253:       int n=g.getNodeCount();  
254:       vector<vector<int> > d(n+1,vector<int> (n+1));  
255:       for(int i=0;i<n+1;i++)  
256:            for(int j=0;j<n+1;j++)  
257:                 d[i][j]=0;  
258:       string str;  
259:    g.getVertex("S");  
260:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
261:       {  
262:            str=(*itr).first;  
263:            g.addEdge("S",str,0);  
264:       }  
265:       bool t=g.bellmanFord("S");  
266:       if(t==false)  
267:       {  
268:            cout<<"Negative Cycle is there in Graph !!Exiting!!"<<endl;  
269:            return false;  
270:       }  
271:       else  
272:       {  
273:            cout<<endl<<"h-value of each node using Bellman_Ford is :->"<<endl;  
274:            for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
275:            {  
276:                 (*itr).second->h=(*itr).second->dist;  
277:                 cout<<(*itr).first<<"  :  "<<(*itr).second->h<<endl;  
278:            }  
279:            cout<<endl<<"Reweighted edges are :->"<<endl;            
280:         for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
281:            {  
282:                 Vertex *w=(*itr).second;  
283:                 for(unsigned int i=0;i<w->adj.size();i++)  
284:                 {  
285:                      w->adj[i].cost=w->adj[i].cost + w->h -w->adj[i].dest->h;  
286:                      cout<<w->name<<" to "<<w->adj[i].dest->name<<" = "<<w->adj[i].cost<<endl;  
287:                 }  
288:                 cout<<endl;  
289:            }       
290:            for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
291:            {  
292:                 if((*itr).first!="S")  
293:                 {  
294:                      g.dijkastra((*itr).first);  
295:                      for(vmap::iterator itr1=vertexMap.begin();itr1!=vertexMap.end();++itr1)  
296:                      {  
297:                           if((*itr1).first!="S");  
298:                           {  
299:                                d[(*itr).second->hash][(*itr1).second->hash]= (*itr1).second->dist + (*itr1).second->h - (*itr).second->h;  
300:                           }  
301:                      }  
302:                 }  
303:            }  
304:        cout<<endl<<"All pair Shortest Path Matrix is -->"<<endl;  
305:        printf("   A  B  C  D  E");  
306:        for(int i=1;i<n+1;i++)  
307:            {  
308:       cout<<endl;  
309:       if(i==1)  
310:                 cout<<"A";  
311:             if(i==2)  
312:                 cout<<"B";  
313:             if(i==3)  
314:                 cout<<"C";  
315:             if(i==4)  
316:                 cout<<"D";  
317:             if(i==5)  
318:                 cout<<"E";  
319:             if(i==6)  
320:                 cout<<"F";  
321:       for(int j=1;j<n+1;j++)  
322:        {  
323:         printf("%5d",d[i][j]);  
324:        }  
325:            }  
326:       return true;  
327:       }  
328:  }  
329:  int main(int argc, char** argv)  
330:  {  
331:       cout<<"Enter the Graph description in following format:->"<<endl;  
332:       cout<<"Edge_sourceName Edge_destName cost_of_Edge"<<endl;  
333:       cout<<"Enter the detail:-"<<endl;  
334:       int a,cost;  
335:       a=1;  
336:       string sName,dName;  
337:       while(a==1)  
338:       {   
339:        cin>>sName>>dName>>cost;  
340:        g.addEdge(sName,dName,cost);  
341:        g1.addEdge(sName,dName,cost);  
342:        cout<<"Wanna Continue(press 1/0):";  
343:        cin>>a;   
344:    }  
345:    g.jhonson();  
346:    return 0;  
347:  }

Implementation of Dijkastra in C++ Using STL

2010-10-21T07:23:00.001-07:00

1:  //   Dykstra.cpp  
2:  //     
3:  //   Copyright 2010 Ananya <Ananya@Ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <stdio.h>  
21:  #include <limits.h>  
22:  #include <map>  
23:  #include <vector>  
24:  #include <string>  
25:  #include <queue>  
26:  #include <functional>  
27:  using namespace std;  
28:  struct Path;  
29:  struct Vertex;  
30:  struct Edge  
31:  {  
32:                 //First is implicit   
33:       Vertex *dest;    //second vertex of Edge  
34:       double cost;    //Edge cost  
35:       Edge(Vertex *d=0,double c =0.0)  
36:        : dest(d),cost(c) {}  
37:  };  
38:  struct Vertex  
39:  {  
40:       string name;    //Vertex name   
41:       vector<Edge> adj;  //Adjacent vertices (and cost)  
42:       double dist;    //cost  
43:       Vertex *prev;    //Previoius vertex on shortest path   
44:    int scratch;    //Extra variable used in algorithm  
45:    Vertex(const string & nm):name(nm)  
46:      {reset();}  
47:    void reset()  
48:     {  
49:             dist=3000000;  
50:             prev=0;  
51:             scratch=0;  
52:        }  
53:  };  
54:  struct Path  
55:  {  
56:       Vertex *dest;  
57:       double cost;  
58:       Path(Vertex *d=0 ,double c=0)  
59:        : dest(d),cost(c){}  
60:       bool operator>(const Path &rhs) const  
61:       {return (cost > rhs.cost);}  
62:       bool operator<(const Path &rhs) const  
63:       {return (cost < rhs.cost);}  
64:  };  
65:  class Graph  
66:  {  
67:       public:  
68:         Graph(){};  
69:        ~Graph();  
70:         void addEdge(const string & sourceName,const string & destName,double cost);  
71:         void printPath(const string & destName) const;  
72:         void dijkastra(const string & startName);  
73:         void printDijkastra();  
74:    private:  
75:      Vertex * getVertex(const string & vertexName);  
76:      void printPath(const Vertex & dest) const;  
77:      void clearAll();  
78:      typedef map<string,Vertex *,less<string> > vmap;  
79:      /*Graph( const Graph & rhs) {}  
80:      const Graph & operator= ( const Graph & rhs)  
81:      {return *this;}*/   
82:      vmap vertexMap;     
83:  };  
84:  //Destructor :clean up the Vertex Object  
85:  Graph::~Graph()  
86:  {  
87:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
88:           delete (*itr).second;  
89:  }  
90:  //If vertexName is not present ,add it to the vertexMap  
91:  //return a pointer to the vertex .  
92:  Vertex * Graph::getVertex(const string & vertexName)  
93:  {  
94:       vmap::iterator itr= vertexMap.find(vertexName);  
95:       if(itr==vertexMap.end())  
96:       {  
97:            Vertex *newv=new Vertex(vertexName);  
98:            vertexMap[vertexName]=newv;  
99:            return newv;  
100:       }  
101:       return (*itr).second;  
102:  }  
103:  //Add a new edge to the graph  
104:  void Graph::addEdge(const string & sourceName,  
105:            const string & destName,double cost)  
106:  {  
107:       Vertex * v =getVertex(sourceName);  
108:       Vertex * w =getVertex(destName);  
109:       v->adj.push_back(Edge(w,cost));  
110:  }  
111:  //Initialize the vertex output prior to running dijkastra  
112:  //Initialize  
113:  void Graph::clearAll()  
114:  {  
115:       for(vmap::iterator itr= vertexMap.begin();  
116:         itr!=vertexMap.end();++itr)  
117:         (*itr).second->reset();  
118:  }  
119:  //Recursive algo to print shortest path to dest after Dijkastra  
120:  void Graph::printPath(const Vertex & dest) const  
121:  {  
122:       if(dest.prev !=0)  
123:       {  
124:            printPath(*dest.prev);  
125:            cout<<" --> ";  
126:       }  
127:       cout<<dest.name;  
128:  }  
129:  //algo to print the cost if node is reachable else print not rechable  
130:  void Graph::printPath(const string & destName) const  
131:  {  
132:       vmap::const_iterator itr= vertexMap.find(destName);  
133:       if(itr==vertexMap.end())  
134:       {  
135:            cout<<"Destination not found "<<endl;  
136:            return ;  
137:       }       
138:       const Vertex & w =*(*itr).second;  
139:       if(w.dist==3000000)  
140:         cout<<destName<<" not reachable "<<endl;  
141:       else  
142:       {  
143:            cout<<"(Cost is: "<< w.dist << ")";  
144:            printPath(w);  
145:       }  
146:       cout<<endl;  
147:  }  
148:  void Graph::printDijkastra()  
149:  {  
150:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
151:        {  
152:            cout<<(*itr).first;  
153:            printPath((*itr).first);  
154:        }  
155:  }  
156:  void Graph::dijkastra(const string & startName)  
157:  {  
158:       priority_queue< Path,vector<Path>,greater<Path> > pq;  
159:       Path vrec;  
160:       vmap::iterator itr=vertexMap.find(startName);  
161:       if(itr==vertexMap.end())  
162:         {  
163:          cout<<"Specified node not found in graph"<<endl;  
164:          return ;  
165:         }  
166:       clearAll();  
167:       Vertex *start= (*itr).second;  
168:       pq.push(Path(start,0));  
169:       start->dist=0;  
170:       unsigned int nodesSeen=0;  
171:       for(;nodesSeen<vertexMap.size();nodesSeen++)  
172:       {  
173:            do  
174:            {  
175:                 if(pq.empty())  
176:                   return;  
177:                 vrec=pq.top();  
178:                 pq.pop();  
179:            }while(vrec.dest->scratch!=0);  
180:            Vertex *v =vrec.dest;  
181:            v->scratch=1;  
182:            for(unsigned int i=0;i<v->adj.size();i++)  
183:            {  
184:                 Edge e=v->adj[i];  
185:                 Vertex *w=e.dest;  
186:                 double cvw=e.cost;  
187:                 if(cvw<0)  
188:                 {  
189:                  cout<<"Negative Weight Edge seen"<<endl;  
190:                  return;  
191:                  }  
192:                  if(w->dist>v->dist+cvw)  
193:                  {  
194:                       w->dist=v->dist+cvw;  
195:                       w->prev=v;  
196:                       pq.push(Path(w,w->dist));  
197:                 }  
198:             }  
199:        }  
200:  }  
201:  int main(int argc, char** argv)  
202:  {  
203:       Graph g;  
204:       cout<<"Enter the Graph description in following format:->"<<endl;  
205:       cout<<"sourceName destName cost_of_Edge"<<endl;  
206:       cout<<"Enter the detail"<<endl;  
207:       int a,cost;  
208:       a=1;  
209:       string sName,dName;  
210:       while(a==1)  
211:       {   
212:        cin>>sName>>dName>>cost;  
213:        if(cost<0)  
214:             cout<<"Pls enter Non-Negative Edge wieght for Dijkastra"<<endl;  
215:        else  
216:             g.addEdge(sName,dName,cost);  
217:        cout<<"Wanna Continue(press 1/0):";  
218:        cin>>a;   
219:    }  
220:    cout<<"Enter the source node:";  
221:    cin>>sName;  
222:    g.dijkastra(sName);  
223:    cout<<"Shortest path to Distinct nodes are :-->"<<endl;  
224:    g.printDijkastra();  
225:    return 0;  
226:  }

For more info goto : http://securityresearch.in/beta/

Implementation of Directed Acyclic Graph(DAG) in C++ using STL

2010-10-21T07:17:00.000-07:00

1:  //   DAG.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <stdio.h>  
21:  #include <limits.h>  
22:  #include <map>  
23:  #include <vector>  
24:  #include <string>  
25:  #include <list>  
26:  #include <functional>  
27:  using namespace std;  
28:  struct Vertex;  
29:  struct Edge  
30:  {  
31:       Vertex *dest;  
32:       double cost;  
33:       Edge(Vertex *d=0,double c=0.0)  
34:        : dest(d),cost(c){}  
35:  };  
36:  struct Vertex  
37:  {   
38:       string name;  
39:       vector<Edge> adj;  
40:       double dist;  
41:       Vertex *prev;  
42:       unsigned int scratch;  
43:       Vertex(const string &nam):name(nam)  
44:       {reset();}  
45:       void reset()  
46:       {  
47:            dist=3000000;  
48:            prev=0;  
49:            scratch=0;  
50:    }       
51:  };  
52:  class Graph  
53:  {  
54:       public:  
55:            Graph(){};  
56:         ~Graph();  
57:         void addEdge(const string & sourceName,const string & destName,double cost);  
58:         void printPath(const string & destName) const;  
59:         bool dag(const string & startName);  
60:         void printdag();  
61:       private:  
62:         Vertex * getVertex(const string & vertexName);  
63:         void printPath(const Vertex & dest) const;  
64:         void clearAll();  
65:         typedef map<string,Vertex *,less<string> > vmap;  
66:         vmap vertexMap;  
67:  };  
68:  Graph::~Graph()  
69:  {  
70:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
71:            delete (*itr).second;  
72:  }  
73:  Vertex * Graph::getVertex(const string & vertexName)  
74:  {  
75:       vmap::iterator itr=vertexMap.find(vertexName);  
76:       if(itr==vertexMap.end())  
77:       {  
78:            Vertex *newv=new Vertex(vertexName);  
79:            vertexMap[vertexName]=newv;  
80:            return newv;  
81:       }  
82:       return (*itr).second;  
83:  }  
84:  void Graph::addEdge(const string & sourceName,  
85:            const string & destName,double cost)  
86:  {  
87:       Vertex *v=getVertex(sourceName);  
88:       Vertex *w=getVertex(destName);  
89:       v->adj.push_back(Edge(w,cost));  
90:  }  
91:  void Graph::clearAll()  
92:  {  
93:       for(vmap::iterator itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
94:            (*itr).second->reset();  
95:  }  
96:  void Graph::printPath(const Vertex & dest) const  
97:  {  
98:       if(dest.prev!=0)  
99:       {  
100:            printPath(*dest.prev);  
101:            cout<<" -->";  
102:       }  
103:       cout<<dest.name;  
104:  }  
105:  void Graph::printPath(const string &destName) const  
106:  {  
107:       vmap::const_iterator itr=vertexMap.find(destName);  
108:       if(itr==vertexMap.end())  
109:       {  
110:            cout<<destName<<" not Found in Graph"<<endl;  
111:            return;  
112:       }  
113:       Vertex & w =*(*itr).second;  
114:       if(w.dist==3000000)  
115:            cout<<destName<<" is not rechable"<<endl;  
116:       else  
117:       {  
118:            cout<<"(Cost is: "<<w.dist<< ")";  
119:            printPath(w);  
120:       }  
121:       cout<<endl;  
122:  }  
123:  void Graph::printdag()  
124:  {  
125:       for(vmap::iterator itr =vertexMap.begin();itr!=vertexMap.end();++itr)  
126:        {  
127:            cout<<(*itr).first;  
128:            printPath((*itr).first);  
129:        }  
130:  }  
131:  bool Graph::dag(const string & startName)  
132:  {  
133:       vmap::iterator itr=vertexMap.find(startName);  
134:       if(itr==vertexMap.end())  
135:       {  
136:            cout<<"Vertex not found"<<endl;  
137:            return false;  
138:    }  
139:    clearAll();  
140:    Vertex *start=(*itr).second;  
141:    start->dist=0;  
142:    list<Vertex *> q;  
143:    for(itr=vertexMap.begin();itr!=vertexMap.end();++itr)  //Computation of
144:    {                                                       //Indegree of each vertices
145:            Vertex *v =(*itr).second;                      // from line no.143 to 150
146:            for(unsigned int i=0;i<v->adj.size();i++)  
147:            {  
148:                 v->adj[i].dest->scratch++;  
149:            }  
150:       }  
151:       for(itr=vertexMap.begin();itr!=vertexMap.end();++itr)  
152:       {  
153:            Vertex *v=(*itr).second;                 //Pushing the vertices in queue
154:            if(v->scratch==0) 
155:            {                                       //Vertices wid indegree 0 are pushed 1st
156:                 q.push_back(v);  
157:            }  
158:       }  
159:       unsigned int y;  
160:       for(y=0;!q.empty();y++)  
161:       {  
162:            Vertex *v=q.front();                
163:            q.pop_front();  
164:            for(unsigned int i =0;i<v->adj.size();i++)  
165:            {  
166:                 Edge e=v->adj[i];  
167:                 Vertex *w=e.dest;  
168:                 double cvw=e.cost;  
169:                 if(--w->scratch==0)  
170:                      q.push_back(w);          
171:                 if(v->dist==3000000)  
172:                      continue;  
173:                 if(w->dist>v->dist+cvw)  
174:                 {  
175:                      w->dist=v->dist+cvw;  
176:                      w->prev=v;  
177:                 }  
178:            }  
179:       }  
180:       if(y!=vertexMap.size())  
181:            {  
182:                 cout<<"Cycle is there in the graph"<<endl;  
183:                 return false;  
184:            }  
185:       else  
186:              return true;  
187:  }            
188:  int main(int argc, char** argv)  
189:  {  
190:       Graph g;  
191:       cout<<"Enter the Graph description in following format:->"<<endl;  
192:       cout<<"sourceName destName cost_of_Edge"<<endl;  
193:       cout<<"Enter the detail"<<endl;  
194:       int a,cost;  
195:       a=1;  
196:       string sName,dName;  
197:       while(a==1)  
198:       {   
199:        cin>>sName>>dName>>cost;  
200:        g.addEdge(sName,dName,cost);  
201:        cout<<"Wanna Continue(press 1/0):";  
202:        cin>>a;   
203:    }  
204:    cout<<"Enter the source node:";  
205:    cin>>sName;  
206:    bool flag;  
207:    flag=g.dag(sName);  
208:    if(flag==true)  
209:    {  
210:       cout<<"Shortest path to Distinct nodes are :-->"<<endl;  
211:       g.printdag();  
212:       return 0;  
213:    }  
214:    else   
215:       return 0;  
216:  }

Politics Explained

2010-09-23T09:36:00.001-07:00

During final semester of my engineering one of my friend was quite impressed with COMMUNISM. I think right now he is drowning a considerable amount of effort for achieving communism in the society.He use to give us fair idea about current political system and social values.Initially i thought all of them as bull shit ,but gradually as time passed i started taking interest in different political system defined due date by intellectual human being or whatsoever is/was followed anywhere in world.

Few of them i am going to quote in this article in simple generic sense :--

FEUDALISM: You have two cows. Your lord takes some of the milk.

PURE SOCIALISM: You have two cows. The government takes them and puts them in a barn with everyone else's cows. You have to take care of all of the cows. The government gives you as much milk as you need.
BUREAUCRATIC SOCIALISM: You have two cows. The government takes them and put them in a barn with everyone else's cows. They are cared for by ex-chicken farmers. You have to take care of the chickens the government took from the chicken farmers. The government gives you as much milk and eggs as the regulations say you need.
FASCISM: You have two cows. The government takes both, hires you to take care of them and sells you the milk.
PURE COMMUNISM: You have two cows. Your neighbors help you take care of them, and you all share the milk.
RUSSIAN COMMUNISM: You have two cows. You have to take care of them, but the government takes all the milk.
CAMBODIAN COMMUNISM: You have two cows. The government takes both of them and shoots you.
DICTATORSHIP: You have two cows. The government takes both and drafts you.
PURE DEMOCRACY: You have two cows. Your neighbors decide who gets the milk.
REPRESENTATIVE DEMOCRACY: You have two cows. Your neighbors pick someone to tell you who gets the milk.
BUREAUCRACY: You have two cows. At first the government regulates what you can feed them and when you can milk them. Then it pays you not to milk them. Then it takes both, shoots one, milks the other and pours the milk down the drain. Then it requires you to fill out forms accounting for the missing cows.
PURE ANARCHY: You have two cows. Either you sell the milk at a fair price or your neighbors try to take the cows and kill you.
LIBERTARIAN/ANARCHO-CAPITALISM: You have two cows. You sell one and buy a bull.
SURREALISM: You have two giraffes. The government requires you to take harmonica lessons.

------------होप-------- रेअदेरस------- विल------ एन्जॉय-----------

How to Read Mathematics contd..

2010-09-11T10:50:00.000-07:00

An Example of Mathematical Writing

To allow an opportunity to experiment with the guidelines presented here, I am including a small piece of mathematics often called the birthday paradox. The first part is a concise mathematical article explaining the problem and solving it. The second is an imaginary Reader's attempt to understand the article by using the appropriate reading protocol. This article’s topic is probability and is accessible to a bright and motivated reader with no background at all.

The Birthday Paradox

A professor in a class of 30 random students offers to bet that there are at least two people in the class with the same birthday (month and day, but not necessarily year). Do you accept the bet? What if there were fewer people in the class? Would you bet then?

Assume that the birthdays of n people are uniformly distributed among 365 days of the year (assume no leap years for simplicity). We prove that, the probability that at least two of them have the same birthday (month and day) is equal to:

What is the chance that among 30 random people in a room, there are at least two or more with the same birthday? For n = 30, the probability of at least one matching birthday is about 71%. This means that with 30 people in your class, the professor should win the bet 71 times out of 100 in the long run. It turns out that with 23 people, she should win about 50% of the time.
Here is the proof: Let P(n) be the probability in question. Let Q(n) = 1 – P(n) be the probability that no two people have a common birthday. Now calculate Q(n) by calculating the number of n birthdays without any duplicates and divide by the total number of n possible birthdays. Then solve for P(n).
The total number of n birthdays without duplicates is:

365 × 364 × 363 × ... × (365 – n + 1)

This is because there are 365 choices for the first birthday, 364 for the next and so on for n birthdays. The total number of n birthdays without any restriction is just 365ⁿ because there are 365 choices for each of n birthdays. Therefore, Q(n) equals

Solving for P(n) gives P(n) = 1 – Q(n) and hence our result.

Reader Attempts to Understand the Birthday Paradox

In this section, a naive Reader tries to make sense out of the last few paragraphs. The Reader’s part is a metaphor for the Reader thinking out loud, and the Professional’s comments represent research on the Reader’s part. The appropriate protocols are centered and bold at various points in the narrative.
My Reader may seem to catch on to things relatively quickly. However, be assured that in reality a great deal of time passes between each of my Reader’s comments, and that I have left out many of the Reader’s remarks that explore dead-end ideas. To experience what the Reader experiences requires much more than just reading through his/her lines. Think of his/her part as an outline for your own efforts.

Know urself

Reader (R): I don’t know anything about probability, can I still make it through?
Professional (P): Let’s give it a try. We may have to backtrack a lot at each step.
R: What does the phrase “30 random students” mean?

"When I use a word, it means just what I choose it to mean"

P: Good question. It doesn’t mean that we have 30 spacy or scatter-brained people. It means we should assume that the birthdays of these 30 people are independent of one another and that every birthday is equally likely for each person. The author writes this more technically a little further on: “Assume that the birthdays of n people are uniformly distributed among 365 days of the year.”
R: Isn't that obvious? Why bother saying that?
P: Yes the assumption is kind of obvious. The author is just setting the groundwork. The sentence guarantees that everything is normal and the solution does not involve some imaginitive fanciful science-fiction.
R: What do you mean?
P: For example, the author is not looking for a solution like this: everyone lives in Independence Land and is born on the 4^th of July, so the chance of two or more people with the same birthday is 100%. That is not the kind of solution mathematicians enjoy. Incidentally, the assumption also implies that we do not count leap years. In particular, nobody in this problem is born on February 29. Continue reading.
R: I don’t understand that long formula, what’s n?
P: The author is solving the problem for any number of people, not just for 30. The author, from now on, is going to call the number of people n.
R: I still don't get it. So what's the answer?

Don't Be a Passive Reader - Try Some Examples

P: Well, if you want the answer for 30, just set n = 30.
R: Ok, but that looks complicated to compute. Where’s my calculator? Let’s see: 365 × 364 × 363 × ... × 336. That’s tedious, and the final exact value won’t even fit on my calculator. It reads:

2.1710301835085570660575334772481e+76

If I can’t even calculate the answer once I know the formula, how can I possibly understand where the formula comes from?
P: You are right that this answer is inexact, but if you actually go on and do the division, your answer won’t be too far off.
R: The whole thing makes me uncomfortable. I would prefer to be able to calculate it more exactly. Is there another way to do the calculation?
P: How many terms in your product? How many terms in the product on the bottom?
R: You mean 365 is the first term and 364 is the second? Then there are 30 terms. There are also 30 terms on the bottom, (30 copies of 365).
P: Can you calculate the answer now?
R: Oh, I see. I can pair up each top term with each bottom term, and do 365/365 as the first term, then multiply by 364/365, and so on for 30 terms. This way the product never gets too big for my calculator. (After a few minutes)... Okay, I got 0.29368, rounded to 5 places.
P: What does this number mean?

Don't Miss the Big Picture

R: I forgot what I was doing. Let’s see. I was calculating the answer for n = 30. The 0.29368 is everything except for subtracting from 1. If I keep going I get 0.70632. Now what does that mean?
P: Knowing more about probability would help, but this simply means that the chance that two or more out of the 30 people have the same birthday is 70,632 out of 100,000 or about 71%.
R: That’s interesting. I wouldn’t have guessed that. You mean that in my class with 30 students, there’s a pretty good chance that at least two students have the same birthday?
P: Yes that’s right. You might want to take bets before you ask everyone their birthday. Many people don’t think that a duplicate will occur. That’s why some authors call this the birthday paradox.
R: So that’s why I should read mathematics, to make a few extra bucks?
P: I see how that might give you some incentive, but I hope the mathematics also inspires you without the monetary prospects.
R: I wonder what the answer is for other values of n. I will try some more calculations.
P: That’s a good idea. We can even make a picture out of all your calculations. We could plot a graph of the number of people versus the chance that a duplicate birthday occurs, but maybe this can be left for another time.
R: Oh look, the author did some calculations for me. He says that for n = 30 the answer is about 71%; that’s what I calculated too. And, for n = 23 it’s about 50%. Does that make sense? I guess it does. The more people there are, the greater the chance of a common birthday. Hey, I am anticipating the author. Pretty good. Okay, let’s go on.
P: Good, now you’re telling me when to continue.

Don’t Read Too Fast

R: It seems that we are up to the proof. This must explain why that formula works. What’s this Q(n)? I guess that P stands for probability but what does Q stand for?
P: The author is defining something new. He is using Q just because it’s the next letter after P, but Q(n) is also a probability, and closely related to P(n). It’s time to take a minute to think. What is Q(n) and why is it equal to 1 – P(n)?
R: Q(n) is the probability that no two people have the same birthday. Why does the author care about that? Don’t we want the probability that at least two have the same birthday?
P: Good point. The author doesn’t tell you this explicitly, but between the lines, you can infer that he has no clue how to calculate P(n) directly. Instead, he introduces Q(n) which supposedly equals 1 – P(n). Presumably, the author will proceed next to tell us how to compute Q(n). By the way, when you finish this article, you may want to deal with the problem of calculating P(n) directly. That’s a perfect follow up to the ideas presented here.
R: First things first.
P: Ok. So once we know Q(n), then what?
R: Then we can get P(n). Because if Q(n) = 1 – P(n), then P(n) = 1 – Q(n). Fine, but why is Q(n) = 1 – P(n)? Does the author assume this is obvious?
P: Yes, he does, but what’s worse, he doesn’t even tell us that it is obvious. Here’s a rule of thumb: when an author says clearly this is true or this is obvious, then take 15 minutes to convince yourself it is true. If an author doesn’t even bother to say this, but just implies it, take a little longer.
R: How will I know when I should stop and think?
P: Just be honest with yourself. When in doubt, stop and think. When too tired, go watch television.
R: So why is Q(n) = 1 – P(n)?
P: Let’s imagine a special case. If the chance of getting two or more of the same birthdays is 1/3, then what's the chance of not getting two or more?
R: It’s 2/3, because the chance of something not happening is the opposite of the chance of it happening.

Make the Idea Your Own

P: Well, you should be careful when you say things like opposite, but you are right. In fact, you have discovered one of the first rules taught in a course on probability. Namely, that the probability that something will not occur is 1 minus the probability that it will occur. Now go on to the next paragraph.
R: It seems to be explaining why Q(n) is equal to long complex-looking formula shown. I will never understand this.
P: The formula for Q(n) is tough to understand and the author is counting on your diligence, persistence, and/or background here to get you through.
R: He seems to be counting all possibilities of something and dividing by the total possibilities, whatever that means. I have no idea why.
P: Maybe I can fill you in here on some background before you try to check out any more details. The probability of the occurrence of a particular type of outcome is defined in mathematics to be: the total number of possible ways that type of outcome can occur divided by the total number of possible outcomes. For example, the probability that you throw a four when throwing a die is 1/6. Because there is one possible 4, and there are six possible outcomes. What's the probability you throw a four or a three?
R: Well I guess 2/6 (or 1/3) because the total number of outcomes is still six but I have two possible outcomes that work.
P: Good. Here’s a harder example. What about the chance of throwing a sum of four when you roll two dice? There are three ways to get a four (1-3, 2-2, 3-1) while the total number of possible outcomes is 36. That is 3/36 or 1/12. Look at the following 6 by 6 table and convince yourself.

1-1, 1-2, 1-3, 1-4, 1-5, 1-6

2-1, 2-2, 2-3, 2-4, 2-5, 2-6

3-1, 3-2, 3-3, 3-4, 3-5, 3-6

4-1, 4-2, 4-3, 4-4, 4-5, 4-6

5-1, 5-2, 5-3, 5-4, 5-5, 5-6

6-1, 6-2, 6-3, 6-4, 6-5, 6-6

What about the probability of throwing a 7?
R: Wait. What does 1-1 mean? Doesn’t that equal 0?
P: Sorry, my bad. I was using the minus sign as a dash, just to mean a pair of numbers, so 1-1 means a roll of one on each die - snake eyes.
R: Couldn’t you have come up with a better notation?
P: Well maybe I could/should have, but commas would look worse, a slash would look like division, and anything else might be just as confusing. We aren’t going to publish this transcript anyway.
R: That’s a relief. Well, I know what you mean now. To answer your question, I can get a seven in six ways via 1-6, 2-5, 3-4, 4-3, 5-2, or 6-1. The total number of outcomes is still 36, so I get 6/36 or 1/6. That’s weird, why isn’t the chance of rolling a 4 the same as for rolling a 7?
P: Because not every sum is equally likely. The situation would be very different if we were simply spinning a wheel with the sums 2 through 12 listed in equally spaced intervals. In that case, each one of the 11 sums would have probability 1/11.
R: Okay, now I am an expert. Is probability just about counting?
P: Sometimes, yes. But counting things is not always so easy.
R: I see, let’s go on. By the way, did the author really expect me to know all this? My friend took Probability and Statistics and I am not sure he knows all this stuff.
P: There’s a lot of information implied in a small bit of mathematics. Yes, the author expected you to know all this, or to discover it yourself just as we have done. If I hadn’t been here, you would have had to ask yourself these questions and answer them by thinking, looking in a reference book, or consulting a friend.
R: So the chance that there are no two people with the same birthday is the number of possible sets of n birthdays without a duplicate divided by the total number of possible sets of n birthdays.
P: Excellent summary.
R: I don’t like using n, so let me use 30. Perhaps the generalization to n will be easy to see.
P: Great idea. It is often helpful to look at a special case before understanding the general case.
R: So how many sets of 30 birthdays are there total? I can’t do it. I guess I need to restrict my view even more. Let’s pretend there are only two people.
P: Fine. Now you’re thinking like a mathematician. Let’s try n = 2. How many sets of two birthdays are there total?
R: I number the birthdays from 1 to 365 and forget about leap years. Then these are the all the possibilities:

1-1, 1-2, 1-3, ... , 1-365,

2-1, 2-2, 2-3, ... , 2-365,

...

365-1, 365-2, 365-3, ... , 365-365.

P: When you write 1-1, do you mean 1-1 = 0, as in subtraction?
R: Stop teasing me. You know exactly what I mean.
P: Yes I do, and nice choice of notation I might add. Now how many pairs of birthdays are there?
R: There are 365 × 365 total possibilities for two people.
P: And how many are there when there are no duplicate birthdays?
R: I can’t use 1-1, or 2-2, or 3-3 or ... 365-365, so I get

1-2, 1-3, ... , 1-365,

2-1, 2-3, ... , 2-365,

...

365-1, 365-2, ... , 365-364

The total number here is 365 × 364 since each row now has 364 pairs instead of 365.
P: Good. You are going a little quickly here, but you’re 100% right. Can you generalize now to 30? What is the total number of possible sets of 30 birthdays? Take a guess. You’re getting good at this.
R: Well if I had to guess, (it’s not really a guess, after all, I already know the formula), I would say that for 30 people you get 365 × 365 ×... × 365, 30 times, for the total number of possible sets of birthdays.
P: Exactly. Mathematicians write 365³⁰. And what is the number of possible sets of 30 birthdays without any duplicates?
R: I know the answer should be 365 × 364 × 363 × 362 × ... × 336, (that is, start at 365 and multiply by one less for 30 times), but I am not sure I really see why this is true. Perhaps I should do the case with three people first, and work my way up to 30?
P: Splendid idea. Let’s quit for today. The whole picture is there for you. When you are rested and you have more time, you can come back and fill in that last bit of understanding.
R: Thanks a lot; it’s been an experience. Later.

How to Read Mathematics

2010-09-10T03:37:00.000-07:00

"Mathematics is “a language that can neither be read nor understood without initiation.”

A reading protocol is a set of strategies that a reader must use in order to benefit fully from reading the text. Poetry calls for a different set of strategies than fiction, and fiction a different set than non-fiction. It would be ridiculous to read fiction and ask oneself what is the author's source for the assertion that the hero is blond and tanned; it would be wrong to read non-fiction and not ask such a question. This reading protocol extends to a viewing or listening protocol in art and music. Indeed, much of the introductory course material in literature, music and art is spent teaching these protocols.

Mathematics has a reading protocol all its own, and just as we learn to read literature, we should learn to read mathematics. Students need to learn how to read mathematics, in the same way they learn how to read a novel or a poem, listen to music, or view a painting. Ed Rothstein’s book, Emblems of Mind, a fascinating book emphasizing the relationship between mathematics and music, touches implicitly on the reading protocols for mathematics.

When we read a novel we become absorbed in the plot and characters. We try to follow the various plot lines and how each affects the development of the characters. We make sure that the characters become real people to us, both those we admire and those we despise. We do not stop at every word, but imagine the words as brushstrokes in a painting. Even if we are not familiar with a particular word, we can still see the whole picture. We rarely stop to think about individual phrases and sentences. Instead, we let the novel sweep us along with its flow and carry us swiftly to the end. The experience is rewarding, relaxing and thought provoking.

Mathematical ideas are by nature precise and well defined, so that a precise description is possible in a very short space. Both a mathematics article and a novel are telling a story and developing complex ideas, but a math article does the job with a tiny fraction of the words and symbols of those used in a novel. The beauty in a novel is in the aesthetic way it uses language to evoke emotions and present themes which defy precise definition. The beauty in a mathematics article is in the elegant efficient way it concisely describes precise ideas of great complexity.

What are the common mistakes people make in trying to read mathematics? How can these mistakes be corrected?

“Reading Mathematics is not at all a linear experience ...Understanding the text requires cross references, scanning, pausing and revisiting”

Don’t be a Passive Reader

“A three-line proof of a subtle theorem is the distillation of years of activity. Reading mathematics… involves a return to the thinking that went into the writing”

Mathematics says a lot with a little. The reader must participate. At every stage, he/she must decide whether or not the idea being presented is clear. Ask yourself these questions:

Why is this idea true?
Do I really believe it?
Could I convince someone else that it is true?
Why didn't the author use a different argument?
Do I have a better argument or method of explaining the idea?
Why didn't the author explain it the way that I understand it?
Is my way wrong?
Do I really get the idea?
Am I missing some subtlety?
Did this author miss a subtlety?
If I can't understand the point, perhaps I can understand a similar but simpler idea?
Which simpler idea?
Is it really necessary to understand this idea?
Can I accept this point without understanding the details of why it is true?
Will my understanding of the whole story suffer from not understanding why the point is true?

Putting too little effort into this participation is like reading a novel without concentrating. After half an hour, you wake up to realize the pages have turned, but you have been daydreaming and don’t remember a thing you read.

Don’t Read Too Fast

Make the Idea your Own

An Example of Mathematical Writing

---example will be presented in the next article
--Shai Simpson