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 );     while (L != Φ)     {  

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: Assume

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

CLIENT SERVER ARCHITECTURE  Client/server architecture is a computing model in which the server hosts, delivers and manages most of the resources and services to be consumed by the client. This type of architecture has one or more client computers connected to a central server over a network or internet connection.   Client server application consists of multiple application system combines or divided but interlinked to make various layers or tier The application logic tier.   The application logic tier is where all the “thinking” happens, and it knows what is allowed by your application and what is possible, and it makes other decisions.   This logic tier is also the one that writes and reads data into the data tier. The data tier. The data tier is where all the data used in your application are stored.   You can securely store data on this tier, do transaction, and even search through volumes and volumes of data in a matter of seconds. The presentation

Heap Sort   A heap is a nearly complete binary tree with the following two properties: Structural property: all levels are full, except possibly the last one, which is filled from left to right Order (heap) property: for any node x, Parent(x) ≥ x Array Representation of Heaps A heap can be stored as an array A. Root of tree is A[1] Left child of A[i] = A[2i] Right child of A[i] = A[2i + 1] Parent of A[i] = A[ i/2 ] Heapsize[A] ≤ length[A] The elements in the subarray A[( ⌊ n/2 ⌋ +1) .. n] are leaves Max-heaps (largest element at root), have the max-heap property:   for all nodes i, excluding the root:     A[PARENT(i)] ≥ A[i] Min-heaps (smallest element at root), have the min-heap property: for all nodes i, excluding the root:   A[PARENT(i)] ≤ A[i] Adding/Deleting Nodes New nodes are always inserted at the bottom level (left to right) and nodes are removed from the bottom level (right to left). Operations on Heaps Maintai

Heap A heap is a complete tree with an ordering-relation R holding between each node and its descendant. Note that the complete tree here means tree can miss only rightmost part of the bottom level. R can be smaller-than, bigger-than. E.g. Heap with degree 2 and R is “bigger than”. Heap Sort  Build a heap from the given set (O(n)) time, then repeatedly remove the elements from the heap (O(n log n)). Implementation Heaps are implemented by using arrays. Insertion and deletion of an element takes O(log n) time. More on this later Heap Sort Pseudo Code Heapsort ( A ) {     BuildHeap ( A )     for i <- length (A) downto 2 {       exchange A [ 1 ] <-> A [i]       heapsize <- heapsize - 1       Heapify (A, 1 ) } BuildHeap (A)    {    heapsize <- length (A)     for i <- floor ( length/ 2 ) downto 1       Heapify (A, i)    }     Heapify (A, i)    {        le < - left (i)                    ri < - right (i)                             if (le