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.

Java Statements

Java statements is the most fundamental topic to master to be an effective Java programmer.
Four types of statements are:

Assignment Statement:
Assignment statements of all primitives will return their primitive values.
1. Value can be assigned as shown below
int a;
int b;
a = (b=true);


2. common type of assigning value is
int a = 9;

3. Remember that the only valid literal values for the boolean primitives are true and false. Below statements are invalid
boolean isValid = TRUE;

boolean isValid = 1;

Conditional Statement:
Valid scenarios
1. true  or false statements and the following type of assignment statement is correct inside a if statement.
boolean a = false;
if(a = true)
{}

2. Boolean wrapper class can be used as unboxing is the automatic production of its primitive value in cases where it is needed. So the following code is correct.
Boolean wrapperBoolean = new Boolean("true");
if(wrapperBoolean)
{}

3. Order does not matter in the switch cases. If a case is satisfied then default is ignored.
int a = 1;
switch(a)
{
  default:
     System.out.println("Default executed first");
  case 1:
     System.out.println("a executed first");
}
Output:  a executed first

4. String can be used in cases starting Java 7

String a = "hello";

switch(a)

{

    default:

        System.out.println("Default executed first");

        break;

    case "1":

        System.out.println("1 executed first");

        break;

    case "hello":

        System.out.println("hello executed first");

        break;

}

Output: hello executed first

5. Arithmetic operations are allowed in case as shown below
int a = 2;
switch(a)
{
    default:
        System.out.println("Default executed first");
        break;
    case 3-1:
        System.out.println("2 executed first");
        break;

}
Output: 2 executed first

6. Switch fall through can be taken advantage because all the cases following a success case without a break will get executed. Eg of fallthrough is shown below

public class SwitchDemoFallThrough {

    public static void main(String[] args) {
        java.util.ArrayList futureMonths =
            new java.util.ArrayList();

        int month = 8;

        switch (month) {
            case 1:  futureMonths.add("January");
            case 2:  futureMonths.add("February");
            case 3:  futureMonths.add("March");
            case 4:  futureMonths.add("April");
            case 5:  futureMonths.add("May");
            case 6:  futureMonths.add("June");
            case 7:  futureMonths.add("July");
            case 8:  futureMonths.add("August");
            case 9:  futureMonths.add("September");
            case 10: futureMonths.add("October");
            case 11: futureMonths.add("November");
            case 12: futureMonths.add("December");
                     break;
            default: break;
        }

        if (futureMonths.isEmpty()) {
            System.out.println("Invalid month number");
        } else {
            for (String monthName : futureMonths) {
               System.out.println(monthName);
            }
        }
    }
}

This is the output from the code:

August
September
October
November
December

7. Following statement compiles without any problem.
if (x == 0) ; else if (x == 1){} else {;}

8. Following statements compiles without any problem.
if (true) ;
if (true) {}
if (true) {;}
if (true) {;;}
if (true) ;{};

Invalid scenarios
1. Since assignment statements return their primitive values, following code will fail to compile
int a = 1;
if(a = 2)
{}

2. Ranges are not allowed in cases.

3.Following statement throws compilation error because no space between elseif
if (x == 0) {;} elseif (x == 1) {System.out.println("Valid Statement");}

How to compile and interpret Java code in command line?

Compilation & Interpretation life cycle is shown below

To compile your java code:
Using -d & -cp option
javac -d classes -cs somedirectory/classes/:. JavaOutput.java
Here -d = directory switch telling the compiler to save the output class file in the classes directory. Sub-directories are created according to package names
         classes = destination directory
         JavaOutput.java = is the file to be compiled.
         -cs = classpath switch telling the compiler to find the user-defined classes and packages in the specified directory
         somedirectory/classes - contains the user defined classes
Note that : is a delimiter in POSIX systems and .(period) is the current directory

All the available options are shown below

To interpret your java code:
Interpreter is used to interpret bytecode and execute your program.
java Car
executes Car.class file. Option -cs is similar to compiling code and -D switch is used to set property values

All the available options are shown below

Java Class Structure

Conventions are used to increase the maintainability of Java code across multiple developers & projects. Below shown is the tabular column consisting of the naming conventions & symbols used in Java

Using Third party Library in your Android project

Things to know:

• You can create Android library projects, which you can reference in other Android projects. Library projects cannot be installed onto a device. They are pulled into the APK file at build time.
• The Android Support Library package is a set of code libraries that provide backward-compatible versions of Android framework APIs as well as features that are only available through the library APIs. Because of the library support your applications can use advanced libraries' features and still be compatible with devices running Android 1.6 (API level 4) and up.

Procedure:

1.  To create a Android Library Project , click New > 'Android Application Project'. Check 'Mark this project as a library' and uncheck 'Create custom...icon' & 'Create activity' as shown below.

2. Am just reusing the Timber class from JakeWharton for this example. Now this will be the reusable library I'll be using throughout my Android projects.

3. Now open your existing project or create a new project. Shown below is the Android Support Library , TimberLoggerLibrary and the Android project TimberLoggerUser in which I'll be using the TimberLoggerLibrary

     

       When you create a new project you might see Android Support Libraries automatically linked by eclipse to provide backward compatibility. I am mentioning this here just for you to witness the use of android support libraries.

4. Right click on your Android project > properties. Click 'Android' tab on the left as choose the library by clicking 'Add'. Click 'Apply' > 'ok'

5. At this point you have successfully linked the library project to your Android project and is ready to be reused. Below you can see that 'timberloggerlibrary.jar' is automatically added under Android Dependencies

Working with Java Jar files

1.  Create a normal Java project

2. Create a class with the necessary methods with static declaration as shown below.

3. Once free of errors, click file > export and click 'JAR file' from the options shown

4. Select the project and click finish in the following screen

5. Now the jar file contains the the class files and is ready to be used in any project. To check out how it's working create a separate project and use the method as shown below. Right click > properties on the newly created project

6. Click 'Add External JARs ' and add the created jar in your project.

7. The added JAR appears as shown in the 'Referenced Libraries'

8. Now use it in your project by directly invoking the method name without instantiating the MathLib class as shown below