Graph Definition

Graph Definition

 

A graph is a kind of data structure, which is a collection of nodes, called vertices and line segments called arcs or edges that connect pairs of nodes.

         In the concept of mathematics, a graph G is defined as follows: G=(V,E), where V is a finite, non-empty set of vertices (singular vertex) and E is a set of edges (links between pairs of vertices).  When the edges in a graph have no direction, the graph is called undirected, otherwise called directed.

Cycle:A cycle is a path consisting of at least three vertices that starts and ends with same vertex. Two vertices are said to be connected if there is a path between them.

• A directed graph is strongly connected if there is a path from each vertex to every other vertex in the graph.
• A directed graph is weakly connected if at least two vertices are not connected.
• Adjacency list: An adjacency list is the representation of all edges or arcs in a graph as a list.
• Adjacency matrix: The adjacency matrix uses a vector (one-dimensional array) for the vertices and a matrix (two –dimensional array) to store the edges.

• Depth First Traversal: In the depth first traversal. We process all of the vertex’s descendants before we move to an adjacent vertex. It uses stack to store the nodes.
• Breadth – First Traversal: In the breadth – first traversal of a graph, we process all adjacent vertices of a vertex before going to the next level. The breadth – first traversal uses a queue rather than a stack. As we process each vertex, we place all of its adjacent vertices in the queue.

• Spanning trees: A spanning tree of a graph is an undirected tree consisting of only those edges necessary to connect all the nodes in the original graph.
• Network: A network is a graph that has weights or costs associated with its edges. It is also called weighted graph.
• Minimum Spanning Tree: This is a spanning tree that covers all vertices of a network such that the sum of costs of its edges is minimum. There are two algorithms which are:

           1)      Kruskals algorithm     2) Prims algorithm

• Forest: An undirected graph which contains no cycles is called a forest.  A directed acyclic graph is often referred to as dag.
• Complete graph: A graph is said to be complete if there is an edge between every pair of vertices.
• Bipartite graph: A graph is said to be bipartite if the vertices can be split into sets V1 and V2. Such there are no edges between two vertices of V1 or vertices of V2.

• Uniformed search: A problem consists of four parts: the initial state, a set of operators, a goal test function, a path cost function. A path through the state space from the initial state to a goal state is a solution.

Search algorithms are judged on the basis of completeness, optimally, time complexity and space complexity.

• Completeness:It is the strategy guaranteed to find a solution when there in one.
• Time complexity: It is the how long does it take to find a solution.
• Space complexity: It is the how much memory needs to perform the search.
• Optimality: Does the strategy find the highest quality solution when there are several different solutions.

Breadth first search: Expands the shallowest node in the search tree first. It is complete optimal for unit-cost operations, and has time and space complexity of O(b^{^d}). The space complexity makes it impractical in most cases. Using BFS Strategy, the root node is expanded first, then all the nodes generated by the root node are expanded next, and their successors and so on.

Uniform cost search: Expands the least – cost leaf nod first. It is complete, and unlike breadth-first search is optimal even when operators have differing costs. It’s space and time complexity are the same as BFS.

Depth- First search: Expands the deepest node in the search tree first. It is neither complete nor optimal, and has time complexity of O(b^{^m}) and space complexity of O(bm), where m is the maximum depth. In search trees of large of finite depth, the time complexity makes this impractical.

Depth-Limited search: Places a limit on how deep a depth-first search can go. If the limit happens to be equal to the depth of shallowest goal state, then the time and space complexity are minimized.

Iterative deepening search: Calls depth – limited search with increasing limits until a goal is found. It is completed and optimal, and has time complexity of O(b^{^d}).

Bidirectional search: Can enormously reduce time complexity, but is not always applicable. Its memory requirements may be impractical. BDS simultaneously search both forward form the initial state and backward from the goal and stop when the two search meet in the middle.

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree

For more other Posts: Click Here

Definition of Tree

Definition of Tree

A tree is a combination of a finite set of elements, called nodes and a finite set of directed lines, called branches that connect the nodes.

The number of branches associated with a node is the degree of the node. When the branch is directed towards the node, it is an indegree branch. When the branch is directed away from the node, it is an out degree branch, the sum of outdegree and indegree branches equal to the degree of the node.

Some important terms:

• Root node: If the tree is non empty, then the first node is called as root. The indegree of root by definition is zero.
• Leaf node: A node with no successors (nodes after it). There will usually be many leaves in a tree.
• Non Leaf node: A node which has both a parent and at least one child.
• Internal nodes: Nodes that are not root and not leaf are called as internal nodes
• Parent node: A node is a parent if it has successor nodes; means out degree greater than zero.
• Child node: A node is child node if indegree is one.
• Siblings: Two or more nodes with same parent are siblings.
• Ancestor node: An ancestor is any node in the path from the root to the node.
• Descendant node: A descendent is any node on the path below the parent node.
• Subtree: A subtree is any connected structure below the root.
• Directed tree: A directed tree is an acyclic digraph, which has only one node with indegree 0, and others nodes have indegree 1.
• Binary tree: A binary tree is a tree in which no node can have more than two subtrees. In other word it is a directed tree in which outdegree of each node is less than or equal to two. (i.e. zero, one or two). An empty tree is also a binary tree.
• Strictly binary tree: If the outdegree of every node in a tree is either 0 or 2, then the tree is said to be strictly binary tree. i.e. each node can have maximum two children or empty left and empty right child.
• Complete binary tree: A strictly binary tree in which the number of nodes at any level i is 2 i-1 then the tree is said to be complete binary tree.
• Almost binary tree: A tree of depth d is an almost complete binary tree, if the tree is complete up to the level d-1.
• Tree traversals: Tree traversal is the technique in which each node in the tree is processed or visited exactly once systematically one after the other. The different tree traversal techniques are Inorder, Preorder and Postorder.Algorithm for tree traversal

     i) Inorder (Left-Root-Right)

• Traverse the left sub tree in inorder [L]
• Process the root node [N]
•  Traverse the right sub tree in inorder [R]

     ii) Preorder (Root-Left-Right)

• Process the root node [N]
• Traverse the left sub tree in preorder [L]
• Traverse the right sub tree in Preorder [R]

     iii) Postorder (Left-Right-Root)

• Traverse the left subtree in post order. [L]
• Traverse the Right sub tree in postorder [R]
• Process the root node [N]

Binary Search tree: A binary search tree is a binary tree in which for each node say x in the tree elements in the left subtree are less than info(x) and elements in the left subtree are greater or equal to info(x).

The operations performed on binary search tree are:

•  Insertion: An item is inserted
•  Searching: Search for a specific item in the tree.
•  Deletion: Deleting a node from a given tree.

Balanced Search trees: Balanced search tree is on that exhibits a good ratio of breadth to depth. There are special classes of Balanced Search Trees that are self-balancing. That is as new nodes are added or existing nodes are deleted, these Balanced search Trees automatically adjust their topology to maintain an optimal balance. With an ideal balance, the running time for inserts, searches, and deletes even in the worst case is log2n.

AVL trees, Red-Black trees, Lemma are the examples of balanced search trees.

AVL Trees: An AVL tree is a binary search tree whose left subtree and right subtree differ in height by at most 1 unit, and whose left and right trees are also AVL trees.

To maintain balance in a height balanced binary tree, each node will have to keep an additional piece of information that is needed to efficiently maintain balance in the tree after every insert and delete operation has been performed. For an AVL tree, this additional piece of information is called the balance factor and it indicates if the difference in height between the left and right subtrees is the same or, if not, which of the two subtrees has height one unit larger. If a node has a balance factor rh(right high). It indicates that the height of the left subtree. Similarly the balance factor for a node could be lh(left height) or eh(equal height).

Binary Heap tree: A binary heap is a complete binary tree. A tree that is completely filled except possibly at the bottom level, which is filled from left to right with no missing nodes.

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Graph Definition

For more other Posts: Click Here

Definition of List and Linked List

Definition of List and Linked List

List is a generic term for a collection of objects. It may or may not contain duplicates and application may or may not require that it be kept in specified order.

The functions defined to operate on a list are

·         Insert:  Insert a new entry into a list
·         Delete: Delete an entry from list
·         Length: Compute length of a list
·         Next: Return the next element in a list
·         Search: Search if an element is in a list

Linear list: A linear list is a sequence of n>=0 nodes x[1], x[2], x[3] ……………x[n] whose essential structural properties between items as they appear in a line.

Restricted list: In restricted list, Data can only be added or deleted at the ends of a structure and processing is restricted to operations at the end of lists.

The two restricted list structures are First In First Out (FIFO) stacks and Last In First Out (LIFO) queue.

The four operations performed on linear lists are

         i.            Insertion
       ii.            Deletion
      iii.            Retrieval
     iv.            Traversal

         Depending on the type of linear list, an insertion can be made at the beginning of the list, or at the end of the lists. When inserting data into ordered list, the data must be inserted so that the ordering is maintained. Deletion from general lists requires that the list be searched for the data to be deleted.

List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the lists.

List traversal is a special case of retrieval in which all the elements are retrieved in a sequence.

Definition of Linked list

A link list is a collection of records, called nodes, each containing at least one field(member) that gives the location of the next node contains two members; a data member (the value of the list item) and a link member (a value locating the next node).The link list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built.

The Typical basic linked-list operations are

         i.            Create: Makes a new linked list
       ii.            Insert: Puts a new node in its place in the list.
      iii.            Remove: Remove a node from the list.
     iv.            Traverse: This function allow user to visit each node in the list.
       v.            Is empty: The function returns a true/false indication of whether or not there are any nodes in the list.
     vi.            Is full: This function returns a true/false indication of whether or not the list is full

Types of linked lists

         i.            Singly linked lists
       ii.            Circular singly linked lists
      iii.            Doubly linked lists
     iv.            Circular Doubly linked lists

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Tree
• Graph Definition

For more other Posts: Click Here

Definition of Queues

Definition of Queues

A queue is defined as a special type of data structure where elements are inserted from one end and elements are deleted from other end.

The end from where the elements are inserted is called rear end (r) and the end from where elements are deleted called front end (f). In a queue always elements are inserted from the rear end and elements are deleted from the front end.

Queue is a linear list for which all insertions are made at the end of the list; all deletions (and usually all accesses) are made at the other end. So queue is also called First in First out (FIFO) data.

Different types of queues

1. Ordinary queue
2. Double ended queue
3. Circular queue
4. Priority queue

1. Ordinary queue

 

This queue operates on the first come first serve basis. Items will be inserted from one end and they are deleted at the other end in the same order in which they are inserted. A queue can be represented by using an array by using an array as shown in the figure.


The operations that can be performed on these queues are

• Insert an item at the rear end
• Delete an item from the front end
• Display the contents of the queue

Disadvantage of Ordinary queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1, so item cannot be inserted into the queue.

2. Double ended queue (Deque)

Another type of queue called double ended queue also called Deque. Deque is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue. The operations can be performed on Deques are

• Insert an item from front end
• Insert an item from rear end
• Delete an item from front end
• Delete and item from rear end
• Display the contents of queue

3. Circular queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1 item cannot be inserted. But this disadvantage is overcome using circular queue. In circular queue an item can be published circularly. This can be achieved using the statement r = (r+1)%QUEUE_SIZE


The operations can be performed on circular queue are.

• Insert an item from rear end
• Delete an item from front end
• Display queue contents

4. Priority queue

Such a queue where a job is processed based on the priority is called a priority queue

Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

Fundamental of data structures

Fundamental of data structures

What is data Structure?

A data Structure is the organization of data in computers memory or in a file.

Some examples of data structures are: array, stack, queue, link list, binary tree hash table, heap and graph. Data structures are often used to build databases. Typically, data structures are manipulated using various algorithms.

Based on the concept of Abstract data types (ADT), we define data structure by the following three components.

1.       Operations: Specifications of external appearance of data structure.
2.     Storage Structures: Organizations of data implemented in lower-level data structures.
3.       Algorithms: Description on how to manipulate information in the storage structures to obtain the results defined for operations.

Implementation of Data Structure

There are three levels of implementation of data structure which are:
1. The Abstract Level: The abstract (or logical) level is the specifications of the data structure the “What” but not “how”. At this level. The user or data structure designer is free think outside the bounds of anyone programming language.

2. Application Level: At the application or user level, the user is modeling real-life data in a specific context.

3.  Implementation Level: The implementation level is where the model becomes compatible, executable code.

Abstract data types

                The data structure can only be accessed with defined operations. This set of operations is called interface and abstract data type is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Properties of an abstract data type

Abstract data type is characterized by the following Properties.
1.       It exports a type.
2.       It exports a set of operations. This set is called interface.
3.       Operations of the interface are the one and only access mechanism to the type’s data structure.
4.       Axioms and preconditions define the application domain of type.

Parts of ADT description

1.       Data: This part describes the structure of the data used in the ADT in an informal way.
2.       Operations: This part describes valid operations for this ADT; hence, it describes its interface. We use special operation constructor to describe the actions which are to be performed once an entity of this ADT is created and destructed to describe the actions which are to be performed once an entity is destroyed.

You Might also view the following Related Posts

• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

For more other Posts: Click Here

Programming Language Definition

Programming Language Definition

Programming Language Definition: A sequence of instructions that a computer can interpret and execute to complete task is called computer program. The language which is used to develop a computer program is called programming language. There are two types of programming language which are procedure oriented programming language and object oriented programming language.
1.       Procedure Oriented programming:Conventional programming, using high level languages such as COBOL, FORTAN and C is commonly known as procedure oriented programming (POP). In the procedure oriented approach, the problem is viewed as a sequence of things to be done such as reading, calculating and printing. Procedure oriented programming basically consists of writing a list of instructions (or actions) for the computer to flow and organizing these instructions into groups known as functions.

Characteristics of Procedure Oriented Programming
i)        Emphasis is on doing things (algorithms)
ii)       Large Programs are divided into smaller Programs Known as functions.
iii)     Most of the functions share global data
iv)     Data move openly around the system from function to function.
v)      Functions transform data from one to another.
vi)     Employs top-down approach in program design.

Drawbacks of Procedure Oriented Programming
i)        In large program it is very difficult to identify what data is used by which function. In case we need to revise an external data structure, we also need to revise all functions that access the data. This provides an Opportunity for bugs to creep in.
ii)       With the procedural approach is that it does not model real world problems very well. This is because functions are action oriented and do not really corresponding to the elements of the problem.

2.       Object-oriented Programming: Object oriented programming treats data as a critical element in the program development and does not allow it to flow freely around the system. It ties data more closely to the functions that operate on it, and protects it from accidental modification from outside functions. OOP allows decomposition of a problem into a number of entities called objects and then builds data and functions around these objects.

Characteristics of Object-Oriented programming
i)        Emphasis is on data rather than procedure.
ii)       Programs are divided into what are known as objects.
iii)     Data structures are designed such that they characterize the objects.
iv)     Functions that operate on the data of an object are tied together on the data structure.
v)      Data is hidden and cannot be accessed by external functions.
vi)     Objects may communicate with each other through functions.
vii)   New data and functions can be easily added whenever necessary. Follows bottom up approach is program design.

Benefits of Object Oriented Programming
i)        Through inheritance we can eliminate redundant code and extend the use of existing classes.
ii)       We can build programs from the standard working modules that communicate with one another, rather than having to start writing the code from scratch. This leads to saving of development time and higher productivity.
iii)     The principle of data hiding helps the programmer to build secure programs that cannot be invaded by code in other parts of the program.

Some terms used in Object Oriented Programming

Ø  Objects: Objects are basic run-time entities in an object oriented system.
Ø  Classes: A class is a collection of objects of similar type.
Ø  Data Abstraction and Encapsulation: The wrapping up of data and functions into a single unit is known as encapsulation.
Abstraction refers to the act of representing essential features to the act of representing essential features without including the background or explanations.
Ø  Inheritance: Inheritance is the process by which objects of one class acquire the properties of objects of another class.
Ø  Polymorphism: Polymorphism is another important OOP concept. Polymorphism, a Greek term means the ability to take more than one form. The operation may exhibit different instances the behavior depends upon the types of data is the operation.
Ø  Dynamic Binding: Binding refers to the linking of a procedure call to the code to be executed in response to the call. Dynamic binding (also known as late binding) means that the code associated with a given procedure call is not known until the time of the call at run time.
Ø  Message passing: A message for an object is a request for execution of a procedure and therefore will invoke a function (procedure) in the receiving object that generates the desired result.
 

Network Topology

Network Topology

Network topology describes the layout or appearance of a network that is, how the computers, cables and other components within a data communication network are interconnected, both physically and logically. The physical topology describes the way in which a network is physically laid out, and the logical topology describes how data actually flow through the network. In data communication network, two or more devices are connected to from a link whereas two or more links from a topology. The topology of a network is the geometric representation of the relationship of all the links connecting the devices.

Types of Network Topology:

1.      Bus Topology: A bus topology is a multipoint data communication circuit that makes it relatively simple to control data flow between and among the computers because this configuration allows all stations to receive every transmission over the network. 

          The bus topology is usually used when a network installation is small, simple or temporary. On a typical bus network, the cable is just one or more wires, with no active electronics to amplify the signal or pass it along from computer to computer. 

         The speed of the bus topology is slow because only one computer can send a message at a time. A computer must wait until the bus is free before it can transmit. The bus topology requires a proper termination at both ends of the cable. Since, the bus is passive topology; the electrical signal from a transmitting computer is free to travel the entire length of the cable. Without termination when the signal reaches the end of the cable, it returns back and travels break up the cable. 

Advantages of Bus Topology

i) The bus topology is easy to understand, install and use for small networks.

ii) The cabling cost is less as the bus topology requires the least amount of cable to connect the computers.

iii) The bus topology is easy to expand by joining two cables with a BNC barrel connector.

iv) In the expansion of bus topology, repeaters can be used to boost the signal and increase the distance.

Drawbacks of Bus Topology

i) Heavy network traffic slows down the bus speed. In bus topology, only one computer can transmit and         others have to wait till their turn comes and there is no co-ordination between computers for reservation of transmitting time slot. 

ii) The BNC connectors used to expansion of the bus attenuates the signal considerably. 

iii) A cable breaks or loses BNC connector causes reflection and brings down the whole network causing all network activity to stop.

2. Ring Topology: In a ring topology, each computer is connected to the next computer, with the last one connected to the first. Rings are used in high-performance networks where large bandwidth is essential, e.g. time attractive features such as video and audio. In other words, a ring topology is a multipoint data communication network where all stations are interconnected is series to form a closed loop or circle. A ring topology is sometimes called a loop. Each station is the loop is joined by point-to-point links to two other stations. 

        The messages flow around the ring in one direction. There is no termination because there is no end to the ring. Some ring networks do token passing. A short message called a token is passed around the ring until a computer wishes to send information to another computer. That computer modifies the token, adds an electronic address and data and sends it around the ring. Each computer is sequence receives the token and the information and passes them to the next computer until either the electronic address matches the address of a computer or the token returns to its origin. The receiving computer returns a message to the originator indicating that message has been received. 

Advantages of Ring Topology

i) No one computer can monopolize the network because every computer is given equal access to the token.

ii) The fair sharing of the network allows the network continue function in a useful, if slower, manner rather than fail once capacity is exceeded as more users are added.

Drawbacks of Ring Topology

i) Failure of one computer on the ring can affect the whole network.

ii) It is difficult to troubleshoot the ring.

iii) Adding or removing the computers disturbs the network activity.

3. Star Topology: In star topology, all the cables run from the computers to a central location where they are all connected by a device called a hub. Stars are used to concentrated networks, where the endpoints are directly reachable from a central location when network expansion is expressed and when the greater reliability of a star topology is required. 

           Each computer on a star network communicates with a central hub that re-sends the message either to all the computers is a broadcast star network or only to the destination computer in a switched star network. The hub is a broadcast star network can be active or passive. An active hub generates the electrical signal and sends it to all the computers connected to it. This type of hub is usually called a multiport repeater. Active hubs require external power supply. A passive hub is a wiring panel or punch down block which acts as a connection point. It does not amplify or regenerate the signal. Passive hubs do not require electrical power supply. Several types of cables can be used to implement a star network. 

Drawbacks of Star Topology

i) If the central hub fails, the whole network fails to operate.

ii) Many star networks require a device at the central point to rebroadcast or switch the network traffic.

iii) The cabling cost is more since cables must be pulled from all computers to the central hub.

4. Mesh Topology: In a mesh topology, every device has a dedicated point-to-point link to every other device. The term dedicated means that the link carries traffic only between two devices if connects. A fully connected mesh network therefore has n(n-1)/2 physical channels to link hn devices. To accommodate those links, every device on the network must have n-1 input/output ports. 

Advantages of Mesh Topology

i) The use of dedicated links guarantees that each connection can carry its own data load, thus eliminating traffic problems.

ii) A mesh topology is robust because the failure of single computer does not bring down the entire network.

iii) It provides security and privacy because every message sent travels along a dedicated line.

iv) Point to point links make fault diagnose easy.

Drawbacks of Mesh Topology

i) Since every computer must be connected to every other computer installation and configuration is difficult.

ii) Cabling cost is more.

iii) The hardware required connecting each link input/output and cable is expensive.

5. Tree Topology: A tree topology is the variation of a star. As in a star, nodes in a tree are linked to a central hub that controls the traffic to the network. However, not every computer plugs into the central hub, majority of them are connected to a secondary hub which, in turn, is connected to the central hub. The central hub in the tree is an active hub which contains repeater. The repeater amplifies the signal and increases the distance a signal can travel. The secondary hubs may be active or passive. A passive hub provides a simple physical hub provides a simple physical connection between the attached devices.

Advantages of Tree topology

i) It allows more devices to be attached to a single hub and can therefore increase the distance of a signal can travel between devices.

ii) It allows the network to isolate and priorities communications from different computers.

Drawbacks of Tree Topology

i) If the central hub fails, the system breaks down.

ii) The cabling cost is more.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here