Prims Algorithm

Let G=(V,E) be an undirected,connected and weighted graph.A sub-graph T=(V,E’) of G is a spanning tree of G if T is a
tree.There may be several spanning trees that may be extracted from it.A spanning tree has N vertices and N-1 edges.This is because of the property of trees.A minimum cost spanning tree is a spanning tree which has a minimum total cost.Prims algorithm can be used to obtain the minimum cost spanning tree.

Example-

cost[1:N][1:N] is the cost matrix of the graph.If there is no edge from i to j,then cost[i][j]=INT_MAX.If i equals j,then cost[i][j]=0.

Cost matrix for a graph is-

@ denotes INT_MAX

0 6 1 7 @ @
6 0 5 @ 3 @
1 5 0 5 6 4
7 @ 5 0 @ 2
@ 3 6 @ 0 6
@ @ 4 2 6 0

The minimum cost spanning tree consists of the edges-

(1,3) (3,6) (6,4) (3,2) (2,5)

This tree has a minimum cost of 1+4+2+5+3=15.

Algorithm-

Method 1-

V is the set of vertices.
Let R be the set of edges which are to be extracted to obtain the minimum cost spanning tree.
R=NULL ///Initialize R to null set
Select a minimum cost edge (u,v) from E.
S={u}; //include u in S.
while(S!=V)
{
Let (u,v) be the lowest cost edge such that u is in S and v in V-S;
Add edge (u,v) to set R.
Add v to set S.
}

Method 2-

1) Create a set S that keeps track of vertices already included in minimum spanning tree.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While S doesn’t include all vertices
{
a) Pick a vertex u which is not there in S and has minimum key value.
b) Include u to S.
c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v.
u-v edge is in the MST.
}

The time complexity of Prims algorithm is O(N^2).

Android Development Primer: Working with Videos in Android

In the last post, I showed you how to integrate audios to your Android Application. Just like audios, we can also have our applications play videos if we want to.

However, one thing worth remembering is that once we are done with the programming part, we are going to want to run the application on an actual device not an emulator because it usually does not run the video file properly. Obviously, the video we are going to play will be stored on the sd card of the device and not in the application.

  • Create an activity and set it’s content view. We will not be adding any buttons here. In here, I will show you how to run the video file just when the activity starts. You can, of course, trigger this on a button click.
  • In the layout of the activity add a VideoView from the palette on the left. By default it occupies the complete space of the activity. This is exactly what we want. Again, you can limit the height and width according to your requirements.
  • Switch over to the java file and write the following code just after the setContentView() method().
    [java]
    VideoView v = (VideoView)findViewbyId(R.id.videoView1);
    v.setVideoPath(“/sdcard/myvideo.mp4”);
    v.setMediaController(new MediaController(this));
    v.start();
    v.requestFocus();
    [/java]
  • Save your work and execute it on an Android Device.

Understanding the Code

  • VideoView is a default view to support videos.
  • setVideoPath() : This function defines the exact location of the video file you want the application to run. Make sure you get the location, name and the format of the video file correct, failing which the application will behave in an unwanted manner.
  • setMediaController() : This function displays the media controls like play/pause, fast forward, rewind. We may choose to have this or not. It is generally advisable to have one so that the user has some control over the playback.
  • start() : It triggers the video playback.
  • requestFocus() : It might so happen that there are other modules of our application being executed along with the video playback. This function causes the video playback to stay on top of all these modules.

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
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);
VideoView v = (VideoView)findViewbyId(R.id.videoView1);
v.setVideoPath(“/sdcard/myvideo.mp4”);
v.setMediaController(new MediaController(this));
v.start();
v.requestFocus();
}
}

[/java]

Minimum Cost Path (DP Example)

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems and optimal substructure.When applicable,the method takes far less time than naive methods that don’t take advantage of the sub-problem overlap.

A problem is said to have overlapping sub-problems if the problem can be broken down into sub-problems which are reused several times or a recursive algorithm for the problem solves the same sub-problem over and over rather than always generating new sub-problem.

A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its sub-problems.

Example of dynamic programming-

Given a cost matrix cost[][] having m rows and n columns,the task is to find the cost of minimum cost path to reach (m-1,n-1) from (0,0).Each cell of the matrix represents a cost to traverse through that cell. You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i,j), cells (i+1,j),(i,j+1) and (i+1, j+1) can be traversed.

Example-

Cost matrix-

1 2 3
4 8 2
1 5 3

The minimum cost path is (0,0)–>(0,1)–>(1,2)–>(2,2). The cost of the path is 8 (1 + 2 + 2 + 3).

Recursive Code-

[cpp]
//mcost(m-1,n-1) is called.
//cost[][] is the cost matrix
int mcost(int a,int b)
{
if (b < 0 || a < 0)
return INT_MAX;
//base condition
else if (a == 0 && b == 0)
return cost[a][b];
else
return cost[a][b] + min( mcost(a-1,b-1),mcost(a-1,b),mcost(a,b-1) );
}
[/cpp]

Efficient Code-

[cpp]
//mcost(m-1,n-1) is called.
//temp[][] is used for storing the results which need to be calculated again & again.
int mcost(int a,int b)
{
int i, j;

int temp[R][C];

temp[0][0] = cost[0][0];

//initializing first column
//a cell in first column can be traversed only from cell just above it.
for (i = 1; i <= a; i++)
temp[i][0] = temp[i-1][0] + cost[i][0];

//initializing first row
//a cell in first row can be traversed only from cell just left to it.
for (j = 1; j <= b; j++)
temp[0][j] = temp[0][j-1] + cost[0][j];

//constructing rest of the array
for (i = 1; i <= a; i++)
{
for (j = 1; j <= b; j++)
{
temp[i][j] = min(temp[i-1][j-1], temp[i-1][j], temp[i][j-1]) + cost[i][j];
}
}
return temp[a][b];
}
[/cpp]

Time Complexity of the DP implementation is O(mn) which is much better than Naive Recursive implementation.

Android development primer: Working with Audio in Android

We can have audios in our Android application. It can be used as and when required and is decided by the Application Developer.
Adding and configuring audios to our application is fairly simple.

In this post I am going to show you how to add audios to your Android Application and play the audio. Complete Source Code is at the bottom.

  • Navigate to <yourprojectname> -> res.
  • Now right click on the res folder and select New -> Folder.
  • Name this folder raw. All the audios that you have in your application, necessarily need to be in a folder names raw inside the res folder.
  • Now copy-paste an audio file inside the raw folder. You can do this by navigating to the Eclipse workspace on your system and then to your project’s res folder, or you can drag and drop it in Eclipse itself.
  • Once the audio file is in your raw folder, create an Activity and set the content view. Make sure you have a button in the activity, so that the audio can be played when the button is clicked.
  • Now in the onClick() method of the button write the following code.
    [java]
    MediaPlayer mp = MediaPlayer.create(Main.this, R.raw.beep);
    mp.start();
    [/java]
  • Worth noting here, is the MediaPlayer class and that we have not used a constructor but a static method to initialize it. MediaPlayer class is used for any media related operations that you might have to perform. The mp.start() method starts the MediaPlayer. 
  • Save your work and execute it on an emulator/device.
  • It might happen that the audio file does not play on the emulator. In such circumstances, you must install the application on a device and check whether it works

COMPLETE SOURCE CODE

[java]
package com.nero.myfirstapp;

import android.media.MediaPlayer;
import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
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);
Button but = (Button) findViewById(R.id.but);

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View arg0) {
MediaPlayer mp = MediaPlayer.create(MainActivity.this, R.raw.beep);
mp.start();
}

});

}
}

[/java]

Magic Square

A magic square is an arrangement of numbers in a square grid, where the numbers in each row, and in each column, and the numbers in the forward and backward main diagonals, all add up to the same number.A magic square of order N means it has N rows and N columns.It contains all integers from 1 to N^2.
The constant that is the sum of every row, column and diagonal is called the magic constant or magic sum.Let it be M.

M=[N*(N^2+1)]/2 where N is the order of magic square.

Example-

Magic square of order 3-

2 7 6
9 5 1
4 3 8

M(constant) = [3*(3^2+1)]/2 = 15.

Magic square of order 5-

9 3 22 16 15
2 21 20 14 8
25 19 13 7 1
18 12 6 5 24
11 10 4 23 17

The task is to generate the magic square given its order or number of rows/columns.

Algorithm-

There is a pattern in which the numbers are stored in a magic square.

In any magic square, the first number i.e. 1 is stored at position (N/2, N-1). Let this position be (i,j). The next number is stored at position (i-1, j+1) and the process continues.

Note-

1. If the calculated row position becomes -1, it will be N-1.Similarly,if the calculated column position becomes N, it will be equal to 0.
2. If the magic square already contains a number at the calculated position, calculated column position will be decremented by 2, and calculated row position will be incremented by 1.
3. If the calculated row position is -1 & calculated column position is N, the new position would be: (0, N-2).

Code-

[cpp]

int magicSquare[100][100];

// Initialize position for 1

int i = N/2;
int j = N-1;

// Putting values in magic square

for (int num=1; num <= N*N; )
{
//3rd condition
if (i==-1 && j==N)
{
j = N-2;
i = 0;
}
//1st condition
else
{
if (j == N)
j = 0;

if (i < 0)
i=N-1;
}
//2nd condition
if (magicSquare[i][j])
{
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++; //set number

j++; i–; //normal condition
}

[/cpp]

Note-

This approach works only for odd values of N.

Android development primer: Progress Dialog in Android – Horizontal Style

In the last post, we saw how to make a Progress Dialog with Spinner style progress bar. Here, we will see how to make a Horizontal Style bar.

  • Set the content view of the activity. Make sure the layout of the activity contains a button so that the Progress Dialog can be triggered on the click of the button.
  • After setting the content view, declare and define the button in the java file.
  • Add the Progress Dialog hereafter, using the following code.
    [java]
    final ProgressDialog pd = new ProgressDialog(this);
    pd.setProgressStyle(ProgressDialog.STYLE_HORIZONTAL);
    pd.setMessage(“Working…”);
    pd.setIndeterminate(false);
    pd.setCancelable(true);
    [/java]

    We will not be defining the Progress Dialog inside the onClick() method of the button so that we can use this dialog in other places, if need be.

  • Set up the onClickListener() and within it the onClick() methods. Inside the onClick() method, write the following code.
    [java]
    pd.show();
    pd.setProgress(30);
    [/java]

    In addition to showing the Progress Dialog we also need to set the progress of the bar.

  • Save your work and execute on an emulator/device.

Progress2

Points to Note :-

  • On examining the code carefully, you will find that in addition to change in the setProgressStyle(), the setIndeterminate() method now has a value of false.
  • This is because we will be showing the progress of the work in percentage now. So the dialog needs not be indeterminately displaying till the work ends.
  • We have set the initial percentage progress only for demonstration purposes. When you will be incorporating this in your application, you will be performing some tasks and updating the progress of the dialog accordingly.

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
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);
Button but = (Button) findViewById(R.id.but);
final ProgressDialog pd = new ProgressDialog(Main.this);
pd.setProgressStyle(ProgressDialog.STYLE_HORIZONTAL);
pd.setMessage(“Working…”);
pd.setIndeterminate(false);
pd.setCancelable(true);

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View arg0) {
pd.show();
pd.setProgress(30);
//Do some more tasks
//update the progress of the dialog
//Do some more tasks
//update the progress of the dialog
}

});

}
}

[/java]

Largest multiple of 3

Given an array of digits,the task is to find the largest multiple of 3 that can be formed from array elements.

Example-

Input array is {4,8,0}.Then,the largest number formed using these digits and divisible by 3 is 840.

Properties of multiples of 3-

1.Sum of the digits of the multiple is divisible by 3.

Example-

840 is divisible by 3 and (8+4+0=12) is also divisible by 3.

2.We get the same remainder when we divide the number and sum of digits of the number by 3.

Example-

841 when divided by 3 gives remainder 1.
(8+4+1=13) when divided by 3 also gives remainder 1.

Naive Algorithm-

Generate all the combinations of the given digits and maximum of the numbers which is divisible by 3 is the result.
But,it will have a time complexity of O(2^n).

Efficient Algorithm-

1.Sort the array in increasing order.
2.Queue q0 stores the elements which on dividing by 3 gives remainder 0.
3.Queue q1 stores the elements which on dividing by 3 gives remainder 1.
4.Queue q2 stores the elements which on dividing by 3 gives remainder 2.
5.Find the sum of all the given digits.Let it be ‘s’.
6.If s is divisible by 3,goto step 9.
7.If s when divided by 3 gives remainder 1:
Remove one item from q1.
If q1 is empty,remove two items from q2.
If q2 contains less than two elements,number is not possible.
8.If s when divided by 3 gives remainder 2:
Remove one item from q2.
If q2 is empty,remove two items from q1.
If q1 contains less than two elements,number is not possible.
9.Empty all queues into an temporary array and sort it in decreasing order.

Code-

[cpp]
//a[] is the input array
//s is the sum of the digits
//n is the number of digits in the given array

#include<stdio.h>
#include<algorithm>
#include<queue>
int main()
{
using namespace std;
int i,n,s,a[1000],p[1000],w,z;
queue<int> q0;
queue<int> q1;
queue<int> q2;

scanf(“%d”,&n);s=0;
//taking the input
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
s=s+a[i];
}
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]%3==0) q0.push(a[i]);
else if(a[i]%3==1) q1.push(a[i]);
else q2.push(a[i]);
}
if(s%3==1)
{
// either remove one item from queue1
if ( !q1.empty() )
q1.pop();

// or remove two items from queue2
else
{
if ( !q2.empty() )
q2.pop();
else printf(“No number can be formed\n”);
if ( !q2.empty() )
q2.pop();
else printf(“No number can be formed\n”);
}
}
else if ((s% 3) == 2)
{
// either remove one item from queue2
if ( !q2.empty() )
q2.pop();

// or remove two items from queue1
else
{
if ( !q1.empty() )
q1.pop();
else
printf(“No number can be formed\n”);

if ( !q1.empty() )
q1.pop();
else
printf(“No number can be formed\n”);
}
}
//emptying all the queues
w=0;
while(!q0.empty())
{
z=q0.front();
p[w++]=z;
q0.pop();
}
while(!q1.empty())
{
z=q1.front();
p[w++]=z;
q1.pop();
}
while(!q2.empty())
{
z=q2.front();
p[w++]=z;
q2.pop();
}
sort(p,p+w);
//printing in descending order
for(i=w-1;i>=0;i–)
printf(“%d”,p[i]);
return 0;
}

[/cpp]

Android development primer: Progress Dialog in Android – Spinner Style

I have already posted about the Alert Dialog and the Custom Dialog in Android. However, in this post, I will show you how to make your application fancier by adding Progress Dialog in it. What is a Progress Dialog? It is a dialog that shows the user how much of the current work, if any being performed, is complete. Below is an image that shows exactly what one looks like in an Eclair emulator.

Progress1

Want to have one of these in your application? Open up an activity and start programming. Complete Source Code is at the bottom.

  • Set the content view of the activity. Make sure the layout of the activity contains a button so that the Progress Dialog can be triggered on the click of the button.
  • After setting the content view, declare and define the button in the java file.
  • Add the Progress Dialog hereafter, using the following code.
    [java]
    final ProgressDialog pd = new ProgressDialog(this);
    pd.setProgressStyle(ProgressDialog.STYLE_SPINNER);
    pd.setMessage(“Working…”);
    pd.setIndeterminate(true);
    pd.setCancelable(true);
    [/java]

    We will not be defining the Progress Dialog inside the onClick() method of the button so that we can use this dialog in other places, if need be.

  • Set up the onClickListener() and within it the onClick() methods. Inside the onClick() method, write the following code.
    [java]
    pd.show();
    [/java]

    All we need to do is to show the dialog.

  • Save your work and execute on an emulator/device.

Understanding the Code

Here I provide a little explanation as to what some of the functions in the declaration of the Progress Dialog are doing.

  • setProgressStyle() : This defines the style in which the progress will be shown. This can take one of two values – Spinner or Horizontal. Both have their own set of values in the methods described below. I will discuss the Horizontal style in the next post.
  • setMessage() : Quite obviously, it defines the message shown to the user while the Progress Dialog is displayed.
  • setIndeterminate() : This defines whether the Progress Dialog is an ongoing percentage thing. It takes a boolean value as an argument. A value of true means that it will end once the work being done ends. At this time the dialog disappears. A value of false means we will be displaying details about the progress in percentage.
  • setCancelable() : It tells the application whether the user can cancel the progress by pressing the back button. It again takes a boolean value as an argument.

COMPLETE SOURCE CODE

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.app.ProgressDialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
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);
Button but = (Button) findViewById(R.id.but);
final ProgressDialog pd = new ProgressDialog(Main.this);
pd.setProgressStyle(ProgressDialog.STYLE_SPINNER);
pd.setMessage(“Working…”);
pd.setIndeterminate(true);
pd.setCancelable(true);

but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View arg0) {
// TODO Auto-generated method stub
pd.show();
}

});

}
}

[/java]

Remember that the spinner in this dialog will keep spinning as we have not defined any action that needs to be completed. Hence you must hit the back button to end it.

Android development primer: Creating Dialogs in Android

We have seen how to create and use Alert Dialog. Now we will see how to create and use a general dialog. In most places you find Alert Dialog explained on after they have given you a basic tutorial about Dialogs, their creation and use. However since Alert Dialog is a complete predefined element of Android, I chose to give you the tutorial earlier so that the learning curve for you remains smooth.

Here we will create a dialog, a layout for it and display it in an activity. Complete Source Code is at the bottom.

  • Navigate to <yourpackagename> -> res -> layout.
  • Create an XML, pick up a layout for it and name it according to your choice. We will use this layout for the dialog.
  • I will just have a button and a text view in the dialog. You can follow along or you can become creative and add more elements. Write the following code in the dialog
    <?xml version="1.0" encoding="utf-8"?>
    <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
        android:layout_width="match_parent"
        android:layout_height="match_parent" >
    
        <TextView
            android:id="@+id/textView1"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_alignParentTop="true"
            android:layout_centerHorizontal="true"
            android:text="This is a test dialog"
            android:textAppearance="?android:attr/textAppearanceMedium" 
            android:paddingBottom="10sp"/>
    
        <Button
            android:id="@+id/button1"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:layout_below="@+id/textView1"
            android:layout_centerHorizontal="true"
            android:text="Button" />
    
    </RelativeLayout>
  • Now in the activity I have a button that triggers the dialog on the click. Add the following code to the onClick() method of the onClickListener() constructor.
    [java]
    final Dialog d = new Dialog(Main.this);
    d.setContentView(R.layout.dialog);
    Button tempbut = (Button) d.findViewById(R.id.button1);
    tempbut.setOnClickListener(new OnClickListener() {

    @Override
    public void onClick(View v) {
    // TODO Auto-generated method stub
    d.dismiss();
    }
    });
    d.setTitle(“Test Dialog”);
    d.show();
    [/java]

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

dialog

This is how it looks on my Eclair emulator. Clicking the button will dismiss the dialog. This has been defined in the dialog code. Take some time to go through the code you have just added. It is very simple but nonetheless important.

COMPLETE SOURCE CODE

dialog.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent" >

    <TextView
        android:id="@+id/textView1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true"
        android:text="This is a test dialog"
        android:textAppearance="?android:attr/textAppearanceMedium" 
        android:paddingBottom="10sp"/>

    <Button
        android:id="@+id/button1"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_below="@+id/textView1"
        android:layout_centerHorizontal="true"
        android:text="Button" />

</RelativeLayout>

activity_main.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context=".Main" >

    <Button
        android:id="@+id/but"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_alignParentLeft="true"
        android:text="Button" />

</RelativeLayout>

MainActivity.java

[java]
package com.nero.myfirstapp;

import android.os.Bundle;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.Dialog;
import android.content.DialogInterface;
import android.content.Intent;
import android.view.LayoutInflater;
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);
Button but = (Button) findViewById(R.id.but);
but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
final Dialog d = new Dialog(MainActivity.this);
d.setContentView(R.layout.dialog);
Button tempbut = (Button) d.findViewById(R.id.button1);
tempbut.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
// TODO Auto-generated method stub
d.dismiss();
}
});
d.setTitle(“Test Dialog”);
d.show();
}
});

}
}

[/java]

Fibonacci Numbers

Fibonacci is the most famous sequence in the programming world.
It is defined by the following recursive formulation:
f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1.
The first few numbers of the sequence are:
0,1,1,2,3,5,8,13,21,34,55……
Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an optimized algorithm.

Using Recursion-

[cpp]
fib(n)
{
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1)+fib(n-2);
}
[/cpp]

This has an exponential time complexity.

Using Iteration-

[cpp]
fib(n)
{
if(n==0) return 0;
if(n==1) return 1;
a=0;
b=1;
for(i=2;i<=n;i++)
{
c=a+b;
a=b;
b=c;
}
return b;
}
[/cpp]

This code has a time complexity of O(N).

Using power of the matrix{(0,0),(1,1)}-

If we n times multiply the matrix M = {{1,1},{1,0}} to itself,then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

|1 1|^n = | F(n+1) F(n) |
|0 1|        | F(n)   F(n-1)|

Result of exponentiation can be calculated using this method in O(logn).

[cpp]
/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}

/* Optimized version of calculating power*/
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if( n%2 != 0 )
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
[/cpp]

This code has a time complexity of O(logN).