Learning Made Easy

An independent set   S   is a subset of   V   in   G   such that no two vertices in   S   are adjacent. I suppose that its name is meaning that vertices in an independent set   S   is independent on a set of edges in a graph  G . Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows: The independent set  S  is  maximal  if  S  is not a proper subset of any independent set of  G. The independent set  S  is  maximum  if there is no other independent set has more vertices than  S . That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.

Decomposition: ------------------------------- Let R be a relation schema A set of relation schemas { R1, R2,…, Rn } is a decomposition of R if R = R1 U R2 U …..U Rn Each Ri is a subset of R ( for i = 1,2…,n) Lossy Decomposition: When union of R1UR2UR3.......Rn is taken and output obtained from this does not match with original relation schema i.e. R that means there is loss of information and such type of decomposition is called as lossy decompostion. Lossless Decomposition : A decomposition of {R1,R2,R3,.............Rn} of a relation R is called a lossless decomposition is R is natural join of R1,R2.........Rn produces exactly relation R.

Some Graph Terminology: ==========================  Bipartite Graph  :  A  bipartite  graph is a graph  G  whose vertex set  V  can be partitioned into two non empty sets  V 1  and  V 2  in such a way that every edge of  G  joins a vertex in  V 1  to a vertex in  V 2. Star Graph : Suppose we start with  n  vertices, choose one special vertex and then draw edges from the special vertex to every other vertex. The graph we would obtain is called the star  on  n  vertices,  S n Wheel Graph : A wheel   on  n  vertices  W n  is a graph with  n  vertices  x 1 ,   x 2 , ...,  x n ,  with  x 1  having degree  n-1  and all the other vertices having degree  3.  The vertex  x 1  is adjacent to all the other vertices, and for  i=2, ..., n-1 ,  x i  i...

AVL Trees =============== - Also called height balanced tree -Height of children present at same level may not have same height. There height can differ at most by 1. -The height of an AVL tree T storing n keys is O(log n) Structure of AVL Tree ======================== - Consoder an AVL tree of n nodes -Cosider a leaf which is closest to the root - Suppose this leaf is at level k. -Then height of a tree is at most 2k - 1. Summary of AVL Tree ========================== - If height is h , then leaf closest to root is at level  at least (h+1)/2 -On the first (h-1)/2 levels the AVL tree is a complete binary tree - After (h-1)/2 level the AVL tree may start "thinning out" -Number of nodes in AVL tree is at least 2 to raise (h-1)/2 and at most 2 raise to h Insertion in AVL Tree ========================== Insertion of node make tree changes height and hence height balance property voilated. If Insertion causes T to become unbalanced , we travel up the ...

Definition: A  binary tree       T  is a finite set of  nodes    with the following properties: Either the set is empty,  ; or The set consists of a root,  r , and exactly two distinct binary trees   and  ,  . The tree   is called the  left subtree    of  T , and the tree   is called the  right subtree    of  T . They are considered as Ordered subtrees. Level i has   2 i    nodes. In a tree of height h, Leaves are level at h. No of leave are    2 h. No of internal nodes  2 h      -1. No of internal nodes = no of leaves -1 Total no of nodes =  2 h+1   -1 =n In a tree on n nodes  No of leaves is (n+1)/2 height =    Log 2 (n+1)/2 Tree Traversal PostOrder Traversal PreOrder  Traversal InOrder  Traversal PostOrder Traversal...

Running time of an algorithm, order of growth.  Worst case.   Running time of an algorithm  increases with the size of the input in the limit as the size of the input increases without bound. Big-theta notation (a=b) g(n) is an asymptotically   tight bound of f(n). Asymptotically non negative/positive. If g(n) is asymptotically negative then theta(g(n)) = empty.  Example 1/2n2 - 3n= theta(n2). Big O-notation (a<=b) Asymptotic upper bound Not tight bound  Theta is stronger than O O notation describe upper bound on every input. We also have amortized analysis.[An amortized analysis is any strategy for analyzing a sequence of perations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive] ] Example The running time is O(n2) means there is a function f(n) that is O(n2) such that for any value of n, no matter what ...

Whenever the word "Gate" comes in my mind , it always reminds me one thing " Jo bhi faltugiri ki Engg me bhul jao, Now its time to be serious. "  Gate is one most important exam from my point of view. It is like mirror that tells you what you have studied throughout engineering. It tells you whether you were really serious  or it was  just the TechMax which helped you to overcome your hurdles. Most of the gate questions comes from following subjects... 1.Data Structures including Graph theory,Algorithms  etc...it looks easy but really needs to be studied thoroughly.  2. Theory of computation science , in this parser part you should understand properly. 3. Math its one of my favourite ..No comments on this. 4. DataBase System looks very easy but you should all concepts of it. 5. At the End COA ,CN ,OS SA , it hate all these subjects  ,  specially CN, but still we have to study. Gate is not a difficult exam, So just chill maro yaar.....