UnionFind for Dynamic connectivity

Union Find is used to find the connection between two objects.
Why do we need Union Find algorithm?

There are three approaches to implement this each with it's own complexity.
1. Quick Find:
Simplest but does union is quadratic in nature

2. Quick Union:

Union is Linear time but find also becomes linear which is constant in Quick find

3. Weighted QuickUnion:

Union and find are logarithmic in nature

Implementation:
The class diagram of my implementation uses code from Dr.Robert Sidgewich's code base. Here I use the template method and strategy pattern to do a quick comparison of performance of all the three types.

The following images show how the implementation is done.

UF is the abstract class from which all other union find classes inherit

UFclient uses the strategy pattern by invoking run() from the main factory method.

QuickFind inherits from UF and uses a single array with a simple idea to find connectivity as shown below.

 QuickUnionUF inherits from UF and uses a single array with tree structure to find connectivity as shown below.

QuickUnionUF inherits from UF and uses a single array with tree structure to find connectivity as shown below. It goes one step further to use a second array for maintaining and balancing weight on the tree.

Performance:

Significant performance difference can be observed from the output as shown below

Time taken for QuickFindUF is 177
Time taken for QuickUnionUF is 66
Time taken for WeightedQuickUnionUF is 25

You can see the difference between Quadratic vs Linear vs Logarithmic time. They are in the ratio 7:3:1

Why do we need better algorithms?

This is the most fundamental question every student must ask himself before taking a course on Algorithms. Rather than talking too much about algorithms let me straight away give examples. All the shown examples are from the speech 'Beyond Computation - Michael Sipser'
Problem 1: Finding the factorial of a large number.

We still don't know whether there is any other possible way to find the solution or not.

Problem 2: Finding the largest clique in a given graph with 100 nodes

But trying to find a large clique in the below figure is very difficult for the computer.

Solution: Trying to find the analogy of magnet in mathematics

If you can find the magnet, you are one of the most Intelligent on the planet.

Other Problems:

So you can see that the biggest challenge is 

This is the ultimate reason why we need better algorithms.

To understand more, let me show you the difference between P and NP problems

If P = NP is proved, then we do not need to search for a search algorithm else we need to search. Whether P = NP or P != NP is a mystery.

NP-Completeness

This is the first step taken by humans towards solving an NP problem. NP-Completeness defines that a set of problems are linked to each other and can be easily transformed into each other which means if there is a solution to one problem, then the solution for the other can be found but the reverse is not true. Eg: Factoring can be converted into CLIQUE but not CLIQUE into Factoring

NP-Hard:

There are NP problems for which even checking is not possible. These are called NP-Hard. Eg of such a problem is Chess.

Will it ever be solved?

Understanding Screens

Android runs on a variety of devices that offer different screen sizes and densities. For applications, the Android system provides a consistent development environment across devices and handles most of the work to adjust each application's user interface to the screen on which it is displayed. There are 4 key terms you should remember. They are,
1. Screen Size:
Actual physical size, measured as the screen's diagonal.
For simplicity, Android groups all actual screen sizes into four generalized sizes: small, normal, large, and extra large. The actual to general mapping is shown below,

xlarge screens are at least 960dp x 720dp
large screens are at least 640dp x 480dp
normal screens are at least 470dp x 320dp
small screens are at least 426dp x 320dp

2. Pixels Per Inch(PPI) or Dots Per Inch(DPI):
The quantity of pixels within a physical area of the screen
For simplicity, Android groups all actual screen densities into four generalized densities: low, medium, high, and extra high. The actual to general mapping is shown below,

3. Density Independent Pixels(DP):
A virtual pixel unit that you should use when defining UI layout, to express layout dimensions or position in a density-independent way.
Calculation: px = dp * (dpi/160).
Let's for example take Google Nexus 5 & Google Nexus 4. According to DPI love , Google Nexus 5 has 445dpi and Google Nexus 4 has 318dpi. Now when the developer defines a view to be having a width of 40 dp , the corresponding pixels will be px5 = 40 * (445/160) = 111 for Google Nexus 5 and px4 = 40 * (318/160) = 80. So you can see that , the view is optimized according to the specific screen using a simple logic. Without this approach, directly mentioning the size using px or cm will give a inconsistent view across multiple screens as shown below.

Best Practices:

1. The following is a list of resource directories in an application that provides different layout designs for different screen sizes and different bitmap drawables for medium, high, and extra high density screens.

res/layout/my_layout.xml             // layout for normal screen size ("default")

res/layout-small/my_layout.xml       // layout for small screen size

res/layout-large/my_layout.xml       // layout for large screen size

res/layout-xlarge/my_layout.xml      // layout for extra large screen size

res/layout-xlarge-land/my_layout.xml // layout for extra large in landscape orientation

res/drawable-mdpi/my_icon.png        // bitmap for medium density

res/drawable-hdpi/my_icon.png        // bitmap for high density

res/drawable-xhdpi/my_icon.png       // bitmap for extra high density

2. Always design the screen with a mobile or tablet in mind. Specifically, when selecting resources based on the size qualifiers, the system will use resources designed for a screen smaller than the current screen if there are no resources that better match (for example, a large-size screen will use normal-size screen resources if necessary). However, if the only available resources are larger than the current screen, the system will not use them and your application will crash if no other resources match the device configuration (for example, if all layout resources are tagged with the xlarge qualifier, but the device is a normal-size screen).

3. To create alternative bitmap drawables for different densities, you should follow the 3:4:6:8 scaling ratio between the four generalized densities. For example, if you have a bitmap drawable that's 48x48 pixels for medium-density screen (the size for a launcher icon), all the different sizes should be:

36x36 for low-density

48x48 for medium-density

72x72 for high-density

96x96 for extra high-density

4. Use wrap_content, fill_parent, or dp units when specifying dimensions in an XML layout file

5. Do not use hard coded pixel values in your application code

6. Do not use AbsoluteLayout (it's deprecated)

7. Supply alternative bitmap drawables for different screen densities

Working with Animation

There are two ways to work with animation. Below chart shows various ways to animate

The two types of animation are,

1. View Animation
2. Property Animation

Let's look each of this type of animation in detail.

1. View Animation:

View animation is simple and Android provides three support classes. They are, 

• TransitionDrawable
• AnimationDrawable
• Animation

    TransitionDrawable

This drawable is used to transit between two drawables on a single view. Create a TransitionDrawable class and start the animation as shown below.

R.drawable.shape_transition defines the transition between two drawables and this xml file looks like the following. Here you can see that the transition is between two shapes defined in an xml which can be easily replaced by two images.

    AnimationDrawable

This class is used to provide a slideshow kind of animation where you provide a set of drawables which is drawn to the screen in an imageView in a given sequence with the given time. The code below shows how the class must be created and used. Involes three steps.
First is to find the imageView in which the transition should be shown.
Second the tranisition is set as background to the imageView and
Thirdly, ref to the animation drawable is acquired and animation can be started/stopped

This is also a good time to discuss when to use onWindowFocusChanged() and onResume(). As a general rule, however, a resumed activity will have window focus... unless it has displayed other dialogs or popups that take input focus, in which case the activity itself will not have focus when the other windows have it. Likewise, the system may display system-level windows (such as the status bar notification panel or a system alert) which will temporarily take window input focus without pausing the foreground activity. Thus use onWindowFocusChanged() when you want an action to be performed even in scenarios where onResume() may not be called. Shown below is the code to start the animation in onWindowFocusChanged() method.

    Animation
This class helps us to animate a view by changing properties of the view. Multiple transformations can be applied conveniently using this method.
First define your animation file and store it in res/anim folder.

Now load the animation in the xml file into the current activity using the following calls

Finally start the animation using the startAnimation() callback as shown above

2. Property Animation:

Sometimes you want animate other objects other than view, for this purpose the Android provides the Property Animation framework. Helps to change generic properties of objects over time.

Working with 2D graphics

There are two ways to draw to the screen. Check below chart to find various ways to draw 2D graphics

1. Draw to the view - Simple graphics with little or no updates
2. Draw to a canvas - More complex graphics with regular updates

1. Draw to a view:
Let's first see how to draw to view. Drawing to view can be done using the Drawable objects like the ShapeDrawable, ColorDrawable and BitmapDrawable class. A simple way to draw a bitmap is shown in the xml file below
BitmapDrawable:
Any images can be drawn to a imageview as shown below

ShapeDrawable:

Following shapes can be drawn using the drawable class

Similar to Bitmaps, shapes can be drawn as shown below

Just like putting the image to be drawn in res/drawable folder, a shape can be defined manually using an xml and put in the res/drawable folder. Below is shown an example of how to define drawable shape.

Drawing to view is especially useful when setting background for buttons like shown below.

2. Draw to a canvas:

To draw using canvas you need 4 things. They are,

There are two ways to draw. 

*By extending View and overriding the onDraw() method - for less updates using internal thread as shown below

*By extending SurfaceView  and implementing the SurfaceHolder.Callback interface - for more updates

What is SurfaceView?

SurfaceViews need a separate, non-UI thread in which to do their work so their operations won't interfere with UI thread unlike the 'By extending View' shown above. A SurfaceView manages a low-level drawing area called a Surface. And this Surface is a dedicated drawing area, that is positioned within the applications view hierarchy. To define a SurfaceView, you need to create a custom class, which is a subclass of SurfaceView. And this custom class must, must also implement the SurfaceHolder.Callback interface. 

Setup of surfaceview:

>First use the SurfaceViews getHolder method to acquire the SurfaceView's SurfaceHolder. 

>Next, you register the SurfaceView for SurfaceHolder callbacks

Below code shows the callback methods where the thread which does the actual surface locking and other important housekeeping is handled is defined. This ensures less work on the UI thread.

Drawing on surfaceview:

>After the setup is done, draw using the canvas supplied by the lockCanvas() method.