Explore topic-wise InterviewSolutions in Current Affairs.

The height of left subtree minus height of RIGHT subtree is called BALANCE FACTOR of a node in AVL tree.The balance factor MAY be either 0 or +1 or -1.The height of an empty tree is -1.

The height of left subtree minus height of right subtree is called balance factor of a node in AVL tree.The balance factor may be either 0 or +1 or -1.The height of an empty tree is -1.

A splay tree is a binary search tree in which RESTRUCTURING is done using a SCHEME CALLED splay. The splay is a heuristic method which moves a given vertex v to the ROOT of the splay tree using a sequence of ROTATIONS.

A splay tree is a binary search tree in which restructuring is done using a scheme called splay. The splay is a heuristic method which moves a given vertex v to the root of the splay tree using a sequence of rotations.

Splaying reduces the total accessing time if the most FREQUENTLY accessed NODE is MOVED towards the root. It does not require to maintain any information regarding the height or balance factor and hence saves space and SIMPLIFIES the code to some extent.

Splaying reduces the total accessing time if the most frequently accessed node is moved towards the root. It does not require to maintain any information regarding the height or balance factor and hence saves space and simplifies the code to some extent.

<P>Let us assume that the splay is performed at vertex v, whose parent and grandparent are p and g respectively. Then, the three ROTATIONS are named as:

Zig: If p is the root and v is the left child of p, then left-left rotation at p would suffice. This case always terminates the splay as v REACHES the root after this rotation.

Zig-Zig: If p is not the root, p is the left child and v is also a left child, then a left-left rotation at g followed by a left-left rotation at p, brings v as an ancestor of g as well as p.

Zig-Zag: If p is not the root, p is the left child and v is a right child, perform a left-right rotation at g and BRING v as an ancestor of p as well as g.

Let us assume that the splay is performed at vertex v, whose parent and grandparent are p and g respectively. Then, the three rotations are named as:

Zig: If p is the root and v is the left child of p, then left-left rotation at p would suffice. This case always terminates the splay as v reaches the root after this rotation.

Zig-Zig: If p is not the root, p is the left child and v is also a left child, then a left-left rotation at g followed by a left-left rotation at p, brings v as an ancestor of g as well as p.

Zig-Zag: If p is not the root, p is the left child and v is a right child, perform a left-right rotation at g and bring v as an ancestor of p as well as g.

A HEAP is defined to be a complete BINARY TREE with the property that the value of each node is atleast as small as the value of its child nodes, if they exist. The root node of the heap has the SMALLEST value in the tree.

A heap is defined to be a complete binary tree with the property that the value of each node is atleast as small as the value of its child nodes, if they exist. The root node of the heap has the smallest value in the tree.

The minimum number of nodes S(H), in an AVL tree of HEIGHT h is given by S(h)=S(h-1)+S(h-2)+1. For h=0, S(h)=1.

The minimum number of nodes S(h), in an AVL tree of height h is given by S(h)=S(h-1)+S(h-2)+1. For h=0, S(h)=1.

A B-TREE of ORDER M is a tree that is not binary with the following structural PROPERTIES:

• The ROOT is either a leaf or has between 2 and M children.
• All non-leaf nodes (EXCEPT the root) have between [M/2] and M children.
• All leaves are at the same depth.

A B-tree of order M is a tree that is not binary with the following structural properties:

A B-tree of order 3 is CALLED 2-3 tree. A B-tree of order 3 is a tree that is not binary with the following STRUCTURAL PROPERTIES:

• The ROOT is either a leaf or has between 2 and 3 children.
• All non-leaf nodes (EXCEPT the root) have between 2 and 3 children.
• All leaves are at the same depth.

A B-tree of order 3 is called 2-3 tree. A B-tree of order 3 is a tree that is not binary with the following structural properties:

A B-TREE of order 4 is CALLED 2-3-4 tree. A B-tree of order 4 is a tree that is not BINARY with the following STRUCTURAL PROPERTIES:

• The root is either a leaf or has between 2 and 4 children.
• All non-leaf nodes (except the root) have between 2 and 4 children.
• All leaves are at the same depth.

A B-tree of order 4 is called 2-3-4 tree. A B-tree of order 4 is a tree that is not binary with the following structural properties:

• DATABASE IMPLEMENTATION.
• Indexing on non PRIMARY KEY fields.

In a multiuser environment, the operating system scheduler must decide which of the SEVERAL processes to run only for a fixed period of time. One algorithm uses queue. Jobs are initially placed at the end of the queue. The scheduler will repeatedly take the first JOB on the queue, run it until either it finishes or its time LIMIT is up and place it at the end of the queue if it does not finish. This strategy is not appropriate, because very short jobs will soon to take a long time because of the wait involved in the run.

Generally, it is important that short jobs finish as fast as possible, so these jobs should have precedence over jobs that have already been running. Further more, some jobs that are not short are STILL very important and should have precedence. This particular application seems to require a special kind of queue, known as priority queue. Priority queue is ALSO called as Heap or Binary Heap.

In a multiuser environment, the operating system scheduler must decide which of the several processes to run only for a fixed period of time. One algorithm uses queue. Jobs are initially placed at the end of the queue. The scheduler will repeatedly take the first job on the queue, run it until either it finishes or its time limit is up and place it at the end of the queue if it does not finish. This strategy is not appropriate, because very short jobs will soon to take a long time because of the wait involved in the run.

Generally, it is important that short jobs finish as fast as possible, so these jobs should have precedence over jobs that have already been running. Further more, some jobs that are not short are still very important and should have precedence. This particular application seems to require a special kind of queue, known as priority queue. Priority queue is also called as Heap or Binary Heap.

• STRUCTURE PROPERTY.
• HEAP ORDER Property.

A heap is a binary TREE that is COMPLETELY filled with the POSSIBLE exception at the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree.

A heap is a binary tree that is completely filled with the possible exception at the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree.

In a HEAP, for EVERY NODE X, the key in the parent of X is smaller than (or equal to) the key in X, with the exception of the root (which has no parent).

In a heap, for every node X, the key in the parent of X is smaller than (or equal to) the key in X, with the exception of the root (which has no parent).

• The SELECTION PROBLEM.
• EVENT SIMULATION.

To insert an ELEMENT, we have to create a HOLE in the next available heap location. INSERTING an element in the hole would sometimes violate the heap order property, so we have to slide down the PARENT into the hole. This strategy is CONTINUED until the correct location for the new element is found. This general strategy is known as a percolate up; the new element is percolated up the heap until the correct location is found.

To insert an element, we have to create a hole in the next available heap location. Inserting an element in the hole would sometimes violate the heap order property, so we have to slide down the parent into the hole. This strategy is continued until the correct location for the new element is found. This general strategy is known as a percolate up; the new element is percolated up the heap until the correct location is found.

When the minimum element is removed, a hole is created at the root. Since the heap now becomes ONE smaller, it follows that the last element X in the heap must move somewhere in the heap. If X can be placed in the hole, then we are done.. This is UNLIKELY, so we slide the smaller of the hole’s children into the hole, thus PUSHING the hole down one level. We repeat this step until X can be placed in the hole. Thus, our action is to place X in its correct spot along a path from the root containing minimum children. This general strategy is KNOWN as PERCOLATE down.

When the minimum element is removed, a hole is created at the root. Since the heap now becomes one smaller, it follows that the last element X in the heap must move somewhere in the heap. If X can be placed in the hole, then we are done.. This is unlikely, so we slide the smaller of the hole’s children into the hole, thus pushing the hole down one level. We repeat this step until X can be placed in the hole. Thus, our action is to place X in its correct spot along a path from the root containing minimum children. This general strategy is known as percolate down.

Hashing is the transformation of string of CHARACTERS into a usually shorter fixed LENGTH value or key that represents the original string. Hashing is used to index and retrieve items in a DATABASE because it is faster to FIND the item using the short hashed key than to find it using the original value.

Hashing is the transformation of string of characters into a usually shorter fixed length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the short hashed key than to find it using the original value.

The hash table DATA structure is MERELY an array of some fixed size, containing the keys. A KEY is a STRING with an associated value. Each key is MAPPED into some number in the range 0 to tablesize-1 and placed in the appropriate cell.

The hash table data structure is merely an array of some fixed size, containing the keys. A key is a string with an associated value. Each key is mapped into some number in the range 0 to tablesize-1 and placed in the appropriate cell.

A hash FUNCTION is a key to ADDRESS TRANSFORMATION which acts upon a given key to COMPUTE the relative position of the key in an array. The choice of hash function should be simple and it must distribute the DATA evenly. A simple hash function is hash_key=key mod tablesize.

A hash function is a key to address transformation which acts upon a given key to compute the relative position of the key in an array. The choice of hash function should be simple and it must distribute the data evenly. A simple hash function is hash_key=key mod tablesize.

• Maps KEY with the corresponding value using hash function.
• Hash tables support the efficient addition of new ENTRIES and the TIME spent on searching for the required data is independent of the number of ITEMS STORED.

When an element is inserted, it HASHES to the same value as an already inserted element, and then it PRODUCES COLLISION.

When an element is inserted, it hashes to the same value as an already inserted element, and then it produces collision.

• Separate chaining or EXTERNAL hashing.
• OPEN addressing or CLOSED hashing.

Separate chaining is a collision resolution technique to keep the LIST of all ELEMENTS that hash to the same value. This is CALLED separate chaining because each hash table element is a separate chain (linked list). Each linked list contains all the elements WHOSE keys hash to the same INDEX.

Separate chaining is a collision resolution technique to keep the list of all elements that hash to the same value. This is called separate chaining because each hash table element is a separate chain (linked list). Each linked list contains all the elements whose keys hash to the same index.

More number of elements can be inserted as it USES LINKED LISTS.

More number of elements can be inserted as it uses linked lists.

• The elements are evenly distributed. Some elements may have more elements and some may not have anything.
• It requires pointers. This LEADS to slow the algorithm down a bit because of the time required to ALLOCATE new cells, and also ESSENTIALLY requires the implementation of a second data STRUCTURE.

OPEN addressing is a collision resolving strategy in which, if collision occurs alternative cells are tried until an EMPTY cell is found. The cells h0(X), H1(x), h2(x),…. are tried in succession, where hi(x)=(Hash(x)+F(i))mod Tablesize with F(0)=0. The function F is the collision resolution strategy.

Open addressing is a collision resolving strategy in which, if collision occurs alternative cells are tried until an empty cell is found. The cells h0(x), h1(x), h2(x),…. are tried in succession, where hi(x)=(Hash(x)+F(i))mod Tablesize with F(0)=0. The function F is the collision resolution strategy.

• LINEAR PROBING.
• QUADRATIC probing.
• DOUBLE HASHING.

Probing is the PROCESS of getting next AVAILABLE hash table ARRAY CELL.

Probing is the process of getting next available hash table array cell.

Linear PROBING is an open addressing collision resolution strategy in which F is a linear function of i, F(i)=i. This amounts to trying SEQUENTIALLY in search of an EMPTY cell. If the table is big enough, a free cell can always be found, but the time to do so can get QUITE large.

Linear probing is an open addressing collision resolution strategy in which F is a linear function of i, F(i)=i. This amounts to trying sequentially in search of an empty cell. If the table is big enough, a free cell can always be found, but the time to do so can get quite large.

In linear PROBING collision resolution strategy, even if the table is relatively empty, blocks of occupied CELLS start forming. This effect is known as primary clustering means that any KEY hashes into the CLUSTER will require several attempts to resolve the collision and then it will ADD to the cluster.

In linear probing collision resolution strategy, even if the table is relatively empty, blocks of occupied cells start forming. This effect is known as primary clustering means that any key hashes into the cluster will require several attempts to resolve the collision and then it will add to the cluster.

QUADRATIC probing is an open addressing collision resolution STRATEGY in which F(i)=i2. There is no guarantee of finding an empty cell once the table gets half full if the table size is not prime. This is because at most half of the table can be USED as ALTERNATIVE locations to resolve COLLISIONS.

Quadratic probing is an open addressing collision resolution strategy in which F(i)=i2. There is no guarantee of finding an empty cell once the table gets half full if the table size is not prime. This is because at most half of the table can be used as alternative locations to resolve collisions.

Although quadratic probing eliminates PRIMARY CLUSTERING, elements that hash to the same POSITION will PROBE the same ALTERNATIVE cells. This is known as secondary clustering.

Although quadratic probing eliminates primary clustering, elements that hash to the same position will probe the same alternative cells. This is known as secondary clustering.

Double HASHING is an OPEN addressing collision resolution strategy in which F(i)=i.hash2(X). This formula says that we apply a second hash function to X and probe at a distance hash2(X), 2hash2(X),….,and so on. A function such as hash2(X)=R-(XmodR), with R a prime SMALLER than Tablesize.

Double hashing is an open addressing collision resolution strategy in which F(i)=i.hash2(X). This formula says that we apply a second hash function to X and probe at a distance hash2(X), 2hash2(X),….,and so on. A function such as hash2(X)=R-(XmodR), with R a prime smaller than Tablesize.

If the table gets too full, the running time for the operations will START taking too long and inserts might fail for OPEN addressing with quadratic RESOLUTION. A solution to this is to build another table that is about twice as big with the associated new hash function and scan down the entire original hash table, computing the new hash value for each element and INSERTING it in the new table. This entire operation is CALLED rehashing.

If the table gets too full, the running time for the operations will start taking too long and inserts might fail for open addressing with quadratic resolution. A solution to this is to build another table that is about twice as big with the associated new hash function and scan down the entire original hash table, computing the new hash value for each element and inserting it in the new table. This entire operation is called rehashing.

If either open addressing hashing or separate chaining hashing is used, the major problem is that collisions could cause several BLOCKS to be examined during a Find, even for a well-distributed hash table. Extendible hashing allows a find to be PERFORMED in TWO DISK accesses. Insertions also REQUIRE few disk accesses.

If either open addressing hashing or separate chaining hashing is used, the major problem is that collisions could cause several blocks to be examined during a Find, even for a well-distributed hash table. Extendible hashing allows a find to be performed in two disk accesses. Insertions also require few disk accesses.

• Time TAKEN for FINDING the next AVAILABLE cell is large.
• In LINEAR probing, we come across a problem known as clustering.

Advantage: The PROBLEM of PRIMARY clustering is eliminated.
Disadvantage: There is no guarantee of finding an UNOCCUPIED cell once the table is NEARLY half full.

Advantage: The problem of primary clustering is eliminated.
Disadvantage: There is no guarantee of finding an unoccupied cell once the table is nearly half full.

A relation R is defined on a set S if for EVERY PAIR of ELEMENTS (a,B), a,b ε S, aRb is either true or false. If aRb is true, then we say that a is RELATED to b.

A relation R is defined on a set S if for every pair of elements (a,b), a,b ε S, aRb is either true or false. If aRb is true, then we say that a is related to b.

An equivalence relation is a relation R that satisfies THREE properties:

• (Reflexive) aRa, for all a ε S.
• (SYMMETRIC) aRb if and only if BRA.
• (Transitive) aRb and bRc implies that aRc.

An equivalence relation is a relation R that satisfies three properties:

• Maintaining a set of CONNECTED components of a graph.
• Maintain list of duplicate COPIES of web PAGES.
• CONSTRUCTING a minimum spanning TREE for a graph.

A collection of non-empty disjoint SETS S=S1,S2,….,Sk i.e;each Si is a non-empty SET that has no element in common with any other Sj. In mathematical NOTATION this is: Si∩Sj=Ф. Each set is identified by a unique element called its REPRESENTATIVE.

A collection of non-empty disjoint sets S=S1,S2,….,Sk i.e;each Si is a non-empty set that has no element in common with any other Sj. In mathematical notation this is: Si∩Sj=Ф. Each set is identified by a unique element called its representative.

A set S is an unordered collection of elements from a universe. An element cannot appear more than once in S. The CARDINALITY of S is the number of elements in S. An empty set is a set whose cardinality is ZERO. A SINGLETON set is a set whose cardinality is ONE.

A set S is an unordered collection of elements from a universe. An element cannot appear more than once in S. The cardinality of S is the number of elements in S. An empty set is a set whose cardinality is zero. A singleton set is a set whose cardinality is one.

Let S and T be SETS and e be an ELEMENT.

• SINGLETON(e) returns {e}.
• UNION(S,T) returns S Ụ T.
• INTERSECTION(S,T) returns S ∩ T.
• FIND returns the name of the set containing a GIVEN element.

Let S and T be sets and e be an element.

Keep TRACK of the weight IE; SIZE of each tree and always append the SMALLER tree to the larger one when performing UNION.

Keep track of the weight ie; size of each tree and always append the smaller tree to the larger one when performing UNION.

Path compression is PERFORMED during a Find operation. Suppose if we want to perform Find(X), then the EFFECT of path compression is that every NODE on the path from X to the root has its PARENT changed to the root.

Path compression is performed during a Find operation. Suppose if we want to perform Find(X), then the effect of path compression is that every node on the path from X to the root has its parent changed to the root.

A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a MAPPING from the set for edge E to a set of PAIRS of ELEMENTS of V. It can ALSO be REPRESENTED as G=(V, E).

A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set for edge E to a set of pairs of elements of V. It can also be represented as G=(V, E).

Any two nodes which are connected by an edge in a graph are called adjacent nodes. For EXAMPLE, if an edge X ε E is associated with a PAIR of nodes (u,v) where u, v ε V, then we say that the edge x CONNECTS the nodes u and v.

Any two nodes which are connected by an edge in a graph are called adjacent nodes. For example, if an edge x ε E is associated with a pair of nodes (u,v) where u, v ε V, then we say that the edge x connects the nodes u and v.

A GRAPH in which EVERY EDGE is DIRECTED is CALLED a directed graph.

A graph in which every edge is directed is called a directed graph.

A graph in which every EDGE is UNDIRECTED is called a DIRECTED graph.

A graph in which every edge is undirected is called a directed graph.