Algorithm Design

/

An algorithm is a step-by-step procedure for performing calculations. Types of algorithms include:

Sometimes it's hard to know where to start in designing an algorithm for a task at hand. Below are some elements to consider during algorithm design.

Performance

Consider factors such as the average and worst case performance of your algorithm.

Design Patterns

Find a code design pattern that fits the problem you're solving.

Data Structure

The data structure you choose should reflect your data access needs.

Database Structure

A database is often a good data storage choice when the data needs to be accessed using a variety of search, sort and display options.

Data Sort

There's a large selection of sorting algorithms to select from. See which one most closely fits the nature of your data and access requirements.

Java abstract Classes and Methods

/

The abstract modifier for classes and methods has to do with instantiation. Here's a summary:

abstract class

  • can't be instantiated
  • can be extended
  • must be declared abstract if it contains one or more abstract methods

abstract method

  • has only a declaration with no body, such as:
public abstract myMethod(String myString);

Java final, abstract and static Modifiers

/

The meaning of the final, abstract and static Java modifiers can be confusing and hard to remember. Here's a brief summary:

final

Generally means "can't be changed".

  • final class: can't be extended (sub-classed)
  • final method: can't be overridden or hidden by sub-classes
  • final variable: can only be initialized once 

abstract

Generally means "can't be instantiated".

  • abstract class: can't be instantiated, can be extended, must be declared abstract if it contains one or more abstract methods
  • abstract method: has only a declaration with no body
  • abstract variable: not allowed

static

Generally means "not associated with an instance".

  • static class: only nested inner classes can be static, they are not associated with any instance of the enclosing class
  • static method: doesn't use instance variables
  • static variable: is the same across all instances of it's containing class

additional notes

  • constants: use static final as variable modifiers
  • abstract static methods are not allowed

Android Common Tasks

/

Android Lists

/

This video, part of my Android Quick Code Access series of posts, explains Android Lists. It's from my course Learning Android App Programming.

The Java source code for this example is shown below...

// Copyright (C) 2007 The Android Open Source Project.

package com.example.android.apis.view;

import android.app.ListActivity;
import android.os.Bundle;
import android.widget.ArrayAdapter;

/**
 * A list view example where the 
 * data for the list comes from an array of strings.
 */
public class List1 extends ListActivity {

    // onCreate method executed when the ListActivity is started.
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        // Use an existing ListAdapter that will map an array
        // of strings to TextViews
        setListAdapter(new ArrayAdapter(this,
                android.R.layout.simple_list_item_1,
                mStrings));
        getListView().setTextFilterEnabled(true);
    }
    // String array containing items to be displayed.
    private String[] mStrings = Cheeses.sCheeseStrings;
}

For list item layout options (like android.R.layout.simple_list_item_1 used in the sample above), see the R.layout class.

Android Fragments

/

This video, part of my Android Quick Code Access series of posts, explains Android Fragments.  It's from my course Learning Android App Programming published by InfiniteSkills.

The Java source code for the example with additional comments for clarification...

// Copyright (C) 2010 The Android Open Source Project

package com.example.android.apis.app;

import com.example.android.apis.R;

import android.app.Activity;
import android.app.Fragment;
import android.app.FragmentManager;
import android.app.FragmentTransaction;
import android.os.Bundle;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.TextView;

// Demonstration of hiding and showing fragments.
public class FragmentHideShow extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        // Set the display layout.
        setContentView(R.layout.fragment_hide_show);

        // Instantiate a Fragment Manager.
        FragmentManager fm = getFragmentManager();

        // Attached listeners to the fragments.
        addShowHideListener(R.id.frag1hide,
                    fm.findFragmentById(R.id.fragment1));
        addShowHideListener(R.id.frag2hide,
                    fm.findFragmentById(R.id.fragment2));
    }
    // Show and Hide Listener method.
    void addShowHideListener(int buttonId, 
                             final Fragment fragment) {
        // Button variable.
        final Button button = (Button)findViewById(buttonId);

        // Attach the onClickListener to the Button.
        button.setOnClickListener(new OnClickListener() {
            public void onClick(View v) {

                // Get and start a Fragment Manager.
                FragmentTransaction ft =
                    getFragmentManager().beginTransaction();

                // Set a fade in and out custom animation.
                ft.setCustomAnimations(
                    android.R.animator.fade_in,
                    android.R.animator.fade_out);

                // Perform the fragment show and hide.
                if (fragment.isHidden()) {
                    ft.show(fragment);
                    button.setText("Hide");
                } else {
                    ft.hide(fragment);
                    button.setText("Show");
                }
                // Commit the fragment transaction.
                ft.commit();
            }
        });
    }
    // First Fragment Class.
    public static class FirstFragment extends Fragment {

        // TextView for the changeable text.
        TextView mTextView;

        // Method invoked when the view is created.
        @Override
        public View onCreateView(
                        LayoutInflater inflater,
                        ViewGroup container,
                        Bundle savedInstanceState) {

            // Inflate the view.
            View v = inflater.inflate(
                            R.layout.labeled_text_edit, 
                            container, false);

            // Get the id of the message.
            View tv = v.findViewById(R.id.msg);

            // Display the text.
            ((TextView)tv)
                .setText("The fragment saves and restores this text.");

            // Retrieve the text editor.
            mTextView = (TextView)v.findViewById(R.id.saved);

            // Restore the last saved state if needed.
            if (savedInstanceState != null) {
                mTextView.setText(
                   savedInstanceState.getCharSequence("text"));
            }
            // Return the view.
            return v;
        }
        // Method defining instance state saving action.
        @Override
        public void onSaveInstanceState(Bundle outState) {
            super.onSaveInstanceState(outState);

            // Save the current text. 
            outState.putCharSequence("text", mTextView.getText());
        }
    }
    // Second Fragment Class.
    public static class SecondFragment extends Fragment {

        // Method invoked when the view is created.
        @Override
        public View onCreateView(
                        LayoutInflater inflater,
                        ViewGroup container,
                        Bundle savedInstanceState) {

            // Inflate the view.
            View v = inflater.inflate(
                        R.layout.labeled_text_edit, 
                        container, false);

            // Get the id of the message.
            View tv = v.findViewById(R.id.msg);

            // Display the text.
            ((TextView)tv).setText(
                 "The TextView saves and restores this text.");

            // Retrieve the text editor and 
            // tell it to save and restore its state.
            // Note that you will often set this 
            // in the layout XML, but since
            // we are sharing our layout with the other
            // fragment we will customize
            // it here.
            ((TextView)v.findViewById(R.id.saved))
                .setSaveEnabled(true);

            // Return the view.
            return v;
        }
    }
}

Android Listeners and Toasts

/

This video, part of my Android Quick Code Access series of posts, explains Android Listeners and Toasts. It's from my course Learning Android App Programming published by InfiniteSkills.

The Java code for the example is below...

import java.util.Random;
import android.app.Activity;
import android.content.Context;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.Toast;

public class ListenerToastMain extends Activity {
	
    // onCreate method.
	@Override
	protected void onCreate(Bundle savedInstanceState) {
	    super.onCreate(savedInstanceState);
	    
	    // Initialize display.
	    setContentView(R.layout.main);
	        
           // Declare button variable for Get Answer.
	    Button getAnswer =
               (Button)findViewById(R.id.getAnswerButton);
	        
	    // Set listener for button.
	    getAnswer.setOnClickListener(getAnswerListener);    
	}   
    // Define OnClickListener for getAnswer button.
    private OnClickListener getAnswerListener = new OnClickListener() {
        public void onClick(View v){
       		
            // Generate answer number.
            Random toastGen = new Random();
            int toastNum = toastGen.nextInt(19);
            toastNum++;
       		
            // Get answer text.
            CharSequence text = "";
            switch (toastNum) {
                case 1:  text = getString(R.string.answer1);  break;
                case 2:  text = getString(R.string.answer2);  break;
                case 3:  text = getString(R.string.answer3);  break;
                case 4:  text = getString(R.string.answer4);  break;
                case 5:  text = getString(R.string.answer5);  break;
                case 6:  text = getString(R.string.answer6);  break;
                case 7:  text = getString(R.string.answer7);  break;
                case 8:  text = getString(R.string.answer8);  break; 
                case 9:  text = getString(R.string.answer9);  break;
                case 10: text = getString(R.string.answer10); break;
                case 11: text = getString(R.string.answer11); break;
                case 12: text = getString(R.string.answer12); break;
                case 13: text = getString(R.string.answer13); break;
                case 14: text = getString(R.string.answer14); break;
                case 15: text = getString(R.string.answer15); break;
                case 16: text = getString(R.string.answer16); break;
                case 17: text = getString(R.string.answer17); break;
                case 18: text = getString(R.string.answer18); break;
                case 19: text = getString(R.string.answer19); break;
                case 20: text = getString(R.string.answer20); break;       		    
            }
            // Toast answer.
            Context context = getApplicationContext();
            int duration = Toast.LENGTH_LONG;
            Toast toast = Toast.makeText(context, text, duration);
            toast.show();
        }	        	
    };
}

Android Broadcast Receiver Concepts and Sample App

/

This video, part of my Android Quick Code Access series of posts, explains Android Broadcast Receivers.  It's from my course Learning Android App Programming published by InfiniteSkills.

Here's the Java code for the example...

import android.app.Activity;
import android.content.BroadcastReceiver;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
import android.os.Bundle;
import android.widget.Toast;

// Declare main activity for the application.
public class Main extends Activity {

    // Instantiate BroadcastReceiver.
    private BroadcastReceiver receiver = new BroadcastReceiver(){

        // Define actions to be taken when broadcast is received.
        @Override
        public void onReceive(Context c, Intent i) {
			
            // Do the work of the BroadcastReceiver.
            // In this example, a message is toasted to the user.
            Toast.makeText(getBaseContext(), 
                           "ACTION_TIME_TICK intent received.", 
                           Toast.LENGTH_LONG)
                           .show();
        }
    };
    // Initialize the user interface in the onCreate method
    // of the main activity.
    @Override  
    public void onCreate(Bundle savedInstanceState) {  
        super.onCreate(savedInstanceState);  
        setContentView(R.layout.main);  
    } 
    // Register the receiver with its filter.
    @Override  
    protected void onResume() {  
        this.registerReceiver(receiver, filter);  
        super.onResume();  
    } 
    // Unregister the receiver when the application is paused.
    @Override  
    protected void onPause() {  
        this.unregisterReceiver(receiver);  
        super.onPause();  
    }  
}

Android Database Query Display

/

This is part of the Android Quick Code Access series of posts. The code below displays the results of a Database Query. You'll need to run the Query code in a background thread in your production version.

// Database Display Activity.
public class DatabaseDisplayActivity extends ListActivity {

   // Database display columns.
   private static final String[] PROJECTION = new String[] {
    	COLUMN_NAME_1,   // 0 Position
    	...
   }
   @Override
   // Activity onCreate method.
   protected void onCreate(Bundle savedInstanceState) {
       super.onCreate(savedInstanceState);
		
       // Database Query. 
       Cursor cursor = managedQuery(
            MyContent.CONTENT_URI,
            PROJECTION,
            null,
            null,
            MyContent.DEFAULT_SORT_ORDER  
       );		
       // Cursor columns to display.
       String[] dataColumns = {     		
            COLUMN_NAME_1,
            ...
       } ;
       // View IDs for formatting.
       int[] viewIDs = { 	
            android.R.id.text1,   
            ...		
       };
       // Adapter for the ListView.
       SimpleCursorAdapter adapter = new SimpleCursorAdapter(       		
            this,                                 
            android.R.layout.simple_list_item_1, 
            cursor,  
            dataColumns,
            viewIDs   
            );
       // Binder to display row results.
       adapter.setViewBinder(new SimpleCursorAdapter.ViewBinder() {
           public boolean setViewValue(
                View view, Cursor cursor, int columnIndex) {
        		
                // Get row of cursor.
                String displayText = 
                    DatabaseUtils.dumpCurrentRowToString(cursor);

                // Set text in display.
                ((TextView) view).setText(displayText);
                return true;
            }
       });        
       // List Adapter.
       setListAdapter(adapter);	
   }
}

Android Eclipse Waiting for Debugger

/

This is part of the Android Quick Code Access series of posts. Depending on the specifics of your Android code, you may need to add code to force a wait for the Eclipse debugger. This is especially true for asynchronous code functions like background threads. Without the code below, you may see Eclipse break points not being triggered. You might think that your code is broken, when in fact you just need to add a code line to force it to wait for the debugger to catch up.

android.os.Debug.waitForDebugger()

Android Allowing Main Thread I/O

/

An important aspect of Android App design is to never block the main UI thread with long running tasks. Doing so can result in an Application Not Responding (ANR) condition that can cause your App to be stopped. To prevent ANR conditions, always perform long running tasks such as I/O in background threads.

If you need to test I/O access from the main UI thread, you'll need to change the Thread Policy as shown below. Only do this for testing. In your production App, make sure you perform I/O operation in a background thread.

StrictMode.ThreadPolicy policy = 
    new  StrictMode.ThreadPolicy.Builder().permitAll().build(); 
StrictMode.setThreadPolicy(policy);

Android Image Button Listener

/

This is part of the Android Quick Code Access series of posts. For more information on handling Buttons, see the Android Button class.

// Listener for Button.
ImageButton imageButton = (ImageButton) findViewById(R.id.myButton);
imageButton.setOnClickListener(new OnClickListener() {
			
    // Button onClick method.
    @Override
    public void onClick(View v) {
				
        // Take action here.
         . . .

    } 
});

Android Content Provider/SQLite Methods

/

There are a number of key methods for accessing data via an Android Content Provider or directly on the underlying SQLite database.  The table below summarizes the method parameters and return values. The graphic is from the video training course Learning Android App Programming.

B-tree and Binary Search Tree Data Structures

/

B-tree and Binary Search Tree data structures are similar but different ways to store data. The advantage of using search trees is that the test for membership can be performed efficiently provided that the tree is reasonably balanced, that is, the leaves of the tree are at comparable depths.

B-tree Implementations

B-tree implementations are normally commercial. Languages don't typically provide direct B-tree support. To find B-tree implementations, search Google for B-tree software.

Binary Search Tree Implementations

Some languages do provide support for Binary Search Trees. In Java, see the TreeMap class, which implements a variant of the Binary Search Tree, the Red-Black Tree.

Binary Tree Data Structure Comparison

Both structures operate in the average in O(log n) time. Note that in the worst case, B-tree, at O(log n), is faster than Binary Search Tree at O(n).

P Versus NP Complexity Theory

/

The P Versus NP issue deals with whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This is a major unsolved problem in computer science.

In common, practical terms, it deals with how to identify problems that are either extremely difficult or impossible to solve.  In order of difficulty from easy to hard, problems are classified as P, NP, NP-Complete and NP-Hard.

So why do we care? When approaching complex problems, it's useful to have at least some idea of whether the problem is precisely solvable, or if an approximation is the best that can be accomplished. 

Big O Notation

/

Big O notation is a way to characterize the time or resources needed to solve a computing problem.  It's particularly useful in comparing various computing algorithms under consideration. Below is a table summarizing Big O functions. The four most commonly referenced and important to remember are:

  • O(1)              Constant access time such as the use of a hash table.
  • O(log n)        Logarithmic access time such as a binary search of a sorted table.
  • O(n)              Linear access time such as the search of an unsorted list.
  • O(n log(n))   Multiple of log(n) access time such as using Quicksort or Mergesort.

Sorting Algorithms

/

Before delving into the large variety of sorting algorithms, it's important to understand that there are simple ways to perform sorts in most programming languages. For example, in Java, the Collections class contains a sort method that can be implemented as simply as:

Collections.sort(list);

where list is an object such as an ArrayList. Some aspects of the Java sort() method to note are:

  • You can also use the Java Comparator class methods to implement your own list item comparison functions for specialized sorting order needs.
  • The Java Collections class (plural) is different than the Collection class (singular).
  • Which sorting algorithm (see below) is used in the Collections.sort() implementation depends on the implementation approach chosen by the Java language developers. You can find implementation notes for Java Collections.sort() here. It currently uses a modified merge sort that performs in the range of Big O O(n log(n)).

If you don't want to use a built-in sort function and you're going to implement your own sort function, there's a large list of sorting algorithms to choose from.  Factors to consider in choosing a sort algorithm include:

  • Speed of the algorithm for the best, average and worst sort times. Most algorithms have sort times characterized by Big O functions of O(n), O(n log(n)) or O(n^2).
  • The relative importance of the best, average and worst sort times for the sort application.
  • Memory required to perform the sort.
  • Type of data to be sorted (e.g., numbers, strings, documents).
  • The size of the data set to be sorted.
  • The need for sort stability (preserving the original order of duplicate items).
  • Distribution and uniformity of values to be sorted.
  • Complexity of the sort algorithm.

For a comparison of sorting algorithms based on these and other values see: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Here's a quick reference for the major algorithms:

  • Exchange Sorts: based on swapping items
    • Bubble sort: for each pair of indices, swap the items if out of order, loop for items and list.
    • Cocktail sort: variation of bubble sort, passes alternately from top to bottom and bottom to top.
    • Comb sort: variation of bubble sort, selective swap of values
    • Gnome sort: also called the stupd sort, moves values back to just above a value less than it
    • Odd-even sort: developed originally for use with parallel processors, examines odd-even pairs and orders them, alternates pairs until list is ordered
    • Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Repeat. Often the method of choice. One of the fastest sort algorithms
  • Hybrid Sorts: mixture of sort techniques
    • Flashsort: Used on data sets with a known distribution, estimates used for where an element should be placed
    • Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
    • Timsort: adaptative algorithm derived from merge sort and insertion sort. 
  • Insertion sorts: builds the final sorted array one item at a time
    • Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
    • Library sort: like library shelves, space is created for new entries within groups such as first letters, space is removed at end of sort
    • Patience sorting: based on the solitaire card game, uses piles of "cards"
    • Shell sort: an attempt to improve insertion sort
    • Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
    • Cycle sort: in-place with theoretically optimal number of writes
  • Merge sorts: takes advantage of the ease of merging already sorted lists into a new sorted list
    • Merge sort: sort the first and second half of the list separately, then merge the sorted lists
    • Strand sort: repeatedly pulls sorted sublists out of the list to be sorted and merges them with the result array
  • Non-comparison sorts
    • Bead sort: can only be used on positive integers, performed using mechanics like beads on an abacus
    • Bucket sort: works by partitioning an array into a number of buckets, each bucket is then sorted individually using the best technique, the buckets are then merged
    • Burstsort: used for sorting strings, employs growable arrays
    • Counting sort: sorts a collection of objects according to keys that are small integers
    • Pigeonhole sort: suitable for sorting lists of elements where the number of elements and number of possible key values are approximately the same, uses auxiliary arrays for grouping values
    • Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
    • Radix sort: sorts strings letter by letter
  • Selection sorts: in place comparison sorts
    • Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
    • Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
    • Smoothsort
  • Other
  • Unknown class

 

Android Release and Device Support Summary

/

Below is a summary of Android releases and device support.  It shows that by using the  Android Support Libraries you can code your apps to run on a large percentage of Android devices.

For more information on the compatibility Support Libraries see: ​http://developer.android.com/tools/extras/support-library.html 

For more information on Device Support see: http://developer.android.com/about/dashboards/index.html

Android Concepts

/

Android WebView Combines Native and HTML5 Code

/

A battle is raging over whether native mobile code apps, such as those for Android and iOS, are a better approach than using HTML5.  Each has its advantages.​

There is, though, a way to blend the two in order to take advantages of the benefits each has to offer.  The graphic below shows the anatomy of an app that displays an HTML5 Canvas on an Android screen display.

This app is from the Learning Android App Programming video training course.​

The HTML5 Canvas animation displayed is from HTML5 Canvas for Dummies.​

You can see the HTML5 Canvas animation by clicking here. ​To see the JavaScript code that generates the animation, right click on the display page and select View Source Code.