CSE InfoNotes

Another example of divide and conquer method is Strassen’s Matrix  that help us to multiply two matrices of size n × n. Let A and B are the two n × n matrices, then its product C= AB is also n × n matrix. These n × n matrix product can be formed by taking the element in the i th  row of A and j th  column of B and multiplying them to get   To compute C(i,j), we need to have n multiplication. Divide and conquer method suggest another way to compute C(i,j) i.e the product matrix of n × n. imagine that A and B are two n × n matrices divided into two square matrices of size n/2 n/2. then the product matrix AB can be computed by using the above formula as  

- Simple network management protocol (SNMP) is framework for managing the devices in an internet using TCP/IP suit. - Basically it provide the set of fundamental operation for monitoring and maintaining internet. - Mainly SNMP uses concept of manager and agent. - Generally manager i.e host controls and monitors a set of agent, usually routers.

- Basically OSI reference model is introduced by international standard organization (ISO) . - The OSI model is not protocol, generally it is model to show how to facilitate the communication between different system without changing any hardware and software. - The OSI model is the layered framework that allows the communication between any kind of system. - Generally OSI model is the 7 layer structure as follows

- The user datagram protocol (UDP) is called as connection-less, unreliable transport protocol. - It provides process to process communication instead of host to host communication. - UDP is very simple protocol using minimum of overhead. - If a process wants to send a message without the care of reliability then it uses UDP. - UDP takes much less interaction between sender and receiver than using TCP and SCTP. - UDP packets called as user data gram having the fixed size header of 8 bytes. Following figure shows the UDP header.

- Transmission control protocol (TCP) is set of rules used along with the internet protocol (IP) to send the data in the form of message units between the computers. - During the sending of data, IP take care of delivery of the actual whereas the TCP take care of individual units of the data (called as packets). - TCP is known as connection oriented protocol, means that the connection is established and maintain such time as the message is to be exchanged by the application program. - TCP guarantees the delivery of data and also guarantees that the packets will be delivered in the same order in which they were send. - TCP uses a fixed connection, if one application wants to communicate with another via TCP, then it sends the communication request to an exact address after hand-shaking. - Connection establishment via TCP is called as three way handshaking. - The process starts with the server. Server program tells its TCP that it is actually ready to send the request. This

- T he TCP/IP protocol suit was developed prior to the OSI model. - Originally TCP/IP protocol suit is having four layers i) Host to network ii) Internet iii) Transport iv) Application - However, the TCP/IP compared to the OSI model, we can say that host to network layer is generally equivalent to the combination of physical and data link layer. - Internet layer is equivalent to the network layer. - Application layer is equivalent to the combination of session layer, presentation layer and application layer of OSI model. - We assume that the TCP/IP protocol suit is just consist of five layer compare to the OSI model i) Physical ii) Data link iii) Network iv) Transport v) Application - The TCP/IP hierarchical  model contain relatively independent protocol that can be mixed and match depending on the needs of the protocol. - TCP/IP architecture can be as follows

Lets try to apply the greedy method to solves the knapsack problem.Suppose, object i has the weight w i  and the knapsack has the capacity m. If the fraction x i  which 0≤ x i ≤ 1 is added to the knapsack then ultimately the profit p i x i  earned. The objective of this is nothing but to maximizes the total number of profits that we earned. Since the knapsack capacity is m, we required all chosen object’s weight is at most m. Formally the problem can be stated as follows The profits and weights are the positive numbers and the feasible solution is the any kind of set (x i ……..x n ) satisfying the above condition. Consider the following algorithm for more clear of the feasible solution.

When more than two sorted files are merged together, the merge can be accomplish by repeatedly merging sorted files in pairs. Thus if the files x 1 , x 2 , x 3  and x 4 are to be merged then we would have to merge first x 1 and x 2  to get result y 1  then y 1 and x 3  to get y 2 and then y 2  to x 4 to get result y 3  desired sorted files. Alternatively, we also do the merging of files x 1  and x 2  to get the result y 1  then merge file x 3  and x 4  to get y 2  and at last merge y 1  and y 2  to get sorted files. For example the files x 1 , x 2 , and x 3 are the three sorted files with the length 30, 20 and 10 records each. If we merge x 1  and x 2  then we get 50 moves and then if we merge with x 3  we get another 60 moves.        Alternatively by this method we give the merging file of about 110 moves.