The Complete Codes

Graph Traversals There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edges of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs. Depth First Search This is another technique that can be used to search the graph. Choose a vertex as a root and form a path by starting at a root vertex by successively adding vertices and edges. This process is continued until no possible path can be formed. If the path contains all the vertices then the tree consisting of this path is the DFS tree. Otherwise, we must add other edges and vertices. For this move back from the last vertex that is met in the previous path and find whether it is possible to find a new path starting from the vertex just met. If there is such a path...

Graph Traversals There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edges of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs. Breadth-first search This is one of the simplest methods of graph searching. Choose some vertex arbitrarily as a root. Add all the vertices and edges that are incident in the root. The new vertices added will become the vertices at level 1 of the BFS tree. Form the set of the added vertices of level 1, and find other vertices, such that they are connected by edges at level 1 vertices. Follow the above step until all the vertices are added. Algorithm: BFS ( G , s ) // s is start vertex {     T = {s};     L = Φ; // an empty queue     Enqueue (L, s );...

Job Sequencing with Deadline We are given a set of n jobs. Associated with each job I, di>=0 is an integer deadline and pi>=O is profit. For any job i profit is earned if the job is completed by the deadline. To complete a job one has to process a job for one unit of time. Our aim is to find a feasible subset of jobs such that profit is maximum. Example n=4, (p1,p2,p3,p4)=(100,10,15,27),(d1,d2,d3,d4)=(2,1,2,1) n=4, (p1,p4,p3,p2)=(100,27,15,10),(d1,d4,d3,d2)=(2,1,2,1) We have to try all the possibilities, complexity is O(n!). Greedy strategy using total profit as optimization function to above example. Begin with J= Job 1 considered, and added to J ->J={1} Job 4 considered, and added to J -> J={1,4} Job 3 considered, but discarded because not feasible   ->J={1,4} Job 2 considered, but discarded because not feasible   -> J={1,4} The final solution is J={1,4} with a total profit of 127 and it is optimal Algorithm: ...

Huffman coding Huffman coding is an algorithm for the lossless compression of files based on the frequency of occurrence of a symbol in the file that is being compressed. In any file, certain characters are used more than others. Using binary representation, the number of bits required to represent each character depends upon the number of characters that have to be represented. Using one bit we can represent two characters, i.e., 0 represents the first character and l represents the second character. Using two bits we can represent four characters, and so on. Unlike ASCII code, which is a fixed-length code using seven bits per character, Huffman compression is a variable-length coding system that assigns smaller codes for more frequently used characters and larger codes for less frequently used characters in order to reduce the size of files being compressed and transferred. For example, in a file with the following data: ‘XXXXXXYYYYZZ. The frequency of "X" is 6, t...