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

A Group chat application in Java

In this post, a group chat application using MulticastSocket (Java Platform SE 7) class is discussed. A MulticastSocket is a (UDP) DatagramSocket, with additional capabilities for joining “groups” of other multicast hosts on the internet.

Implementation

import java.net.*;
import java.io.*;
import java.util.*;
public class GroupChat
{
    private static final String TERMINATE = "Exit";
    static String name;
    static volatile boolean finished = false;
    public static void main(String[] args)
    {
        if (args.length != 2)
            System.out.println("Two arguments required:
            <multicast-host> <port-number>");
        else
        {
            try
            {
                InetAddress group = InetAddress.getByName(args[0]);
                int port = Integer.parseInt(args[1]);
                Scanner sc = new Scanner(System.in);
                System.out.print("Enter your name: ");
                name = sc.nextLine();
                MulticastSocket socket = new MulticastSocket(port);
            
                // Since we are deploying
                socket.setTimeToLive(0);
                this on localhost only (For a subnet set it as 1)
                socket.joinGroup(group);
                Thread t = new Thread(new
                ReadThread(socket,group,port));
            
                // Spawn a thread for reading messages
                t.start();
                
                // sent to the current group
                System.out.println("Start typing messages...\n");
                while(true)
                {
                    String message;
                    message = sc.nextLine();
                    if(message.equalsIgnoreCase(GroupChat.TERMINATE))
                    {
                        finished = true;
                        socket.leaveGroup(group);
                        socket.close();
                        break;
                    }
                    message = name + ": " + message;
                    byte[] buffer = message.getBytes();
                    DatagramPacket datagram = new
                    DatagramPacket(buffer,buffer.length,group,port);
                    socket.send(datagram);
                }
            }
            catch(SocketException se)
            {
                System.out.println("Error creating socket");
                se.printStackTrace();
            }
            catch(IOException ie)
            {
                System.out.println("Error reading/writing from/to
                socket");
                ie.printStackTrace();
            }
        }
    }
}
class ReadThread implements Runnable
{
    private MulticastSocket socket;
    private InetAddress group;
    private int port;
    private static final int MAX_LEN = 1000;
    ReadThread(MulticastSocket socket,InetAddress group,int port)
    {
        this.socket = socket;
        this.group = group;
        this.port = port;
    }
    
    @Override
    public void run()
    {
        while(!GroupChat.finished)
        {
                byte[] buffer = new byte[ReadThread.MAX_LEN];
                DatagramPacket datagram = new
                DatagramPacket(buffer,buffer.length,group,port);
                String message;
            try
            {
                socket.receive(datagram);
                message = new
                String(buffer,0,datagram.getLength(),"UTF-8");
                if(!message.startsWith(GroupChat.name))
                    System.out.println(message);
            }
            catch(IOException e)
            {
                System.out.println("Socket closed!");
            }
        }
    }
}

Save the file as GroupChat.java and compile it using javac and then run the program using two command line arguments as specified. A multicast host is specified by a class D IP address and by a standard UDP port number. Class D IP addresses are in the range 224.0.0.0 to 239.255.255.255, inclusive. The address 224.0.0.0 is reserved and should not be used.
Here is a sample output of the above program:
multicast socket api in java

multicast socket api in java1multicast socket api in java12
We have used the multicast host IP address as 239.0.0.0 and the port number as 1234 (since the port numbers 0 through 1023 are reserved). There are 3 members in the group: Ironman, CaptainAmerica, and Groot. Start all three terminals first before sending the message, otherwise messages which are sent before starting the terminal are lost (since there is no facility of buffer incorporated to store the messages.) We need two threads in this application. One for accepting the user input (using the java.util.Scanner class) and the other for reading the messages sent from other clients. Hence I have separated the thread which does the reading work into ReadThreadclass. For leaving the group, any of the user can type in Exit to terminate the session.

The above program is executed on a single machine. Socket programming is meant for distributed programming. The same piece of code snippet when present on different machines which have Java installed can satisfy that requirement. This is just the bare bones service logic. The project would be even more fascinating if the front-end is developed. You can use Java’s AWT (Abstract Window Toolkit) or its advanced counterpart, Java Swing to develop the front end. Since this wouldn’t be part of Socket programming I’m leaving it untouched without getting into the details.
Additional points:

  • You can incorporate network security feature by performing encryption before sending the message over the network.
  • Primitive techniques such as Caesar cipher or advanced methods such as RSA can be used to perform encryption-decryption. You can try using Java’s RMI (Remote Method Invocation) to perform the same task.
  • Here, you can leverage the abstraction offered by Java to maximum extent. However, if your primary objective is efficiency, then Socket programming is the best choice. Since it doesn’t require any run time support, it is a bit faster compared to RMI.

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

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

Main thread in Java

Java provides built-in support for multithreaded programming. A multi-threaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread, and each thread defines a separate path of execution.

Main Thread

When a Java program starts up, one thread begins running immediately. This is usually called the main thread of our program, because it is the one that is executed when our program begins.

Properties :

  • It is the thread from which other “child” threads will be spawned.
  • Often, it must be the last thread to finish execution because it performs various shutdown actions

Flow diagram :

main thread in java

How to control Main thread

The main thread is created automatically when our program is started. To control it we must obtain a reference to it. This can be done by calling the method currentThread( ) which is present in Thread class. This method returns a reference to the thread on which it is called. The default priority of Main thread is 5 and for all remaining user threads priority will be inherited from parent to child.

// Java program to control the Main Thread
public class Test extends Thread
{
    public static void main(String[] args)
    {
        // getting reference to Main thread
        Thread t = Thread.currentThread();
        
        // getting name of Main thread
        System.out.println("Current thread: " + t.getName());
        
        // changing the name of Main thread
        t.setName("Geeks");
        System.out.println("After name change: " + t.getName());
        
        // getting priority of Main thread
        System.out.println("Main thread priority: "+ t.getPriority());
        
        // setting priority of Main thread to MAX(10)
        t.setPriority(MAX_PRIORITY);
        
        System.out.println("Main thread new priority: "+ t.getPriority());
        
        
        for (int i = 0; i < 5; i++)
        {
            System.out.println("Main thread");
        }
        
        // Main thread creating a child thread
        ChildThread ct = new ChildThread();
        
        // getting priority of child thread
        // which will be inherited from Main thread
        // as it is created by Main thread
        System.out.println("Child thread priority: "+ ct.getPriority());
        
        // setting priority of Main thread to MIN(1)
        ct.setPriority(MIN_PRIORITY);
        
        System.out.println("Child thread new priority: "+ ct.getPriority());
        
        // starting child thread
        ct.start();
    }
}
// Child Thread class
class ChildThread extends Thread
{
    @Override
    public void run()
    {
        for (int i = 0; i < 5; i++)
        {
            System.out.println("Child thread");
        }
    }
}

Output:

Current thread: main
After name change: Geeks
Main thread priority: 5
Main thread new priority: 10
Main thread
Main thread
Main thread
Main thread
Main thread
Child thread priority: 10
Child thread new priority: 1
Child thread
Child thread
Child thread
Child thread
Child thread

Relation between the main() method and main thread in Java

For each program, a Main thread is created by JVM(Java Virtual Machine). The “Main” thread first verifies the existence of the main() method, and then it initializes the class. Note that from JDK 6, main() method is mandatory in a standalone java application.

Deadlocking with use of Main Thread(only single thread)

We can create a deadlock by just using Main thread, i.e. by just using a single thread. The following java program demonstrate this.

// Java program to demonstrate deadlock
// using Main thread
public class Test
{
    public static void main(String[] args)
    {
        try
        {
            
            System.out.println("Entering into Deadlock");
            
            Thread.currentThread().join();
            
            // the following statement will never execute
            System.out.println("This statement will never execute");
            
        }
        
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }
    }
}

Output:

Entering into Deadlock

Explanation :
The statement “Thread.currentThread().join()”, will tell Main thread to wait for this thread(i.e. wait for itself) to die. Thus Main thread wait for itself to die, which is nothing but a deadlock.

 

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