Data structure - What is a matrix? Explain its uses with an example - Learnengineeringforu

Data structure - What is a matrix? Explain its uses with an example - Learnengineeringforu

Home   December 19, 2018

What is a matrix? Explain its uses with an example

Matrix is a way to store data in an organized form in the form of rows and columns. Matrices are usually used in computer graphics to project 3-dimensional space into a 2-Dimensional screen.Matrices in the form of arrays are used to store data in an organized form.

What is a matrix? Explain its uses with an example

A matrix is arepresentatio of certain rows and columns, to persist homogenius data. It can also be called as double-dimensional array.

Uses:

-To represent class hierarchy using Boolean square matrix

-  For data encryption and decryption

- To represent traffic flow and plumbing in a network

- To implement graph theory of node representation

Data Structure - Graph Data Structure - Learnengineeringforu

Data Structure - Graph Data Structure - Learnengineeringforu

Home   December 19, 2018

A graph is pictorial representation of a set of objects where some pairs of objects are cnnects by links. The interconnected objects are represented by points termed as Vertices, and the links that connect the vertices are called edges.

Formally, a graph is a pair of sets (V,E),Where V is the et of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph -

                                                
In the above graph,
V={a, b, c, d, e}
E={ab, ac, bd, cd, de}

Graph Data Structure

Mathematical graphs can be represented in data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let's familiarize ourselves with some important terms −

• Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
• Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
• Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
• Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D. 
•                             

Basic Operations

Following are basic primary operations of a Graph -

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.
• 
  

This article is contributed by Khan Shadab Alam. If you like Learnengneeringforu and would like to contribute, you can also write an article for our learnenrs.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Data Structure and Algorithm Hashing - Learnengineeringforu

Data Structure and Algorithm Hashing - Learnengineeringforu

Home   December 19, 2018

Hashing Data Structure

Introduction: 

Hashing is an important Data structure which is designed to use a special function called the Hash function which is used to map a given Value with a particular key for faster access of elements.The efficiency of Mapping depends of the efficiency of the hash function used.

Index Mapping (or Trivial Hashing) with negatives allowed

Given a limited range array contains both positive and non positive numbers,i.e.,elements are in range from -MAX to +MAX. Our task is to search if some number is present in the array or not in O(1) time.

Since range is limited, we can use index mapping(or trivial hashing).We use values as index in a big array. Therefore we can search and insert elements in O(1) time.

Assign all the values of the hash matrix as 0.
Traverse the given array:
    If the element ele is non negative assign 
        hash[ele][0] as 1.
    Else take the absolute value of ele and 
         assign hash[ele][1] as 1.

To search any elements x in the array.

If X is non-negative check if hash[X][0] is 1 or not. If Hash[X][0] is one then the number is present else not present.

If X is negative take absolute value of X and then check if hash[X][1] is 1 or not. if hash [X][1] is one then the number is present.

Below is the implementation of the above idea.

C++ 

// CPP program to implement direct index mapping

// with negative values allowed.

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

  

// Since array is global, it is initialized as 0.

bool has[MAX + 1][2];

  

// searching if X is Present in the given array 

// or not.

bool search(int X)

{

    if (X >= 0) {

        if (has[X][0] == 1)

            return true;

        else

            return false;

    }

  

    // if X is negative take the absolute 

    // value of X.

    X = abs(X);

    if (has[X][1] == 1)

        return true;

  

    return false;

}

  

void insert(int a[], int n)

{

    for (int i = 0; i < n; i++) {

        if (a[i] >= 0) 

            has[a[i]][0] = 1;

       else

            has[abs(a[i])][1] = 1;

    }

}

  

// Driver code

int main()

{

    int a[] = { -1, 9, -5, -8, -5, -2 };

    int n = sizeof(a)/sizeof(a[0]);

    insert(a, n);

    int X = -5;

    if (search(X) == true)

       cout << "Present"; 

    else

       cout << "Not Present";

    return 0;

}




Java

// Java program to implement direct index 

// mapping with negative values allowed. 

class GFG

{

  

final static int MAX = 1000;

  

// Since array is global, it 

// is initialized as 0. 

static boolean[][] has = new boolean[MAX + 1][2];

  

// searching if X is Present in 

// the given array or not. 

static boolean search(int X) 

{

    if (X >= 0) 

    {

        if (has[X][0] == true) 

        {

            return true;

        } 

        else 

        {

            return false;

        }

    }

  

    // if X is negative take the 

    // absolute value of X. 

    X = Math.abs(X);

    if (has[X][1] == true) 

    {

        return true;

    }

  

    return false;

}

  

static void insert(int a[], int n) 

{

    for (int i = 0; i < n; i++) 

    {

        if (a[i] >= 0) 

        {

            has[a[i]][0] = true;

        } 

        else 

        {

            has[Math.abs(a[i])][1] = true;

        }

    }

}

  

// Driver code 

public static void main(String args[]) 

{

    int a[] = {-1, 9, -5, -8, -5, -2};

    int n = a.length;

    insert(a, n);

    int X = -5;

    if (search(X) == true)

    {

        System.out.println("Present");

    } 

    else 

    {

        System.out.println("Not Present");

    }

}

}

  

C#

// C# program to implement direct index

// mapping with negative values allowed.

using System;

class GFG
{

static int MAX = 1000;

// Since array is global, it
// is initialized as 0.
static bool[,] has = new bool[MAX + 1, 2];

// searching if X is Present in
// the given array or not.
static bool search(int X)
{
if (X >= 0)
{
if (has[X, 0] == true)
{
return true;
}
else
{
return false;
}
}

// if X is negative take the
// absolute value of X.
X = Math.Abs(X);
if (has[X, 1] == true)
{
return true;
}

return false;
}

static void insert(int[] a, int n)
{
for (int i = 0; i < n; i++) { if (a[i] >= 0)
{
has[a[i], 0] = true;
}
else
{
has[Math.Abs(a[i]), 1] = true;
}
}
}

// Driver code
public static void Main()
{
int[] a = {-1, 9, -5, -8, -5, -2};
int n = a.Length;
insert(a, n);
int X = -5;
if (search(X) == true)
{
Console.WriteLine(“Present”);
}
else
{
Console.WriteLine(“Not Present”);
}
}
}

// This code is contributed
// by Akanksha Rai

Output:

Present

This article is contributed by Khan Shadab Alam. If you like Learnengneeringforu 

and would like to contribute, you can also write an article for our learnenrs.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.