Errors running builder Android Resource Manager error when creating a new Android project in Eclipse

Recently, I had updated my Android SDK Manager but had not updated my Eclipse Android plugins.  This lead to a strange error when I tried to create a new Android project.

Errors occurred during the build.Errors running builder 'Android Resource Manager' on project *.java.lang.NullPointerException

There were many solutions in stackoverflow.
http://stackoverflow.com/questions/20043521/errors-running-builder-android-resource-manager-on-adt
http://stackoverflow.com/questions/18096315/mac-error-create-android-project-errors-running-builder-android-resource-man

But none of these worked for me.

To solve this, I tried updating my Eclipse Android plugins. And immediately, the error was gone and I could create a new project without any errors.

1. In Eclipse, Help menu -> Check for Updates
2. Select all Android related plugins (most probably will have the word Android in its name)
3. Click Next, Accept the agreement page then proceed to install the plugin.

Great offer from Microsoft for Xbox

I got this offer from Microsoft as a part of Google Adsense when I was browsing through one of the websites.

Someone in Microsoft would have thought.. "An offer for 3 cents.. Who could resist that?"

Create a Google App Engine project that uses Spring + using Maven to create + Eclipse as IDE

I did not find any tutorial to create a maven project that uses Google App Engine and Spring and use Eclipse IDE.  So, I thought I would document what I had done recently to create a Spring MVC project using Maven and deploys to Google App Engine; using Eclipse as IDE.

I am assuming you have Eclipse plugin for Maven (m2e) installed to Eclipse.

Creation of project:
We need to use maven plugin to create a new Google App Engine project.  I used instructions to create using command line from here.  I am sure we can use Eclipse maven project creation wizard as well.

Adding Spring dependencies:
To add Spring dependencies, add dependencies.

  <!-- Spring Dependencies -->  
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-core</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-context</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-beans</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <!-- Spring MVC framework -->   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-webmvc</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-web</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   

Tips:

• Till Spring 2.5.6, the framework used to provide a single all-encompassing dependency.  From Spring 3.0.x on wards, that is not the case.  So, we will have to include every dependency in pom.xml file.
• It is important to have same version for all Spring dependencies.  If Spring dependencies don't have the same version, it gives out an error:

 [INFO] java.lang.NoSuchFieldError: APPLICATION_CONTEXT_ID_PREFIX  
 [INFO] at org.springframework.web.servlet.FrameworkServlet.createWebApplicationContext(FrameworkServlet.java:430)  
 [INFO] at org.springframework.web.servlet.FrameworkServlet.createWebApplicationContext(FrameworkServlet.java:458)  
 [INFO] at org.springframework.web.servlet.FrameworkServlet.initWebApplicationContext(FrameworkServlet.java:339)  

• Dependencies can be checked using this command: mvn dependency:tree
• When I was iterating through these steps multiple times, I found some old dependencies lingering around. If that happens, this command would clear things up: mvn clean

Create web.xml:
If web.xml has not been created already, create it under ${project}/src/main/webapp/WEB-INF

Add DispatcherServlet to web.xml:
This is a standard Spring stuff you would do in any Spring MVC project.  (I created MVC project, so I did this.  It may or may not done in other cases)  Also, depending on the name given to DispatcherServlet in web.xml, create <dispatcher-servlet-name>-servlet.xml xml file.

Deploying this application now will not work.  Here are some steps I took to get rid of the errors:

1. First, we need to clean up the maven project.  Right click project -> Run As -> maven clean.
2. Right click project -> Properties -> Project Facet -> Select "Dynamic Web Project".
3. Again, Right click project -> Properties -> Deployment Assembly -> Add -> In popup, "Java Build Path Entries" -> Maven Dependencies -> Finish.  All this does is to copy dependency jar to .../WEB-INF/lib.

Hopefully, this helps someone create a project without any errors.
Thanks to these links:

http://stackoverflow.com/a/12600686/1700184
http://stackoverflow.com/a/6083776/1700184
https://developers.google.com/appengine/docs/java/tools/maven#creating_a_new_maven_app_engine_project_using_skeleton-archetype

pom.xml for Google App Engine + Spring

I am working on a new project that uses GAE (Google App Engine) and Spring.

I faced a few errors while trying to run the project - all related to incorrect configuration in pom.xml

Some of the problems I faced are:

• [ERROR] Failed to execute goal net.kindleit:maven-gae-plugin:0.8.0:run (default-cli) on project XYZ: ${gae.home} is not a directory: ${gae.home} is not a directory:[ERROR] Please set the sdkDir configuration in your pom.xml to a valid directory. Make sure you have correctly extracted the app engine sdk.
• [ERROR] Failed to execute goal net.kindleit:maven-gae-plugin:0.8.0:run (default-cli) on project XYZ: Execution default-cli of goal net.kindleit:maven-gae-plugin:0.8.0:run failed: Plugin net.kindleit:maven-gae-plugin:0.8.0 or one of its dependencies could not be resolved: Could not transfer artifact com.google.appengine:appengine-tools-sdk:jar:1.4.0 from/to central (http://repo.maven.apache.org/maven2): No response received after 60000 -> [Help 1]

 <?xml version="1.0"?>  
 <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  
  xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">  
  <modelVersion>4.0.0</modelVersion>  
  <groupId>xx.xx.xx</groupId>  
  <artifactId>XYZ</artifactId>  
  <packaging>war</packaging>  
  <version>0.0.1</version>  
  <name>XYZ Webapp</name>  
  <url>http://maven.apache.org</url>  
       <dependencies>  
      <!-- Spring framework -->  
      <dependency>  
           <groupId>org.springframework</groupId>  
                <artifactId>spring</artifactId>  
                <version>2.5.6</version>  
           </dependency>  
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-core</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-context</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-beans</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <!-- Spring MVC framework -->   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-webmvc</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <dependency>   
                <groupId>org.springframework</groupId>   
                <artifactId>spring-web</artifactId>   
                <version>${spring.version}</version>   
           </dependency>   
           <!-- Apache Commons Upload -->   
           <dependency>   
                <groupId>commons-fileupload</groupId>   
                <artifactId>commons-fileupload</artifactId>   
                <version>1.2.2</version>   
           </dependency>   
           <!-- Apache Commons Upload -->   
           <dependency>   
                <groupId>commons-io</groupId>   
                <artifactId>commons-io</artifactId>   
                <version>1.3.2</version>   
           </dependency>   
            <!-- JSTL -->   
           <dependency>   
                <groupId>javax.servlet</groupId>   
                <artifactId>jstl</artifactId>   
                <version>1.1.2</version>   
           </dependency>   
            <dependency>   
                <groupId>taglibs</groupId>   
                <artifactId>standard</artifactId>   
                <version>1.1.2</version>   
           </dependency>  
           <dependency>  
                <groupId>com.google.appengine</groupId>  
                <artifactId>appengine-tools-sdk</artifactId>  
                <version>1.8.0</version>  
           </dependency>  
           <dependency>  
                <groupId>com.google.appengine</groupId>  
                <artifactId>appengine-api-1.0-sdk</artifactId>  
                <version>1.8.0</version>  
           </dependency>  
           <dependency>  
       <groupId>net.kindleit</groupId>  
       <artifactId>gae-runtime</artifactId>  
       <version>${gae}</version>  
       <type>pom</type>  
     </dependency>  
      </dependencies>  
      <build>   
      <finalName>SpringFileUpload</finalName>   
           <plugins>   
                <plugin>   
                     <groupId>org.apache.tomcat.maven</groupId>   
                     <artifactId>tomcat7-maven-plugin</artifactId>   
                     <version>2.1</version>   
                     <configuration>   
                          <url>http://localhost:8080/manager/text</url>   
                          <server>my-tomcat</server>   
                          <path>/SpringFileUpload</path>   
                     </configuration>   
                </plugin>   
                <plugin>   
                     <groupId>org.apache.maven.plugins</groupId>   
                     <artifactId>maven-compiler-plugin</artifactId>   
                     <version>3.0</version>   
                     <configuration>   
                          <source>${jdk.version}</source>   
                          <target>${jdk.version}</target>   
                     </configuration>   
                </plugin>  
                <plugin>  
                     <groupId>net.kindleit</groupId>  
                     <artifactId>maven-gae-plugin</artifactId>  
                     <version>0.8.0</version>  
                     <configuration>  
                          <unpackVersion>1.8.0</unpackVersion>  
                          <gae.home>C:\Users\koushik\.m2\repository\com\google\appengine\appengine-java-sdk\1.8.0\appengine-java-sdk-1.8.0</gae.home>  
                     </configuration>  
                </plugin>  
           </plugins>   
      </build>  
      <profiles>  
        <profile>  
          <id>repositories</id>  
                <repositories>  
                     <repository>  
                          <id>maven-gae-plugin-repo</id>  
                          <name>maven-gae-plugin repository</name>  
                          <url>http://maven-gae-plugin.googlecode.com/svn/repository</url>  
                     </repository>  
                </repositories>  
                <pluginRepositories>  
                     <pluginRepository>  
                          <id>maven-gae-plugin-repo</id>  
                          <name>maven-gae-plugin repository</name>  
                          <url>http://maven-gae-plugin.googlecode.com/svn/repository</url>  
                     </pluginRepository>  
                </pluginRepositories>  
                <properties>  
                     <gae.home>C:\Users\koushik\.m2\repository\com\google\appengine\appengine-java-sdk\1.8.0\appengine-java-sdk-1.8.0</gae.home>  
                </properties>  
        </profile>  
      </profiles>  
      <properties>  
           <spring.version>3.0.5.RELEASE</spring.version>  
           <jdk.version>1.5</jdk.version>  
           <gae.home>C:\Users\koushik\.m2\repository\com\google\appengine\appengine-java-sdk\1.8.0\appengine-java-sdk-1.8.0</gae.home>  
           <gae>1.4.0</gae>  
      </properties>  
 </project>  

A Quick tip on Data Structure for DFS/BFS

Breadth-First Search and Depth-First Search are two very common graph traversal algorithms for any Graph.

There are two ways of representing graph - Adjacency Matrix and Adjacency Lists.  Well, this link gives more ways of representing a Graph.  But, let us not get into that.

Both DFS and BFS requires us to iterate over the children of a node.  This will be done for almost all nodes.

• Iterating through all children is O(n) in Adjacency Matrix.
• It is O(branches) in Adjacency Lists.

In a sparsely connected Graph, O(branches) is much smaller than O(n).  So, if we need to do a DFS, we should always choose Adjacency Lists over Adjacency Matrix.

Create an Android Activity as a popup

For the most of your popup needs, Android's Dialog should be good enough.  To popup some message, use AlertDialog.  Always use AlertDialog.Builder to build a new AlertDialog.  If you need a custom set of controls in the main message, use AndroidDialog.Builder's setView() method to set appropriate layout.

Now, if we need to popup a special kind of Activity that a Dialog cannnot solve, we can still do that.  But using Activity as a popup has a few problems.  In this post, I would like to discuss some of the approaches that I had taken to solve the problems.

How to disable back button in Android

Android phones come with a back button to go to previous activity.

http://docs.xamarin.com/static/guides/android/application_fundamentals/activity_lifecycle/Images/image4.png


There can be workflows where you may not want to go to previous Activity unless certain action is completed.  Sometimes, the current workflow may be in unstable state.  Sometimes, going back may not make any sense in the workflow.

The simple way to avoid using back button is to implement

onBackPressed() event in the activity.

If you are using a old version of Android, you may have to override onKeyDown.

public boolean onKeyDown(int keyCode, KeyEvent event)

Just check for (keyCode == KeyEvent.KEYCODE_BACK).

-----

This leads to another button that may close the Application - the Home button.  Home button takes you to Android device home.  Should that be overridden too?

It is unwise to override Home button.  Instead of trying to handle Home button's press, the Application's workflow should be designed to handle Home button is press during its execution. Here is a www.stackoverflow.com discussion on this topic.

Happy coding

Find the longest shortest-path between any two points in a graph

Given a graph, G, with edges E with weights W and vertices V.  You will have a path between two connected vertices.  Of the multiple paths between two vertices there should be one of the path that has the minimum weight.  Take the shortest path between every two points and return the one that has the maximum value.

This is a classic case of Floyd-Warshall algorithm.  The algorithm finds the shortest path between every two vertices in a graph.  We can use this to find all distances and then finally, find the maximum path.

Floyd-Warshall algorithm takes every pair of vertices in a graph and computes the distance of path through a third vertex.  This gives shortest path between any two vertices.  The complexity of the algorithm is O(|V|3)

A more efficient solution: We can calculate the path from a vertex V1 such that it is shortest path between V1 and one of the vertex and is longer than shortest path between any other vertex.  See this post for an algorithm.  Then, we can iterate through every vertex and find the longest path with every vertex as the root.  Once we have the list of all longest shortest-path, we can find the one that has the max value and return it.


find maxDepthInGraph(G)
{
  V <- G.vertices()
  E <- G.edges()

  for every vertex v in V:
    depth[v]=do breadth-first-search(v) and get the longest-  shortest-path

  maxDepth = -1
  for every vertex v in V:
    if maxDepth < depth[v]:
      maxDepth = depth[v]

  return maxDepth
}

Find the longest route from a vertex to any other vertex in a graph

Given a graph, G, with vertices, V, and edges, E, and V1 is one of the vertices in the graph, find the path in G such that it is the shortest path between V1 and a vertex and the path is greater than the shortest path between V1 and any other vertex in the graph.

For example, take this graph

In this graph, given V1 = node 4; the path that should result is 4 -> 1 -> 3 -> 5.  The reason is that, the path 4-1-3-5 is the shortest path between 5 and 4 and it is the path that is longer than shortest paths between node 4 and any every other vertices.

Solution: We need to do a Breadth-First Search.

1) Take V1 as the root node.  Then take all its children in a queue.

2) Do this till there is no more nodes in the queue:
2.a) If the children has been processed before, ignore it.
2.b) Otherwise, if the depth is the highest yet found, note down the path and depth for next iteration.
3) When all nodes are processed, return the highest yet depth and path. 

Orlando Trip

I had not been to any long-distance trips lately.  So, my wife and I decided to go to Orlando, Florida.  I thought I would share some of my experience with all of you.

1. Orlando's hotels cost a lot.  For example, we got a decent place to stay at Chicago for around $40.  The same in Orlando would have costed us some $100.  The place we chose was for $40 - which meant, it was below our expectations.  There were insects in the bathroom.  The AC was old - did not work as we intended it to work.  The wash basin happened to be outside the bathroom.  I personally was not satisfied.
2. Then we went to Disney World - Hollywood Studios.  I went there expecting a lot of rides and stuff.  Unfortunately, most of the things available were shows.  The website is right - they have very little number of rides.
3. The Island of Adventure in Universal Resort was great.  I thoroughly enjoyed it.  It had so many rides and stuff.

My recommendation:

1. Choose a good hotel.  You must estimate the cost of your hotel to be about twice as much as what you pay in a normal place.
2. Choose Universal for theme parks, if you need adventure.  Choose Disney World, if you dont like that much of adventure.

There are other places like Sea World, etc.  I did not go there.  So, I have no idea about those places.

Fight of narratives

I am mostly a passive reader in Quora.  But something kept cropping up again and again under the topic of "Tamil Nadu, India", or "Chennai, Tamil Nadu, India".  It is that why do Tamils hate North Indians.

http://www.quora.com/Chennai-Tamil-Nadu-India/Why-tamil-people-have-hatered-feelings-for-out-siders-Why-they-hate-north-indians-specially-Why-outsiders-cant-feel-homely-in-chennai-which-they-feel-in-Banglore-Mumbai-Hyderabad-and-rest-of-the-cities

http://www.quora.com/Tamil-Nadu-India/Why-do-Tamils-hate-Hindi-and-the-people-in-Tamil-Nadu-reluctant-to-learn-Hindi

I was totally surprised because I have been totally indifferent about the person's place or origin.  Most of the people who I know do not harbour any hatred for North Indians.  So, why do people ask these questions?  I had been thinking about these questions for a while now.  And these are the results of my reasoning.

India as a narrative

Traditional nations are made up of people who were almost homogeneous - almost all Germans speak German and are Christians and are white, almost all of the US is White, Christian, and speak English.  Think of it this way, there is a majority who get to frame the rules of the land and live happily - and minority fight for equal rights, and nowadays have succeeded quiet a bit.

India, on the other hand, is a minority-majority country.  The language spoken by the the largest numbers is Hindi which is a mother-tongue for just 40% of the population.  India is 80% Hindu - but there are multiple streams of Hinduism.  You can practically find all shades of skin color in India.  Ramachandra Guha, says it beautifully - India is like a salad bowl.  We have many sub-cultures living amongst us.  So, how did India manage to stay together, given there is so much of differences?

The answer, I feel, is narratives.  I come from deep-south of India.  Here, the idea of India is that we have four southern states - where we (Tamils) and other Indians live in; then there are some regions in north - where people speak Hindi - and where a few other Indians live.  The narrative in the north India is, we have a bunch of Hindi-speaking states, bordered with Hindi-speakable states.  There are a few people in the fringe regions in the South.  There is another narrative in West India (by Thackreys) - which is not gaining ground.

These narratives are very powerful.  They put the people holding the narratives at the center of Indian nation (in their minds).  Thus they feel India is "theirs".  But then, there are multiple narratives - each of which puts different peoples as the backbone of India.  So, almost all Indians live in their respective thought-bubbles - thinking that they are Indians.

Pakistan separated from India because in their narrative, they did not see India as "theirs" - so they separated.

Narrative-bust

These narratives get busted when an Indian step out into a region that does not comply to their narrative.  The way s/he reacts to narrative-bust is unique to the sub-culture that s/he belongs to.

It seems North Indians are more active on Quora than South Indians - which explains these rant-like questions about Tamils.

How do you fade in and fade out text in Android?

I had a requirement to make text blink in my Android application.  This came in prety handy:

http://stackoverflow.com/questions/3450839/blinking-text-in-android-view

ViewFlipper is a control available in Android to flip through many controls.  Define all controls within ViewFlipper in layout.  Then call startFlipping() to make ViewFlipper flip.

Now, there is another control called ViewSwitcher.  According to Android docs - "ViewAnimator that switches between two views, and has a factory from which these views are created. You can either use the factory to create the views, or add them yourself. A ViewSwitcher can only have two child views, of which only one is shown at a time."

From what I understand, use ViewSwitcher like you would use themes.  Use ViewFlipper like movie names is displayed in http://www.marcustheatres.com/.

My personal Avaniavittam reminders

Avaniavittam is a festival day when we change the sacred thread (poonal).

This time, I had missed a few things and had to get ready quickly.  I thought I would keep a Things to do for my own reference next year.

Week before

1. Make sure you have
2. Poonal
3. Dharbai
4. Powthiram
5. Black Sesame
6. Rice
7. Sandhyavandhanam book
8. All mantra details - like greeshma rithu, varsha rithu etc.

Day before

1. Materials to make vadai and payasam
2. Vaccum clean the place
3. Saree for wife
4. Silk veshti
5. Alarm

The Set

A common pattern in an interview is to ask for a data structure that would store a collection of items.  In Java, there are three types of objects that holds collection of data - Map, Set and List.

Here is a tip that would make sure that you choose an appropriate data type: Set should be your default choice.  A choice for a List should be based on you reasoning yourself out of using a Set.

Why?
Set has this data structure called HashSet.  It is super efficient.  Let us see this table for CURD operations.

	HashSet	ArrayList	LinkedList
C - Add to Collection	1	n	1
R - Find in Collection	1	lg n if sorted n otherwise	n
D - Remove from Collection	1	n remove and move all elements	1 (finding will take n. but removing will be 1)

As you can see, HashSet is super-efficient in all cases.

When should I not use Set?

1. If your collection can allow duplicates
2. If you need to maintain an ordering of some kind.

Always use a Set by default.  Set is wonderful.

Android App not getting published

I created an Android App.  I followed all steps given here

I waited for almost two days.  The App did not get published.  It usually takes 5-24 hrs to get published.

Then I figured out that I had uploaded APKs under Alpha, Beta and Production.  But the App had remained in Alpha.  So, I moved the application to Production.

Here is the screenshot of the page:

Developer Console -> Your App -> APK -> Production tab -> Move to (drop-down)-> Choose Production.

Android: Wake Up - Mistakes that I made

I had been working on a very simple Android Alarm App.  The users would set up an alarm after certain period of time.  When the time for Alarm arrives, the BroadcastReceiver defined in our application receives a signal.  If the phone is in lock mode, we have to wake the phone up and display to the user that it is time.

To wake the phone up, I am using android.os.PowerManager and PowerManager.WakeLock.

1. I had tried waking the phone up from inside BroadcastReceiver.  It should be done from Activity's onCreate() method.
2. The parameters that I passed for getting a new WakeLock were not working right.  In fact, I don't know which is the correct parameter I should use.  I am now using a deprecated parameter which is the only thing that is working for me.  The method is PowerManager'sInstance.newWakeLock().  The first parameter is levelAndFlags - I am using PowerManager.SCREEN_DIM_WAKE_LOCK.  I know I will have to use a combination of different non-deprecated flags.  But, I have not figured it out yet.
3. Always release the WakeLock in onFinish(), onPause(), onStop() methods.

HashSet delegates all its functions to HashMap

This is an old one.  In Java, HashSet delegates all its functions to HashMap.

What goes on under the covers of a HashSet<T> is:

• A member variable, map, of type HashMap<T, Object> is maintained.
• All operations on HashSet is delegated to a corresponding operation on HashMap - add(), remove(), contains(), etc.
• A dummy object

add(T objOfTypeT)
Invokes put(objOfTypeT, dummy object)

remove(T objOfTypeT)
Invokes HashMap's remove(objOfTypeT)

size()
returns map's size

contains(T objOfTypeT)
returns map.containsKey(objOfTypeT)

iterator()
returns map's keySet's iterator

Installing packages from Python

I am new to python.  I am using python 2.7.5.

I was working on writing a screen scrapper for one of my projects.  I am using scrapy framework for screen scrapping.

After setting up and testing my spider, I wanted to test how it could be called from another Python script.  Till this point I had been testing using scrapy's commands.

I looked up online to find an example to call scrapy from another Python script.  Scrapy, it seems, uses a network framework called twisted.  Twisted was not installed in my machine.  So, I proceeded to do a sudo apt-get install python-twisted in my command prompt.  That did not seem to work.

I created a sample twisted script and attempted to run that.  This would help in testing if Python really recognizes Twisted  Obviously, that failed.

So, after a bit of looking around, I stumbled upon this.  Python packages needs to be installed from tar files.  So, download a tar file, un-tar it.  This should create a source directory which is supposed to have a file called setup.py.  To install the package, run python setup.py install 

This is exactly what I did.  I downloaded tar of Twisted from here.  Then un-tar'ed it using tar xjf Twisted-13.1.0.tar.bz2 which created a folder Twisted-13.1.0.  Then changed directory into Twisted-13.1.0 using cd Twisted-13.1.0.  Finally, python setup.py install.  This gave an error.  Twisted required another package called zope.interface.

I downloaded tar of zope.interface from here and then did the above steps first for zop.interface so zope gets installed.  Then proceeded to Twisted-13.1.0 folder to do a python setup.py install in that folder.

So, in general, if you need to install a package in Python, get the tar file and use python install feature on setup.py file of the tar.

To synchronize or not to synchronize?

Let us say we implement a very common functionality and offer our implementation as a open source library.  For example, we develop a library to keeping track of count of how many times a certain operation has taken place - like a call to web service.  We know this is very reusable.  But, we do not know how this functionality will be used by developers.  There could be many concerns on how this library could be used by the developers; but in this post, let us concentrate on: will the functionality be called from a multi-threaded environment?

The traditional way of handling multi-threading is to ensure make a critical-section is accessed in a single-threaded way.  To achieve this in Java, we use synchronized key word.  synchronized gets a lock (atomically) on the object (non-static methods) or class (static methods).  In Java, we also have an option of maintaining lock on an arbitrary object.  Code that is safe for execution by multiple threads is called thread-safe.

Now, the downside of synchronized is that it takes a lot of performance-hit.  For a fast program, it is advisable to use synchronized in as few places as possible - (a) this will reduce the performance-hit produced by synchronized (b) it ensures that as many threads executes in parallel as possible - both of which are good for performance.

So, given these facts about synchronized, in our Counter library, should we synchronize to make it thread-safe or not synchronize to make it fast?

The advisable approach is: do not synchronize unless you are sure that the code will be used in multi-threaded environment.

So, we would not make our Counter's methods synchronized.  If a developer intends to use our Counter class in a multi-threaded code, then the developer should ensure that the methods are called in a thread-safe manner.  This can be done by synchronizing over Counter object (or some other lock object) or by providing a wrapper method that is synchronized on the calling object.

Some simple multi-threading tips:

• Always check if object is used in a multi-threaded environment.
• Make the object immutable.  This means that you set values to an object's state only in constructor.  There should be no method accessible to other classes that can change the state of object after constructor has finished execution.
• If you are dealing with a group of objects, use a separate lock object and synchronize based on that lock object.

Given a sum S and number of non-negative number N, how many different ways can N non-negative numbers can be chosen such that their sum is S - II

Please refer to previous post for more information regarding the problem that we are discussing.

In our previous post, we discussed a bad solution for the problem of finding how many combination of N non-negative numbers can we find such that it yields a given sum S.

The complexity of the discussed solution was SN 

The solution had a sample Java code for the method - count_correct_combination

Let us again consider S = 3 and N = 3.  To compute this answer, we compute

S = 3, N = 3

S = 3, N = 2

S = 3, N = 1

S = 2, N = 1

S = 1, N = 1

S = 2, N = 2

S = 2, N = 1

S = 1, N = 1

S = 1, N = 2

S = 1, N = 1

S = 0, N = 2

We can find that S = 1, N = 1 is calculated repeatedly.  For some large input values of N and S, there will be many such intermediate values of S and N that will get calculated repeatedly.  All these contributes to exponential complexity.

This can be improved by remembering what the value was when we calculated the result for a give S and N.

To do that, create a two-dimensional array of dimensions (S + 1, N) and store intermediate values in the array.  S + 1 - because there are S + 1 possible values for every variable (0 to S - both included).

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                  2	1
variables          .	1
.	1
N - 1	1
N	1

The first column and the first row are all 1's.  This is because of the following two facts:

1. The number of different ways we can choose N non-negative numbers such that the sum of the numbers is 0 = is always 1.  This is because to get sum(n numbers) = 0, we need every number to be equal to 0.  There is no other way to pick non-negative numbers to result in sum of zero.
2. The number of different ways in which 1 variable can result in a sum of S = is 1.  That is that one variable should be = S.  Otherwise, sum(variables) will not be = S.

To calculate the value for the rest of the elements in our array, we know that result of (S, N) = sum of (S - x, N - 1) where x = 0 to S (both included).  Applying this formula 

Variables\Sum	0	1	2	.	.	S - 1	S
Number             1	1	1	1	1	1	1	1
of                   2	1					xxx	= value(0, 1) + value(1, 1).. + value(S, 1)
variables          .	1					xxx
.	1					xxx
N - 1	1	xxx	xxxx	xxx	xxx	xxx	= value(0, N-2) + value(1, N-2).. + value(S, N-2)
N	1	= value(0, N-1) + value(1, N-1)				= value(0, N-1) + value(1, N-1).. + value(S-1, N-1)	= value(0, N-1) + value(1, N-1).. + value(S, N-1)

In other words, the value of any element in a given (col, row) is equal to sum of values of all elements from 0th column till col in the row above.

But if we do a sum of elements in a row-above to find values in the desired row, we might be computing sum of first few elements again and again.  This can be simplified further.

So, given col1 and row1 for which we need to calculate value, we do 

value(col1,row1) = (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1))

To find the value of col1 + 1, row1, we do (Note: Take note of how the paranthesis changes)

= (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1) + value(col1 + 1, row1 - 1))

=  (value(0, row1 - 1) + value(1, row1 - 1) + value(3, row1 - 1) + ... value(col1, row1 - 1)) + value(col1 + 1, row1 - 1)

= value(col1,row1) + value(col1 + 1, row1 - 1)

Translating this to an arbitrary col, row, we get:

value(col, row) = value(col - 1, row) + value(col, row - 1)

In simple words, value of an element at col1, row1 = value of cell above + value of cell to the left.