Today had been in fact a busy day when compared to the last
two days. We discussed many new and interesting things. The discussions started
with Hamiltonian path. Unlike the Euler path this one has a requisite of
visiting the entire vertices just once, one at a time. This is similar to the
case as travelling salesman problem. There is no hard and fast rule to
determine if a path is Hamiltonian or not as Euler path and hence only a trial
and error will solve the problem. And hence TSP and Hamiltonian have a
complexity other than polynomial time. Algorithms having polynomial time
complexity are known as P class algorithms and those which do not have are
known as NP class/ Non deterministic algorithms.
Data encryption
and decryption had been an interesting topic. RSA algorithm is used to for the
purpose. Every data transferred across the web is encoded in PRIVATE PUBLIC
RELATION. Encryption using public key follows a P class algorithm, decryption using a private key follows a P class algorithm whereas decrypting using a
public key follows an NP class algorithm.NP class algorithms have not been
solved yet. There is a NP complete set which is a subset of NP class. i.e if we
have a solution for any of the NP class algorithms then we can solve all the
other problems. This will be a revolution that will change the face of the
world!!!!!!!!!!!!!!
Yes …we then came to the most interesting part The Machine Design.
Alphabets are the basic building blocks just as in any other
language. It is represented by epsilon. String of these alphabets forms the
language. We did the machine design to accept given set of
alphabets and language. When there is only one choice for alphabets from all
the states in machine then they are called DETERMINISTIC FINITE STATE
AUTOMACHINE and those with multiple choices at any state are NON DETERMINISTIC
FINITE STATE MACHINE. In NFA there are many parallel paths to reach the answer.
When the power of alphabets increases say for eg: to design a machine with
language L= {0n , 1n } simple states will not be
sufficient and hence we will have to go for stack. Such machines with
additional power of stacks are called PUSH DOWN automata.
Next session was about the Octave
programming language. Octave language is used for numerical/matrix
calculations. We worked out a code to find the square root of a number using
bisection method. Next up we attended a session on DATA STREAM ALGORITHM AND
APPLICATION by Dr. Naveen Sivadasan of
IIT Hyderabad . It was quite a different topic for me. It deals with the
difficulties faced to develop an algorithm to monitor streams of data exploding through the internet.
No comments:
Post a Comment