mutex Vs read-write lock

what is the diff between mutex and readwrite lock?

Mutex:

A Mutex is an OS object which supports a state of ‘locked’ or ‘available’. What it means is that if multiple threads attempt to lock the Mutex, only one will ‘own’ that lock while others will be waiting in the queue behind each other.

The waiting threads will block the function call from where they are initiated until Mutext is unlocked ‘available’ and a thread gets chance to claim it.

There are two types of Mutex, ‘named’ and ‘unnamed’. A named Mutext can be accessed from different processes running on the system whereas unnamed Mutex can only be used from inside a single process. On Windows OS, the Mutex is replaced with Critical Section which is faster, unnamed and can be used from a single process only.

Read-Write Lock:

It is a file system construct that works over peer-to-peer file sharing or any other file sharing schemes.
They are similar to Mutex with the difference that once the file is locked, other threads are denied the lock request and are not being put in the waiting queue.

File locking supports ‘shared-read’ request. What it means is threads requesting for reading the file, get the lock and can read the file however there can be only one file write access.

Little note on Algorithms and Data Structures - Part 1

Is O(2^n) equal to O(3^n)? Why?

No. O(f(n)) = O(g(n)) if and only if f(n)/g(n) is bounded between two positive real numbers for all sufficiently large values of n; but as n increases, the ratio 2^n / 3^n tends to zero.

 

What is the expected run-time of quicksort? What is the worst-case run-time?

The expected run-time of quicksort (for random inputs) is O(n log n). The worst-case run-time of quicksort is O(n^2).

What is the difference between a binary tree (that should be binary search tree) and a B-tree? When and why does this difference matter?

Internal nodes in a binary tree have at most two children, while internal nodes in a B-tree can have many children (depending on the block size). This is useful when the tree data is stored in a manner which exhibits large read latencies (e.g., on disk) since the higher fan-out means that the height of a B-tree is less than the height of a corresponding binary tree.

 

Name the heap operations used by heapsort and the asymptotic running time of each.

There are two operations: Heapify, which takes n elements and builds a heap out of them in O(n) time; and pop-max, which deletes the largest element from the heap and returns it in O(log n) time.

 

Describe an algorithm that determines if a graph is bipartite.

Attempt to 2-colour the graph as follows:

1. Pick an uncoloured vertex; if there are none remaining, return success.
2. Colour that vertex red.
3. Perform a graph traversal (depth-first search and breadth-first search both work) starting from the vertex we picked. Every time we reach a vertex, colour it green if all its coloured neighbours are red, or red if all of its coloured neighbours are green; if it has both red and green neighbours, return failure.
4. Go to step 1.

The graph is bipartite if and only if the 2-colouring algorithm did not fail.

Publishing Android applications - Part 4

In our previous tutorials, we have walked through on how to setup the android environment and also trying out a sample application.

Here is the detailed documentation on how to publish already developed application:
http://developer.android.com/guide/publishing/publishing.html

Before we move on for publishing the application, there are few things we need to do:
 testing. testing:
Make sure you test your application on emulator thoroughly and then on the real device.
this article lists out some keyboard shortcuts to change the orientation of the device. This will help
test your application in different orientation. Creating virtual devices of different sizes and testing the application
on them will help find any presentation issues with your application.

Performance and SDK compatibility: make sure your application performs as expected and
there are no bottleneck in the speed. Apart from this, try to develop the application for older SDK versions
so that it can run on most of the Android devices. e.g. SDK 2.1 is currently installed on almost 50% of Android devices.
If you develop on later versions then your application will not be compatible and hence will not be installed on these many devices.

 

Getting ready for the publishing...

1. give required permissions to your application

<uses-permission android:name="android.permission.INTERNET"/>

2. choose right icon and name of the application

<application android:label="@string/my_app_name" android:icon="@drawable/my_icon">

3. increment version number in manifest file
...package="com.example" android:versionCode="1"
android:versionName="1.0"...

note that on every update, you need to increment the value of versionCode where as
versionName is your choosen name  of the version.

4. SDK compatibility

make sure you set right values for android:minSdkVersion, android:targetSdkVersion and android:maxSdkVersion attributes.

5. export and sign your application and generate .apk file

go to File > Export

click on "Export Android Application"

now fill in all the options and generate the .apk file. make sure you store the .key file for later application update.

now navigate to http://market.android.com/publish and upload the application.

 

Login to your Google Account on Without Typing Anything

Logging in to your accounts using public computers may be at risk due to virus, key loggers or any other programs which may collect your account credentials and later compromise your account.

Today Google came up with the novel idea “allowing users to login using their trusted phones”.

Here is the solution:

Step 1: open https://accounts.google.com/sesame on the computer which you feel might be at risk.

         opening the above link will show a QR code.

Step 2: make sure you have smart phone with QR code reader application (e.g. Google Goggle, Bakodo, Red Laser etc). Scan the bar code shown on your computer screen (from Step 1).

Step 3: you will be shown a URL to open and sign in with your google account (Gmail or iGoogle).

Step 4: within a few moments, Google will sign-in the page and your page on screen will redirected to either Gmail or iGoogle as per your selection in Step 3.

Step 5: now continue using your google account on the computer.

Step 6: After you are done your work on the computer, don’t forget to sign off manually.

 

All is fine so far and loved the creative way to reduce the risk of account take over. This is fantastic and a great way to avoid risk.

However I did not like “Step 6”, why? its because sign-up and sign-in are done differently and from different devices. Since Google has knowledge about both of these devices, so why can’t allow sign off using my device? what if I forgot to sign-off from computer, any way to do the same from my phone device which was used to sign-in? how about when user marks in his device for sign-off and the next action on google account (related to the session with the same QR code) on the computer logs off automatically?

This may be another checkpoint where there needs some improvements.

Google has solved its problem here however the same problem exists for other websites and for whole internet space. The internet needs it badly, to make surfing a better experience.

Hope Google still working on this to make it a general solution which whole industry could benefit.

 

Well done and Good Luck Google!!!

 

-a programmer’s opinion.

Android: Creating Multi-Column Layout with ArrayAdapter

Android provides ListView for creating list with single column where as there is GridView which is used to create the grid view. However there cases when you would want to create tabular format data view e.g. list view with multiple columns. In order to display a list of data in a multi-column layout spreadsheet style, you could follow some examples on stackoverflow.com. I have gone through most of them and used the simple and easy to use format for my app and thought to share for my viewers.

here are the steps:

Step 1. insert a simple list view which you would turn it to multi column.

file: main.xml

[xml]
<ListView android:id="@+id/mylist" android:layout_width="wrap_content" android:layout_height="wrap_content">
</ListView>
[/xml]

Step 2. create a row format which will be shown for each row in the list. (multi column view).

file: mylistrow.xml

[xml]
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout
xmlns:android="http://schemas.android.com/apk/res/android"
android:paddingTop="4dip"
android:paddingBottom="6dip"
android:layout_width="fill_parent"
android:layout_height="wrap_content"
android:orientation="horizontal">
<TextView android:id="@+id/column1"
android:gravity=”left”
android:layout_width="50dip"
android:layout_height="wrap_content"/>
<TextView android:id="@+id/column2"
android:gravity=”center”
android:layout_width="70dip"
android:layout_height="wrap_content"
android:layout_weight="1"/>
<TextView android:id="@+id/column3"
android:gravity=”right”
android:layout_width="60dip"
android:layout_height="wrap_content"
android:layout_weight="1"/>
</LinearLayout>
[/xml]

notice the gravity field, which means how you would like to change the orientation of the text. The last two columns have layout weight 1 which means the extra space in the row will be evenly distributed to these columns in order to fill the space. you can read more about weight here.

Step 3. using SimpleAdapter to configure the data binding to these columns

[java]
ListView list = (ListView) findViewById(R.id.mylist);
ArrayList<HashMap<String, String>> mylistData =
new ArrayList<HashMap<String, String>>();

String[] columnTags = new String[] {"col1", "col2", "col3"};

int[] columnIds = new int[] {R.id.column1, R.id.column2, R.id.column3};
for(int i=0; i<3; i++)
{
HashMap<String,String> map = new HashMap<String, String>();
//initialize row data
for(int j=0; j<3; j++)
{
map.put(columnTags[j], "row”+i+”col"+j);
}
mylistData.add(map);
}
SimpleAdapter arrayAdapter =
new SimpleAdapter(this, mylistData, R.layout.mylistrow,
columnTags , columnIds);
list.setAdapter(arrayAdapter);
[/java]

Here is how the list will look like:

row0col0	row0col1	row0col2
row1col0	row1col1	row1col2
row2col0	row2col1	row2col2

for more details on how to use advanced features of the listview, refer here.

Wordpress: how to generate DocBook style posts

I'm regular follower of http://www.vogella.de site. What I liked most about the site is its presentation and a way to show users how up to date the articles are. Users like to know how fresh the content is and how frequently they are updated. I would also don't like to read the technical articles which are pretty old and may not be up to how technology is changing.

The site uses "DocBook XSL Stylesheets" tool to generate the contents and manage the revisions. As we all know that most of the blogging sites are based on WordPress. I have done my homework on how easy it is to convert the wordpress posts into revision based article.

sample screenshot:



Here is the code base which you can try out.


Note that all these code changes have to happen in your theme code.

1. functions.php

add below function to functions.php file.

[php]

<?php

function get_post_revision_info($postId) {
global $wpdb;

$sql = "("
. " SELECT ID, post_author, post_name, post_modified, post_parent, post_type"
. " FROM wp_posts"
. " WHERE post_parent =".$postId.""
. " AND post_type = \"revision\""
. " )"
. " UNION"
. " ("
. " SELECT ID, post_author, post_name, post_modified, post_parent, post_type"
. " FROM wp_posts"
. " WHERE id =".$postId.""
. " AND post_type = \"post\""
. " ) ORDER BY `ID` ASC";

$posts=$wpdb->get_results($sql);
$header="";
$lastrevision = "1";
$output="";
$postYear = date('Y'); ;

if ($posts)
{
$cnt = 1;

$output .= "<h3>Revision History</h3>";
$output .="<table>";

foreach ($posts as $post)
{
$lastrevision = $cnt;

$author = get_the_author_meta( 'display_name', $post->post_author);
$datetime = strtotime($post->post_modified);
$modified = date( 'm.d.Y', $datetime);

$rev = "Revision ".$cnt.".0";
$updated = "updated";
if($post->post_type == "post")
{
$updated = "created";
$postYear = date( 'Y', $post->post_modified ); //post created date
}

$output .="<tr>";
$output .="<td>".$rev."<td>"."<td>&nbsp;</td>";
$output .="<td>".$updated."<td>"."<td>&nbsp;</td>";
$output .="<td>".$modified."<td>"."<td>&nbsp;</td>";
$output .="<td>".$author."<td>"."<td>&nbsp;</td>";
$output .="</tr>";

$cnt++;
}
$output .="</table>";
}
else
{
$output .= "no revision history found.<br />";
$output = $sql;
}

$curYear = date('Y'); ;
$copyright = "Copyright &copy; ".$postYear . (($postYear != $curYear) ? '-' . $curYear : ''). " ".get_the_author();

$header .= "Author ".get_the_author()."<br>";
$header .= "Current Version ".$lastrevision.".0"."<br>"; //1.0, 2.0...
$header .= $copyright."<br>";
$header .= date("m.d.Y")."<br>";

$footer = "<h3>Excerpts:</h3>";
$footer .= "<i>".get_the_excerpt()."</i><br/><br/>";
$footer .= "<h2>Article Details</h2>";

return "<h2>".$header."</h2><br/>".$output."<br/><br/>".$footer."<br/>";
}

[/php]

2. single.php

add below code (a call to post_revision_info) in single.php

[php]

<div class="entry-content">
<?php print get_post_revision_info(get_the_ID()); ?>

[/php]

This is my first version of the code. it may not generate the well-formed HTML code or may not suit to your theme.
so please change the code according to your need.

your comments will encourage me to come up with more articles on the related topic.

Bonus on How To: Building Android Application - Part 3

After going through the Part 1 and Part 2 of “How To: Building Android Application”, we will go explore more on the android sample and some tips to improve the performance of the emulator.

Playing with Android Sample Application

In this tutorial, we will setup the Android sample application which will help you play with most of the android components.

Step1: click on File->New->Other and then select Android->Android Sample Project

click Next and Finish.

in case you see “ This target has no samples. Please select another target.” message, you should click Windows->Android SDK Manager and select the sample and other versions (if needed) and Install the packages. This step will take a while. After that is done, retry Step 1.

useful emulator Shortcuts:

Alt+Enter maximizes the emulator. Nice for demos.

Ctrl+F11 changes the orientation of the emulator.

F8 turns network on / off.

F6 to turn on / off the trackball

Performance Considerations

Try to use a smaller resolution for your emulator as for example HVGA. The emulator gets slower the more pixels its needs to render as it is using software rendering.
While creating device (e.g. myDevice), set the flag "Enabled" for Snapshots. This will save the state of the emulator and let it start much faster.