The Data Ilm

 A tree is an abstract data type that stores elements hierarchically. Each element in a tree has a parent element and zero or more children elements. The top element of the tree is called root. A tree can also be defined as a set of nodes storing elements in a parent child relationship. The children nodes of the same parent are called siblings. The node which has children is known as internal. The node which has no children is known as external or leaves. A free is ordered if there is a linear ordering defined for the chi1dren of each node. e.g, structured documents such as Books. A binary tree is an ordered tree in which every node has at most two children. The depth of a node is the number of ancestors of the node excluding the node itself. The depth of the root of a tree is 0. The height of a tree is equal to the maximum depth of an external node of the tree. The height of the external node is 0. A traversal of a tree is a systematic way of accessing all the nodes of the tree. T...

In 1998, Simplex company came up with a simple processor with a clock rate of 4.5 GHz and average CPI of 6. Later, they decided to upgrade the system by replacing simple processor with 5 stage pipelined processor. Due to internal pipeline delay, the processor clock is reduced to 2.5 GHz. Assume that the new system does not implement any techniques to avoid hazards. Find out the following. a) Clock time in non pipeline processor b) Execution time of non pipeline processor c) Clock time in pipeline processor d) Execution time of pipeline processor for 100 tasks e) Speedup achieved in pipeline processor Answer: a) Clock time in non pipeline processor Frequency of the clock = 4.5 GHz Cycle time = 1 / frequency            = 1 / 4.5 GHz = 1 / 4.5 X 10 9 Hz            = 0.222 ns b) Execution time of non pipeline processor Non pipeline execution time to process one instruction     = No of clock cycles taken to execute o...

Infix / Postfix Expression 1. The following postfix expression with single-digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are: Answer: 6, 1 2. Assume that the operators +, -, × are left-associative and ^ is right-associative. The order of  precedence (from highest to lowest) is ^, x, +, -. The postfix expression corresponding to the infix  expression a + b × c - d ^ e ^ f is Answer:  abc × + def ^ ^ - 3.  The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is Answer: 142 4.  Convert the following infix expression into its equivalent post fix expression (A + B^ D) / (E – F) + G Answer:  ABD^ + EF – / G+ 5. The best data structure to check whether an arithmetic expression has balanced parenthesis is a __________ Answer:   Stack

Time Complexity 1. What is the time complexity of following code: int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); } Answer: O(N) + O(M) 2. What is the time complexity of following code: int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } Answer:  O(N 2 ) 3. What is the time complexity of following code: int i, j, k = 0; for (i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; } } Answer:  O(nlogn) 4. What is the time complexity of following code: int a = 0, i = N; while (i > 0) { a += i; i /= 2; } Answer:  O(logn) 5. What is the time complexity of following code: function(int n) { if (n==1) return; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { printf("*"); break; }  } } Answer:  O(n) 6. What is the time complexity of following code: void function(int n) { int count = 0; for (int i=n/2; i<=n; i++) for (int j=1; j<=n;...

A tree whose elements have at most 2 children is called a binary tree. The three common types of Binary Trees. Full Binary Tree Complete Binary Tree Perfect Binary Tree Full Binary Tree A Binary Tree is a full binary tree if every node has 0 or 2 children. The nodes of full binary tree have two children except leaf nodes. No of Leaf Nodes = No of Internal Nodes + 1 Complete Binary Tree A Binary Tree is a complete binary tree if all levels completely filled except last level and nodes in last level are as left as possible. Max no of nodes at level i = 2 i Perfect Binary Tree A Binary Tree is a perfect binary tree in which all internal nodes have two children and all leaf nodes are at the same depth or same level. Maximum no of nodes in a binary tree with height h = 2 h+1   – 1  Height of complete binary tree h = floor (log 2 n)  Balanced Binary Tree is a tree in which height of the left and the right sub trees of every node may differ by at most 1. The complete binary tree...

A tree is an abstract model of a hierarchical structure. The tree consists of nodes with a parent-child relation. The each element of the tree except the top element, has a parent and zero or more children elements. The few applications of tree structure are Organization Data, Compiler processing, File system, Searching algorithm etc. The node without parent is called Root . The nodes with at least one child is called Internal nodes . The nodes without children is called External nodes or Leaf . The nodes which share the same parent is called Siblings . The parent, grandparent, great-grandparent of a node is called Ancestor . The child, grandchild, great-grandchild of a node is called Descendant . The number of children of a node is called Degree . The number of edges in path from root node to a node is called Depth of the node. The number of edges in longest path from a node to a leaf is called Height of the node. A node and its descendants in a tree is called Sub-tree . The le...

The concept of the Gershgorin Circle Theorem is that the diagonal entries of an n x n matrix can be taken as the coordinates in the complex plane. These points then act as the centers of n discs which have radii of the sum of the magnitudes of the n − 1 other entries from the same row. Then, all of the eigenvalues of this matrix will lie within the union of these discs.  Let  λ  be an eigenvalue of an arbitrary matrix A Then for some  integer j, Every eigenvalue of a matrix A must lie in a Gershgorin disc corresponding to the columns of A.