Longest Increasing Sub-sequence

Given a sequence of numbers,we need to find the longest increasing sub-sequence from the given input(not necessary continuous).

Example-

Input- 1 10 4 5 3 2 9 11 13

Increasing Sub-sequences-

1 4 5
5 9 11 13
10 11 13
4 5 9,etc

Longest Increasing Sub-sequence– 1 4 5 9 11 13
Length of Longest Increasing Sub-sequence(LIS) – 6

Naive Algorithm-

Check all the sub-sequences,but its time complexity will be approximately O(n^2) where n is the number of elements.

Efficient Algorithm-

x[] is the input sequence.Let it be 1 10 4 5 3 2 9 11 13.
The first element to be added in m[] is the first element of the input sequence.
Each element of the input sequence is taken one by one.
1. If it is greater than or equal to the last element of m[],insert the element in m[] at the end.
2. Else,replace the element in m[] which is just greater than element of the input sequence with the selected element of the input sequence.

Finally,the length of the array m[] is the length of the longest increasing sub-sequence.
Note-Elements of m[] are not elements of LIS.The actual values in the sub-sequence can be found by storing them in another array during the loop.

Illustration-

m=[]
m=[1]
m=[1 10]
m=[1 4] // 10 is replaced by 4 as number just greater than 4 is 10.
m=[1 4 5]
m=[1 3 5] //4 is replaced by 3 as number just greater than 3 is 4.
m=[1 2 5] //3 is replaced by 2 as number just greater than 2 is 3.
m=[1 2 5 9]
m=[1 2 5 9 11]
m=[1 2 5 9 11 13]

Thus,length of LIS is 6,that is size of m[].

Code-

[cpp]
m[1]=a[0];
p=2;
for(i=1;i<n;i++)
{
s=1;
//finding element just greater than x[i]
for(j=1;j<p;j++)
{
if(x[i]<m[j])
{
m[j]=x[i];s=0;break;
}
}
//value of s determines if element just greater than
// x[i] is found or not.
//If not found,then it is inserted at the end.
if(s==1){m[p]=x[i];p++;}
//p-1 is the size of the array and
// thus the length of LIS.
}
[/cpp]

N Queens Problem (Backtracking)

Given a chess board of size n*n,the task is to find all the ways to place n queens so that they don’t attack each other.
In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally.

Naive Algorithm-

[cpp]
while there are untried configurations
{
generate the next configuration
if queens don’t attack in this configuration then
{
print this configuration;
}
}
[/cpp]

Backtracking Algorithm-

If queens are at (i,j) and (k,l) coordinates,then they can attack each other if:
1. i=k (same row)
2. j=l (same column)
3. |i-k|=|j-l| (diagonally),| | denotes the absolute value

[cpp]
bool place(k,i)
{
//returns true if the queen can be placed at k-th row and i-th column
//x[] is a global array with first (k-1) values set already.
//x[p]=q means a queen is at location (p,q)

for(j=1 to k-1)
{
if(x[j]==i)||(ABS(x[j]-i)==ABS(j-k)) //checking if another queen in same column or diagonally
return false;
}
return true;
}
[/cpp]

To print all possible placements using backtracking:

[cpp]
void NQueens(k,n)
{

for(i=1 to n)
{
if(place(k,i)) //checking if queen can be placed at (k,i)
{
x[k]=i;
if(k==n) then write (x[1:n]);
else Nqueens(k+1,n);
}
}
}
[/cpp]

Android development primer: Creating Options Menu in Android – Part IV

This is the last post in the  Creating Options Menu in Android section. I told you in the first post of this section, that the Options Menu layout can also be created using  XML. In this post I am going to show you how.

I will be editing my codes from previous posts. You can create a new project and follow along. I would recommend creating a new project because we will not be changing the default code provided in the MainActivity.java much. Complete Source Code is at the bottom.

  • Navigate to <yourprojectname> -> res -> menu -> main.xml. Open the main.xml file.
  • You can already see one item in it. That is provided by default. You may or may not delete it.
  • Write the following code before the closing menu tag i.e. before </menu>.
    <item
            android:id="@+id/menuitem1"
            android:title="MenuItem1"
            android:icon="@drawable/menuitemicon1" />
    
    <item
            android:id="@+id/menuitem2"
            android:title="MenuItem2"
            android:icon="@drawable/menuitemicon2" />
  • Switch over to MainActivity.java and in the onCreateOptionsMenu() method, write the following
    [java]
    getMenuInflater().inflate(R.menu.main, menu);
    return true;
    [/java]
  • Save and execute the application on the emulator/device.
  • In order to use the onOptionsItemSelected() method, write the following code in the method
    [java]
    switch (item.getItemId()) {
    case R.id.menuitem1:
    Toast.makeText(getApplicationContext(), “MenuItem1 selected”, Toast.LENGTH_LONG).show();
    return true;
    case R.id.menuitem2:
    Toast.makeText(getApplicationContext(), “MenuItem2 selected”, Toast.LENGTH_LONG).show();
    return true;
    }
    return super.onContextItemSelected(item);
    [/java]
  • Remember that unlike the previous post, the cases here will not be 1,2.. but R.id.menuitem1, R.id.menuitem2
  • This is because when we were adding the menu items from java we were assigning it an ItemId. That allowed Android to identify the menu item uniquely. But here the id assigned is menuitem1, menuitem2 etc. Hence we reference them using R.id.menuitem1, R.id.menuitem2 etc.

img4

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.content.Intent;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
getMenuInflater().inflate(R.menu.main, menu);
return true;
}

public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case R.id.menuitem1:
Toast.makeText(getApplicationContext(), “MenuItem1 selected”, Toast.LENGTH_LONG).show();
return true;
case R.id.menuitem2:
Toast.makeText(getApplicationContext(), “MenuItem2 selected”, Toast.LENGTH_LONG).show();
return true;
}
return super.onContextItemSelected(item);
}

}

[/java]

main.xml(<yourprojectname> -> res -> menu -> main.xml)

<menu xmlns:android="http://schemas.android.com/apk/res/android" >

    <item
        android:id="@+id/menuitem1"
        android:title="MenuItem1"
        android:icon="@drawable/menuitemicon1" />

    <item
        android:id="@+id/menuitem2"
        android:title="MenuItem2"
        android:icon="@drawable/menuitemicon2" />

</menu>

Android development primer: Creating Options Menu in Android – Part III

Till now we have seen how to create and customize our Options Menu. In this post I will show you how to actually make use of the Options Menu to do something i.e. how to handle the clicks on Menu Items.

I will continue with the code from the previous post. Complete Source Code is at the bottom.

  • The function we will be overriding here is, onOptionsItemSelected() from android.app.activity class.
  • We will be using Toast so I would recommend you get a brief idea about what a Toast is and what it looks like from here. I will explain the different components of the Toast syntax in a while.
  • Write the following code below the onCreateOptionsMenu() method or onPrepareOptionsMenu() if you have one.[java]
    public boolean onOptionsItemSelected(MenuItem item) {
    switch (item.getItemId()) {
    case 1:
    Toast.makeText(getApplicationContext(), “MenuItem1 selected”, Toast.LENGTH_LONG).show();
    return true;
    case 2:
    Toast.makeText(getApplicationContext(), “MenuItem2 selected”, Toast.LENGTH_LONG).show();
    return true;
    }
    return super.onContextItemSelected(item);
    }
    [/java]
  • Save and execute the application in an emulator/device

part3-2   Part3-1

Here’s a little explanation for the Toast syntax.

  • getApplicationContext() : It returns the context for the whole application. It is used in order to get the context tied to the life cycle of the complete application and not some particular activity.
  • <char_sequence_of_your_choice> : This is the text to be displayed in the Toast.
  • Toast.LENGTH_LONG/Toast.LENGTH_SHORT : This defines the time for which the Toast should be visible.
  • show() : Everything to the left of show() is used to create the Toast. Once created it needs to be displayed. The show() method serves this purpose

Here I have shown you how to create a Toast on the click of a menu item. You can extend this to do practically anything you want like showing dialogs, creating notifications, retrieving data from databases etc.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.content.Intent;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.menuitemicon1);
menu.add(0, 2, 0, “MenuItem2”).setIcon(R.drawable.menuitemicon2);
return true;
}

public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case 1:
Toast.makeText(getApplicationContext(), “MenuItem1 selected”, Toast.LENGTH_LONG).show();
return true;
case 2:
Toast.makeText(getApplicationContext(), “MenuItem2 selected”, Toast.LENGTH_LONG).show();
return true;
}
return super.onContextItemSelected(item);
}

}

[/java]

Sieve of Eratosthenes

The task is to find all the primes between 1 to N.Numbers are called prime if they do not have any factors other than 1 and the number itself.

Brute Force-

Each number from 1 to N is checked if it is prime or not.
To check if a number is prime or not,check its divisibility by each number less than or equal to N.

[cpp]
int IsPrime(int N) {
int i;
for (i=2; i<N; i++)
{
if (N % i == 0)
return 0; //N is divisible by i.
}
return 1; //not divisible by any of the numbers (2,3….N-1) and thus prime.
}

for(i=1;i<=N;i++)
{
if(IsPrime(i))
printf(“%d\n”,i); // prints the number if it is a prime.
}
[/cpp]

Optimized Code-

To check if a number is prime or not,check its divisibility by
each number less than or equal to sqrt(N).

[cpp]
int IsPrime(int number) {
int i;
for (i=2; i*i<=number; i++) //less number of iterations compared to above code.
{
if (number % i == 0)
return 0;
}
return 1;
}

for(i=1;i<=N;i++)
{
if(IsPrime(i))
printf(“%d\n”,i); // prints the number if it is a prime.
}
[/cpp]
Sieve of Eratosthenes-

Above methods are inefficient for large values of N,since we would be repeating the same calculations.
In this situation it is best to use a method known as the Sieve of Eratosthenes.
The Sieve of Eratosthenes will generate all the primes from 2 to a given number n.It begins by assuming that all numbers are prime. It then takes the first prime number and removes all of its multiples. It then applies the same method to the next prime number.This process is continued till sqrt(n).

Illustration-

Initially,the list is
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 is the first prime and all its multiples are removed from the list.
So,the new list is
2 3 5 7 9 11 13 15 17 19

3 is the first prime and all its multiples are removed from the list.
So,the list is
2 3 5 7 11 13 17 19

Thus,we get all the primes between 1 to 20.

Code-

[cpp]
//prime[i]=1 if i is prime and
// prime[i]=0 if i is not prime.

prime[0]=0;
prime[1]=1;
m=sqrt(N);

for (int i=2; i<=m; i++)‏
{
if (prime[i])‏
{
for (int k=i*i; k<=N; k+=i)‏
{
prime[k]=false;
}
}
}
[/cpp]

Merge Sort

Merge Sort is an example of a divide and conquer algorithm.
A Divide and Conquer algorithm solves a problem using following three steps-

1. Divide: Break the given problem into sub-problems of same type.
2. Conquer: Recursively solve these sub-problems.
3. Combine: Appropriately combine the answers.

In merge sort,the input array is divided in two halves and the function is called again for the two halves.Then,merge() function is used for merging two halves and thus a sorted array is obtained.

Its time complexity is O(N*log(N)) for all cases(worst,best and average).

Algorithm-

Sorting-

1.The middle point of the array is found to divide the array into two halves.
2.MergeSort() is called for the first half.
3.MergeSort() is called for the second half.
4.The two halves sorted in step 2 and step 3 are merged.

Merging-

Let the two arrays to be merged be L[] & R[] and the output is arr[].
[cpp]
k=0;
while( i!=size of L[] && j!=size of R[] )
{
if(L[i]<=R[j]),then arr[k]=L[i] and i and k are incremented by 1.
if(L[i]>R[j]),then arr[k]=R[j] and j and k are incremented by 1.
}
[/cpp]
The remaining elements of L[] are copied, if there are any.
The remaining elements of R[] are copied, if there are any.

Code-

Let arr[] contain all the elements,l denote the starting position of the array,r denote the ending position of the array.m denotes the middle point of the array.

[cpp]
void MergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2; //middle point of the array is found
MergeSort(arr, l, m); //function called for left sub-array
MergeSort(arr, m+1, r); //function called for right sub-array
merge(arr, l, m, r); //merging of the two sub-arrays
}
}
[/cpp]

[cpp]
void merge(int arr[], int l, int m, int r)
{

int n1,n2,i,j,k;
n1 = m – l + 1; //size of left sub-array
n2 = r – m; //size of right sub-array
//copying contents of left sub-array into a temporary array L[]
for(i = 0; i < n1; i++)
L[i] = arr[l + i];
//copying contents of right sub-array into a temporary array R[]
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;

while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}

}
[/cpp]

Applications-

1.Useful for sorting linked lists.
2.Concept of merge sort can be used in Inversion Count Problem.

Android development primer: Creating Options Menu in Android – Part II

In the previous post, I showed you how to create a basic Options Menu in Android activity. Sometimes, a situation may arise that you need to change the menu item text or icon or anything else depending on a condition. In other words, in order to make the menu items dynamic, we cannot depend on the onCreateOptionsMenu() function.So how can we do it? We will use onPrepareOptionsMenu() method. The onPrepareOptionsMenu() method is always called from within onCreateOptionsMenu() in the actual definition of it in the android.app.activity class.

I’ll be using the source code from my previous post to show you how it’s done. Complete Source code is at the bottom.

  • Comment out everything in the onCreateOptionsMenu() method and write the following lines
    [java]
    super.onCreateOptionsMenu(menu);
    return true;
    [/java]

    We are calling the original onCreateOptionsMenu() from the Activity class because that automatically calls the onPrepareOptionsMenu() every time it is called.

  • After the onCreateOptionsMenu() write the below code[java]
    public boolean onPrepareOptionsMenu(Menu menu){
    menu.clear();
    int flag = 0;
    //int flag = 1;
    String temp;
    if(flag>0)temp = “MenuItem2on”;
    else temp = “MenuItem2off”;
    menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.menuitemicon1);
    menu.add(0, 2, 0, temp).setIcon(R.drawable.menuitemicon2);
    return true;
    }
    [/java]
  • Save and run it in the emulator/device.

Capture1     Capture2

  • You can change it according to your needs to have changing icons or texts. onPrepareOptionsMenu() is a very useful method in such cases.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.content.Intent;
import android.view.Menu;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;

public class Main extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
// Inflate the menu; this adds items to the action bar if it is present.
//getMenuInflater().inflate(R.menu.main, menu);
//menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.clock);
//menu.add(0, 2, 0, “MenuItem2”).setIcon(R.drawable.checkbox);
super.onCreateOptionsMenu(menu);
return true;
}

public boolean onPrepareOptionsMenu(Menu menu){
menu.clear();
int flag = 0;
//int flag = 1;
String temp;
if(flag>0)temp = “MenuItem2on”;
else temp = “MenuItem2off”;
menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.clock);
menu.add(0, 2, 0, temp).setIcon(R.drawable.checkbox);
return true;
}

}

[/java]

Floyd Warshall Algorithm

The problem is to find shortest distances between every pair of vertices in a given edge weighted directed graph.

The graph is represented in the form of an adjacency matrix where each cell A[i][j] represents the weight of the edge from vertex i to vertex j.
If i==j,then A[i][j]=0.
If there is no edge from vertex i to vertex j,then A[i][j]=INF.

Algorithm-

We update the matrix by considering all the vertices as intermediate vertex one by one.
If vertex number k is selected,for every pair(i,j),there are two possible cases.
1. k is not an intermediate vertex.Thus,dist[i][j] remains the same.
2. k is an intermediate vertex.Thus,dist[i][j]=dist[i][k]+dist[k][j].

[cpp]dist[i][j]= min (dist[i][j],dist[i][k]+dist[k][j]) for k=0,1…..N-1.[/cpp]

Its time complexity is O(N^3).

Code-

[cpp]
//N is the number of vertices.
//dist[][] denotes the adjacency matrix.
for(k=0;k<N;k++) //choosing an intermediate vertex
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
dist[i][j]=std::min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
//Updated dist[][] contains shortest distance
// between each pair of vertices.
[/cpp]

Note-

1. INF can be taken as INT_MAX from in C.
2. This algorithm can also be used to find the transitive closure which means the minimal pairs that convert a set S into a transitive set.A set S is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c.
Example of a transitive set- { (2,3),(3,4),(2,4) }

Android development primer: Creating Options Menu in Android – Part I

We can have Options Menu in Android activities. Options Menu is the one that appears when the Menu button on the device is pressed. Many applications do nothing on the press of the button. These applications do not have an Options Menu configured. In this post I’ll show you how to have an Options Menu and I’ll do this using Java. Remember that this can also be done using XML, but programming in Java is far more intuitive and also because well, I know very little xml 😛
The image below shows the Menu Button on an Eclair AVD.

Capture

You know the drill. Create a new project, switch over to MainActivity.java that inherits from android.app.activity, and start coding. Complete Source Code is at the bottom.

  • If you are using the newer versions of SDK, you can already see the function onCreateOptionsMenu(Menu menu)
  • We will be overriding the original function in the Activity class to customize our menu.
  • If you run the skeleton application on the emulator and click the Menu button, a menu will pop up with only one option Settings. Depending on the SDK you are using this may or may not appear.
  • The menu has been already customized. You can see the following line in the method onCreateOptionsMenu(Menu menu).[java]
    getMenuInflater().inflate(R.menu.main, menu);
    [/java]
  • You can look at the predefined layout by navigating to <yourprojectname> -> res -> menu -> main.xml in Eclipse. For the time being, we will not be editing this xml and concentrate on working with Java.
  • Comment out getMenuInflater().inflate(R.menu.main, menu); and insert the below code.[java]
    menu.add(0, 1, 0, “MenuItem1”);
    menu.add(0, 2, 0, “MenuItem2”);
    [/java]
  • MenuItem1 and MenuItem2 are placeholders. Change them as you like. The syntax of the menu.add() function used here is[java]
    public abstract MenuItem add(int groupId, int itemId, int order, CharSequence title).
    [/java]

    Remember that this is an overloaded function, but we will be using the one specified above for the time being.

  • Save it and execute it on the emulator/device.

img3

Want to make your menu fancier? Keep reading.

You can insert images/icons to you menu items. A point to note however, is that the resolution of the icon should be pretty small so that it can appear over the menu item text. I would suggest one about the dimensions of 48×48.

  • Edit the lines you have just added, to read the following:
    [java]
    menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.menuitemicon1);
    menu.add(0, 2, 0, “MenuItem2”).setIcon(R.drawable.menuitemicon2);
    [/java]
  • Obviously, your drawable folders must have images that have menuitemicon1.png and menuitemicon2.png for their names.

img4

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.content.Intent;
import android.view.Menu;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;

public class MainActivity extends Activity {

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
// Inflate the menu; this adds items to the action bar if it is present.
//getMenuInflater().inflate(R.menu.main, menu);
menu.add(0, 1, 0, “MenuItem1”).setIcon(R.drawable.menuitemicon1);
menu.add(0, 2, 0, “MenuItem2”).setIcon(R.drawable.menuitemicon2);
return true;
}
}
[/java]

Largest Sum Contiguous Subarray

We have a sequence of integers and we need the maximum sum from the continuous sub-sequences.

Example-

Let the sequence of integers be (3,-4,5,-7,8,-6,21,-14,-9,19).
Then,the sub-array or sub-sequence with maximum sum is (8,-6,21) and the maximum sum is 23.

Brute Force-

We can check sums of all sequences of different sizes from 1 to N.Its complexity will be O(N^2).

Code-
[cpp]
//arr[1…N] contains the given integers
for(i=1;i<N;i++)
{
s=0;
for(j=i;j<N;j++)
{
s=s+arr[j];
if(s>max) max=s;
}
}
[/cpp]
‘max’ gives the value of the maximum sum.

Efficient code-

Formulation of linear recurrence-

Let S[i] be the maximum sum of a sequence that starts with any index and ends at i.
Then,

S[i] = max (S[i-1]+arr[i],arr[i]);

Maximum of all the values of S[1…N] gives the value of the maximum sum from the continuous sub-sequences.

Example-

arr[]={2,3,-4,5}
S[1]=2;
S[2]=max(S[1]+arr[2],arr[2])=5
S[3]=max(S[2]+arr[3],arr[3])=1
S[4]=max(S[3]+arr[4],arr[4])=6

Thus,the result is max of (S[1],S[2],S[3],S[4]) which is 6.

Its time complexity is O(N).

Code-

[cpp]
S[1]=arr[1];
result=S[1];
for(i=2;i<=N;i++)
{
S[i]=std::max( S[i-1]+arr[i], arr[i] );
if(S[i]>result) result=S[i];
}
[/cpp]

NOTE– This algorithm is similar to Kadane’s algorithm.