Collision Resolution Techniques

Types of Collision Resolution Techniques 

1. Open addressing (closed hashing), The methods used include: Overflow block.
2. Closed addressing (open hashing), The methods used include: Linked list, Binary tree.

Hashing Functions

Classify the Hashing Functions based on the various methods by which the key value is found.

1. Direct method,
2. Subtraction method,
3. Modulo-Division method,
4. Digit-Extraction method,
5. Mid-Square method,
6. Folding method,
7. Pseudo-random method. 

Bucket

One is the bucket size, when the overlapping and collision occur at same time. If there is only one entry possible in the bucket, when the collision occurs, there is no way to accommodate the colliding value. This results in the overlapping of values.

B+ Tree

In RDBMS, B+ tree is the efficient data structure used in the internal storage representation. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall be stored in leaf nodes.

Spanning Tree

A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

The Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn't mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

Linked List

According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Non-linear one.

AVL Tree

In an AVL tree, balancing is to be done, If the 'pivotal value' (or the 'Height factor') is greater than 1 or less than -1.

Backtracking algorithm or 8 Queens problem

Backtracking is a technique used to solve problems with a large search space, by systematically trying and eliminating possibilities.

Backtracking algorithm used in solving the 8 Queens problem.

Backtracking – Eight Queens Problem

Find an arrangement of 8 queens on a single chess board such that no two queens are attacking one another.
In chess, queens can move all the way down any row, column or diagonal (so long as no pieces are in the way).
Due to the first two restrictions, it's clear that each row and column of the board will have exactly one queen.

The backtracking strategy is as follows:
Place a queen on the first available square in row 1.

Move onto the next row, placing a queen on the first available square there (that doesn't conflict with the previously placed queens).
Continue in this fashion until either: you have solved the problem, or you get stuck.
When you get stuck, remove the queens that got you there, until you get to a row where there is another valid square to try.
When we carry out backtracking, an easy way to visualize what is going on is a tree that shows all the different possibilities that have been tried.
On the board we will show a visual representation of solving the 4 Queens problem (placing 4 queens on a 4x4 board where no two attack one another).
The neat thing about coding up backtracking, is that it can be done recursively, without having to do all the bookkeeping at once.
Instead, the stack or recursive calls does most of the bookkeeping (ie, keeping track of which queens we've placed, and which combinations we've tried so far, etc.)

perm[] - stores a valid permutation of queens from index 0 to location-1.
location – the column we are placing the next queen
usedList[] – keeps track of the rows in which the queens have already been placed.

void solveItRec(int perm[], int location, struct onesquare usedList[]) {

 //Found a solution to the problem, so print it! 
   if (location == SIZE) {
      printSol(perm);
  }
  //Loop through possible rows to place this queen.
  for (int i=0; i<SIZE; i++) {
       //Only try this row if it hasn’t been used
      if (usedList[i] == false) {
          if (!conflict(perm, location, i)) {
                //Check if this position conflicts with any previous queens on the diagonal 
                perm[location] = i; // mark the queen in this row
                 usedList[i] = true; // mark the row as used 
                solveItRec(perm, location+1, usedList); // solve the next column location recursively
                 usedList[i] = false;// un-mark the row as used, so we can get ALL possible valid solutions.
            }                                      
        }   
    }   
}

Another possible brute-force algorithm is generate the permutations of the numbers 1 through 8 (of which there are 8! = 40,320), and uses the elements of each permutation as indices to place a queen on each row.  Then it rejects those boards with diagonal attacking positions.

The backtracking algorithm, is a slight improvement on the permutation method, constructs the search tree by considering one row of the board at a time, eliminating most non-solution board positions at a very early stage in their construction. Because it rejects row and diagonal attacks even on incomplete boards, it examines only 15,720 possible queen placements.

A further improvement which examines only 5,508 possible queen placements is to combine the permutation based method with the early pruning method: The permutations are generated depth-first, and the search space is pruned if the partial permutation produces a diagonal attack 

File Structure

Sequential is the simplest file structure.


Methods available in storing sequential files

1. Straight merging,
2. Natural merging,
3. Polyphase sort,
4. Distribution of Initial runs. 

Notations

Polish and Reverse Polish Notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms.

Example: Convert the expression ((A + B) * C - (D - E) ^ (F + G)) to equivalent Prefix and Postfix notations.

1. Prefix Notation: - * +ABC ^ - DE + FG
2. Postfix Notation: AB + C * DE - FG + ^ -

Sorting

• Sorting is not possible in Deletion. 
• Using insertion we can perform insertion sort, 
• Using selection we can perform selection sort, 
• Using exchange we can perform the bubble sort 

Tree Data Structure

In Tree construction Linked list is the suitable efficient data structure.

Application of Tree Data Structure

1. The manipulation of Arithmetic expression,
2. Symbol Table construction,
3. Syntax analysis.

Multilinked Structures

Applications that make use of Multilinked Structures

1. Sparse matrix,
2. Index generation. 

Stack or Recursion

Stack is used to perform recursion. Because of its LIFO (Last In First Out) property it remembers its 'caller' so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.

Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.

Priority Queue

Minimum Two queues needed to implement the priority queue.

One queue is used for actual storing of data and another for storing priorities.

Heterogeneous Linked List

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

Data Structure Introduction

In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. A data structure is not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.

Data Structures are applied extensively:

1. Compiler Design,
2. Operating System,
3. Database Management System,
4. Statistical analysis package,
5. Numerical Analysis,
6. Graphics,
7. Artificial Intelligence,
8. Simulation

 Major data structures used in the following areas :

1. RDBMS = Array (i.e. Array of structures)
2. Network data model = Graph
3. Hierarchical data model = Trees