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

HTML5 vs. Native App Development

As you're likely aware, there's a big debate going on about whether HTML5 web sites are a better platform for mobile apps than native code development using Android, iOS and Windows.

The main selling point for HTML5 is the write-once-run-anywhere advantage. Web browsers on mobile devices can access web sites from any mobile platform. HTML5 is providing features that allow web page JavaScript code to access phone features like devices sensors and geo positioning. In theory, a well constructed HTML5 web page will look and perform like a mobile device native code app.

However, currently not all device features are available to HTML5 JavaScript code and native code apps have a performance advantage over HTML5 web pages viewed using a browser. Native code apps are presently the dominant choice among developers.

In HTML5's corner, though, the technology is improving and web browsers are ramping up their implementation of HTML5 features. Life would certainly be simpler for mobile developers if they could develop for only one platform, HTML5, instead of multiple native platforms.

Longer term, HTML5 will certainly continue to get better. But so will native platforms. In fact, native platforms may improve more rapidly than HTML5. HTML5 is a global standard developed by the W3C. It takes years of effort to change the standard and have these changes adopted by the various browsers. The individual native platforms (Android, iOS, Windows) can change as quickly as their developers (Google, Apple and Microsoft) want them to. So will HTML5 ever catch up?

Maybe not. Google, Apple and Microsoft have lots of developers and big budgets. They want their products to be competitive ... and that means constant improvements.

So, what's likely to happen? In my opinion, we'll have a blend of the two. In fact, this is taking place today. Native code platforms have Application Programming Interfaces (APIs) that support displaying web pages from within native code apps. Developers can use native code for what it does best and HTML5 web pages for what they do best. The exact mix will shift over time as all the platforms change and improve. 

For developers, this means that separate native code platforms will likely continue to exist. Write-once-run-anywhere will remain an elusive goal probably not realized for a long time, if ever. This doesn't mean that development costs can't be managed or reduced. HTML5 web pages can be developed and used by native code apps where appropriate. Functions specific to those pages can be write-once-run-anywhere. This may not be an optimal solution, but it's the game on the ground.

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.

Integrating Audio with HTML5 Canvas

One of the useful features of HTML5 Canvas is the ability to integrate audio, either with or without an audio player. Click here or on the image to see if it works on your browser ... click on my dog Daisy and/or the pelican to test simultaneous sounds.

When the new browser window opens, you can view the page source to see the code that generates the Canvas display.

This is one of the sample applications from HTML5 Canvas for Dummies.