CodeMarvels – Page 16 – All's the Code !

Binomial Coefficient

Posted on July 16, 2013 by saurabh / 0 Comment

Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial expansion of (1+x)^n.It also represents an entry in Pascals Triangle.

Properties-

1. nCk=(n!)/[(k!)*(n-k)!]
2. nCn=1
3. nC0=1
4. nCk=(n-1)C(k)+(n-1)C(k-1)
5. nCk=(n)C(n-k)

The task is to find the value of nCk given the values of n and k.

Recursive solution-

[cpp]
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;

// Recurrence
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
[/cpp]

For large values of n,there will be many common subproblems.For example-
To calculate 5C2,function will be called for 4C2 and 4C1.
To calculate 4C1,function will be again called for 3C0 and 3C1.
To calculate 4C2,function will be called for 3C1 and 3C2.
So,3C1 is being calculated twice.
This problem has overlapping sub-problems property.Re-computation of same sub-problems can be avoided by constructing a temporary array C[][] and storing the results like we do in other dynamic programming problems.

DP based solution-

[cpp]
//C[][] is the temp array

for(i=0;i<=n;i++)
{

for(j=0;j<=i;j++)
{

//base condition
if((i==0)||(j==0)) C[i][j]=1;

else C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
//C[n][k] gives the result
[/cpp]

Time Complexity of this code is O(n*k).

Note-

n,k are non negative integers.
nCk is valid only for n>0 and 0<=k<=n.

Android Development/Technology

Android development primer: Know the AndroidManifest.xml

Posted on July 15, 2013 by nero / 0 Comment

Enough programming. Let’s take a break and look into one of the vital components of any Android application, the AndroidManifest.xml file. Every Android application must have an AndroidManifest.xml file with that exact name, in its root directory. It provides the Android system important information about the application you are about to run in the device.

Navigate to <yourprojectname> -> AndroidManifest.xml. I will give you a brief overview of what purpose do the various sections of the manifest serve. Some of these might not be present in your manifest file. That is because components are added in the manifest file according to the needs of the developer. Nonetheless it will do you good to know about them.

package : This names the package your Android Application is in. You can change this at any time you want, but it will require further changes in each java file in your application.
versionCode : This is the version code of your application. This is useful when you are modifying you application and want to have a clean copy of the application as another version.
versionName : You can also name the version of your application. Change this to your liking.
minSdkVersion : While creating the project you must have selected a minimum API level. Devices having android versions below this API will not be able to run your application.
targetSdkVersion : While creating the project you must have selected a target API level. Devices having android versions below this API (and above the minimum API level) will be able to run your application, but you have indicated that this API is the one you are particularly targeting.
icon : This is the icon that will appear once the application has installed in your device. You can have an image in the drawable folder and make that you application icon.
label : This is the name of your application. Your application will be installed in the device or uploaded to the Android market by this name. The default value is @string/app_name. I will talk about what that is and how to change it in a later post.
theme : This is the basic theme of your application. It is the one you selected while first creating a project.
activity -> name : This is the name of you activity. There will be as many activity tags in your manifest, as there are activities in your application. Each activity must be declared in the manifest, failing which your application will crash as soon as you try to navigate to an undeclared activity.
activity -> screenOrientation : This indicates the orientation of the screen that the developer wants his application to have. It can have two possible values – portrait and landscape. For simplicity, portrait is vertical and landscape is horizontal. These are used when you do not want to auto-rotate the screen when the device is rotated. If the screenOrientation attribute is not specified, it indicates auto-rotation of the device screen is allowed.
intent-filter : If you have read my previous posts, I told you that an intent is used to push the current activity into the back stack and call upon another activity. The intent filter here acts in the same way. This, by default is present in only one activity MainActivity. That is because it is the activity which is first displayed when the application is launched. Since we are not switching from one activity to another here thus the Android system’s intent is used to do this.
receiver : Just like there are activities in the application, it can also contain broadcast receivers. Each broadcast receiver must be declared in the manifest.
uses-permission : This is an interesting component. Your application might use some data or features from the user’s device that might/might not be acceptable to the user. In order to let the user know that some specific features and data are required in order for your application to work, uses-permission is used. This informs the user, at the time of installation of the application about these requirements. It is only after the user approves, that your application will be installed.
It also declares the permissions other applications need in order to communicate with your application.
The manifest also lists the library against which the application must be linked, if any.

So, you can see that the AndroidManifest.xml file serves the most important purpose of letting the Android system and the user know about what your application needs, what it does and other vital details.
Above are the most frequently seen/used components of the android manifest file. You might come across many more as you step into advanced Android Programming.

Algorithms

Longest Increasing Sub-sequence

Posted on July 14, 2013 by saurabh / 0 Comment

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]

Algorithms

N Queens Problem (Backtracking)

Posted on July 14, 2013 by saurabh / 0 Comment

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/Technology

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

Posted on July 13, 2013 by nero / 0 Comment

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.

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

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

Posted on July 11, 2013 by nero / 0 Comment

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

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;

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]

Algorithms

Sieve of Eratosthenes

Posted on July 10, 2013 by saurabh / 0 Comment

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]

Algorithms

Merge Sort

Posted on July 10, 2013 by saurabh / 0 Comment

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/Technology

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

Posted on July 9, 2013 by nero / 0 Comment

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.

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]

Algorithms

Floyd Warshall Algorithm

Posted on July 8, 2013 by saurabh / 0 Comment

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) }