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.

Subarray with given sum

Given a list of integers,our task is to find if a sub-sequence which adds to a given number exists or not.

Example-

The given list is (1,4,20,5,5) and the given number or sum is 29.
Then,the sub-sequence which adds to 29 is (4,20,5).

Brute Force-

All the sub-sequences are considered and its sum is compared with the given value.Its time complexity is O(N^2).

Code-

[cpp]

//arr[0…N-1] contains the given integers
// and the given number is X.
for(i=0;i<N;i++)
{
s=arr[i];
for(j=i+1;j<N;j++)
{
s=s+arr[j];
if(s==X) return 1; // sub array found
}
}
return 0; //sub-array not found
[/cpp]

Efficient Code-

Algorithm-

1. Initialize a variable curr_sum as first element.
2. Start from the second element and add all elements one by one to the curr_sum.
3. If curr_sum becomes equal to X, then a sub-sequence/sub-array is found.
4. If curr_sum exceeds X, then remove trailing elements one by one until curr_sum is less than X.

Its time complexity is O(N).

Code-

[cpp]
{
curr_sum=arr[0];
start=0;

for (i = 1; i <= n; i++)
{
// If curr_sum exceeds X, then
// remove the starting elements

while (curr_sum > X && start < i-1)
{
curr_sum = curr_sum – arr[start];
start++;
}

// If curr_sum becomes equal to X,
// then return true

if (curr_sum == X)
{
return 1; //sub-array found
}

// Add this element to curr_sum

if (i < n)
curr_sum = curr_sum + arr[i];
}
return 0; //sub-array not found
}

[/cpp]

Android development primer: Looking into Eclipse IDE

This post is aimed at giving you a little idea about what Eclipse IDE is and how you can use it’s features to the fullest for relatively faster coding. This is based strictly on it’s use in Android Development.

  • Eclipse is a multi-language Integrated Development Environment.
  • In it’s primitive form it is mostly used for writing Java programs.
  • It can be used, with the help of various plug-ins, to develop applications in an array of languages. Some of the most widely used ones are C, C++, PHP and Python.
  • If we are not speaking strictly, we can say it is similar to any WYSIWYG editor.

If we look into what and how it can help us in Android Programming, a couple of striking features are present. They are described in layman terms.

XML ASSISTANCE

  • It allows developers having little or no knowledge of XML to create layouts.
  • It allows Dragging and Dropping of elements from Palette to the Layout. It adds the required source code to XML automatically.
  • It allows for changing the attribute values of elements from the Properties tab. The source code is edited to reflect the changes made.
  • If the attributes of a particular element is changed, it allows for reflection of the changes in all codes in a project where this element might have been referred. It saves the programmer both time and effort.
  • The elements can be added in different configurations depending on the type of Layout selected. While dragging and dropping, Eclipse understands this layout and places the elements accordingly. For instance, in Relative Layout it allows for attributes like android:toLeftOf and android:toRightOf etc. In Linear Layouts it doesn’t allows such attributes.
  • It also understands the orientation of layouts.

CODE HINTING

  • Code Hinting refers to a feature where the IDE guesses the commands you want to enter as soon as you enter a few letters and it presents you with suggestions.
  • Ctrl+Space in Windows and Cmd+Space in Mac is the default key combination for Code Hinting.
  • While typing long statements, hit the Code Hinting key combination and choose the suitable statement from the list of statements presented.
  • Based on the SDK you are using for Android, Eclipse tells you whether some functions and features are out of date. They are deprecated by Eclipse.
  • It shows warnings and errors progressively as you type in statements so you know whether you have got the syntax and function arguments correct.

Although these may not seem very useful or time-saving in the initial stages of development, but they save a lot of effort when you are in the later stages and every single code in your project consists of more than a hundred lines.

Android development primer: Multiple Screen Support for Android, using Intents

We saw that on creating an Android Application Project, a skeleton “Hello World” application is created. The “Hello World” module is always the first step to learning anything. I’m sure you did a Hello World program when you were learning your first programming language. Quite boring isn’t it? Well, let’s get a bit creative.

We will add a few elements to our application and see how they work.

Create a new application project or edit the Hello World Application. Open up the MainActivity.java file and activity_main.xml and get ready for some coding.

If you have a problem while adding code snippets to you code, please have a look at the complete code at the bottom.

In the activity_main.xml follow the below steps:

  • Drag and drop an EditText from the Palette on the left.
  • Drag and drop a Button from the Palette on the left.
  • Click on the EditText and it’s properties should appear on the Properties tab to the right. If it doesn’t, Right Click->Show In->Properties.
  • Edit the Id attribute of the EditText to “@+id/et” and click Yes/OK on any dialog that appears. Remember the name.
  • Click on the Button and it’s properties should appear on the Properties tab to the right. If it doesn’t, Right Click->Show In->Properties.
  • Edit the Id attribute of the Button to “@+id/but” and click Yes/OK on any dialog that appears. Remember the name.
  • For now, leave the EditText and the Button in their respective places. We will concentrate on how to make them work and not how to place them in the layout.

Save the activity_main.xml.
Now follow the below steps carefully:

  • Navigate to <yourpackagename> -> src. Right Click on <com.yourname.yourappname> and select New -> Class.
  • You are creating a new Class. In the Name field enter Second.
  • In the Superclass browse and type Activity. Select the android.app.activity. This makes your class an Activity.
  • Hit Finish and you the class opens up.
  • Navigate to <yourpackagename> -> res -> layout. Right Click on <com.yourname.yourappname> and select New -> Android XML File.
  • Name it second and choose relative layout from the Root Element list.
  • Hit Finish and the XML file opens up.

In the Second.java file add the following code inside the class.

[java]
protected void onCreate(Bundle savedInstanceState)
{
super.onCreate(savedInstanceState);
setContentView(R.layout.second);
}
[/java]

If you have read my previous posts you will know exactly what we are doing here.

Now open second.xml and follow the below steps:

  • Drag and drop a TextView and change the Id attribute to “@+id/tv”.
  • Enter in the Text attribute – “This is the second Activity.”

Save second.xml. Switch over to MainActivity.java and add the following code in the onCreate() function.

[java]
Button but = (Button) findViewById(R.id.but);
EditText et = (EditText) findViewById(R.id.et);
but.setOnClickListener(new OnClickListener()
{
public void onClick(View v)
{
Intent intent = new Intent(MainActivity.this,Second.class);
startActivity(intent);
}
}
);
[/java]


As you type in the first statement, you’ll notice that Eclipse places a small cross so as to indicate there is an error in that line. What is the error? We have not imported the Android Button widget in our activity and so Eclipse doesn’t know what we mean when we type in “Button”. Hit Ctrl+1 on your keyboard. This is a shortcut to bring up suggested fixes to the errors. Select Import ‘Button’ (android.widget). You will now see that the statement just after the ‘=’ symbol is now erroneous. Hit Ctrl+1 again and select Add cast to ‘Button’. This way we have used type casting and import statements with which you must already be familiar from your Java knowledge. Do the same for the EditText statement.

  • OnClickListener() :  This adds a listener to the button that triggers when it is clicked
  • OnClick() : Holds the set of instructions that need to be executed when the button is clicked
  • Intent : This is a very important feature of Android. For the time being, it’ll be sufficient for you to know that an Intent is used to call other Activities. We can also pass data using this across activities. We’ll see this in a while. The syntax of the constructor is new Intent(<currentactivityobject>, <destinationactivityclass>). The object of current activity is MainActivity.this and the class of the destination activity is Second.class.
  • startActivity() : It is used to start off a new activity while pushing the current one to the Back Stack. It takes an intent as an argument.

What we’ve done is we’ve added a button and configured it to fire the Second Activity when clicked. Run this application using the emulator. When the MainActivity is up and you click the button to go to the second Activity, your application will crash unexpectedly. Why? Because we have not added the Second activity to the AndroidManifest.xml file.

How do you get to know what went wrong? Well, here’s how. On the top right you can see Java and DDMS. DDMS (Dalvik Debug Monitor Server) tells you exactly what went wrong. Click on it and scroll to the top of the group of lines in red. You will see ActivityNotFoundException. It also says – “Have you declared this activity in your AndroidManifest.xml?”. So that’s how we know that we haven’t declared the Second activity in the Android Manifest file.

The Android Manifest file needs to recognize each and every activity in your application.

  • Open up AndroidManifest.xml file from the project contents list and from the tabs at the bottom select AndroidManifest.xml
  • Just before </application> add this – <activity android:name=”.Second” />
  • Save.

Launch the application again and this time it should work just fine. 🙂

You must be wondering why we did not make use of the EditText that we added to the layout. I told you before that we can send data across activities using Intents. That is preciseld what this EditText is for. Here we go.

  • Add this line in the MainActivity.java before the startActivity() function :-
    [java]
    intent.putExtra(“data”, et.getText().toString());
    [/java]



  • Add the following lines in Second.java after the setContentView() function :
    [java]
    TextView tv = (TextView) findViewById(R.id.tv);
    tv.setText(getIntent().getStringExtra(“data”));
    [/java]

As you can see we can set the text to be displayed in the TextView from java too and this takes precedence over the xml.
What we have done here is that we will be displaying whatever text the user enters in the MainActivity in the Second Activity. Launch the application and see it work.

img1    img2

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.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);
Button but = (Button) findViewById(R.id.but);
final EditText et = (EditText) findViewById(R.id.et);
but.setOnClickListener(new OnClickListener() {

@Override
public void onClick(View v) {
Intent intent = new Intent(Main.this,Second.class);
intent.putExtra(“data”, et.getText().toString());
startActivity(intent);
}
});
}
@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);
return true;
}
}
[/java]

Second.java

[java]
package com.nero.myfirstapp;

import android.app.Activity;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class Second extends Activity {
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.second);
TextView tv = (TextView) findViewById(R.id.tv);
tv.setText(getIntent().getStringExtra(“data”));
}
}
[/java]

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" >

<EditText
 android:id="@+id/et"
 android:layout_width="wrap_content"
 android:layout_height="wrap_content"
 android:layout_alignParentLeft="true"
 android:layout_marginLeft="30dp"
 android:ems="10" >

<requestFocus />
 </EditText>

<Button
 android:id="@+id/but"
 android:layout_width="wrap_content"
 android:layout_height="wrap_content"
 android:layout_alignLeft="@+id/et"
 android:layout_below="@+id/et"
 android:layout_marginLeft="53dp"
 android:text="Button" />

</RelativeLayout>

second.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/tv"
 android:layout_width="wrap_content"
 android:layout_height="wrap_content"
 android:layout_alignParentLeft="true"
 android:layout_alignParentTop="true"
 android:text="This is the second Activity" />

</RelativeLayout>

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
package="com.nero.myfirstapp"
android:versionCode="1"
android:versionName="1.0" >

<uses-sdk
 android:minSdkVersion="7"
 android:targetSdkVersion="17" />

<application
 android:allowBackup="true"
 android:icon="@drawable/ic_launcher"
 android:label="@string/app_name"
 android:theme="@style/AppTheme" >
 <activity
 android:name="com.nero.myfirstapp.Main"
 android:label="@string/app_name" >
 <intent-filter>
 <action android:name="android.intent.action.MAIN" />

<category android:name="android.intent.category.LAUNCHER" />
 </intent-filter>
 </activity>
 <activity android:name=".Second" />
 </application>

</manifest>

Binary Search

This is a short note on using binary search, in continuance of my series on Algorithms.

Suppose we have to find whether a particular element exists in the sorted list of N numbers or not.
Let “arr” be the array which contains the N elements and the element to be searched is “key”.
Then, the time complexity using brute force will be O(N).

CODE-

[cpp]

for(i=0;i<N;i++)
{
if(arr[i]==key)
{
printf(“Element is found\n”);break;
}
}

[/cpp]

But,using binary search,the time complexity will be O(log(N)).A binary search halves the number of items to be checked each time and thus has logarithmic complexity.

ALGORITHM-

In this algorithm,the key is compared with the middle element of the array.
Cases:
1.If the middle element is equal to the key,then the search is completed.
2.If the key is less than the middle element,then the algorithm is repeated on the sub-array to the left of the middle element.
3.If the key is greater than the middle element,then the algorithm is repeated on the sub-array to the right of the middle element.
4.If the remaining array to be searched is empty,then the key cannot be found in the array and the search is completed.

CODE-

Recursive solution-

[cpp]
int binarysearch(int arr[],int key,int beg,int last)
{

// beg and last indicate the starting and ending indices of the subarray.
// Initially,beg has the value 0 and last has the value n-1.</em>

if(beg >last) return 0; // key not found</em>

else
{
int mid=(beg+last)/2; // finding the middle element</em>

if(key==arr[mid])return 1; // key found</em>

else if(key < arr[mid]) return binarysearch(arr,key,beg,mid-1);

else
return binarysearch(arr,key,mid+1,last);
}
}
[/cpp]

NOTE- Binary Search is used only when the given list is sorted.If the list is unordered,brute force is better as sorting will have a complexity of O(N*log(N)).