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. 

View fullsize

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.

View fullsize

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
  • Bitonic sorter
  • Pancake sorting
  • Topological sort
• Unknown class
  • Samplesort

Android Concepts

For quick reference, here are links to some blog entries that provide graphics to help understand key Android concepts:​

• ​Activity Lifecycle
• AsyncTasks
• Bound Services
• Button Listener Code
• Client-Server Across the Internet
• Content Provider Classes and Objects
• Cursors
• Release and Device Support
• Service Methods
• SQL Database Join Operations
• WebView

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.

View fullsize

Android Bound Services Using Inter Process Communications

Android Service components can be implemented using a number of mechanisms.  If you want your Service to be able to communicate with other applications running in separate processes, using Inter Process Communications (IPC) is one approach.

The diagram below shows the major classes and methods needed in the binding activity and bound service.  The details of this implementation can be found on the Android Developers Web site here on the Bound Services page. 

In summary, the major classes involved are:

• Service - Application component for longer-running operations that do not interface directly with the user.
• ServiceConnection - Interface for monitoring a service.
• Messenger - Creates a Messenger pointing to a Handler in one process, and handing that Messenger to another process.
• Message - Description and arbitrary data object that can be sent to a Handler.
• IBinder - Interface for a remotable object.
• Handler - allows you to send and process Message and Runnable objects associated with a thread's MessageQueue.

View fullsize

Android/PHP/JQuery RESTful JSON MySQL Client-Server Overview

The title of this blog entry is quite a mouthful.  The purpose is to give a broad overview of the moving parts necessary to implement an application with client mobile and desktop devices that interact with a server database to alter and retrieve data.

I won't define all the classes, methods and acronyms on the graphic as they're easy to look up using an Internet search.  There are other choices that can be made for the details of the implementation, but this should provide a starting point for thinking through the necessary elements.

The communication vehicle for client-server interaction is typically the Internet Protocol Suite.

View fullsize

Android Broadcast Receivers

Broadcast Receivers are one of the four basic Android components, along with Activities, Services and Content Providers.  Broadcast Receivers respond to Intents issued by the Android system or Android apps.  It's one way to respond to "things happening" on the user device.

The video below from the training course Learning Android App Programming explains the basics of Broadcast Receivers.​

SQL Database Join Operations

It can be challenging to remember the details of all the SQL Join operations.  A convenient way to do this is to use Venn diagrams shown below. For examples of SQL Joins, go here. 

Commonly used SQL Join operations are:

• inner join: requires each record in the two joined tables to have matching records.
• outer join: does not require each record in the two joined tables to have a matching record.

View fullsize

Android Button Listener Code Dissected

Android listeners are the mechanism used to respond to user interaction with a display screen.  Setting up a listener is a very common Android coding task.​  Although it can be done with just a few lines of code, it involves a number of elements that must be configured to interact correctly.

​The diagram below from the video training course Learning Android App Programming dissects the code to establish a listener for a screen button.

View fullsize

Android Service Methods

Android Services can be configured to run in the same thread as the interface activity or a separate background thread.  The diagram below from the video training course Learning Android App Programming details the methods used to start, stop and send messages to a service.​

View fullsize

Android Cursor Interface

An Android Cursor provides read-write access to a data set from an SQL Database.  The Android Cursor interface is a bit of a naming paradigm misdirection.  We normally think of a cursor as an indicator on our computer screen as to where we can type.  And we usually think of the cursor as primarily moving horizontally. he Android Cursor is more complex than this and its cursor movement is primarily vertical, indicating rows in a matrix.  You can think of a Cursor as providing access to an array of data.

The chart below from the video training course Learning Android App Programming provides some convenient visual cues to help understand and remember Android Cursor functionality.

View fullsize

Android AsyncTask Method Flow

The Android AsyncTask class provides a convenient way to handle background threads. The chart below from the video training course Learning Android App Programming provides an overview of a typical AsyncTask method flow.

View fullsize

Android Content Provider Classes and Objects

Android Content Providers involve a lot of "moving parts." The chart below from the video training course Learning Android App Programming provides an overview of the classes, objects and methods involved.​

View fullsize

Android Activity Lifecycle Methods Typical Uses

Understanding the uses of the various Android Activity Lifecycle methods can be a bit tricky.  That is, knowing what do do when.  The chart below shows some typical uses for each of the callback methods.  The chart of from the video training course Learning Android App Programming.

A convenient way to remember the structure of the Activity callback methods is to think of when they're called relative to when the Activity is running:

• onCreate()   (the only Activity method that must be implemented)
• onStart()
• onRestart()
• onResume()
• --------------- Activity running
• onPause()
• onStop()
• onDestroy()

Actions taken in the callback methods often relate to the resources they're effecting. Resources that are typically more time consuming to establish, restore or eliminate are dealt with further from when the Activity is running. Conversely, resources that are less time consuming are dealt with closer to when the Activity is running. Here are some examples:

• --------------- Activity running
• Variables
• Preferences
• Animations
• Broadcast Receivers
• Server Connections
• Databases
• Background Threads
• --------------- Activity shut down

View fullsize

Android User Interaction Through Listeners and Toasts

​Every Android App interacts with its users.  There are lot's of ways to implement this interaction, but two basic capabilities are listeners and toasts.

Click here to see a video from Learning Android App Programming demonstrating a Listener and Toast to give you a basic understanding of these important and useful techniques.

Android Development Using API Demos

Google provides API Demos apps for various releases of the Android system.  These apps contain hundreds of demos of Android capabilities.  They demonstrate the use of tens of thousands of lines of code and can be a big help to developers as they create their own apps.

However, the API Demos apps are not well documented and it can be difficult to find the code within them for a given function.  In authoring a recently released video tutorial course for Android Developers, I addressed this issue by creating an Excel worksheet that gives developers a tool to better understand the structure of the API Demos and to search the demos based on keywords to find the code they need.

A video explaining the use of API Demos is below...

Describes how to use Android API Demos. From the course Learning Android App Programming published by InfiniteSkills. More information is available at http://donkcowan.com/android-development-course/

Bridge Design Pattern

This entry is part of a series on programming Design Patterns that provides a framework for the rapid recall and use of patterns during application design. 

The Bridge design pattern is used to define multiple processes that work on multiple object types with similar aspects.

To understand how this pattern might be used, consider how software to control a real bridge might be constructed. Such an application would have two processes: trafficControl() and gateControl() which would control two types of objects: cars and boats. 

      class Bridge - contains methods to control bridge activities.

          trafficControl(trafficType) - method that controls traffic signals.

            gateControl(trafficType) - method that controls the bridge gates.

      class Traffic - contains objects describing types of traffic.

            cars() - defines car objects

            boats() - defines boat objects

Adapter Design Pattern

This entry is part of a series on programming Design Patterns that provides a framework for the rapid recall and use of patterns during application design. 

The Adapter design pattern is used to wrap a class in code that allows that class to be used via a different interface. Another name for the pattern is a Wrapper.

To understand how this pattern might be used, consider how software to display an image on a fixed size device might be constructed. Assume the following class and method are provided by the standard device software:

class Display - contains methods to create displays on the device.

displayImage(source) - method that displays an image with the dimensions of the device screen.

An adapter would fit an image of any size to the device screen:

class DisplayAdapter - contains methods that fit an image of any size to the device screen.

imageAdapter(original) - method that changes the size of the original image to fit the display screen.

imageResample(original, resized) - method that resamples the image for size change.

displayImage(resized) - uses the method built into the device to display the resized image.

What is HTML5 Canvas?

The Canvas feature of HTML5 is one of the most exciting new developments in web based capabilities in many years. Here are some key aspects:

HTML5 - Canvas is a part of the latest revision and improvement of the previous version (HTML4, released in the late 1990's) markup language for displaying web pages on the Internet.

Canvas Tag - The <canvas> tag joins the other HTML tags (there are around 100 now) as a way to include single or multiple Canvas areas on a web  page. 

Bit Map Display - The Canvas area you define with a <canvas> tag is a bit map display. You can manipulate individual pixels to draw objects, images, animations and video.

JavaScript Control - The JavaScript language is used to control what is seen on the Canvas. The JavaScript application code is placed between the <head></head> and <script></script> tags of the web page.

Browser Based - The computing needed to create a Canvas display is done within the browser. In other words, it's client based, not server based. The means that creating a Canvas application is simpler than one requiring server based programming. It also means that the computing power needed to generate the Canvas display is not concentrated in single servers. Each user's browser handles its own work.

Animation - Canvas applications can generate animations. This is accomplished using callbacks from the browser. The Canvas application designates one of its functions to be called from the browser at specified time intervals. During each of these callbacks, the application draws a new Canvas display, moving objects slightly. When viewed as a continuous flow of Canvas displays, an animation is generated.

Audio/Video - Audio and video can be incorporated into your Canvas applications. Moving objects can create sounds and video images can be melded into other application objects. This is done without the use of any audio or video plugins.

Gaming - Game developers have all to tools necessary to create compelling HTML5 Canvas games.

Fun - Putting aside the technical aspects of Canvas ... it can be described as just plain fun. An HTML5 Canvas is a place where as a developer you can express your creative energies and as a user you can have expanded and enjoyable experiences.

For a more details look at HTML5 Canvas, watch for my upcoming book: HTML5 Canvas for Dummies.