Graph Traversal

Graph in the simplest terms is a representation of some real world fact in terms of nodes and edges. It consists of a collection of nodes and a set of edges connecting them. In a general graph, there is no restriction on  type of nodes that can be connected by an edge.


Tree on the other hand are special case of graph where there exists exactly one path between each pair of nodes. A tree is just connected. Adding even a single edge results in a cycle. So a tree with n nodes has n-1 edges.

Traversal
When graph represent some real world entity and we want to examine all the nodes which are connected to each other then its called traversing a graph. Since a general graph can contain a cycle, hence algorithms do exists to avoid such issues. In this blog i will be covering about most recognized graph traversal algorithms. Many of these algorithms are also related to tree traversal. We will be discussing about following graph traversal algorithms
1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Prim' Algorithm
4. Kruskal's Algorithm
5. Dijkstra's Algorithm (Single Source Shortest Path )
6. Bellman Ford Algorithm ( Single Source Shortest Path )
7. Floyd Warshall Algorithm (All Pair Shortest Path )

Some of coomon terminology used are
SSSP i.e. Single source shortest path in which we try to find optimum traversal strategy so that all the nodes are at a shortest distance from a particular node.
All Pair is the generalized form of SSSP algorithm. In this, we try to find shortest path between all pair of vertices. i.e. overall distance is minimum.
----------------------------------------------------------------------------------------------
1. Breath First Search


2. Depth First Search


3. Prim's Algorithm
It finds spanning tree in only one of connected graph.

4. Kruskal's Algorithm
If the graph consist of multiple disjoint connected graph then it finds minimum spanning tree in each of graph at once.

5. Dijkstra's Algorithm
SSSP where each node has non negative weight

6. Bellman Ford Algorithm
SSSP where nodes can have negative weight but any cycle with negative value should not exist.
It is interesting to know that a similar problem i.e. graph where negative weight cycle exists, and shortest path finding such that no edge appears twice is NP complete problem

7. Floyd Warshall's Algorithm

XML parsing made easy

Hi All,
   If you are a programmer, then XML is not a new term for you.

Extensible Markup Language : Simple and universal data representation format. They can be used to represent any structure or any nested and complicated data structure.
  While using on your system typically you transmit your data from one system to another using either a file or some object. As file do not store structure and object are programming language dependent. So, they both have limitation.
   To overcome these issues, XML is a better option. XML, like a file stores data in the form of human readable files and also preserves the structure. But a question that is obvious is how to convert a data in program into XML file and vice versa. This typical problem is Serialization and deserialization.

  Writing XML using Simple files is fine but deserialization will become difficult. Also both client and server must share their representation which is difficult. Even more challenging is data validation. As the structure becomes complex you will tend to commit sucide..


But Wait.
There is a better and clean way to express yourself. :)
There is a way which allows you to express your XML to program bridge using a representation. Yes, we are talking about Simple XML parser.

http://simple.sourceforge.net/


More information about this later.. :)

First Things first

So, its been a long time since my last post.

Even i'm bored of my boring life..
So, the best way to keep yourself interested is to keep on learning new stuff.
Starts from today :)

From now on, i will try to learn atleast one new thing and will try to post it here. :)

-------------------------------------------------------------------------------------------------------------
Starts with JRebel Today ..


Have you ever spent hours and hours of your time developing some web application and trying to fix a bug or trying to improve it..

Have you ever encountered a moment where you just sit in front of computer and wait for next 5 minutes starring at it and wishing if this time its loaded faster than last time ..

If not then this post is probably not for you..
If you already have the same pain then welcome to the world of JRebel.

JRebel Automatically reloads the class file simply by pastiing the jar file and replacing the older value.
Read this interesting article.
http://zeroturnaround.com/blog/reloading-objects-classes-classloaders/

This explains what is so great task that JRebel does.




http://zeroturnaround.com/jrebel/

802.XX Standards

802.XX standards came into existence by IEEE. Various IEEE standards for the same are:-


Ø 802.1 is an internetworking standard for compatibility of different LANs and MANs across protocols.

Ø 802.2 Logical link control (LLC) is the upper sublayer of the data link layer which is non-architecture-specific, that is remains the same for all IEEE-defined LANs.

Ø Ethernet LAN (802.3),

Ø Token ring LAN (802.4),


Ø Token bus LAN (802.5).

Ø 802.6 is distributed queue dual bus (DQDB) designed to be used in MANs.

Interesting, isn't it ?

Connection Oriented Versus Connection less

There are 3 terms.
1. Circuit Switched N/w
2. Datagram N/w
3. Virtual Circuit N/w.

All the 3 types of network can be established by using same infrastructure. but in each case, every node behaves differently. Lets see what each type of network does.

1. Circuit Switched N/w :
    Infrastructure is considered to be consisting of many physical links which are connected using switches. Each link is divided into channels.
    So, the link is like a road on high way. And the channels are lane on the road. this analogy is sufficient to understand the meaning of channel and its significance also.
   
   In Circuit Switched N/w before the call is established or before the data transmission, intermediate route is determined and is reserved for the same purpose. So, link x's channel y is reserved for a particular duration of time for a specific data transfer. Before the time ends even if channel is idle, it is considered as busy and no one else can access it.

   This gives the guarantee regarding QoS of the data. As far as reliability is concerned, it depends on whether the intermediate links are active during entire session. Even if one channel fails or one link fails the entire set up fails and need to be closed. And here the links are truly dedicated to particular connection.

    Hence it is considered as fully dedicated. So the major disadvantage of the system is that resource utilization is poor, as can be seen from the idea of protocol itself. Connection establishment and teardown both requires certain amount of time.

2. Datagram N/w:
    As the above mentioned protocol is very very poor in terms of resource utilization, another better technique is decided i.e. Datagram n/w. In this technique, the entire n/w is considered to be  same as above, set of physical links and nodes. Each node has its routing table. Now, when the request is sent, it can go from anywhere, it just has to reach the desitnation. Each node can see where to route the packet and can forward them accordingly.

   The end user is expected to have a high buffer size so that incoming packets if reached in any order can be assembled. Hence, generally a minimum and maximum allowed time for the packet is always decided so that it goes to destination without buffer overflow.

   The major advantage of the system is that, Resource utilization is very high. And the reliability is maximum as the packet will reach destinaiton as long as there is at least one path possible. The major disadvantage of the system is that QoS cannot be guaranteed. Infact it may vary over a period of time. So, for initial 3 minutes you may get very clear sound quality and after that the sound is not even audible. So, for certain important data transmission, where QoS is very important , it cannot be used much. No time is required for Connection establishment and teardown.


3. Virtual Circuit N/w:
    Virtual Circuit is the combination of above 2 in one. So, like the Circuit switched a virtual circuit is set up but the same circuit can be shared among many types of data transmission. So, all the pkts going from source to destination goes through same set of nodes. But different set of packets may go through same set of nodes if desired. Also if certain link fails then packet stram can be forwarded to another node and the node can be changed accordingly.

    This makes it possible to give very high Reliability and optimum uses of resources is possible. QoS, if desired can be provided for the data transmission. Connection establishment and teardown both requires certain amount of time.


If you want to share something more about the same, please do add more to it. !!!

Variations of Turing Machine

Turing Machine represents a model of computational machine with equivalent computational power with respect to any computer.

Computational power of a device is class of problems which can be solved by it.

It was realized later that a Finite Automata can recognize basic patterns in the given input called as Regular Expression.

A FA with one extra stack has more computational power than a FA with no stack. Also called as PDA.
A PDA with one more extra stack has even more computational power than a PDA can solve more general class of problems. also called as TM.

Interestingly, TM has most computational power and adding any thing else to it only increases the speed which with the calculation can be done and not the computational power.
Hence, various Automata have been stated with minor variations to TM which are even equally powerful.

1. Turing machine with Stay Option:
2. Turing machine with multiple tracks.
3. TM with semi infinite tape.
4. Offline Turing Machine.
5. Multi dimensional TM
6. Non Deterministic TM
7. Universal TM


But there are various ways to reduce its power for example.

1. A pushdown automaton can be regarded as a Non Deterministic TM with a tape that is restricted to being used as a stack.
2. Also a finite automata is a turing machine where only a finite part of the tape can be used as work space.
3. Another Interesting automata is Linearly bounded Automata in which you strict the tape length to be exactly same as input length.

It is still not known whether Deterministic and Non deterministic LBA's are equivalent or not..
But LBA are less powerful than TM but more powerful than a PDA.

Concurrency Control

Maintaining synchronization among concurrently executing processes is a challenging task. Hence a general idea is use LOCK constructs on data item to maintain consistency and access control to them. The idea is that at a time if one process or thread is updating some variable then no other thread or process can either write or even read the same variable. Various Locking protocols are :--->

1. Two phase Locking

  1.1 Strict Two phase Locking

  1.2 Rigorous Two phase Locking

2. Graph Protocol

3. Time Stamp Protocol

4. Validation based protocol

One of very strange thing was if there are more than one copies of a variable present in distributed manner, then how to do updation ? is it necessary to update all the copies ?? sometimes it is not possible and not even efficient to update them all. 

There is one protocol developed for the same problem which i really liked very much. Its m isto n protocol (dont' remember the exact name).

According to this protocol, when you are trying to read some value whose values are distributed among different machines, to avoid inconsistency and to maintain efficiency, update atleast half of the values. Similarly, while reading read from atleast half the values.

Tree Predecessor and Successor

In a tree, any node is predecessor and successor of itself.

--> so, the intersection of predecessor set and successor set is the node itself.

Also height and depth of a node in a tree are different things.

Height is calculated from leaf
It is distance of node from farthermost leaf node who is its successor.


Depth is calculated from root.
It is length of a path from root to the node.

Connection versus Session

Often people who are studying the networking are confused with the concept of What is difference between connection and session.

Connection and Session are different Things Altogether

A connection is a transport level connection between two peers, used to send and receive Diameter messages.
A session is a logical concept at the application layer, and is shared between an access device and a server, and is identified via the Session-Id AVP.


+--------+            +---------+             +----------+
| Client |             | Relay |              | Server |
+--------+            +---------+             +----------+


           <---------->           <----------->
     peer connection A    peer connection B


<------------------------------------------------------------>
                      User session x






[From RFC 3588]

ASCII Encoding

ASCII Characters are only 7 bit in size for representation.
Still 1 byte per character is used for storage.

Because,

Additional one bit stores the parity.


So, the 8 bit code has Error Detection Capability up to one bit but no error correction capability.

Chromatic Number For different types of Graph

Chromatic Number: Minimum no of colors to color a node.

Graph Type                                      Chormatic no.
--------------------------------------------------------------------------
Complete Graph (G(kn) )                           n
Cyclic Graph (Cn)                                     3           (n = odd)
                                                               2           (n = even)
Star Graph (Sn)                                        2
Wheel Graph (Wn)                                    3           (n = odd)
                                                               4           (n = even)
Bipartile Graph                                          2

Facts in Relations

* Number of distinct binary relations of n elements is 2^(n^2).

* Number of reflexive relation of n elements is 2^((n^2)-n).* Number of distinct irreflexive relations of n elements is.2^((n^2)-n)
* Number of symmetric relation of n elements is.... 2^((n^2)+n)/2...* Number of distinct anti symmetric relations of n elements is 2^n *3^((n^2)-n)/2* Number of Asymmetric relation of n elements is 3^((n^2)-n)/2

Terminology in Graph Theory

Some Of Graph Theory Related Terminology.

* Loop: An edge connecting a vertex to itself.

* Directed Edge: Each edge has a direction.

* Simple Graph: Graph with no loops or multi-edges.

* Walk: A sequence v0e1v1 . . . envn.

* Trail: A walk with distinct edges.

* Path: A trail with distinct vertices.

* Connected Graph: A graph where there exists a path between any two vertices.

* Component: A maximal connected subgraph.

* Tree: A connected acyclic graph.

* Free tree: A tree with no root.

* DAG: Directed acyclic graph.

* Eulerian Graph: Graph with a trail visiting each edge exactly once.

* Hamiltonian Graph: Graph with a cycle visiting each vertex exactly once.

* Cut: A set of edges whose removal increases the number of components.

* Cut-set: A minimal cut.

* Cut-edge: A size 1 cut.

* k-Connected: A graph connected with the removal of any k − 1 vertices.

* k-Regular: A graph where all vertices have degree k.

* k-Factor: A k-regular spanning subgraph.

* Matching: A set of edges, no two of which are adjacent.

* Clique: A set of vertices, all of which are adjacent.

* Independent set: A set of vertices, none of which are adjacent.

* Vertex cover: A set of vertices which cover all edges.

* Planar graph: A graph which can be embeded in the plane.

* Plane graph: An embedding of a planar graph.

Various Well known Services and their Port numbers

Port-      TCP/UDP             Protocol

7                                           Echo

20           TCP                       FTP—data transfer

21           TCP                       FTP—control

22                                         SSH

23                                         Telnet

25           TCP                       Simple Mail Transfer Protocol (SMTP)

53           TCP, UDP              Domain Name System (DNS)

67                                          DCHP Server

68                                          DHCP Client

69                                          TFTP (Initialization)

80           TCP, UDP              Hyper Text Transfer Protocol (HTTP)

109         TCP                        Post Office Protocol v2 (POP2)

110         TCP                        Post Office Protocol v3 (POP3)

443         TCP                        HTTPS (HTTP Over SSL/TLS)

465         TCP                        SMTP over SSL

546                                         DHCP Client(IP v6)

547                                         DHCP Server(IP v6)

587         TCP                        E-mail message submission (SMTP)

Thanks to Meraj Khan and Chankey Pathak, my friends for suggesting more port numbers.

Serializability

1. Conflict Serializable :-- If a given schedule can be converted to another one without swapping two conflicting instructions then its conflict serializable. (A bit more strict)

Testing whether a particular schedule is conflict serializabile is a simple polynomial time complex problem. 

2. View Serializable :-- A superset of above, where for external person two schedule produce same output and no inconsistency. ( A bit more lenient)

Testing whether a particular schedule is view serializable is an NP complete problem.

Complexity Classes

Different Types of Complexity Classes :-

P Type: They can be solved by Deterministic Turing Machine in Polynomial time.

NP Type: They can be solved by Non Deterministic Turing Machine in Polynomial time.

NP Complete: Hardest Problems set in NP Type. (Any NP can be converted to another NP in polynomial time)

NP Hard: Any NP complete problem can be reduced to NP Hard Problem in Polynomial time. So, at least as hard as any NP complete problem.

Note:--

NP Hard are either NP complete or those kind of problems which are even harder than NP type. So It can be above NP also.

Automata & Complexity Theory.

Computational science is one of very interesting subject. It's an abstract topic but something which i believe to be most essential for anyone who wants to learn Computers. Learning about this won't help you to write a program or to understand how to build a computer but it will help you to understand the limitation of any mechanical computational device in terms of what kinds of problems it can solve.

Most of books discuss about only 3 categories of Devices i.e.
1. Finite Automata
2. Push down Automata and
3. Turing Machine.

FA is mainly concern with basic computation including matching whether a particular input satisfies any specified pattern or not. These devices are memory-less so they cannot count the occurrence of any specific alphabet. They are very limited in terms of expressiveness yet very helpful.

PDA are mainly concerned with Context Free Grammars i.e. Non Ambiguous Grammars. They have infinite amount of memory which is provided by a stack. They are mainly used for parsing of an expression. So, any compiler you see or any XML parser you see, all have Context Free Grammar. For someone from non CS background, a CFG is a grammar where if you write any statement then it can always be evaluated to one value only not the other.

Turing Machines are computational device which are equivalent in terms of computational power to a computer. So, anything you can do with a computer can be done with a Turing Machine. In fact all the programming languages are expected to be Turing Complete. The grammar is called Unrestricted Grammar.


------------------------------------------------------------------------------------------------------------

Now, above all you can get from any other TCS book, and its their in every syllabus.
Having said above, do you really think all kinds of computational machines can be represented by above 3 automata ??


If you say yes, then think again, what about parallel processing and what about distributed system ???
can you represent this entire world and interaction among all the living species ??
can you represent the complex patterns which occur in this world ???


Yes, these kind of things can also be represented using an automata ...

GATE 2012

Hi All,

    Well, if you are preparing for GATE 2012 then i would like to wish you good Luck. As of now you might have already known that this year GATE exam is being organized by IIT Delhi. Check out the web site for more details.. http://gate.iitd.ac.in/GATE/

   And dont' expect me to put all the news updates regarding GATE. If you want to then you can subscribe to the http://inspirenignite.com/ and you'll get free alerts and all the updates.

   Nothing else to say...

Good luck :)

Welcome to Blog..

Hi All,
   Welcome to my blog. To introduce myself, I am Mahesh Gupta, BE Computer Engineer from Mumbai University. I'm currently working with Rancore Technologies.

   Well, I am one of those people who believe in understanding things and believe in passion rather than working to get some grades or certificate. I love CS because I consider it as a science rather than Computer Engineering.

   A Great thanks to my Elder brother Dinesh Gupta who is my greatest inspiration and ideal and who always motivated me to do something i love.

   Through this blog, I'm trying to highlight some of very interesting facts on Computer Science which I've noted. As of now, my posts are mainly focused on posting those posts which are important for anyone who is preparing for GATE exam.

   As time goes, I might publish some other posts related to Computer Science .

   So, you can enjoy reading my blog and feel free to post your comments and suggestion where ever you feel that i'm not right or somewhere you can give more refinements.

   Welcome to My Blog... :)