tag:blogger.com,1999:blog-45121212686928915742024-03-14T09:27:28.633+05:30FuzzyNothing is absolute.Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-4512121268692891574.post-3900937252575464232015-02-20T12:25:00.000+05:302015-02-20T12:32:50.460+05:30Connect to Oracle database through Unix<div dir="ltr" style="text-align: left;" trbidi="on">
Due to my professional requirements nowadays I use Oracle most of the time and sometimes I need to use Oracle through Linux environment. Today I am going to discuss the basics of connecting to Oracle database through Linux. For this purpose Oracle provided us a pretty cool utility with a basic command line interface. Yes, <a href="http://en.wikipedia.org/wiki/SQL*Plus" target="_blank">SQL*Plus</a> is the utility I am talking about.<br />
<br />
<a name='more'></a><br />
<br />
Now one disclaimer, I have tested all the below in Redhat Linux environment only.<br />
<b>Connection to Database:</b><br />
First you need to connect to the database. Use the <b>sqlplus</b> command to connect.<br />
<br />
<pre><b>sqlplus <USER_NAME>/<PASSWORD>@<SERVICE_NAME></b></pre>
<b>
</b>Now Let your USER_NAME, PASSWORD and SERVICE_NAME is "U1UATSBRPK", "xzy321" and "ODSRUAT" respectively. So you will use like :<br />
<br />
<pre><b>sqlplus U1UATSBRPK/xzy321@ODSRUAT</b></pre>
<pre>after you are connected successfully you will probably get a screen like this:</pre>
<pre></pre>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-U-jWROnge3E/VObZW1N5P1I/AAAAAAAAAd0/pU8nE0SmGso/s1600/Capture.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-U-jWROnge3E/VObZW1N5P1I/AAAAAAAAAd0/pU8nE0SmGso/s1600/Capture.JPG" height="137" width="400" /></a></div>
<b>Formatting the output:</b><br />
Now you are connected to database, so you can type your SQL queries and get the result. Ok , lets get data from a table.<br />
<blockquote class="tr_bq">
SELECT * FROM TEST_TEMP;</blockquote>
wait a minute, what are these garbage on the screen. Nope they are not garbage, its the output of your query only in non-formatted form. You need to format the output. So you first run below commands:<br />
<br />
<blockquote class="tr_bq">
set wrap off;<br />
set linesixe 3000;</blockquote>
But beware, your output may get truncated now, if it doesn't fit on the specified line size.<br />
I am not going in details for formatting , so you can have a look <a href="http://stackoverflow.com/questions/188118/how-do-i-format-my-oracle-queries-so-the-columns-dont-wrap" target="_blank">here </a>and <a href="http://stackoverflow.com/questions/5771573/ugly-formatting-in-sqlplus" target="_blank">here</a>.<br />
<br />
<b>Connection through bash script:</b><br />
Most of the times you will need to connect to the database through bash script. Just place all the commands you used to connect to the database from a terminal in the script. Have a look in the below script:<br />
<br />
<br />
<blockquote class="tr_bq">
sqlplus U1UATSBRPK/xzy321@ODSRUAT << END<br />
<blockquote>
WHENEVER SQLERROR EXIT SQL.SQLCODE<br />
set wrap off<br />
set linesize 3000<br />
SELECT * FROM TEST_TEMP;<br />
DESC TEST_TEMP; </blockquote>
</blockquote>
<blockquote class="tr_bq">
END</blockquote>
<pre></pre>
<b>Spooling the result:</b><br />
When you are connected to the database, you can no longer use unix command. So how you will store the result of the query you run. For that purpose you can use the concept of spooling a file.<br />
You just define a spool file and start spooling it before execution of any database query. After execution of all the query don't forget to stop the spooling. You can alter the script to accommodate the concept of spooling like this:<br />
<br />
<blockquote class="tr_bq">
touch spool_file.txt<br />
sqlplus U1UATSBRPK/xzy321@ODSRUAT << END<br />
WHENEVER SQLERROR EXIT SQL.SQLCODE<br />
set wrap off<br />
set linesize 3000<br />
spool spool_file.txt<br />
SELECT * FROM TEST_TEMP;<br />
DESC TEST_TEMP;<br />
spool off<br />
END</blockquote>
<b></b><br />
<br />
<b><br /></b>
<b>Keep the screen clear:</b><br />
Whenever you use some query in database through bash script, you will end up with a messy screen with all the result of the queries you made. If you are spooling the results and don't need the query result on the screen you can redirect the output to <a href="http://en.wikipedia.org/wiki/Null_device" target="_blank">/dev/null</a> . You can do this like:<br />
<br />
<blockquote class="tr_bq">
touch spool_file.txt<br />
sqlplus U1UATSBRPK/xzy321@ODSRUAT << END > /dev/null<br />
WHENEVER SQLERROR EXIT SQL.SQLCODE<br />
set wrap off<br />
set linesize 3000<br />
spool spool_file.txt<br />
SELECT * FROM TEST_TEMP;<br />
DESC TEST_TEMP;<br />
spool off<br />
END</blockquote>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-19260040524781995422014-08-13T18:53:00.002+05:302014-08-13T18:53:51.088+05:30No Suitable Title Found..<div dir="ltr" style="text-align: left;" trbidi="on">
Many times I have availed the Cab facility of my office whenever I got late for
project work. But yesterday I got a new idea from some guys traveling with me in
the same cab. In my office when I am availing cab service, its cost is
going to be added on your project cost. <br />
<a name='more'></a><br />
So, if I use cab facility many times
without any reason( i.e without project work) my manager going to poke me
for sure. So no cab if you have no job until 10 pm. In Kolkata branches you can avail Cab
only after 10pm. Another point is that you need to apply
through online portal for Cab service. So any request for cab made by you is
being stored and your manager is also being informed. Now what these guys do is
that they don’t apply for cab service through portal, instead they directly
reaches the boarding point a bit early. Now they requests the transport people
to allocate them to any of the cab as they have forgot to raise a request for
cab. For courtesy transport people also assign them on some cab, overpopulating
the cab. Now you can’t ask transport people that you have forgot to book a cab on a regular basis.
So sometimes they directly boards the cab of their route, without
acknowledgment of transport people. Now obvious question is “why do they do
that??”. Now this is totally mind blowing. They saved Rs. 35 daily. “What the
hell!!!” this must be your first expression, so was mine. Actually this information was given by one f them. He even told
me that they are saving approx. rs. 500/month. Another essential question that I
asked them “don’t you get bored waiting for the cab till 10pm where your office time is upto 6pm?”. Here also they
have some strong logic. They said that they would spend their time on Facebook
if they reaches home early. In office they have facebook and even
air-conditioned environment and even your late night presence going to effect
your rating for sure. So that’s it. New people new idea. These guys shouldn’t
be in technical group , they should be in management. They deserve this. Really
hats off guys.</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-89112761185071969882014-02-10T00:05:00.002+05:302014-02-10T00:05:29.975+05:30Introduction to Quantum Cryptography<div dir="ltr" style="text-align: left;" trbidi="on">
Imagine you want to send some message to your friend and you don't want others to peek on your message. So you lock your message in a box using a key and send the box to your friend and your friend also have a key to unlock the box so he can easily unlock the box and read the message. In general this is the technique used by any cryptographic algorithm. Locking up the message in the box is called Encryption and Unlocking is called Decryption. Before message being sent to the receiver the data is encrypted using an encryption algorithm and a secret key. On the receiver side the encrypted data is decrypted using the reverse encryption algorithm. Classical cryptographic algorithms mostly rely on mathematical approaches to secure key transmission. The security they offer is based upon unproven assumptions and depends on the technology available to an eavesdropper. But rapidly growing parallel technology and Quantum technology may be a threat to these classical cryptography in near future. One of the solutions of these threats is Quantum Cryptography. Now what is Quantum Cryptography? Quantum cryptography is a complex topic because it brings in to play something most people find hard to understand -- quantum mechanics. Now lets focus on some basic quantum physics that we must know to understand this article.<br />
<br />
<a name='more'></a><br /><br />
<span style="color: orange;"><b>Simple Quantum Physics:</b></span><br />
<span style="color: orange;"><b> </b></span>Quantum, in physics is discrete natural unit, or packet of energy, charge, angular momentum, or other physical property. Light for example, appearing in some respect as a continuous electromagnetic wave, but on the submicroscopic level it is emitted and absorbed in discrete amounts or quanta. These particle like packets (quanta) of light are called photons, a term, also applicable to quanta of other forms of electromagnetic energy such as X rays and gamma rays. One speciality about quantum is that they can exist in all of their possible states at once. This also applies for photon. This means that whatever direction a photon can spin in say diagonally, vertically and horizontally, it does all at once. Quantum of lights in this state is called unpolarized photons. This is like someone moving in north, south, east, west, up and down all at the same time. This property is called Superposition. One thing that we should keep in mind is that measuring something that is in its superposition causes it to collapse into a definite state (one of the all possible states) . Superposition can be described well by the following diagram.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-CWxhmprH86E/Uve5ZSf9dDI/AAAAAAAAAZI/PiSkD6KHYK0/s1600/Necker_cube.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-CWxhmprH86E/Uve5ZSf9dDI/AAAAAAAAAZI/PiSkD6KHYK0/s1600/Necker_cube.jpg" /></a></div>
<br />
<br />
<b> </b> Necker Cubes<br />
<br />
Looking at the diagram you can identify one of four possibilities: Either both squares are protruding forward or both backwards or one forward and the other backwards. Each time you look at the diagram only one possibility comes true. In a sense all four options exist together but when you look at the diagram it collapses into just one. This is the essence of quantum superposition. Through the use of polarization filters, we can force the photon to take one of its states or technically polarize it. If we use a vertical polarizing filter some photons will be absorbed and some will emerge on the other side of the filter. Those photons that<br />
aren't absorbed will emerge on the other side with a vertical spin. Thus we can polarize the photons to our required orientation using suitable filters.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-ZPJtBmwz1lQ/Uve59JeSqaI/AAAAAAAAAZQ/SQfr15EuDmw/s1600/Quantum_polarization.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-ZPJtBmwz1lQ/Uve59JeSqaI/AAAAAAAAAZQ/SQfr15EuDmw/s1600/Quantum_polarization.jpeg" height="200" width="400" /></a></div>
Polarizing Photons<br />
<br />
The foundation of quantum physics is the unpredictability factor. This unpredictability is pretty much defined by Heisenberg's Uncertainty Principle.This principle says, Certain pairs of physical properties are related in such a way that measuring one property prevents the observer from knowing the value of the other. But when dealing with photons for encryption Heisenberg's Principle can be used to our advantage. When measuring the polarization of a photon, the choice of what direction to measure affects all subsequent measurements. The thing about photons is that once they are polarized, they can't be accurately measured<br />
again, except by a filter like the one that initially produced their current spin. So if a photon with a vertical spin is measured through a diagonal filter, either the photon won't pass through the filter or the filter will affect the photon's behavior, causing it to take a diagonal spin. In this sense,the information on the photon's original polarization is lost.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-yoI7yaTw-oc/Uve6SAnbLsI/AAAAAAAAAZc/6Mg6xEWiTCU/s1600/Diff_basis.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-yoI7yaTw-oc/Uve6SAnbLsI/AAAAAAAAAZc/6Mg6xEWiTCU/s1600/Diff_basis.jpeg" height="222" width="400" /></a></div>
<br />
Effect of various Basis on polarized photons<br />
<br />
In this diagram we have used wrong basis for the last two cases and we can see that we have changed the polarization of two photons.<br />
<br />
<span style="color: orange;"><b>Quantum Information:</b> </span><br />
<div class="MsoNormal">
The bit is the fundamental concept of classical computation and classical information. Quantum computation and quantum information are built upon an analogous concept, the quantum bit or qbit for short. Just as a classical bit has a state either 0 or 1, a qbit is like a bit but it is in superposition between 0 and 1. Two possible states for a qbit are the states "|0 >" and "|1 >" . This notation is called Dirac notation. A qbit can be fully expressed as: a|0 > +b|1 > with a<sup>2 </sup>+ b<sup>2</sup>= 1. When we measure a qbit we get a 0 with probability a<sup>2</sup> and 1 with b<sup>2</sup> . Now consider a quantum computer with two qbits. There are four possible states : |00 >, |01 >, |10 >, |11 > and its superposition is: a|00>+b|01>+c|10>+d|11> where a<sup>2</sup>, b<sup>2</sup>,c<sup>2</sup>,d<sup>2 </sup>are the probabilities of finding two qbits in any of the four states. In a quantum computer the two bits are in all possible state at a time. So it is possible to add a number to the two bits which means we can add the number to 00,01,10,11 and compute the result at the same time. This ability to operate on all state at a time makes it so powerful. Here number of parallel operations depends on the number of qbits used. If N number of qbits are used then 2<sup>N </sup>operations can be done parallely and this inherently parallelism makes quantum computer so fast. But question is how will we encode a photon as a qbit? We know photon has its own spin along all possible direction. As in certain digital system we consider +5 volts as 1 and 0 volt as 0, we can use spin property of photon to encode photon as a qbit. We can use photon's spin about a particular direction as 1 and spin about other direction as 0 say photon with vertical spin will be considered as 1 and photon with angular spin as 0.</div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-8Hjz_k8Qe2A/Uve7KHiR2MI/AAAAAAAAAZk/A7xdD7EkceQ/s1600/Qbit_representation.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-8Hjz_k8Qe2A/Uve7KHiR2MI/AAAAAAAAAZk/A7xdD7EkceQ/s1600/Qbit_representation.png" height="131" width="640" /></a></div>
<br />
Encoding polarized photon as binary values<br />
<br />
<br />
<span style="color: orange;"><b>Quantum Cryptography:</b></span><br />
<b> </b> Before starting to describe what is quantum cryptography we must know about three names we will use throughout the article. They are Alice, Bob and Eve. Alice is sending the message and Bob is receiving the message and Eve is in between them and trying to intercept their message. What Eve does is somehow collects the secret key of the message and decrypts it. Now if Alice can somehow send the key of the message to Bob without any interception then she can send the message without interception. Here we will discuss the BB84 protocol. It is on the name of the inventors <a href="http://en.wikipedia.org/wiki/Charles_H._Bennett_%28computer_scientist%29" target="_blank">Charles Bennet</a> and <a href="http://en.wikipedia.org/wiki/Gilles_Brassard" target="_blank">Gilles Brassard</a> and it was invented on the year 1984. Quantum Cryptography follows two steps first one is sending the secret key and the second step is sending the message. Here Alice and Bob will make use of two fundamentally different communication channel, a classical channel and a quantum channel. Classical channel is something that we use in internet to transfer data. In classical channel Eve can observe the bit-stream without affecting the data. But quantum channel is something different. It is capable of sending information in terms of quantum and Eve can't observe data without affecting the data. In BB84 protocol secret key is sent through the quantum channel but message is sent through ordinary channel but encrypted by the secret key. The first step is called Quantum Key Distribution(QKD). In this step Alice and Bob uses the quantum channel for communication. First we will consider there is no Eve between Alice and Bob. Let us assume Alice is using two type of polarizer one is diagonal polarizer (X)and Rectilinear polarizer (+). In rectilinear basis a photon with spin "|" (i.e up to down ) is considered as 1 and "-" (i.e left to right) is 0 and in diagonal basis a photon with spin "/" is considered as 1 and "\" is 0. The below diagram will help you to understand the way we will represent photon as binary values:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-YDv5bGzIJIo/Uve7mFXkwOI/AAAAAAAAAZs/l_DWZMSaLRg/s1600/Binary_encoding.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-YDv5bGzIJIo/Uve7mFXkwOI/AAAAAAAAAZs/l_DWZMSaLRg/s1600/Binary_encoding.png" height="336" width="640" /></a></div>
<br />
<br />
Binary encoding of photon in our examples<br />
<br />
<br />
Now Alice have a key and for each bit he will select a random basis (either diagonal or rectilinear in our discussion) to encode the bit to send. Nobody not even Bob knows what basis Alice is using. Bob will receive the encoded qbits and Bob will use random basis to decode the qbits. If he uses the same basis then he will get the exact bit that the Alice sent otherwise there is a 50% chance that he will get a wrong bit. For example if Alice uses diagonal basis to encode 1 and Bob also uses diagonal basis to decode that then he will get a 1, if he uses a rectilinear basis then there is 50% chance that he will get a 1 and 50% chance of<br />
getting 0. As Bob is also using random basis he will use 50% right basis (i.e he will use the basis that Alice used) and will decode 50% qbits exact and for the 50% wrong basis he will decode 25% of qbits exact, that means Bob will decode 75% qbits exact. Now Alice and Bob will exchange their basis they used for each bit using normal channel without revealing their bits. Now they can check for which bits they both used the same basis and those bits will be used as the secret key. Consider the below example where Alice is sending the secret key 100101.<br />
<br />
<pre>+---------------+---------------------+---------------------------+
| | Alice | Bob |
+---------------+---------------------+---------------------------+
| Basis used | +,X,+,+,X,X |+,+,+,X,+,X |
+---------------+---------------------+---------------------------+
</pre>
In this case Bob will decode the key as 1,0/1,0,0/1,0/1,1. As Bob have used some wrong basis to measure the qbits, he may get a 0 or 1 randomly on those cases. Then they will exchange their basis with others and they will find that in position 2,4,5 Bob have used wrong basis. So they will use the rest bit (1st,3rd,6th bit) string as secret key i.e 101. Rest part is simple just encrypt the message using that key and send it, that's it. Now the situation gets critical when Eve's comes into action. As we connect using public channel then it is quite possible that Eve will intercept our communication. In this case as previous case Alice encodes the bit information using any of its basis and sends it to Bob but Eve intercepts the qbits. Like Bob, Eve also has decoder of the qbit. But even Eve also doesn't know the basis Alice is using, so like Bob he also randomly use basis to decode the qbits. There is 50% chance that Eve will use right basis and 50% wrong basis. For the right 50%, photon's spin's direction will not be affected but for the wrong 50%, spin direction of photons will be changed. For the 50% qbits for which Eve used right basis Bob will use 25% right basis and 25% wrong basis and for the right 25% qbits he will get 25% right qbit and for the wrong 25% basis Bob used he will get 12.5% qbits correct just by probability, that means from the first 50% for which Eve used right basis Bob will get 37.5% right qbits. For the rest 50% again Bob will use 25%right and 25% wrong basis. From this Bob will get 12.5% and 12.5% both just by probability that means he will get 25% right qbits. So when Eve is between Bob will get 37.5+25=62.5% accuracy. We can visualize this calculation as below:<br />
<span id="goog_1409063834"></span><span id="goog_1409063835"></span><span id="goog_1409063837"></span><span id="goog_1409063838"></span><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-5Tx76K6qIxE/Uve72ntzviI/AAAAAAAAAZ4/fcVDFcAbHzk/s1600/Eve_in_the_middle.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-5Tx76K6qIxE/Uve72ntzviI/AAAAAAAAAZ4/fcVDFcAbHzk/s1600/Eve_in_the_middle.png" height="334" width="640" /></a></div>
<br />
<br />
Accuracy calculation of Bob when Eve is intercepting<br />
<br />
<br />
In this diagram node with "**" like C** represents the nodes where Bob decoded the qbits correctly and node with "*" like F* representing the nodes where Bob decodes the qbits wrong. One question that may arise is why Bob will get a 12.5% of accuracy where(in E,L) he have used wrong basis? Here we should remember that when we will use a wrong basis to decode a qbit then there is a 50% chance that we will get a 0 and 1 with 50% chance. By this logic Bob will get 12.5% accuracy from D. Similarly in case of I where Bob have used correct basis (with respect to Alice's basis) but Eve has already changed the polarization of the qbits using a wrong basis, Bob have 50% chance of being right and 50% false. So overall Bob gets 12.5% right qbit in I and 12.5% wrong qbit in J. Now they will match the basis they used for each qbit and they will use the bits where Bob used the correct basis and they will throw out the bits for which Bob used wrong basis. Now they need to check whether Eve is listening or not.For that purpose they will use a subset of the matched key (after throwing the bits for which Bob used wrong basis) and compare with others using normal channel. Bob will get a 100% accuracy if Eve is not there otherwise Bob will get 75% accuracy in Basis comparison. If accuracy is 100% then they will discard the set of bits they used for matching and rest bit string will be used as the key to encrypt the message. If 100% accuracy is not observed then they will try again to get a key using QKD. In the below example Alice is sending a key of "01101011" to Bob and she is using two types of polarizer as stated above.<br />
<br />
<pre>+-------------------+----+----+----+----+----+----+----+----+
| Alice's basis | + | X | + | + | X | X | X | X |
+-------------------+----+----+----+----+----+----+----+----+
| Alice's Data | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
+-------------------+----+----+----+----+----+----+----+----+
| Eve's Basis | + | + | X | + | X | X | X | + |
+-------------------+----+----+----+----+----+----+----+----+
| Eve's Data | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
+-------------------+----+----+----+----+----+----+----+----+
| Bob's basis | + | + | + | X | + | X | X | X |
+-------------------+----+----+----+----+----+----+----+----+
| Bob's Data | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
+-------------------+----+----+----+----+----+----+----+----+
</pre>
Now Alice and Bob will compare their basis and they will find that Bob has guessed the 1st, 3rd ,7th,and 8th basis correctly. So they will throw the bits of remaining position i.e 2nd, 4th, 5th, and 6th . Now key is "0011". Let them choose the first two bits for matching and then they will find that their second bit in the key is different, that means Eve is between them. Then they will repeat the same procedure again until they gets a 100% key match. When they get a key then they can easily encrypt the message using the key and send it via the public network.<br />
<br />
<span style="color: orange;"><b>Limitations:</b></span><br />
[1] In practical quantum channel will also be affected by noise and it will be hard to distinguish noise and eavesdropping.<br />
<br />
[2] If Eve wants he can intercept the quantum channel just not to allow Alice and Bob communicate.<br />
<br />
[3] No amplifiers are used on the optical fiber carrying the quantum signal. Such devices would perturb the communication in the<br />
same way an eaves- dropper does. This implies in turn that the range of QKD is limited.<br />
<br />
[4] Following no-cloning theorem, QKD only can provide 1 : 1 connection. So the number of links will increase N(N − 1)/2 as<sup> </sup> N represents the number of nodes.<br />
<br />
<span style="color: orange;"><b>Research work:</b></span><br />
Researchers have been developing such systems for more than a decade. DARPA Quantum Network, which became fully operational in BBN’s laboratory in October 2003, and has been continuously running in 6 nodes operating through telecommunications fiber between Harvard University, Boston University, and BBN since June 2004. The DARPA Quantum Network is the world’s first quantum cryptography network, and perhaps also the first QKD systems providing continuous operation across a metropolitan area. [7]<br />
<br />
NIST performs core research on the creation, transmission, processing and measurement of optical qubits. They demonstrated highspeed QKD systems that generate secure keys for encryption and decryption of information using a one-time pad cipher, and extended them into a 3-node quantum communications network. [8]<br />
<br />
Toshiba's Quantum Key Distribution System delivers digital keys for cryptographic applications on fiber optic based computer networks. Based on quantum cryptography.In particular, it allows key distribution over standard telecom fiber links exceeding 100 km in length and bit rates sufficient to generate 1 Megabit per second of key material over a distance of 50 km — sufficiently long for metropolitan coverage. [9]<br />
<br />
Current status of quantum cryptography in Japan includes an inter-city QKD test bed based on DPS-QKD, a field test of one-way BB84 system over 97km with noise-free WDM clock synchronization, and so on. [10]<br />
<br />
The 973 Program and 863 program of China have funded to support the QKD research.[11] <br />
<br />
In Europe SEcure COmmunication based on Quantum Cryptography (SECOQC) (2004–2008) project was funded for the same reason.[12]<br />
<br />
In 2004, ID Quantique was the first in the world to bring a quantum key distribution system to a commercial market. ID Quantique’s QKD product was used in conjunction with layer 2 Ethernet encryption to secure elections in Geneva.Other companies like MagicQ,QinetiQ,NEC are also working in this field. Companies claim to offer or to be developing QKD products, but limited information is publicly available. It is however likely that the situation will evolve in the near future. [13]<br />
<br />
<span style="color: orange;"><b>References:</b></span><br />
<br />
1. W. Chen, H.-W. Li, S. Wang, Z.-Q. Yin, Z. Zhou, Y.-H. Li, Z.-F. Han and G.C. Guo (2012). Quantum Cryptography, Applied Cryptography and Network Security, Dr. Jaydip Sen (Ed.), ISBN: 978-953-51-0218-2, InTech, Available from: http://www.intechopen.com/books/applied-cryptography-and-network-security/quantum-cryptography.<br />
<br />
2. http://news.sciencemag.org/sciencenow/2010/04/quantum-cryptography-hits-the-fa.html<br />
<br />
3. http://www.peterrohde.org/2012/06/29/do-we-need-quantum-cryptography/<br />
<br />
4. http://www.linux-mag.com/id/8753/<br />
<br />
5. http://thefutureofthings.com/column/5/what-is-a-quantum-computer.html<br />
<br />
6. "Quantum Computation and Quantum Information" by Michael A. Nielsen & Isaac L. Chuang.<br />
<br />
7. "Current status of the DARPA Quantum Network" by Chip Elliott , Alexander Colvin, David Pearson, Oleksiy Pikalo, <br />
John Schlafer, Henry Yeh.<br />
<br />
8. http://w3.antd.nist.gov/qin/index.shtml<br />
<br />
9. https://www.toshiba-europe.com/research/crl/qig/quantumkeyserver.html<br />
<br />
10. "Toward New Generation Quantum Cryptography -- Japanese strategy " by Nukuikita, Koganei.<br />
<br />
11. Post-Quantum Cryptography: Third International Workshop, Pqcrypto 2010, Darmstadt, Germany, May 25-28, 2010, <br />
Proceedings 1st Edition. <br />
<br />
12. http://vcq.quantum.at/publications/all-publications/details/643.html<br />
<br />
13. http://swissquantum.idquantique.com/?-Quantum-Cryptography-#<br />
<br />
<span style="color: #cc0000;"><u><i><b>** </b>This article was first published in<a href="http://www.linuxjournal.com/" target="_blank"> Linux Journal</a> January2013.</i></u></span></div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-79358188639380633412014-02-09T22:22:00.000+05:302014-02-09T22:27:01.710+05:30Searching an element in a row and column wise sorted matrix<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
First let me state the problem we will discuss in this post: You are given a 2-D array of nXn size with all the elements sorted in descending order row and column wise. You need to find a particular element in that array. <br />
There may be lots of ways to solve this problem. I will discuss three ways to solve this problem using a<br />
(i)linear search,<br />
(ii)binary search,<br />
(iii) binary search graph [ I know its bit confusing. Don't go on the name ]<br />
<br />
<a name='more'></a><br />
<br />
<i>Before you start reading solutions I need to state that I have used 2-D array and matrix for the same purpose throughout the post and assumed that the indexing starts from 0.</i><br />
<i>For each function used here, main function described under "Third Method" can be used to call the respective functions commenting and un-commenting respective function calls.</i><br />
<br />
<span style="color: orange;"><b>Linear Search Method:</b></span><br />
This approach is the most general approach. Only thing we need to keep in mind that we are dealing with 2-d array not an 1-d array. Just iterate through all the elements of the matrix<br />
[ as we do in displaying a matrix] and check whether the element exists or not. That's all.<br />
As 2-d array is of size nXn, Its complexity will be O(n<sup>2</sup>).<br />
Here is the code:<br />
<br /></div>
<pre>void _2D_linear(int **mat, int size, int num)
{
int i, j, flag;
flag = 0;
for (i = 0; i < size; i++) {
for (j = 0; j < size; j++) {
if (mat[i][j] == num) {
flag = 1;
break;
}
}
if (flag == 1)
break;
}
if (flag == 0)
printf("Data not found in the matrix!!!\n");
else
printf("Data found at position :%d,%d\n", i + 1, j + 1);
}
</pre>
<b><span style="color: orange;">Binary search Method:</span> </b><br />
This approach is little better than the previous approach. What we can do is to treat each row of the matrix as an 1-d array and
perform a binary search on that 1-d array. If the required number is found then stop the procedure and declare the position otherwise continue the binary search on each row and if after performing binary search on each row of the matrix required element is not found then declare that required number is not found on the matrix.<br />
This will require n binary searches for n number of rows and binary search in each row will require O(logn)
time. That means total complexity will be O(nlogn).<br />
Below is the code:</div>
<pre>void binsearch(int **mat, int size, int num)
{
int low, up, flag,row,mid;
flag = 0;
for (row = 0; row < size; row++) {
low = 0;
up = size - 1;
while (low <= up) {
mid = (low + up) / 2;
if (mat[row][mid] == num) {
flag = 1;
break;
} else if (mat[row][mid] > num)
up = mid - 1;
else
low = mid + 1;
}
if (flag == 1)
break;
}
if (!flag)
printf("Data not found in the matrix!!!\n");
else
printf("Data found at position :%d,%d\n", row + 1, mid + 1);
} </pre>
<pre> </pre>
<span style="color: orange;"><b>Third Method:</b></span><br />
In this approach we need some observation on the input. Matrix is sorted in row and column wise. If we look the matrix from
the left lower corner then we will find an binary search tree like pattern. Now binary search tree patterns means what?
It means in all lesser values are on the leftmost branch of a element and higher values are on the right branch.
Obviously it will not be a tree as vertices can be reached by different paths.<br />
Ok lets have an example:<br />
Our input is :<br />
<br />
<pre>
+---+---+---+
|6 |8 |13 |
+---+---+---+
|14 |19 |21 |
+---+---+---+
|15 |22 | 23|
+---+---+---+
</pre>
Now check the matrix from lower left corner i.e from element 15 and search for the binary search pattern (forget the left and
right orientation concept of general binary search tree).
For better understanding check these diagram:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-D9t0mgy2j0A/Uverg0UW6xI/AAAAAAAAAYw/WnFXrWF4NBk/s1600/2dbin_1.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-D9t0mgy2j0A/Uverg0UW6xI/AAAAAAAAAYw/WnFXrWF4NBk/s1600/2dbin_1.jpeg" /></a></div>
<br />
Diagram - 1 <br />
<br />
Here is the binary search tree like pattern.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-T8_zuW5sLoI/Uver3swzQyI/AAAAAAAAAY4/kDzt5knfFYQ/s1600/2dbin.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-T8_zuW5sLoI/Uver3swzQyI/AAAAAAAAAY4/kDzt5knfFYQ/s1600/2dbin.jpeg" height="278" width="320" /></a></div>
Diagram - 2<br />
<br />
In Diagram - 1 you can see that from a particular position if you move row wise i.e incrementing or decrementing row number, you
will find the numbers are decreasing and column wise numbers are increasing. From 15 if you move row wise you will find 15->14->6
(decreasing) and column wise 15->22->23 (increasing). We will use this property for our use.<br />
<br />
Algorithm will be as follows:<br />
1]Start search from lowest and leftmost corner.<br />
2]If search-item is greater than the current element then move one column right and follow the same process.<br />
3]If the search-item is lesser than the current element then move one row upward and follow the same process.<br />
4]Continue the process until you find the search-element or any move that take you out of the boundary of the matrix.<br />
<br />
We will check dry-run of two example on the above input matrix:<br />
First lets search-item is 13.<br />
Then search will proceed in this way:<br />
15 > 13 so go to 14 (i.e row wise)<br />
14 > 13 go to 6<br />
6 < 13 go to 8 (i.e column wise)<br />
8 < 13 go to 13 and it is the position of 13.<br />
<br />
Now lets have a search-item that is not in the matrix.<br />
Let the search-item be 10.<br />
15 > 10 go to 14<br />
14 > 10 go to 6<br />
6 < 10 go to 8<br />
8 < 10 go to 13<br />
13 > 10 go to position (-1,2) (i.e out of the matrix boundary)
so stop here and declare that element is not in the matrix.<br />
<br />
Here is the code:</div>
<pre>#include < stdio .h >
#include < stdlib .h >
void _2D_binsearch(int **mat, int size, int num);
int main(int argc, char **argv)
{
int **mat, size, num, i, j;
size = atoi(argv[1]);
mat = malloc(sizeof(int *) * size);
for (i = 0; i < size; i++) {
mat[i] = malloc(sizeof(int) * size);
}
printf("Enter the matrix:");
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
scanf("%d", &mat[i][j]);
printf("Enter the number to search:");
scanf("%d", &num);
//_2D_linear(mat, size, num);
//binsearch(mat, size, num);
_2D_binsearch(mat, size, num);
return 0;
}
void _2D_binsearch(int **mat, int size, int num)
{
int posx, posy, flag;
posx = size - 1;
posy = 0;
flag = 0;
while ((posx >= 0) && (posx < size) && (posy >= 0) && (posy < size)) {
if (mat[posx][posy] == num) {
flag = 1;
break;
} else if (mat[posx][posy] < num)
posy++;
else
posx--;
}
if (!flag)
printf("Data not found in the matrix!!!\n");
else
printf("Data found at position :%d,%d\n", posx + 1, posy + 1);
}
</pre>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-43986477929592485372013-09-03T22:26:00.000+05:302013-09-03T22:55:31.485+05:30Use Indent to indent your C-code<div dir="ltr" style="text-align: left;" trbidi="on">
I myself not very much expert in writing indented code and code without indentation looks just horrible. Of course you will not have same feelings if you are using an IDE with auto indentation facility and of course if you know how to write indented code. For this purpose I found <b><i>Indent </i></b>command very useful in linux. One thing you should remember that this command is only for C code. <br />
Actually not me, one of my friend <a href="https://plus.google.com/101636075809591975036" target="_blank">Arjun Pakrashi</a> informed me about this command.<br />
<a name='more'></a>What the command does is it changes the appearance of a C program by inserting or deleting whitespace.<br />
Syntax of the command is like:<br />
<br />
<b>indent [options] [input-files] or</b><br />
<b>indent [options] [single-input-file] [-o output-file]</b><br />
<br />
Indent command provided many options to format the source file like :-<br />
<br />
<b><i>[-bad] : Force blank lines after the declarations.</i></b><br />
<b><i>[-npcs] : Do not put space after the function in function calls. </i></b><br />
<b><i>[-nsaw] : Do not put a space after every while</i> </b>etc.<br />
<br />
Actually I too haven't used all the options provided by the command. I only use the -linux command that converts the source c file to linux coding style. <br />
There are many style that you can follow to indent like :-<br />
<br />
<b>[-gnu] : Use GNU coding style. This is the default.</b><br />
<b>[-kr] : Use Kernighan & Ritchie coding style.</b> etc.<br />
<br />
I will provide a sample unindented code to show how it converted to an indented one.<br />
<br />
<b>Unindented code:-</b><br />
<pre>#include<stdio.h>
int main()
{int a,b,c;
printf("Enter two numbers:");
scanf("%d,%d",&a,&b);
c=a+b;
printf("Sum of %d and %d is:%d\n",a,b,c);
return 0;
}
</pre>
After executing the following command I got the output.<br />
<pre> </pre>
<pre><b>indent -linux input.c -o output.c</b></pre>
<br />
<b>Indented code:-</b><br />
<br />
<pre>#include<stdio.h>
int main()
{
int a, b, c;
printf("Enter two numbers:");
scanf("%d,%d", &a, &b);
c = a + b;
printf("Sum of %d and %d is:%d\n", a, b, c);
return 0;
}</pre>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com2tag:blogger.com,1999:blog-4512121268692891574.post-78324784206305197632013-09-03T21:59:00.000+05:302013-09-03T21:59:05.641+05:30Iterative Quick sort<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
I am not going to state basic <a href="http://en.wikipedia.org/wiki/Quicksort" target="_blank">Quick sort</a> algorithm or its implementation. We all know about these stuffs. Today I am going to focus on Iterative Quick sort implementation in C. We know that Quick sort is recursive in nature. So we need a stack data structure. For that purpose we may use recursive function or use an external stack data structure to simulate recursive functions. Throughout the post I am going to use the leftmost element as the pivot element and we are only concerned about array implementation. <br />
<a name='more'></a>As it is an iterative code it will not have recursive calls to itself . We will use the external stack to hold the required data to operate on the array. We will iterate a loop until the external stack is empty . Every iteration of the loop will signify a recursive function execution. At each iteration we need to provide the limits ( lower and upper bound ) on which range Quick sort will operate. Now Array is same so we need not to worry about the array, only we need to worry about the limits. For that purpose we will use a structure that will hold both the lower and upper limit. Structure look like:</div>
<pre>
typedef struct activation
{
int low;
int up;
}boundary_t;
</pre>
<br />
We will get the arguments (lower and upper bound) for quick sort from the external stack and for that we have to push them first. Now we know that we will operate on the full array for the first time so we will push the structure containing low=0 and up=N-1 before calling Quick sort function. When the Quick sort will be executed, first it will pop the same structure and will operate on the given limit i.e low=0 and up=N-1. And then we will continue pushing signature of the Quick sort function according to partition and popping when we are going to operate on a new limit.<br />
<br />
We can code the iterative version of Quick sort directly from its recursive version just by some modification. We need two modification. First modification is to place a push statement wherever a call to quick sort is and it will push the arguments (mainly lower and upper bound of the array ) of function call. Second is place a pop statement that will pop the required argument to work on the function at the beginning of the Quick sort function and of-course termination checking criteria will change in recursive version it was checking whether the lower bound id smaller than the upper bound or not but in iterative version it will be checking stack's emptiness. If the stack is empty then stop.<br />
This will look like this:-</div>
<pre>+-----------------------------------+
| Recursive version: |
+-----------------------------------+
main()
{
.......
.......
*QS(arr[0:n-1])
.......
.......
}
#QS (arr[ low:up ])
{
.......
.......
@ QS(arr[low:mid-1])
$ QS(arr[mid+1:up])
}
+-----------------------------------+
| Iterative version: |
+-----------------------------------+
main()
{
......
......
* push(array[0:n-1]);
......
......
}
QS()
{
.....
# args=pop()
low=args.low
up=args.up
arr=args.array
.......
.......
@ push(arr[low:mid-1])
$ push(arr[mid+1:up])
}
</pre>
[ special characters used for mapping to recursive to iterative version]<br />
<br />
Here is the C-code for the program:-</div>
<pre> </pre>
<pre>/* File containing the data to be sorted stored in space separated format and name of output </pre>
<pre>file will be provided as command line argument */</pre>
<pre> </pre>
<pre>#include<stdio .h>
#include<stdlib .h>
#define MAX_BUF 100000
typedef struct items
{
int low;
int up;
}item_t;
typedef struct stack
{
item_t *arr;
int top;
}stk_t;
stk_t *get_stack();
void push(stk_t *stk,item_t *item);
item_t pop(stk_t *stk);
void quick_sort(item_t item,int *arr);
int main(int argc,char **argv)
{
int i,*arr,size;
FILE *fp,*ft;
item_t item;
if(argc!=3)
{
printf("Wrong number of arguments!!\nExiting!!\n");
exit(0);
}
fp=fopen(argv[1],"r");
ft=fopen(argv[2],"w");
fseek(ft,0,SEEK_SET);
if(fp==NULL || ft==NULL)
{
printf("Error in openning file!!\n");
exit(0);
}
fscanf(fp,"%d",&size);
arr=malloc(sizeof(int)*size);
for(i=0;i<size 0="" arr="" d="" fclose="" for="" fp="" fprintf="" fscanf="" ft="" get_stack="" i="" item.low="0;" item.up="size-1;" item="" n="" printf="" quick_sort="" return="" rray_after_sorting:="" s="" stk-="" stk="malloc(sizeof(stk_t));" stk_t="" t="">arr=malloc(sizeof(item_t)*(MAX_BUF+1));
stk->top=-1;
return stk;
}
void push(stk_t *stk,item_t *item)
{
char ch;
if(stk->top<max_buf stk-="">arr[++stk->top]=*item;
}
else
{
printf("Stack outof memory!!\n");
exit(0);
}
}
item_t pop(stk_t *stk)
{
item_t empty;
if(stk->top>-1)
{
return (stk->arr[stk->top--]);
}
else
{
empty.low=-1;
empty.up=-1;
printf("Stack is empty!!\n");
return empty;
}
}
void quick_sort(item_t item,int *arr)
{
int pivot,i,j,temp;
item_t *item_1,*item_2,*t_item;
stk_t *stk;
item_1=malloc(sizeof(item_t));
item_2=malloc(sizeof(item_t));
stk=get_stack();
t_item=&item;
push(stk,t_item);
while(1)
{
item=pop(stk);
if(item.low==-1 && item.up==-1)
break;
if(item.low<item .up="" arr="" do="" i="" item.up="" j--="" j="" pivot="" while="">pivot);
if(i<j arr="" i="" item.low="" item_1-="" j="" temp="" while="">low=item.low;
item_1->up=j-1;
item_2->low=j+1;
item_2->up=item.up;
push(stk,item_1);
push(stk,item_2);
}
}
}
</j></item></max_buf></size></pre>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com1tag:blogger.com,1999:blog-4512121268692891574.post-45914360099201167212013-07-14T22:20:00.000+05:302013-07-14T22:20:07.524+05:30Simple Power Set Generator<div dir="ltr" style="text-align: left;" trbidi="on">
Currently I was trying to code some algorithm that one of my friend told me to do. In that algorithm I needed the code of a <a href="http://en.wikipedia.org/wiki/Power_set" target="_blank">power-set</a> generator. I first tried to code in my own way but it proved to be not so much simple. Then I found another simple logic to generate power-set. Logic is simple if you want the power-set of a set with n number of elements then just generate all the combination of n boolean variables.<br />
<br />
<a name='more'></a><br /><br />
Suppose you want the power-set of 3 variables a,b,c. Then take 3 boolean variables and generate their all their possible combination. For 3 variables it will be:<br />
<pre>
+---------+---------+----------+---------+
|Index |pos-2 |pos-1 |pos-0 |
+---------+---------+----------+---------+
| 0 | 0 | 0 | 0 |
+---------+---------+----------+---------+
| 1 | 0 | 0 | 1 |
+---------+---------+----------+---------+
| 2 | 0 | 1 | 0 |
+---------+---------+----------+---------+
| 3 | 0 | 1 | 1 |
+---------+---------+----------+---------+
| 4 | 1 | 0 | 0 |
+---------+---------+----------+---------+
| 5 | 1 | 0 | 1 |
+---------+---------+----------+---------+
| 6 | 1 | 1 | 0 |
+---------+---------+----------+---------+
| 7 | 1 | 1 | 1 |
+---------+---------+----------+---------+
</pre>
Now print 'a' when there is an 1 in pos-0 and 'b' when there is an 1 in pos-1 and 'c' when there is an 1 in pos-2 and all position is 0 means NULL set. Now for 3 element set {a,b,c} power-set will be :<br />
<pre>
{
{NULL}, [000: all positions are 0]
{a}, [001: only pos-0 is 1 others are 0]
{b}, [010: only pos-1 is 1 ]
{a,b} [011: pos-0 and pos-1 is 1]
{c}, [100: only pos-3 is 1]
{a,c}, [101: pos-1 and pos-2 is 1]
{b,c}, [110: pos-1 and pos-2 is 1]
{a,b,c} [111: all positions are 1]
}</pre>
<br />
<br />
Now the problem is how to generate these boolean variables combination. Here we can use bitwise operator. We only need right/left shift operator and the bitwise AND(&) operator for masking purpose. Actually we will iterate a loop from 0 to (2^n) where n is the number of elements in the set and then scanning n leftmost element of each loop count and check whether it is 1 or 0.<br />
For 3 variables we will use a loop i:=0 to 7 and then at each iteration we will scan binary representation (using masking<br />
operation) of i and check leftmost n binary position for 0 or 1.<br />
<br />
<b>Code in C:</b><br />
<pre>
/*It needs one command line argument which is the number of elements in the set*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
char **get_powerset(char *ptr, int k)
{
int i, j, num_element, mask, l, val;
char **power_set;
num_element = pow(2, k);
power_set = malloc(sizeof(char *) * (num_element));
for (i = 0; i < num_element; i++) {
power_set[i] = malloc(sizeof(char) * k);
memset(power_set[i], '#', (sizeof(char) * k));
}
for (i = num_element - 1; i >= 0; i--) {
l = 0;
for (j = k - 1; j >= 0; j--) {
mask = 1 << j;
if (i & mask)
power_set[i][l++] = ptr[j];
}
}
return power_set;
}
int main(int argc, char **argv)
{
int i, num_element, k, j, num_item;
char **power_set, *ptr;
num_item = atoi(argv[1]);
ptr = malloc(sizeof(char) * num_item);
for (i = 0; i < num_item; i++) {
printf("Enter %d no. element:", i);
scanf(" %c", &ptr[i]);
}
power_set = get_powerset(ptr, num_item);
num_element = pow(2, num_item);
printf("\nPower Set is==>\n\n");
for (i = 0; i < num_element; i++) {
printf("{");
for (j = 0; (power_set[i][j] != '#') && (j < num_item); j++) {
printf("%c,", power_set[i][j]);
}
if (i == 0 && (power_set[i][0] == '#'))
printf("NULL,");
printf("\b}");
printf("\n");
}
return 0;
}
</pre>
<b>Description:</b><br />
<br />
The function "get_powerset" returns an 2-d array of size (2^n) X n where each row contains one element of the power-set. As the length of each element of the power set is not constant so we have used # as terminator except the element that contains all the element of the set. For example if the set is {1,2,3} then this function will return the below 2-d array:<br />
<pre>
+----+----+----+
|# | | | {NULL}
+----+----+----+
| 1 | # | | {1}
+----+----+----+
| 2 |# | | {2}
+----+----+----+
| 2 | 1 | # | {2,1}
+----+----+----+
| 3 | # | | {3}
+----+----+----+
| 3 | 1 | # | {3,1}
+----+----+----+
| 3 | 2 | # | {3,2}
+----+----+----+
| 3 | 2 | 1 | {3,2,1}
+----+----+----+
</pre>
One problem with this logic is that it is limited to the size of the memory allocated to the data-type of i. </div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-51834034364325099352013-07-05T23:39:00.000+05:302013-07-05T23:57:05.081+05:30All expired things are not log files.Distinction between expired unnecessary things and log files is very much vague to me. May be for this confusion I somehow decided to keep my old expired admit card for December <a href="http://en.wikipedia.org/wiki/National_Eligibility_Test" target="_blank">NET</a> exam,2012. One thing I should tell that I couldn't sit for this exam as my Semester exam and NET exam collided. Whatever I got another chance for the exam in June,2013 as the exam holds twice a year. Just before the exam when the exam centers were published then I found that my center is "South calcutta girl's College". Then I searched the college in Google Map and the route to it. Till then I had no problem. But on the day of exam before going to the centre I somehow decided to match the center with the printed copy of my Admit card. Then I found that my center is not the above specified college but another one. I didn't have enough time to search the college and go there. Luckily one of my friend Subhajit Ganguly told me that he knows the college and it was near. Then I found that the admit card I was matching for my center was of the december,12 and according to that expired admit card my exam center was South Calcutta girl's College. However I was lucky enough that the college was not far.Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-11348649972420789142013-04-27T21:56:00.000+05:302013-04-27T21:56:15.396+05:30Use ulimit to Increase your system stack size<div dir="ltr" style="text-align: left;" trbidi="on">
Currently I was testing my quick-sort program with a large number of data. It performed well when the data were random but when I used sorted or reversely sorted data then after some time the program stopped showing a message of segmentation fault. I was wondering why such type of exception happened. I was checking whether it was accessing any illegal memory location or not. But I didn't find anything of this kind. Then I found that default memory size for system stack is 8M.B in my memory and it was not sufficient for the program to operate on the given data. Then I found the <a href="http://ss64.com/bash/ulimit.html" target="_blank"><i>ulimit</i></a> command in shell that enhances the memory size for the system stack and it helped me to successfully run my program. <i>ulimit</i> provides control over the resources available to the shell and to processes started by it, on systems that allow such control. The <i>-H </i>and <i>-S </i>options specify that the hard or soft limit is set for the given resource. A hard limit cannot be increased by a non-root user once it is set; a soft limit may be increased up to the value of the hard limit. If neither <i>-H </i>nor <i>-S</i> is specified, both the soft and hard limits are set. There are some options that I found useful:<br />
-a All current limits are reported<br /> -b The maximum socket buffer size<br /> -d The maximum size of a process's data segment<br /> -e The maximum scheduling priority ("nice")<br /> -f The maximum size of files written by the shell and its children<br /> -s The maximum stack size<br /> -T The maximum number of threads<br />
<br />
If limit is given, it is the new value of the specified resource (the -a option is display only). If no option is given, then -f is assumed. Values are in 1024 byte increments. For example if you want to assign 200M.B to your system stack then you need to type: <i> </i><br />
<i>[subhendu@localhost ~]$ ulimit -Ss 204800</i><br />
To know the current limits type:<i> </i><br />
<i>[subhendu@localhost ~]$ ulimit -a</i><br />
<br />
<br />
<br /></div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-3578849688478417852013-04-23T16:02:00.001+05:302013-04-23T16:02:15.382+05:30Constant Pointer<div dir="ltr" style="text-align: left;" trbidi="on">
<ol style="text-align: left;">
<li>int const* ptr;</li>
<li>const int*ptr;</li>
<li>int *const ptr;</li>
<li>const int* const ptr;</li>
<li>int const*const ptr;</li>
</ol>
<a name='more'></a><br />
<div>
At the first glance these stuffs looks so scary but they are not as much as we think. Here is two things one is a integer pointer and another is a <i>const</i> keyword. Nothing I need to say about integer pointer and <i>const</i> in brief is used to create a <i>read only variable</i>. One thing before going further I want to say about the above expressions is that you can use the first <i>const</i> on either side of the type (integer here). That means :<br />
<i>int const *ptr</i> is equivalent to <i>const int *ptr</i> and <i>const int* const ptr</i> is equivalent to <i>int const*const ptr</i>. We can easily understand the meaning of each of the above expression if we read these expression right to left.<br />
<br />
<b><i>const int *ptr</i> </b>: ptr points to a integer that is const. Integer object can't be changed via ptr. For example check this code:<br />
<br />
<ol style="text-align: left;"><pr>
<li>#include<stdio.h></li>
<li>int main()</li>
<li> { </li>
<li> const int *ptr; </li>
<li> int a,b; </li>
<li> a=10; </li>
<li> b=20; </li>
<li> ptr=&a; </li>
<li> printf("%d\n",*ptr); </li>
<li> //*ptr=20; //Error</li>
<li> ptr=&b; </li>
<li> printf("%d\n",*ptr); </li>
<li> return 0;</li>
<li style="text-align: left;"> }</li>
</pr></ol>
<pr></pr>If we uncomment the line 10 then there will be an error saying <i>error: assignment of read-only location ‘*ptr’</i>. This is because we are trying to modify the value pointed by ptr which is not allowed here. But we can modify the pointer to point to other integer object. In line 11 another integer is being assigned to ptr without an error.<br />
<br />
</div>
<b><i>int* const ptr</i></b>: ptr is a const pointer to a integer that means you can change the integer object via ptr but you can't change the pointer ptr itself. Check this example:<br />
<ol style="text-align: left;">
<li>#include<stdio.h></li>
<li>int main()</li>
<li> {</li>
<li> int a=10;</li>
<li> int b=20;</li>
<li> int *const ptr=&a;</li>
<li> printf("%d\n",*ptr);</li>
<li> //ptr=&b; //Error</li>
<li> *ptr=30;</li>
<li> printf("%d\n",*ptr);</li>
<li> return 0;</li>
<li> }</li>
</ol>
<div style="text-align: left;">
Here the line 8 assigning another integer to the pointer ptr which is a const pointer, so this will generate an error if we uncomment it. Otherwise there is no problem in changing the value of the integer variable pointed by ptr. Another thing that you should keep in mind in the time of declaring such type of variable that you must set the pointer at the time of declaration as you can't do it later.<br />
<br />
<b><i>const int* const ptr</i></b>: ptr is a const pointer to a const integer that means you can't change the pointer ptr itself and you can't change the integer object via ptr. Here is the example:<br />
<ol style="text-align: left;">
<li>#include<stdio.h></li>
<li>int main()</li>
<li> {</li>
<li> int a=10; </li>
<li> int b=20; </li>
<li> const int *const ptr=&a; </li>
<li> printf("%d\n",*ptr); </li>
<li> //ptr=&b; //Error</li>
<li> //*ptr=30; //Error</li>
<li> return 0;</li>
<li> } </li>
</ol>
</div>
<div style="text-align: left;">
If we uncomment the lines 8 and 9 then there this code will generate errors. As in line 8 we are trying to modify a const pointer and in line 9 we are trying to modify the value of a pointer pointing to a const object. As the pointer is also const then you need to initialize it at the time of declaration.</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
We also can use a handy rule to understand whether const applies to the pointer or the pointed data.<i> </i><span class="comment-copy"><i> split the statement at asteric(*) sign, then,
if the const keyword appears in the left part (like in 'const int * ptr') - it belongs to pointed data, if it's in the right part ('int *
const ptr') - it's about the pointer. </i></span></div>
<div style="text-align: left;">
<span class="comment-copy"><br /></span></div>
<div style="text-align: left;">
<span class="comment-copy"><b>References:</b> <a href="http://stackoverflow.com/questions/1143262/what-is-the-difference-between-const-int-const-int-const-int-const" target="_blank">StackOverflow</a></span></div>
<div style="text-align: left;">
<br /></div>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-6470419453909226902013-04-21T13:53:00.000+05:302013-04-22T21:17:48.638+05:30Function returning pointer.<div dir="ltr" style="text-align: left;" trbidi="on">
#include<stdio.h><br />
char *fun()<br />
{ <br />
return ("samsung India");<br />
}<br />
<br />
<br />
int main()<br />
{<br />
printf("%s",printf("electronics")+fun());<br />
return 0;<br />
}<br />
<br />
<a name='more'></a><br />
<br />
Explanation:<br />
<br />
Output will be <i><b>electronicsia</b></i>. When the outer printf statement will be<br />
executed then its arguments <i>(printf("electronics")+fun())</i> must be evaluated first. Wheather the <i>inner</i> print statement <i>(printf("electronics"))</i> will be called first or the fun() function will be called first that is an <i>Undefined behaviour </i>according to <i>C-99</i>, but that wont affect our output. whenever the <i>inner</i> printf statement will be executed it will print <i>electrinoics</i> and it will return <i>11</i> as printf returns the number of character printed. Now when the fun() function will be called it will return the base address of the string <i>samsung India</i> say <i>0xbfb6fc8c</i>. Ultimately the argument of the outer printf statement will be reduced to <i>11+0xbfb6fc8c</i> and it is <i>0xbfb6fc97</i> which is address of second i in India.<br />
<br />
<pre> +----+----+----+----+----+----+----+----+----+----+----+----+----+
| s | a | m | s | u | n | g | | I | n | d | i |a |
+----+----+----+----+----+----+----+----+----+----+----+----+----+
^ ^
| |
0xbfb6fc8c 11+0xbfb6fc8c</pre>
<br />
When the outer printf executes it prints <i>ia</i>. So inner printf statement prints <i>electronics</i> and outer printf statemtent prints <i>ia</i>. This can be easy to understand in this step by step method (considering fun() function is being called after the inner printf function):<br />
<br />
printf("%s",printf("electronics")+fun());<br />
printf("%s",11+fun()); // prints "electronics"<br />
printf("%s",11 + 0xbfb6fc8c);<br />
printf("%s",0xbfb6fc97); // prints "ia"</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-59078611757603577562013-04-21T13:08:00.001+05:302013-04-21T15:45:30.500+05:30Short-circuiting in Logical AND<div dir="ltr" style="text-align: left;" trbidi="on">
#include<stdio.h><br />
int main()<br />
{ <br />
int a; <br />
scanf("%d",&a); <br />
a && printf("%d",a) && printf("LOL"); <br />
return 0;<br />
}<br />
<br />
<a name='more'></a><br /><br />
Explanation:<br />
<blockquote class="tr_bq">
If you give an input other than 0 say 2 then the output will be <b><i>2LOL</i></b> and if you input a 0 then nothing will be printed. According to C-99 standard 6.5.13 paragraph 4: </blockquote>
<blockquote class="tr_bq">
<i>Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; if the second operand is evaluated, there is a sequence point between the evaluations of the first and second operands. If the first operand compares equal to 0, the second operand is not evaluated</i>. </blockquote>
<blockquote class="tr_bq">
Now when the input is <i>0 </i>then the first operand <i>a</i> is zero and according to standard rest of the expression will not be executed. If the output is non-zero then the first operand is not zero thats why second operand of <i>&&</i> is executed and it prints the value of a and last operand prints <i>LOL</i>.</blockquote>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-47125830454523558142013-04-21T00:13:00.000+05:302013-09-03T12:43:47.111+05:30Accessing Integer through character pointer<div dir="ltr" style="text-align: left;" trbidi="on">
#include<stdio.h> <br />
int main() <br />
{ <br />
int i=512; <br />
char *c =(char*)&i; <br />
c[0]=2; <br />
printf("%d",i); <br />
return 0; <br />
}<br />
<br />
<a name='more'></a><br />
<br />
Explanation:<br />
The answer is given assuming that your system is Big-endian. For details about endianness you can <a href="http://phoxis.org/2012/10/01/detect-endianness-of-a-system/" target="_blank">check this</a>. <br />
<br />
<pre>
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| 0 |0 |0 |0 |0 |0 |0 | 0 | |0 |1 |0 |0 |0 |0 |0 |0 |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
</pre>
This is the last two byte (0th and 1st) representation of i. When we are assigning i to c, c points to the base address of the i but when we will try to access c we will not get the whole of i at a time as c is a character pointer. So c means only the first 1 byte of i. Similarly c[0] is also points to the first byte of i. So when assigning 2 to c[0] it means it just updating the first byte and 2nd bit of the first bit will be set to 1. Now when we will print the value of i then we will get a value 512+2=514.</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-61702663430974211352013-04-20T00:47:00.000+05:302013-04-20T00:48:48.057+05:30Renaming large number of files This post is just for those who are new to shell scripting. Today I stuck with a problem of renaming a large number of a pdf file. I was trying to rename them like "sequence-point-stack-1" only the last number will change and rest will be same for all files. So I tried to write a script that will help me and ultimately I succeed. Here is the code:<br />
<br />
<a name='more'></a><br /><br />
#!/bin/bash<br />
<div style="text-align: center;">
<div style="text-align: left;">
j=1<br />
for i in *.pdf<br />
do<br />
mv $i "sequence-point-stack-$j.pdf"<br />
j=$((j+1))<br />
done</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
In this script you just need to change the extension as your requirement and the name that you want to give the files. But beware of this fact that if extension is not part of the name of the file this script wont do. Like if you a have two pdf file "lolo" and "lola.pdf" then only the "lola.pdf" will be affected. Another thing that it wont work for those case where you want to rename the file with totally different strings. For example if you want to rename two file as "hehe-1" and "hoho-2" then this script wont work. In generalized case the script will look like:</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
#!/bin/bash<br />
<div style="text-align: left;">
j=1<br />
for i in *.<<your extension>></div>
<div style="text-align: left;">
do<br />
mv $i "<<the name you want to give>>$j.<<your extension>>"<br />
j=$((j+1))<br />
done</div>
</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
** Don't forget to remove "<<" and ">>".</div>
</div>
<br />Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-42320999477136312562013-04-17T00:23:00.000+05:302013-04-17T00:36:00.699+05:30Falling in Love<blockquote class="tr_bq">
Every body says "I fall in love" or "He fell in love". Why people <b><i>falls</i></b> in love? Is there any reason behind it? </blockquote>
<br />
<a name='more'></a><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-9EN_bysorhg/UW2gW-FaqpI/AAAAAAAAAUg/dwBUEqnvSGw/s1600/868472236_1361127390.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-9EN_bysorhg/UW2gW-FaqpI/AAAAAAAAAUg/dwBUEqnvSGw/s1600/868472236_1361127390.jpg" /></a></div>
<br />
<blockquote class="tr_bq">
I never heard any such reason. I think, yes I think (may not all think in the same way) when you falls in love, you have an extra relation to handle, so you need extra time for that. But you can't change the truth that you are given only 24 hours in a day. So you need to manage your time. You need to cut your time from any other place that may be your work time too. Now you will say that "you don't work all the day, there are some time for rest". Yes but are not rest is important? So when you fall in love you are neglecting some job that you should not. But there may some contradictions, some people does balance this new task well, in those case we can't blame that he/she is neglecting his other jobs. Then why we add such a negative word before such pretty word like Love? Is there any statistics that most of the people who falls in love neglects their duties? That may be a reason but I never heard of such statistics. I think we should change this idea of negating Love like this. Better we should say "I woke in love " or "He rise in love". I know these sentence does not sound so sweet as "I fall in love" sounds. But if we continuously use these sentences It will also sound nice after some time and it will be encouraging too.</blockquote>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-19002573691736781782013-04-16T23:35:00.000+05:302013-04-16T23:35:57.535+05:30Are we machine?The topic I am going to share may seem to you funny and induced by some movie. Many times our topic of discussion was distinction between the machine and Human. Some people argues that the things that distinguishes us from the machines are power to think,power to feel. I can feel pity on someone and I may help him though I was instructed to harm him, but a machine can't,It will do as it was instructed. It feels reasonable upto certain distance to me. Yes machine can not feel and can't think. Wait a minute are we sure that machine can't think? Actually I believe machines can think provided that they are given the power to think. How we do something? We observe the situation then analyse the situation and decides to do some thing. Machine also performs some tasks just in the same way we do. Actually we tells them through their design how to perceive the situation and how to analyse the situation. But you may think our thinking power is not manipulated by some others or it is not pre determined that how we will react to a situation or we are?. We all know about genes and how it controls our behaviour and characteristics. Is it not same as the embedding controls in machines design? I think as we embeds control information in a machine, our control information is also embedded in our gene. Actually all the things we do are governed by some rule. Same for how we feel. Maybe how we will feel something or someone is all embedded in our gene. In which situation will we cry or laugh is predetermined, which food will we like, what kind of movie or songs will we like or which kind of people will we like is all predetermined. We are just following the rules according to the situation. If we are feeling sympathy on someone or even falling in love of someone, we are just following the rules. If we can design a machine where we can embed all these kind of control instruction then machines will act as human acts. But due to our limited knowledge we have not been able to read all kind of instructions in our gene, but when we will be able to that we might design a machine that will act as a human accurately. So all that I want to say is that Human body is a big and complex machine (may be controlled by some other ).Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com1tag:blogger.com,1999:blog-4512121268692891574.post-85152938299481374022013-04-03T03:55:00.000+05:302013-04-08T02:30:03.570+05:30Way back to home<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="margin-bottom: 0in;">
<br />
On the occasion of <a href="http://en.wikipedia.org/wiki/Holi" target="_blank">Holi</a>, we all were returning home for the holidays from <a href="http://en.wikipedia.org/wiki/Banaras_Hindu_University" target="_blank">BHU</a>. Though
the holidays were of three days we extended it to 7 days. As we
have nothing but a project work in this final semester so we didn't
got much problem to extend the vacation. We had reserved our tickets
one month before the holidays. Our train time was on the very dawn so
I decided not to sleep at night and sleep on the train. Generally we
sleeps not before 3 to 4 a.m , so I decided better not to sleep as it
will be painful to wake up so early. As we are on the last semester
and we must leave the hostel just after the semester examination we
had a lots of luggage (mainly winter clothing ) with us to reduce the
unnecessary things on hostel. The train was on time but the
compartments were so crowded that it took us near about half of an
hour to reach our seat. Of course most of the people didn't have
legal tickets otherwise compartment would not be so crowded. When we
reached our seats we found those well occupied by others without a valid
ticket. It was their greatness that they offered us to seat on our
reserved seat. Seating on that overcrowded compartment with a
scorching sun I decided never to reserve any train ticket that runs on
day time. However the train took us to our destination on time. From
that place we all will go on different ways. I had to take another
train that will take me to home. I had some notes of hundred rupees
and change of four rupees only. But unfortunately my ticket was of
fifteen rupees and the counter responded as I feared “get a change
of one rupee” . Now I was on real trouble. I had two weighty luggage bags and also my laptop bag. Where should I get a
change of hundred rupees? For that purpose I need to go to the nearby
stalls and buy something. But with those heavy bags I found it hard
to find my way to the stalls as in <a href="http://en.wikipedia.org/wiki/Howrah_railway_station" target="_blank">Howrah</a> station stalls are at a
distance from the station and to access the stalls that are inside
the station I need a ticket which I didn't have at that time. So I
waited there for some time then a man came to me to ask me if I need
reservation tickets. I told him about my misery and it is kind of him
that the man gave me one rupee. Then I got my ticket and went to the
platform to take train. It was late enough. If I am late much then I
will not get any bus from the rail station. Then I heard that most
of the trains have been cancelled on our route due to the maintenance
work on a particular station of that route. Then I waited for the
last train with all other people, no, I better say a crowd that can't
be fitted on a single train. As obvious I couldn't even reach the
train. Then what? One of the last options. I went to room of my
brother and next day in the morning I and my brother both went home.
Really the journey was very tiresome.</div>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-56497420842603984782013-02-16T14:10:00.001+05:302013-04-16T12:18:42.518+05:30Idea on Genetic Algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
<br />
<br />
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">In
the mid 1800's a British naturalist named Charles Darwin published a
book named 'The Origin of Species' and said that including human all
the living being were not put into the earth by God, rather we
evolved from other species. At that time it sounded absurd. But with
the time flow when we invented more and more new stuffs then we
gradually understood that what Darwin said was right. Overtime every
living being is evolving to keep up with the changing environment. If
it can evolve then it will survive otherwise nature will make it
vanish.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
</span></div>
<br />
<a name='more'></a><br />
<br />
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b><span style="text-decoration: none;">A]
</span><u>Background</u>:- </b></span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
</span></div>
<br />
<div style="font-weight: normal; margin-bottom: 0in;">
Now let us
concentrate on what Evolution is and how every living being is
evolving. Evolution is the process of change in the inherited traits
from parents over generations. Every living being gets some
traits(encoded in chromosome) from its parent and it make these
traits flow over its generation. During these flow some chromosome
combines with other type of chromosome and new types of chromosome
with new traits that belongs to neither of the participating
chromosome are evolved. This new type of chromosome may be more
superior or inferior.
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-0sFdrMzcNm0/UR8_WdEt9dI/AAAAAAAAAPo/05Kjjyam1b0/s1600/image.bmp" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="496" src="http://3.bp.blogspot.com/-0sFdrMzcNm0/UR8_WdEt9dI/AAAAAAAAAPo/05Kjjyam1b0/s640/image.bmp" width="640" /></a></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;"> pic-1</span>
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
</div>
<br />
<br />
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b>B]<u>Why
Genetic Algorithms</u><span style="text-decoration: none;">:</span></b><span style="text-decoration: none;"><span style="font-weight: normal;">-</span></span></span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
First let me tell
you something about “hard computing” and “soft computing”.
Hard computing is the conventional computing that requires a
precisely stated analytical model and returns deterministic output.
For example ...</div>
<div style="font-weight: normal; margin-bottom: 0in;">
But soft computing
is unlike hard computing, it is tolerant of imprecision, uncertainty,
partial truth, and</div>
<div style="font-weight: normal; margin-bottom: 0in;">
approximation. In
soft computing algorithm learns to give solution. For example
Handwritten character recognition .</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">Genetic
algorithm(GA)</span> is also a tool of soft computing. <span style="font-size: small;">GA
is one of the best way to solve the type of the problem about which
very little is known. All you need to know what you need the solution
to be able to do well and GA will provide you the solution. GA is
basically a search algorithm that are applied to search for solution
in a large state space that is uneven in nature. </span>
</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">GA is
useful when---</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">=>The
search space is large and complex.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">=>No
mathematical analysis is available.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">=>The
problem is to find solution under multi-objective function.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: small;">=>Conventional
method fails.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b><span style="text-decoration: none;">C]
</span><u>Basic Principles</u>:- </b></span>
</div>
<div style="font-weight: normal; margin-bottom: 0in;">
GA is based on the
theory of natural selection and work on generating a set of random
solutions and making them compete in an arena where only the fittest
survives.</div>
<div style="font-weight: normal; margin-bottom: 0in;">
In GA we initially
generate a fixed number of chromosome that will form the Initial
Population. Actually each chromosome represents a possible solution
and you will ask how? This actually depends upon the programmer, how
he maps the actual problem to GA space. We need to perform this
mapping so that we can use GA operators on these chromosomes.</div>
<div style="font-weight: normal; margin-bottom: 0in;">
For example let a
maximization problem where f(x)=x^2 and x is a integer that <b>belongs
to [0,31]</b>. Here we can represent the possible values i.e integer
decimal values into string of binary numbers of length 5. Our Initial
population may contain chromosomes
10001(17),01010(10),11001(26),10100(20).</div>
<div style="font-weight: normal; margin-bottom: 0in;">
Then we will
select chromosomes with some selection procedure that will go to
matting pool where all GA operators will be applied . In matting pool
chromosomes are selected in pairs and crossover operator is applied
on them and similarly mutation operator is also applied on them. This
process will continue until a termination condition arises. After the
completion of the algorithm there is a high chance that we will get a
feasible solution. Yes there is also a fitness measuring function
that will keep track of the fitness of each chromosome, at the time
of crossover we will replace some chromosome with least fitness,
following the theory of 'Survival of the fittest'.Actually generally
selection process and termination condition is dependent on this
Fitness function. Thus starting from a set of random solutions the
algorithm uses these operators and fitness function to guide its
search for the optimal solution.</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b><span style="text-decoration: none;">D]
</span><u>Methodology</u>:- </b></span>
</div>
<div style="margin-bottom: 0in;">
<b><span style="font-size: large;"> 1]Initialization:-</span>
</b><span style="font-weight: normal;">To start GA first we need to
define the Maximum allowable population(number of maximum
chromosome), Maximum number of generation we will allow the algorithm
to generate . We also need to define the crossover rate and mutation
rate these two value will specify whether a particular chromosome
will undergo crossover and mutation. Above all we need to generate
the initial chromosomes with which we will start our selection
procedure. We can apply some logic to assign the values of the
chromosomes or simply can randomly assign values to chromosomes.</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
For example for
above described problem we can generate chromosome using only two
constraint one is that chromosome will contain only binary values and
chromosome will be of length 5. Then we can generate chromosomes of
length 5 up to Number of initial population.
</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: large;"><b>2]Calculate
Fitness: </b></span><span style="font-size: small;">GA generates solution based on the
fitness value of a chromosome. So after initialization we need to
calculate the fitness value of each of the chromosome in the
population. We will calculate the fitness value using a Objective
function that is called a Fitness function. </span>
</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-size: medium;"><b>2.1]
Fitness function: </b></span><span style="font-size: small;">A fitness function is a
particular type of objective function that is used to evaluate the
quality of a chromosome. It assigns a fitness value to all the
chromosome in the population. This function will vary according to
the problem. Fitness function should contain all the variables that
affects the solution. For some constraint satisfaction problem there
will be some constraints that will lead the search. Of course these
constraint will have different effect on the solution. Some will have
much effect and other will have less. So we need to assign some sort
of weight to these constraint according to their effect on the
solution. For example ,in a constraint satisfaction problem we can
define a fitness function as f(X)= ((CS*X)-((N-X)*CNS))/(CS*N) where
CS is cost for satisfying a constraint and CNS is cost for not
satisfying a constraint. N is the total constraint applied on the
problem and X is the number of satisfied constraint.</span></div>
<div style="margin-bottom: 0in;">
<b><span style="font-size: large;"> 3]Selection:-</span>
</b><span style="font-weight: normal;">GA use the selection operator
to select chromosome from the population that will go to matting pool
and various GA operator will be applied on them. As the selected
chromosomes are the ones whose genes are inherited by the next
generation, it is desirable that the selected chromosomes will have
good fitness value. The convergence rate of a GA is highly determined
by the selection method, with better selection process resulting in
higher convergence rates. However, if the selection process is not
good enough, the convergence rate will be slow. If the selection
process is too active then it may create problem by converging to an
sub-optimal solution.</span></div>
<div style="margin-bottom: 0in;">
<span style="font-size: medium;"><b> 3.1] Roulette Wheel
Selection:-</b></span><b> </b><span style="font-weight: normal;">Roulette
Wheel selection </span><span style="color: black;"><span style="font-family: Times New Roman;"><span style="font-size: small;"></span></span></span></div>
This can be simulated by following algorithm.
<br />
1.Calculate sum of all chromosome
fitness(S) in population.<br />
2.Generate random number (<b>r</b>)
from interval <i><b>(0,S)</b></i>.<br />
3.Go through the population and sum fitness from first chromosome. When the sum is greater than <b>r</b> , stop and return the chromosome where you are.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-DWZz2qyuYOI/UR9B2DyDO-I/AAAAAAAAAP4/IVVrBsAodK4/s1600/selection.png" imageanchor="1"><img border="0" height="272" src="http://4.bp.blogspot.com/-DWZz2qyuYOI/UR9B2DyDO-I/AAAAAAAAAP4/IVVrBsAodK4/s640/selection.png" width="640" /></a></div>
<br />
pic-2<br />
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
<br />
<div style="margin-bottom: 0in;">
<span style="font-size: medium;"><b>3.2] Tournament
selection:-</b></span> It is also one of the popular method for
selection procedure. In this method we first set a value for the size
of tournament let it be k. Then we select k chromosomes randomly from
the population. Now we have (n/k) number of sets each containing k
chromosomes. Now select the chromosome with best fitness value from
each set. Thus we can select n/k number of chromosomes which will go
to matting pool.</div>
For example let the population contains 4 chromosome as<br />
chromosome no. Fitness value<br />
1 2<br />
2 1<br />
3 4<br />
4 3<br />
Now let k=2 and we combine chromosome 1 and 2 in a set and 3 and 4
in other. From first set chromosome 1 will be selected and from
second set chromosome 3 will be selected. Total 4/2=2 chromosome will
be selected for matting pool.<br />
<b><span style="font-size: large;"> 4]Crossover:-</span></b><span style="font-weight: normal;">
It is performed on selected chromosomes to generate offspring. The
idea behind crossover is that the offspring may inherit the good
traits from its parent and a better chromosome will evolve. Thus GA
offers an opportunity to share better solution from one to another.</span><br />
<span style="font-weight: normal;">First we need to find the
chromosomes from matting pool that will undergo crossover using
crossover rate. Crossover rate specifies the number of chromosomes
that will undergo the crossover operation. It will be in the range
[0,1]. To select chromosome from matting pool we will generate a
random number “r” with value [0,1], if “r” is less than the
Crossover rate then that chromosome will undergo crossover. Thus
total chromosome that will undergo crossover operation is Total
population * Crossover rate.</span><br />
<div style="font-weight: normal;">
Then Crossover operator operates on
the selected chromosomes in the following way..</div>
<div style="font-weight: normal; margin-bottom: 0in;">
[1]Choose a random
point on the two parents</div>
<div style="font-weight: normal; margin-bottom: 0in;">
[2]Split parents
at this crossover point</div>
<div style="font-weight: normal; margin-bottom: 0in;">
[3]Create children
by exchanging tails</div>
<div style="font-weight: normal; margin-bottom: 0in;">
Crossover may be
of various type like
</div>
<div style="margin-bottom: 0in;">
<b>Single Point :- </b><span style="font-weight: normal;">
In this case we randomly select a crossover point then swaps the
contents of the parent chromosomes. For example, let crossover point
be 5</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<u>Parent
chromosome</u><span style="text-decoration: none;"> </span><u>Child
chromosome</u></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<i><b>1278734919</b> <b>12787</b></i><span style="font-style: normal;"><u>47933</u></span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<u><span style="font-style: normal;">8911947933</span></u><i><span style="text-decoration: none;"> </span></i><u><span style="font-style: normal;">89119</span></u><i><span style="text-decoration: none;"><b>34919</b></span></i></div>
<div style="font-weight: normal; margin-bottom: 0in;">
</div>
<div style="margin-bottom: 0in;">
<b>Two Point:- </b><span style="font-weight: normal;">In
this case we randomly selects two crossover point and then swaps the
contents of the parent chromosomes. For the below example let the
crossover points be 3 and 7</span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<u>Parent
chromosome</u><span style="text-decoration: none;"> </span><u>Child
chromosome</u></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<i><b>1278734919</b>
<b>127</b><u>1947</u><b>919</b></i></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-style: normal;"><u>8911947933</u></span><i><span style="text-decoration: none;"> </span></i><span style="font-style: normal;"><u>891</u></span><span style="font-style: normal;"><span style="text-decoration: none;"><b>8734</b></span></span><span style="font-style: normal;"><u>933</u></span></div>
<div style="font-style: normal; font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<b>Uniform Point:- </b>bits are copied
from the first or from the second parent depending upon the mask
value ( 0 and 1 )that is generated randomly equal to the number of
bits in the chromosome. For example let the mask be 1100100110 (let 0
means copy from first parent to first child and 0 means copy from
second parent to first child).</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<u>Parent
chromosome</u><span style="text-decoration: none;"> <u></u></span><u>Child
chromosome</u></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<i><b>1278734919</b>
<b>12</b></i><span style="font-style: normal;"><u>11</u></span><i><b>7</b></i><span style="font-style: normal;"><u>47</u></span><i><b>91</b></i><span style="font-style: normal;"><u>3</u></span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<span style="font-style: normal;"><u>8911947933</u></span><i><span style="text-decoration: none;"> </span></i><span style="font-style: normal;"><u>89</u></span><i><span style="text-decoration: none;"><b>78</b></span></i><span style="font-style: normal;"><u>9</u></span><i><span style="text-decoration: none;"><b>34</b></span></i><span style="font-style: normal;"><u>93</u></span><i><span style="text-decoration: none;"><b>9</b></span></i></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<b><span style="font-size: medium;"> </span><span style="font-size: large;">5]
Mutation :-</span><span style="font-size: medium;"> </span></b><span style="font-size: small;"><span style="font-weight: normal;">During
the execution algorithm may stuck into a local optima that is
obviously not our required solution. To get rid of these situation we
can use the mutation operator.</span></span><b><span style="font-size: medium;"> </span></b><span style="font-size: small;"><span style="font-weight: normal;">It</span></span><b><span style="font-size: medium;">
</span></b><span style="font-weight: normal;">is the operator that
operated upon the selected chromosome. Mutation randomly selects some
mutation points and inverts the contents of those points. Thus
mutation enables GA to jump to a random area in the solution space.
The positions where mutation is taking place is called Mutation
point. We will use Mutation operator to select the bits of chromosome
where the mutation will take place. We can write algorithm for
mutation operator as:</span></div>
<ol>
<li><div style="font-weight: normal; margin-bottom: 0in;">
For each
chromosome (C) in matting pool</div>
</li>
<li><div style="font-weight: normal; margin-bottom: 0in;">
For each bit
in (C)</div>
</li>
<li><div style="font-weight: normal; margin-bottom: 0in;">
generate a
random number “r” in[0,1]</div>
</li>
<li><div style="font-weight: normal; margin-bottom: 0in;">
if
r<MUTATION_RATE then invert the bit</div>
</li>
</ol>
<div style="font-weight: normal; margin-bottom: 0in;">
Here the total
number of bits that will undergo mutation is equals to Number of
chromosomes in matting pool * chromosome length * MUTATION RATE .</div>
<div style="font-weight: normal; margin-bottom: 0in;">
For example let
there are two chromosomes (each of them of length 5) in matting pool
and let the MUTATION_RATE=0.4</div>
<div style="font-weight: normal; margin-bottom: 0in;">
10101 and 01010.
Now generate (5*2)=10 random numbers in[0,1] say,
0.1,0.5,0.3,0,7,0,3(for first chromosome ) and 0.6,0,35,0,24,0.9,0.12
(for second chromosome )</div>
<div style="margin-bottom: 0in;">
<span style="font-weight: normal;">so
for first chromosome 2</span><sup><span style="font-weight: normal;">nd</span></sup><span style="font-weight: normal;">
and 4</span><sup><span style="font-weight: normal;">th</span></sup><span style="font-weight: normal;">
bits will be inverted and for second chromosome 1</span><sup><span style="font-weight: normal;">st</span></sup><span style="font-weight: normal;">
and 4</span><sup><span style="font-weight: normal;">th</span></sup><span style="font-weight: normal;">
bits will be inverted. So the resultant chromosomes are: 1</span><b><i><u>1</u></i></b><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">1</span></span></span><b><i><u>1</u></i></b><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">1
and </span></span></span><b><i><u>1</u></i></b><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">10</span></span></span><b><i><u>0</u></i></b><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">0.</span></span></span></div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<b><span style="font-size: large;"> 6] Termination:-
</span></b><span style="font-weight: normal;">Evolution in the real
world of nature , is a continuous process. In the world of computing
“how long do we need to continue the GA to get a feasible
solution?” is a problem to be sorted out. In most of the problem we
do not know the best value of the fitness function. We therefore stop
the search when we feel that there has not been an improvement in
either the maximum or average fitness of the population over several
generations. The GA is then said to have done its work though here
is never a guarantee that the global optimum has been reached. </span>
</div>
<div style="font-weight: normal; margin-bottom: 0in;">
The algorithm may
take very long time to converge to a particular result where it may
provide a solution that is acceptable. In that case algorithm will
not stop unless we forcefully stop it. In that case we need to define
the termination condition other than getting a actual solution like
Acceptable error. Maximum allowable population may also be a
termination criteria as we GA sometime requires an enormous amount of
memory.</div>
<div style="font-weight: normal; margin-bottom: 0in;">
<br /></div>
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b><span style="text-decoration: none;">E]</span><u>Flowchart:-</u></b><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">
</span></span></span><span style="font-size: small;"><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;">We
can represent the whole idea of GA in a flowchart form as:</span></span></span></span></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-J2vBEFIohBI/UR9CLjk5CbI/AAAAAAAAAQA/QGnGB7U4St0/s1600/flowchart.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="454" src="http://1.bp.blogspot.com/-J2vBEFIohBI/UR9CLjk5CbI/AAAAAAAAAQA/QGnGB7U4St0/s640/flowchart.png" width="640" /></a></div>
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><span style="font-size: small;"><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;"> </span></span></span></span></span><br />
<span style="font-size: large;"><span style="font-size: small;"><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;"> pic-3</span></span></span></span></span></div>
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><span style="font-size: small;"><span style="font-style: normal;"><span style="text-decoration: none;"><span style="font-weight: normal;"><br /></span></span></span></span></span></div>
<div style="margin-bottom: 0in;">
<br />
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
</div>
<br />
<div style="margin-bottom: 0in; text-decoration: none;">
<span style="font-size: large;"><b>F]<u>Application</u>:-</b></span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;">Some of the fields where GA can be used are</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<br /></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"><i> <u><b>DOMAINS</b></u><b> </b><u><b>APPLICATION</b></u></i></span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Machine learning designing neural networks,
classification algorithms</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Signal Processing filter design</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Scheduling manufacturing, resource allocation</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Game playing poker,checker,Prisoner's dilemma</span></div>
<span style="font-size: small;"><span style="font-size: small;">O</span>ptimization traveling salesman, bin
packing, graph coloring</span>
<br />
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Robotics trajectory planning</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;"> Control missile evasion, pole balancing</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<br />
<span style="font-size: large;"><b>G]<u>Example</u>:-</b></span> <span style="font-size: small;">To show the use of GA I <span style="font-size: small;">hav<span style="font-size: small;">e used the <a href="http://www.it.lut.fi/ip/evo/functions/node26.html" target="_blank">Six-hump Camel Bac</a><span style="font-size: small;"><a href="http://www.it.lut.fi/ip/evo/functions/node26.html" target="_blank">k function</a>. I<span style="font-size: small;"> will<span style="font-size: small;"> try to <span style="font-size: small;">find the global minima of this f<span style="font-size: small;">unction using GA<span style="font-size: small;">. This function have total six m<span style="font-size: small;">inima, two of <span style="font-size: small;">them are global. <span style="font-size: small;">The functio<span style="font-size: small;">n is: </span></span></span></span></span></span></span></span></span></span></span></span></span><img align="MIDDLE" alt="$\displaystyle f_{m2}(\vec x)=(4-2.1x_1^2+\frac{x_1^4}{3})x_1^2+x_1x_2+(-4+4x_2^2)x_2^2
$" border="0" height="65" src="http://www.it.lut.fi/ip/evo/functions/img113.png" width="426" /></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;">
<style type="text/css">
<!--
@page { margin: 0.79in }
P { margin-bottom: 0.08in }
</style>
</span></div>
with -1.9<=x1<=1.9 and -1.1<=x2<=1.1<br />
This is the 3-D plot of the function:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-f7DSMK9xVZM/UWwU5bLqwsI/AAAAAAAAAUI/1XYF9naNY9o/s1600/6hc.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="263" src="http://2.bp.blogspot.com/-f7DSMK9xVZM/UWwU5bLqwsI/AAAAAAAAAUI/1XYF9naNY9o/s1600/6hc.png" width="320" /></a></div>
and this is the contour plot of the function showing 4 local minima and 2 global minima:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-dSMoM1Ff9B4/UWwVNpGP2KI/AAAAAAAAAUQ/8A-N5rkpMFI/s1600/7hc_con.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="247" src="http://2.bp.blogspot.com/-dSMoM1Ff9B4/UWwVNpGP2KI/AAAAAAAAAUQ/8A-N5rkpMFI/s1600/7hc_con.png" width="320" /></a></div>
<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<br />
I will use a package "<a href="http://cran.r-project.org/web/packages/genalg/" target="_blank">genalg</a>" in language <a href="http://en.wikipedia.org/wiki/R_%28programming_language%29" target="_blank">R</a> in this purpose. This package provides a function "rbga" to implement floating point GA. This function requires a user specified evaluation function. Here is my evaluation function:<br />
<br />
evaluate_shortest_path<-function(string=c())<br />
{<br />
returnValue <- (4-(2.1*string[1]^2)+(string[1]^4/3)) * string[1]^2 + (string[1] * string[2] ) + ( -4 + (4 * string[2]^2)) * string[2]^2;<br />
returnValue<br />
}<br />
<br />
and here is the function call to GA:<br />
rbga.results=rbga(c(-1.9,-1.1),c(1.9,1.1),monitorFunc=NULL,evalFunc=evaluate_shortest_path,<br />
mutationChance=0.1,popSize=50,iters=2000)<br />
and result can be checked as:<br />
summary (rbga.results, T)<br />
<br />
<blockquote class="tr_bq">
GA Settings<br />
Type = floats chromosome<br />
Population size = 50<br />
Number of Generations = 2000<br />
Elitism = 10<br />
Mutation Chance = 0.1<br />
<br />
Search Domain<br />
Var 1 = [-1.9,1.9]<br />
Var 2 = [-1.1,1.1]<br />
<br />
GA Results<br />
Best Solution : -0.0899352302238796 0.712727474793792 </blockquote>
This result is close to one of the global minima: x1=-0.089842, x2=0.712656.<br />
<div style="margin-bottom: 0in;">
<span style="font-size: large;"><b>H]</b><u><b>References</b></u><span style="text-decoration: none;"><b>:-</b></span></span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;">[1] <a href="http://www.obitko.com/tutorials/" target="_blank">http://www.obitko.com/</a><span style="font-size: small;"></span>
</span>
</div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;">[<span style="font-size: small;">2</span>] “Genetic Algorithms in search, Optimization and
Machine Learning” by David E. Goldberg</span></div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<span style="font-size: small;">[<span style="font-size: small;">3</span>] “Neural Networks,Fuzzy Logic and Genetic
Algorithms--synthesis and applications” by S.Rajasekaran and G.A.
Vijayalakshmi Pai. </span>
</div>
<div style="font-weight: normal; margin-bottom: 0in; text-decoration: none;">
<br /></div>
</div>
</div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0tag:blogger.com,1999:blog-4512121268692891574.post-29895410651169807692012-11-02T02:37:00.000+05:302013-04-08T02:28:45.184+05:30Terminal<div dir="ltr" style="text-align: left;" trbidi="on">
I never tried to write blogs before. After continuous motivation from Arjun Pakrashi (one of my close friends ), starting to write blog posts. I just watched the movie <a href="http://www.imdb.com/title/tt0362227/"><i><u>The Terminal</u></i></a> by <i><u>Steven Spielberg</u></i>. Each movie by him, that I have seen are just his genius creation. In this movie central character <a href="http://www.imdb.com/name/nm0000158/?ref_=fn_al_nm_1"><u><i>Tom Hanks</i></u></a> is just awesome. Actually all his movies are just awesome. This is a story of a man Victor Navorski from Krakozhia. He came to know that his country has suspended all travelling privileges on passports as a result of military coup in his country. Airport authority allows him to enter International Transit Lounge until all the problems are sorted out. Then he stumbles upon everything he tries to do there mostly because of his poor English. Gradually he starts to adjust with the area and its people. Meanwhile he helps a man from Russia carying medicines for his dying father and becomes popular. He meets Amelia and slowly falls in her love. Director beautifully showed all the emotions of Victor, regarding his country, Amelia and all his terminal friends. He nicely pictured the situations where Victor faced various problems. He spends a long time in that lounge just to get a chance to go USA and get a signature from Benny Golson which his father did'nt get. Most of the part of the story took place in that airport lounge and demonstrated beautifully with all the feelings and details which the Steven Spielberg always does with his movie. </div>
Fuzzyhttp://www.blogger.com/profile/18129368952871397921noreply@blogger.com0