الاثنين، 12 نوفمبر 2012

First of all e-commerce is surrounded by different issues such as commercial, Network infrastructure, Social and Cultural and Security issues are presented below which are important for successful business. E-commerce security issues are frequently aired in the press and are certainly important. Customers are concerned that the item ordered won’t materialize, or be as described. As (much worse) they worry about their social security number and credit card details being misappropriated. However rare, these things do happen, and customers need to be assured that all e-commerce security issues have been covered. Your guarantees and returns policies must be stated on the website and they must be adhered to. Let us first state the security attacks on e-commerce process and Security goals we want to achieve for successful e-commerce.

Attacks on Security
Security attacks can be classified in the following categories depending on the nature of the attacker.

a)      Passive Attacks
The attacker can only eavesdrop or monitor the network traffic. Typically, this is the easiest form of attack and can be performed without difficulty in many networking environments, e.g. broadcast type networks such as Ethernet and wireless networks.

b)      Active Attacks
The attacker is not only able to listen to the transmission but is also able to actively alter or obstruct it. Furthermore, depending on the attackers actions, the following subcategories can be used to cover to cover the majority to cover the majority of attacks.

c)       Eavesdropping
This is attack is used to gain knowledge of the transmitted data. This is passive attack which is easily performed in many networking environments as motioned above. However, this attack can easily perform in many networking environments. However this attack can easily be prevented by using an encryption scheme to protect the transmitted data.

d)      Traffic Analysis
The main goal of this attack is not to gain direct knowledge about the transmitted data, but to extra information from the characteristics of the transmission, e.g. amount of data transmitted, identity of the communicating nodes etc. This information may allow the attacked to deduce sensitive information, e.g., the roes of the communicating nodes, their position etc. Unlike the previously described attack, this one is more difficult to prevent.

e)      Impersonation
Here, the attacker uses the identity of another node to gain unauthorized access to resource or data. This attack is often used as a prerequisite to eavesdropping. By impersonating a legitimate node, the attacker can try to gain access to the encryption key used to protect the transmitted data. Once, this key is known by the attacker, she can successfully perform the eavesdropping attack.


f)       Modification
This attack modifies data during the transmission between the communicating nodes, implying that the communicating nodes do not share the same view of the transmitted data. An example could be when the transmitted data represents a financial transaction where the attacker has modified the transactions value.

g)      Insertion
This attack involves an unauthorized party, who inserts new data claiming that it originates from a legitimate party. This attack is related to that of impersonation.

You may also wanted to view the following related posts

You can view the following other posts

    E-commerce Security Issues

    Posted at  12:46 ص - by mego almasry 1

    First of all e-commerce is surrounded by different issues such as commercial, Network infrastructure, Social and Cultural and Security issues are presented below which are important for successful business. E-commerce security issues are frequently aired in the press and are certainly important. Customers are concerned that the item ordered won’t materialize, or be as described. As (much worse) they worry about their social security number and credit card details being misappropriated. However rare, these things do happen, and customers need to be assured that all e-commerce security issues have been covered. Your guarantees and returns policies must be stated on the website and they must be adhered to. Let us first state the security attacks on e-commerce process and Security goals we want to achieve for successful e-commerce.

    Attacks on Security
    Security attacks can be classified in the following categories depending on the nature of the attacker.

    a)      Passive Attacks
    The attacker can only eavesdrop or monitor the network traffic. Typically, this is the easiest form of attack and can be performed without difficulty in many networking environments, e.g. broadcast type networks such as Ethernet and wireless networks.

    b)      Active Attacks
    The attacker is not only able to listen to the transmission but is also able to actively alter or obstruct it. Furthermore, depending on the attackers actions, the following subcategories can be used to cover to cover the majority to cover the majority of attacks.

    c)       Eavesdropping
    This is attack is used to gain knowledge of the transmitted data. This is passive attack which is easily performed in many networking environments as motioned above. However, this attack can easily perform in many networking environments. However this attack can easily be prevented by using an encryption scheme to protect the transmitted data.

    d)      Traffic Analysis
    The main goal of this attack is not to gain direct knowledge about the transmitted data, but to extra information from the characteristics of the transmission, e.g. amount of data transmitted, identity of the communicating nodes etc. This information may allow the attacked to deduce sensitive information, e.g., the roes of the communicating nodes, their position etc. Unlike the previously described attack, this one is more difficult to prevent.

    e)      Impersonation
    Here, the attacker uses the identity of another node to gain unauthorized access to resource or data. This attack is often used as a prerequisite to eavesdropping. By impersonating a legitimate node, the attacker can try to gain access to the encryption key used to protect the transmitted data. Once, this key is known by the attacker, she can successfully perform the eavesdropping attack.


    f)       Modification
    This attack modifies data during the transmission between the communicating nodes, implying that the communicating nodes do not share the same view of the transmitted data. An example could be when the transmitted data represents a financial transaction where the attacker has modified the transactions value.

    g)      Insertion
    This attack involves an unauthorized party, who inserts new data claiming that it originates from a legitimate party. This attack is related to that of impersonation.

    You may also wanted to view the following related posts

    You can view the following other posts

      As e-commerce evolves, it will present huge risks for those who don’t take advantage of it. The main risk of e-commerce is that the business won’t capitalize on all it has to offer, while the competition moves ahead. The traditional supply chain consists of the manufacturer, the distributor; the traditional supply chain consists of the manufacturer, the distributor, the retailer, and the end consumer. E-commerce is changing this linear view of the supply chain. Instead of goods flowing from one participant to the next, this new online marketplace can connect each participant to the end-consumer. For some links in the supply chain, increased access to customers could be dangerous as partners could even become competitors.

      In the physical world today, there are requirements for documents to be in writing and for hand-written signatures. Such requirements need to be translated into the electronic realm with the rapid development of electronic commerce and to resolve questions raised regarding the applicability of such legislation to the unique features of the electronic regime. The advent or e-commerce and the use of the digital medium as an alternative to the physical, have created some novel legal issues where there are no clear answers.

      The users of information technology must have trust in the security of information and communication infrastructures, network and systems, in the confidentiality, integrity, and availability of data on them, and in the ability to prove the origin and receipt of data. For communication and transactions occurring over a faceless network, there is a need or reliable methods to authenticate a person’s identity and to ensure the integrity of the electronically transmitted documents.

      The concepts of a secure electronic record and a secure electronic signature, and the rebuttable presumptions that flow from that status, are thus necessary for a viable system of electronic commerce. In the context of electronic commerce, none of the usual indicators of reliability present in a paper-based transaction (the use of paper, letterhead, etc.) exist, making it difficult to know when one can rely on the integrity and authenticity of an electronic record. This lack of reliability can make proving one’s case in court virtually impossible. Rebuttable presumptions with respect to secure records and secure signatures put a relying partying a position to know, at the time of receipt and/or reliance, whether the message is authentic and the integrity of its contents intact and, equally important, whether it will be able to establish both of these facts in court in the event of subsequent disputes.

      You may also wanted to view the following related posts

      You can view the following other posts

      Risk of e-commerce

      Posted at  12:41 ص - by mego almasry 0

      As e-commerce evolves, it will present huge risks for those who don’t take advantage of it. The main risk of e-commerce is that the business won’t capitalize on all it has to offer, while the competition moves ahead. The traditional supply chain consists of the manufacturer, the distributor; the traditional supply chain consists of the manufacturer, the distributor, the retailer, and the end consumer. E-commerce is changing this linear view of the supply chain. Instead of goods flowing from one participant to the next, this new online marketplace can connect each participant to the end-consumer. For some links in the supply chain, increased access to customers could be dangerous as partners could even become competitors.

      In the physical world today, there are requirements for documents to be in writing and for hand-written signatures. Such requirements need to be translated into the electronic realm with the rapid development of electronic commerce and to resolve questions raised regarding the applicability of such legislation to the unique features of the electronic regime. The advent or e-commerce and the use of the digital medium as an alternative to the physical, have created some novel legal issues where there are no clear answers.

      The users of information technology must have trust in the security of information and communication infrastructures, network and systems, in the confidentiality, integrity, and availability of data on them, and in the ability to prove the origin and receipt of data. For communication and transactions occurring over a faceless network, there is a need or reliable methods to authenticate a person’s identity and to ensure the integrity of the electronically transmitted documents.

      The concepts of a secure electronic record and a secure electronic signature, and the rebuttable presumptions that flow from that status, are thus necessary for a viable system of electronic commerce. In the context of electronic commerce, none of the usual indicators of reliability present in a paper-based transaction (the use of paper, letterhead, etc.) exist, making it difficult to know when one can rely on the integrity and authenticity of an electronic record. This lack of reliability can make proving one’s case in court virtually impossible. Rebuttable presumptions with respect to secure records and secure signatures put a relying partying a position to know, at the time of receipt and/or reliance, whether the message is authentic and the integrity of its contents intact and, equally important, whether it will be able to establish both of these facts in court in the event of subsequent disputes.

      You may also wanted to view the following related posts

      You can view the following other posts

      Use of e-commerce technologies helps speed up the flow of information and to eliminate unnecessary human intervention; the computer can now accomplish what computers do better than people process routine business transactions quickly and accurately, 24 hours a day. This in turn, frees up people to handle tasks that computers may never be able to do exercising judgment, creativity, and experience to manage exceptions, solve problems and continually improve business processes.

              E-commerce is growing in importance and means unprecedented opportunities for everyone. When a business takes advantage of the power of e-commerce, it will be able to.


              i.            Increase customer satisfaction
      Internet is always open, even on holidays; business is thus always open, 24 hours a day, 7 days a week and 365 days a year. Customers will appreciate the extra access to product updates, shipping details, billing information and more. And since the internet knows no boundaries, customers can shop from home, work, or anywhere they can make a connection. Besides, by connecting the e-commerce and shipping systems, it would be possible to ship products faster and for less money.

            ii.            Increase sales volumes
      The Internet is a new channel to reach new customers. With a web site, a company can automatically become a global provider of goods and services, with an edge over even the largest competitors. Interactive selling is advantageous because a company is no longer limited by shelf-space or inventory concerns but instead offer all products to suit the customers exact specifications.

          iii.            Decrease costs of doing business
      E-commerce helps cut out or streamline processes that eat away profits. For instance exchange of information from advertising to availability updates, can add to the cost of sale. However, the web site can be an efficient, cost-effective communication vehicle. Customers can find timely accurate information in one place when they need it. By using e-commerce, everything from purchase orders to funds transfer can be handled faster and more efficiently. Even payment processing and bookkeeping are easier.


      You may also wanted to view the following related posts

      You can view the following other posts

      Benefits of e-commerce

      Posted at  12:34 ص - by mego almasry 0

      Use of e-commerce technologies helps speed up the flow of information and to eliminate unnecessary human intervention; the computer can now accomplish what computers do better than people process routine business transactions quickly and accurately, 24 hours a day. This in turn, frees up people to handle tasks that computers may never be able to do exercising judgment, creativity, and experience to manage exceptions, solve problems and continually improve business processes.

              E-commerce is growing in importance and means unprecedented opportunities for everyone. When a business takes advantage of the power of e-commerce, it will be able to.


              i.            Increase customer satisfaction
      Internet is always open, even on holidays; business is thus always open, 24 hours a day, 7 days a week and 365 days a year. Customers will appreciate the extra access to product updates, shipping details, billing information and more. And since the internet knows no boundaries, customers can shop from home, work, or anywhere they can make a connection. Besides, by connecting the e-commerce and shipping systems, it would be possible to ship products faster and for less money.

            ii.            Increase sales volumes
      The Internet is a new channel to reach new customers. With a web site, a company can automatically become a global provider of goods and services, with an edge over even the largest competitors. Interactive selling is advantageous because a company is no longer limited by shelf-space or inventory concerns but instead offer all products to suit the customers exact specifications.

          iii.            Decrease costs of doing business
      E-commerce helps cut out or streamline processes that eat away profits. For instance exchange of information from advertising to availability updates, can add to the cost of sale. However, the web site can be an efficient, cost-effective communication vehicle. Customers can find timely accurate information in one place when they need it. By using e-commerce, everything from purchase orders to funds transfer can be handled faster and more efficiently. Even payment processing and bookkeeping are easier.


      You may also wanted to view the following related posts

      You can view the following other posts

      الأحد، 11 نوفمبر 2012

      Now, most of the companies are using e-commerce technology and going to be used. Even small companies have their own web sites, giving details about their profile, Products and services and are moving up in the e-commerce value chain. Companies that were earlier providing access to information on their respective web sites are now engaging themselves in e-commerce practices. Some of the e-commerce practices which are being done by most of the companies for the development of e-commerce technology for them are as follows.

      a) Better Information technology infrastructure

              E-business models are moving from the proprietary ‘Electronic Data Interchange’ (EDI) ‘Specific’ solutions to internet based ‘mass’ solutions. It has more to do with better computer penetration, increase in number of internet users and high-speed connectivity rather than anything else.

      b) Wider acceptance of online payment system

              Online payment mechanism means ‘payment’ and ‘acceptance’ of virtual money. Any such online payment system requires not only the parties transacting business over the Internet but also a ‘payment gateway’ facilitating such transactions. To begin with, it requires use of credit cards and other modes of online payment using advanced technological tools.

                Master Card has recently introduced Site Data Protection Service (SDP), a comprehensive set of global e-business security services that proactively protects online merchants from hacker intrusions. It is a satellite communications network. Also credit card companies have come out with a technology that proactively helps prevents and skimming by using the ‘intrinsic noise’ properties of magnetic strip, which are unique for every card, to differentiate between and original and cloned cards.

      Apart from credit card based transactions, other proprietary online payment systems to initiate the ‘uninitiated’ to shop on the Internet are:

      • Cybercash: Ensuring encrypted passage over the internet for the data card data.
      • E-Cash: Issued online for use over the Internet and is stored in an electronic device such as a chip card of computer memory. The person who has purchased such cash can use it online for making payments.
      • Online Pay: Online Pay allows consumers to shop online without fear of fraud by allowing them to make purchases without giving out information about their credit card or their checking account to the online vendor.
      • Secure Sockets Layers: It is developed by Netscape, which provides privacy, integrity and authentication through digital certificates. Increasing use of Smart Card has also given fillip to the e-commerce activities. Smart cards store all their information on a chip buried within the card. It works as an electronic purse storing digital money, which could be used over public terminals (Web sites, ATMs, Telephone lines) etc. A new system of credit card transactions over the Internet is being currently developed jointly by Visa and MasterCard with technical assistance from the Internet Information system and cryptology companies like Netscape, IBM. It is known to Secure Electronic Transactions (SET). It is expected that in coming years, SET would become the standard of payment over the Internet. Another important development has the adoption of digital signatures as authentication standards providing integrity, confidentiality and non-repudiation of electronic records. It has paved the way for legal recognition of electronic contracts, an extremely important step in giving legal sanctity to online payment system.

      c) Legal recognition to e-commerce practices. 

            Legal recognition of E-commerce practices has come a long way from the initial adoption of UNCITRAL’s Model Law on Electronic commerce by the General Assembly of the United Nations in early 1997. The purpose of the UNCITRAL Model Law on electronic ecommerce is to encourage the use of electronic commerce and to provide nations with model legislation “governing the use of alternative to paper – based methods of communication and storage of information”. It is based on “fundamental-equivalent” approach and extends notions such as “writing”, “signature” and “original” of traditional paper based requirements to a paperless world. It gives legal acceptance to electronic records and digital signatures. Countries, by adopting the UNCITRAL’s Model Law on Electronic commerce have not only given credence to E-commerce laws globally. The most important element is that the nations’ laws on e-commerce have been based on a similar technology platform, i.e. asymmetric cryptography.


      d) Adoption of security standards by the industry

              Business thrives on safety, security and trust whether it is offline or online. The internet being an open, integrated and public system requires far better security coverage than its offline counterpart. It needs an ‘encryption’ technology that provides (i) confidentially (ii) authentication (iii) Integrity (iv) non repudiation and of electronic transactions.

      1. Confidentiality: The idea that the information should be protected from unauthorized internal as well as external users by making it undecipherable. It uses encryption technology to ‘encrypt’ the information in such a way that only an intended user could ‘decrypt’ the information.
      2. Authentication: It means use of encryption technology to identify the sender of originator of the information. Similarly it should be possible to ensure that the message is sent to the person of whom it is meant.
      3. Integrity: It is to verify that the information, which is received, has not been manipulated during its transmission. On retrieval or receipt at the other end of a communication network the information should appear exactly as it was stored or sent by the sender of originator.
      4. Non-repudiation: It is ensure that sender or originator cannot disown information at a later date. Encryption technologies make it possible to bind messages and message acknowledgements with their originators. 

      You may also wanted to view the following related posts

      You can view the following other posts

      Development of e-commerce

      Posted at  1:05 ص - by mego almasry 0

      Now, most of the companies are using e-commerce technology and going to be used. Even small companies have their own web sites, giving details about their profile, Products and services and are moving up in the e-commerce value chain. Companies that were earlier providing access to information on their respective web sites are now engaging themselves in e-commerce practices. Some of the e-commerce practices which are being done by most of the companies for the development of e-commerce technology for them are as follows.

      a) Better Information technology infrastructure

              E-business models are moving from the proprietary ‘Electronic Data Interchange’ (EDI) ‘Specific’ solutions to internet based ‘mass’ solutions. It has more to do with better computer penetration, increase in number of internet users and high-speed connectivity rather than anything else.

      b) Wider acceptance of online payment system

              Online payment mechanism means ‘payment’ and ‘acceptance’ of virtual money. Any such online payment system requires not only the parties transacting business over the Internet but also a ‘payment gateway’ facilitating such transactions. To begin with, it requires use of credit cards and other modes of online payment using advanced technological tools.

                Master Card has recently introduced Site Data Protection Service (SDP), a comprehensive set of global e-business security services that proactively protects online merchants from hacker intrusions. It is a satellite communications network. Also credit card companies have come out with a technology that proactively helps prevents and skimming by using the ‘intrinsic noise’ properties of magnetic strip, which are unique for every card, to differentiate between and original and cloned cards.

      Apart from credit card based transactions, other proprietary online payment systems to initiate the ‘uninitiated’ to shop on the Internet are:

      • Cybercash: Ensuring encrypted passage over the internet for the data card data.
      • E-Cash: Issued online for use over the Internet and is stored in an electronic device such as a chip card of computer memory. The person who has purchased such cash can use it online for making payments.
      • Online Pay: Online Pay allows consumers to shop online without fear of fraud by allowing them to make purchases without giving out information about their credit card or their checking account to the online vendor.
      • Secure Sockets Layers: It is developed by Netscape, which provides privacy, integrity and authentication through digital certificates. Increasing use of Smart Card has also given fillip to the e-commerce activities. Smart cards store all their information on a chip buried within the card. It works as an electronic purse storing digital money, which could be used over public terminals (Web sites, ATMs, Telephone lines) etc. A new system of credit card transactions over the Internet is being currently developed jointly by Visa and MasterCard with technical assistance from the Internet Information system and cryptology companies like Netscape, IBM. It is known to Secure Electronic Transactions (SET). It is expected that in coming years, SET would become the standard of payment over the Internet. Another important development has the adoption of digital signatures as authentication standards providing integrity, confidentiality and non-repudiation of electronic records. It has paved the way for legal recognition of electronic contracts, an extremely important step in giving legal sanctity to online payment system.

      c) Legal recognition to e-commerce practices. 

            Legal recognition of E-commerce practices has come a long way from the initial adoption of UNCITRAL’s Model Law on Electronic commerce by the General Assembly of the United Nations in early 1997. The purpose of the UNCITRAL Model Law on electronic ecommerce is to encourage the use of electronic commerce and to provide nations with model legislation “governing the use of alternative to paper – based methods of communication and storage of information”. It is based on “fundamental-equivalent” approach and extends notions such as “writing”, “signature” and “original” of traditional paper based requirements to a paperless world. It gives legal acceptance to electronic records and digital signatures. Countries, by adopting the UNCITRAL’s Model Law on Electronic commerce have not only given credence to E-commerce laws globally. The most important element is that the nations’ laws on e-commerce have been based on a similar technology platform, i.e. asymmetric cryptography.


      d) Adoption of security standards by the industry

              Business thrives on safety, security and trust whether it is offline or online. The internet being an open, integrated and public system requires far better security coverage than its offline counterpart. It needs an ‘encryption’ technology that provides (i) confidentially (ii) authentication (iii) Integrity (iv) non repudiation and of electronic transactions.

      1. Confidentiality: The idea that the information should be protected from unauthorized internal as well as external users by making it undecipherable. It uses encryption technology to ‘encrypt’ the information in such a way that only an intended user could ‘decrypt’ the information.
      2. Authentication: It means use of encryption technology to identify the sender of originator of the information. Similarly it should be possible to ensure that the message is sent to the person of whom it is meant.
      3. Integrity: It is to verify that the information, which is received, has not been manipulated during its transmission. On retrieval or receipt at the other end of a communication network the information should appear exactly as it was stored or sent by the sender of originator.
      4. Non-repudiation: It is ensure that sender or originator cannot disown information at a later date. Encryption technologies make it possible to bind messages and message acknowledgements with their originators. 

      You may also wanted to view the following related posts

      You can view the following other posts

      الجمعة، 9 نوفمبر 2012


       
      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

      For more other Posts: Click Here

      Graph Definition

      Posted at  11:31 م - by mego almasry 0


       
      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

      For more other Posts: Click Here

      الخميس، 8 نوفمبر 2012


      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:

      Definition of Tree
        Definition of Tree
      • 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.

        Definition of Tree

        Posted at  9:49 م - by mego almasry 0


        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:

        Definition of Tree
          Definition of Tree
        • 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.

          الأربعاء، 7 نوفمبر 2012

          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

          For more other Posts: Click Here


          Definition of List and Linked List

          Posted at  9:24 م - by mego almasry 0

          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

          For more other Posts: Click Here


          الاشتراك في: الرسائل (Atom)
          Copyright © 2013 hello1. by Bloggertheme9 Powered by Blogger.
          WP Theme-junkie converted by Blogger template