Implementation of Priority Queue in Javascript

  1. Each element of the priority queue has an property associated with it.
  2. Elements are added to the queue as per the priority.
  3. Lowest priority elements are removed first.

We can design a priority queue using two approaches in the first case we can add the queue element at the end of the queue and we can remove the elements of the queue depending on the priority. In the second case we can add elements to the queue according to the priority and remove them from the front of the queeue. In this article we would use the second approach to implement a Priority Queue.
Note: Assuming a Priority queue can grow dynamically we are not considering the overflow condition.
Let’s see an example of a priority queue class:
Example:

// User defined class
// to store element and its priority
class QElement {
    constructor(element, priority)
    {
        this.element = element;
        this.priority = priority;
    }
}
// PriorityQueue class
class PriorityQueue {
    // An array is used to implement priority
    constructor()
    {
        this.items = [];
    }
    // functions to be implemented
    // enqueue(item, priority)
    // dequeue()
    // front()
    // isEmpty()
    // printPQueue()
}

As you can see in the example above we have defined skeleton of PriorityQueue class. We have use an user defined class QElement having two property element and priority. We have used an array in PriorityQueue class to implement priority queue, this array is a container of QElement.

  1. enqueue() – adds an element to the queue according to its priority.
    // enqueue function to add element
    // to the queue as per priority
    enqueue(element, priority)
    {
        // creating object from queue element
        var qElement = new QElement(element, priority);
        var contain = false;
        // iterating through the entire
        // item array to add element at the
        // correct location of the Queue
        for (var i = 0; i < this.items.length; i++) {
            if (this.items[i].priority > qElement.priority) {
                // Once the correct location is found it is
                // enqueued
                this.items.splice(i, 0, qElement);
                contain = true;
                break;
            }
        }
        // if the element have the highest priority
        // it is added at the end of the queue
        if (!contain) {
            this.items.push(qElement);
        }
    }

    In this method we create a qElement have property element and priority. Then we iterate over the queue to find the correct location of the qElement according to its priority and add it.

  2. dequeue() – Removes an element from the priority queue
    // dequeue method to remove
    // element from the queue
    dequeue()
    {
        // return the dequeued element
        // and remove it.
        // if the queue is empty
        // returns Underflow
        if (this.isEmpty())
            return "Underflow";
        return this.items.shift();
    }

    This function removes an element from the front of a queue as the highest priority element is stored at the front of the priority queue. We have used shift method of an array to remove an element from the queue.

  3. front() – returns the front element of the Priority queue
    // front function
    front()
    {
        // returns the highest priority element
        // in the Priority queue without removing it.
        if (this.isEmpty())
            return "No elements in Queue";
        return this.items[0];
    }

    This function returns the front element of the Priority queue. We simply return the 0th element of an array to get the front of a Priority queue.

  4. rear() – returns the last element of the Priority queue
    // rear function
    rear()
    {
        // returns the lowest priorty
        // element of the queue
        if (this.isEmpty())
            return "No elements in Queue";
        return this.items[this.items.length - 1];
    }

    This functions return the last element of the queue or lowest priority element.

Helper Methods:
Let’s declare some helper method which is quite useful while working with the Priority queue queue.

  1. isEmpty() – Returns true if the Priority queue is empty
    // isEmpty function
    isEmpty()
    {
        // return true if the queue is empty.
        return this.items.length == 0;
    }

    We have used the length property of an array to get the length and if its 0 then priority queue is empty.

  2. printPQueue – It prints the element of the queue as per the priority starting from highest to lowest
    // printQueue function
    // prints all the element of the queue
    printPQueue()
    {
        var str = "";
        for (var i = 0; i < this.items.length; i++)
            str += this.items[i].element + " ";
        return str;
    }

    In this method we concatenate the element property of each priority queue item into an string.

Note :- Here we consider ” 1 ” as the highest priority element, you can modify this as per the requirement.
Implementation
Now Let use this Priority Queue class and its different method described above

 

// creating object for queue classs
var priorityQueue = new PriorityQueue();
// testing isEmpty and front on an empty queue
// return true
console.log(priorityQueue.isEmpty());
// returns "No elements in Queue"
console.log(priorityQueue.front());
// adding elements to the queue
priorityQueue.enqueue("Sumit", 2);
priorityQueue.enqueue("Gourav", 1);
priorityQueue.enqueue("Piyush", 1);
priorityQueue.enqueue("Sunny", 2);
priorityQueue.enqueue("Sheru", 3);
// prints [Gourav Piyush Sumit Sunny Sheru]
console.log(priorityQueue.printPQueue());
// prints Gourav
console.log(priorityQueue.front().element);
// pritns Sheru
console.log(priorityQueue.rear().element);
// removes Gouurav
// priorityQueue contains
// [Piyush Sumit Sunny Sheru]
console.log(priorityQueue.dequeue().element);
// Adding another element to the queue
priorityQueue.enqueue("Sunil", 2);
// prints [Piyush Sumit Sunny Sunil Sheru]
console.log(priorityQueue.printPQueue());

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Python | Set 2 (Variables, Expressions, Conditions and Functions)

 

Running your First Code in Python
Python programs are not compiled, rather they are interpreted. Now, let us move to writing a python code and running it. Please make sure that python is installed on the system you are working. We will be using python 2.7.

Making a Python file:
Python files are stored with the extension “.py”. Open text editor and save a file with the name “hello.py”. Open it and write the following code:

print "Hello World"
# Notice that NO semi-colon is to be used

Reading the file contents:
Linux System – Move to the directory from terminal where the created file (hello.py) is stored by using the ‘cd’ command, and then type the following in the terminal :

python hello.py

Windows system – Open command prompt and move to the directory where the file is stored by using the ‘cd’ command and then run the file by writing the file name as command.
running python file in windows system

Variables in Python
Variables need not be declared first in python. They can be used directly. Variables in python are case sensitive as most of the other programming languages.
Example:

a = 3
A = 4
print a
print A

The output is :

3
4

Expressions in Python
Arithmetic operations in python can be performed by using arithmetic operators and some of the in-built functions.

a = 2
b = 3
c = a + b
print c
d = a * b
print d

The output is :

5
6

Conditions in Python
Conditional output in python can be obtained by using if-else and elif (else if) statements.

a = 3
b = 9
if b % a == 0 :
    print "b is divisible by a"
elif b + 1 == 10:
    print "Increment in b produces 10"
else:
    print "You are in else statement"

The output is :

b is divisible by a

Functions in Python
A function in python is declared by the keyword ‘def’ before the name of the function. The return type of the function need not be specified explicitly in python. The function can be invoked by writing the function name followed by the parameter list in the brackets.

# Function for checking the divisibility
# Notice the indentation after function declaration
# and if and else statements
def checkDivisibility(a, b):
    if a % b == 0 :
        print "a is divisible by b"
    else:
        print "a is not divisible by b"
#Driver program to test the above function
checkDivisibility(4, 2)

The output is :

a is divisible by b


Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Puzzle | Couples crossing the river

Three couples are on the vacation.They need to cross the river to reach their hotel. There are 3 rules which are as follows:-
Rule 1:- The boat can only carry two people at a time. If the third person trying to get in the boat then the boat will sink.
Rule 2:- The husbands are so jealous that they can not let their wife with another man, without their presence.
Rule 3:- The boat cannot run on itself. At-least one person should be on the boat to go from one side to another.

How many trips does it take them to all get across the river?
Note:The couples can be identified by their matching color clothes and there is no other way of going to hotel.


Solution:

Let the 3 couples have wore green, red and blue dresses.So, there should be green wife and green husband, red wife and red husband, blue wife and blue husband.
Step 1:-Green couple will go to the hotel side and green husband will return with the boat.(2 moves)
Step 2:-Now red wife and blue wife will go to the hotel side and red wife will return with the boat.(2 moves)
Step 3:-Green husband and blue husband will go to the hotel side and blue couple will return with the boat.(2 moves)
Step 4:-Red husband and blue husband will go to the hotel side and green wife will return with the boat.(2 moves)
Step 5:-Red wife and blue wife will go to the hotel side and blue wife will return with the boat.(2 moves)
Step 6:-Finally, blue wife and red wife will go the hotel side.(1 move)

So, there will be a total of 11 steps.

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Why do you need a Responsive Website

Mobile internet usage is growing at a steady pace, so much so that it is expected to overtake desktop browsing as early as 2016. It means that it has become more than necessary for website owners to think about channelizing their work into designing mobile friendly, handheld device compliant websites.Responsive Website2

What is a Responsive Website?

A responsive website, simply improves the viewing experience; it fits into any device irrespective of resolution. It means a responsive website virtually fits into any device that uses a web browser. Other than being compatible with a unique variety of resolutions, a responsive website works flawlessly across a range of devices, including smartphones, tablets and smartphones.

Why you need to consider a Responsive Website?

No more abandoned checkout at online stores and cluttered viewing experience. With a website fast and responsive you can load it effortlessly. Smartphones can be a great device for viewing websites but when it comes to legibly search out data or filling out information on a website, even smartphones require the loading of mobile friendly websites. With a responsive website, you can ensure easier and effortless browsing

Have a Unique Type of Specific Content

A responsive website quite often uncomplicates the entire task of bowing. With a website that is responsive you can display specific content. For example; if you are organizing information on your website using a display ad, it would pop up differently on different devices, somewhere with uneven aspect ratio. With a responsive website built to work, you can use thumbnails and specific points of contacts to evenly manage ads

Single Format of App

If a website is built compatible for devices, you require not to invest individually to have applications. It means you can keep your cost down, while allowing your website to have a unique application on different variety of devices. So, no need to develop a unique app for different app source

Different other benefits of having a responsive website

SEO benefits – Instead of having an SEO campaign for sites where your website  hosted, with responsive website you can just need to do only SEO for your source.

  • A responsive website is often the answer to a modern website that is neatly designed
  • A responsive website needs you to publish content only once while you require not to write the content again for a different source.

These are some of the vital benefits of having a responsive website. If you require an articulated website, with unique loading attribute; that never works off the mark; rather put your brand to your audience in an improved manner; you can think about utilizing a responsive website. Having a responsive website depends on how you use it.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Comma in C and C++

In C and C++, comma (,) can be used in two contexts:

1) Comma as an operator:
The comma operator (represented by the token ,) is a binary operator that evaluates its first operand and discards the result, it then evaluates the second operand and returns this value (and type). The comma operator has the lowest precedence of any C operator, and acts as a sequence point.

/* comma as an operator */
int i = (5, 10);  /* 10 is assigned to i*/
int j = (f1(), f2());  /* f1() is called (evaluated) first followed by f2().
The returned value of f2() is assigned to j */

2) Comma as a separator:
Comma acts as a separator when used with function calls and definitions, function like macros, variable declarations, enum declarations, and similar constructs.

/* comma as a separator */
int a = 1, b = 2;
void fun(x, y);

The use of comma as a separator should not be confused with the use as an operator. For example, in below statement, f1() and f2() can be called in any order.

/* Comma acts as a separator here and doesn't enforce any sequence.
    Therefore, either f1() or f2() can be called first */
void fun(f1(), f2());

 

You can try below programs to check your understanding of comma in C.

// PROGRAM 1
#include<stdio.h>
int main()
{
   int x = 10;
   int y = 15;
 
   printf("%d", (x, y));
   getchar();
   return 0;
}
// PROGRAM 2:  Thanks to Shekhu for suggesting this program
#include<stdio.h>
int main()
{
   int x = 10;
   int y = (x++, ++x);
   printf("%d", y);
   getchar();
   return 0;
}
// PROGRAM 3:  Thanks to Venki for suggesting this program
intmain()
{
    intx = 10, y;
 
    // The following is equavalent to y = x++
    y = (x++, printf("x = %d\n", x), ++x, printf("x = %d\n", x), x++);
 
    // Note that last expression is evaluated
    // but side effect is not updated to y
    printf("y = %d\n", y);
    printf("x = %d\n", x);
 
    return0;
}
Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Core Dump (Segmentation fault) in C/C++

Core Dump/Segmentation fault is a specific kind of error caused by accessing memory that “does not belong to you.”

  • When a piece of code tries to do read and write operation in a read only location in memory or freed block of memory, it is known as core dump.
  • It is an error indicating memory corruption.

Common segmentation fault scenarios:

  • Modifying a string literal :
    The below program may crash (gives segmentation fault error) because the line *(str+1) = ‘n’ tries to write a read only memory.

    int main()
    {
       char *str;
       /* Stored in read only part of data segment */
       str = "GfG";    
       /* Problem:  trying to modify read only memory */
       *(str+1) = 'n';
       return 0;
    }

    Abnormal termination of program.
    

     

  • Accessing an address that is freed :
    Here in the below code, the pointer p is dereferenced after freeing the memory block, which is not allowed by the compiler. So it produces the error segment fault or abnormal program termination at runtime.
    Example:

    // C program to illustrate
    // Core Dump/Segmentation fault
    #include <stdio.h>
    #include<alloc.h>
    int main(void)
    {
        // allocating memory to p
        int* p = malloc(8);
        *p = 100;
        
        // deallocated the space allocated to p
        free(p);
        
        // core dump/segmentation fault
        //  as now this statement is illegal
        *p = 110;
        
        return 0;
    }

    Output:

    Abnormal termination of program.
    
  • Accessing out of array index bounds :
    // C++ program to demonstrate segmentation
    // fault when array out of bound is accessed.
    #include <iostream>
    using namespace std;
    int main()
    {
       int arr[2];
       arr[3] = 10;  // Accessing out of bound
       return 0;
    }

    Output:

    Abnormal termination of program.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Project Idea | (Model based Image Compression of Medical Images)

The project is about providing fast transfer of medical images to/from rural areas where bandwidth is low. The idea is to keep model medical images at all locations (rural and urban). To transfer a patient’s image from one location to another, find the difference image from patients image to model image. The difference image would have less data to transfer. To further minimize size of difference image, use Image Registration. So the sending side sends a difference image, the receiving side adds this image to model image to get the patient’s image.

Research:
There can be specialized methods to compress difference images. One method is discussed in below reference paper.

Tools:
If we want to do research oriented project for compression, Matlab can be used. To build complete application with networking, Java can be used.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Divide and Conquer | Set 5 (Strassen’s Matrix Multiplication)

Given two square matrices A and B of size n x n each, find their multiplication matrix.

Naive Method
Following is a simple way to multiply two matrices.

void multiply(int A[][N], int B[][N], int C[][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            C[i][j] = 0;
            for (int k = 0; k < N; k++)
            {
                C[i][j] += A[i][k]*B[k][j];
            }
        }
    }
}

Time Complexity of above method is O(N3).

Divide and Conquer
Following is simple Divide and Conquer method to multiply two square matrices.
1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.
2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

strassen_new

In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N2) time. So the time complexity can be written as

T(N) = 8T(N/2) + O(N2)

From Master's Theorem, time complexity of above method is O(N3)
which is unfortunately same as the above naive method.

Simple Divide and Conquer also leads to O(N3), can there be a better way?
In the above divide and conquer method, the main component for high time complexity is 8 recursive calls. The idea of Strassen’s method is to reduce the number of recursive calls to 7. Strassen’s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the above diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.

stressen_formula_new_new

Time Complexity of Strassen’s Method
Addition and Subtraction of two matrices takes O(N2) time. So time complexity can be written as

T(N) = 7T(N/2) +  O(N2)

From Master's Theorem, time complexity of above method is
O(NLog7) which is approximately O(N2.8074)

Generally Strassen’s Method is not preferred for practical applications for following reasons.
1) The constants used in Strassen’s method are high and for a typical application Naive method works better.
2) For Sparse matrices, there are better methods especially designed for them.
3) The submatrices in recursion take extra space.
4) Because of the limited precision of computer arithmetic on noninteger values, larger errors accumulate in Strassen’s algorithm than in Naive Method.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Rearrange positive and negative numbers in O(n) time and O(1) extra space

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

The solution is to first separate positive and negative numbers using partition process of QuickSort. In the partition process, consider 0 as value of pivot element so that all negative numbers are placed before positive numbers. Once negative and positive numbers are separated, we start from the first negative number and first positive number, and swap every alternate negative number with next positive number.

// A C++ program to put positive numbers at even indexes (0,
// 2, 4,..) and negative numbers at odd indexes (1, 3, 5, ..)
#include <stdio.h>
// prototype for swap
void swap(int *a, int *b);
// The main function that rearranges elements of given array.
// It puts  positive elements at even indexes (0, 2, ..) and
// negative numbers at odd indexes (1, 3, ..).
void rearrange(int arr[], int n)
{
    // The following few lines are similar to partition process
    // of QuickSort.  The idea is to consider 0 as pivot and
    // divide the array around it.
    int i = -1;
    for (int j = 0; j < n; j++)
    {
        if (arr[j] < 0)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // Now all positive numbers are at end and negative numbers
    // at the beginning of array. Initialize indexes for starting
    // point of positive and negative numbers to be swapped
    int pos = i+1, neg = 0;
    // Increment the negative index by 2 and positive index by 1,
    // i.e., swap every alternate negative number with next
    // positive number
    while (pos < n && neg < pos && arr[neg] < 0)
    {
        swap(&arr[neg], &arr[pos]);
        pos++;
        neg += 2;
    }
}
// A utility function to swap two elements
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
// A utility function to print an array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%4d ", arr[i]);
}
// Driver program to test above functions
int main()
{
    int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrange(arr, n);
    printArray(arr, n);
    return 0;
}

Output:

    4   -3    5   -1    6   -7    2    8    9

Time Complexity: O(n) where n is number of elements in given array.
Auxiliary Space: O(1)

Note that the partition process changes relative order of elements.

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

Returning Multiple values in Java

Java doesn’t support multi-value returns. We can use following solutions to return multiple values.

 

If all returned elements are of same type

We can return an array in Java. Below is a Java program to demonstrate the same.

// A Java program to demonstrate that a method
// can return multiple values of same type by
// returning an array
class Test
{
    // Returns an array such that first element
    // of array is a+b, and second element is a-b
    static int[] getSumAndSub(int a, int b)
    {
        int[] ans = new int[2];
        ans[0] = a + b;
        ans[1] = a - b;
        // returning array of elements
        return ans;
    }
    // Driver method
    public static void main(String[] args)
    {
        int[] ans = getSumAndSub(100,50);
        System.out.println("Sum = " + ans[0]);
        System.out.println("Sub = " + ans[1]);
    }
}

The output of the above code will be:

Sum = 150
Sub = 50

 

If returned elements are of different types

We can be encapsulate all returned types into a class and then return an object of that class.

Let us have a look at the following code.

// A Java program to demonstrate that we can return
// multiple values of different types by making a class
// and returning an object of class.
// A class that is used to store and return
// two members of different types
class MultiDiv
{
    int mul;    // To store multiplication
    double div; // To store division
    MultiDiv(int m, double d)
    {
        mul = m;
        div = d;
    }
}
class Test
{
    static MultiDiv getMultandDiv(int a, int b)
    {
        // Returning multiple values of different
        // types by returning an object
        return new MultiDiv(a*b, (double)a/b);
    }
    // Driver code
    public static void main(String[] args)
    {
        MultiDiv ans = getMultandDiv(10, 20);
        System.out.println("Multiplication = " + ans.mul);
        System.out.println("Division = " + ans.div);
    }
}

Output:

 Multiplication = 200
Division = 0.5



Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org