Using Stochastic Processes to Help Humanize Artificial Intelligence

In developing examples for my book on HTML5 Canvas (HTML5 Canvas for Dummies) I experimented with using stochastic processes to improve the realism of an animated displays. Early versions of the displays appeared rigid and artificial. Adding stochastic (random) variations brought the displays closer to real life and made them much more fun to watch.

Stochastic processes are already important to AI. Stochastic Gradient Descent combined with Backpropagation is used to iteratively modify data values passed between neural network nodes in order to minimize the error between the output of the neural network and the correct/true result.

Recently, I've explored whether stochastic techniques can be used to help humanize AI. Humans are not robots. We don't mindlessly pursue objectives without variation from a given path. A more human-like AI would certainly make the man-machine interface more pleasant to deal with than a purely robotic one. There are certainly AI applications where we don't want these kind of random variations taking place ... in autonomous vehicles for example. 

You can experiment with one of my displays that employs stochastic processes ... click here to see it in action - once it's started, click control to see the variables you can modify using your keyboard.

Machine Learning Mathematics

Machine Learning Mathematics

Mathematics is the study of topics such as quantity, structure, space and change. Mathematics provides a means to represent the real world in the form of numbers, relationships and equations.

Machine learning employs a wide variety of mathematical concepts and functions in order to create processes that:

  • analyze vast amounts of data in workable timeframes
  • discover actions, relationships and forces occurring in nature 
  • model the real world
  • interact with the real world

In short, mathematics is the base methodology employed to create machine learning modelsthat are used to address challenging applications such as image recognition, face recognition, natural language processing and pattern recognition: 

Mathematics -> Models -> Applications

Read More

The Layers of Technology in Machine Learning and Artificial Intelligence

Machine Learning (ML) and Artificial Intelligence (AI) are changing the landscape of computing around the world, allowing us to do things with computers that were previously thought to be nearly impossible. ML/AI systems are now able to hear, speak, see, touch and interact with the environment and people around them.

In this article, I'll treat ML and AI together as a single topic. ML is the computer learning subset of AI, but for this discussion, they can be thought of as one.

A high level understanding of the layers of technology in ML/AI can help sort through the many options for developing and implementing an ML/AI system. ML/AI technology can be viewed as a three level hierarchy:

Mathematics > Models > Applications

Each of these layers provides an essential set of elements needed for a successful ML/AI system. Let's start with the mathematics base and build from there...

Mathematics

Mathematics, which dates back to 3000 BC and basic arithmetic, is a field of study that uses formulas (sequences of symbols) to represent ideas and the real world. Sounds a bit abstract, right? It is, but think about it ... ML/AI by its nature is doing just that inside a computing device - representing ideas and the real world. So mathematics is naturally and ideally suited to the pursuits of ML/AI.

ML/AI derives its tremendous power from the use of mathematics to, among other things, analyze probabilistic situations and outcomes. For example, an object recognition model might return the probability of .73 that a given photo contains the image of a cat. When we humans see a cat, we're usually pretty sure it's a cat. However, the combination of our senses and brains have done the complex mathematical-like analysis that produces that conclusion. Mathematics represents the calculations, estimations and processes needed to develop successful ML/AI models.

It's not necessary to understand all the math involved in an ML/AI system if you're using commercially supplied APIs or building on existing open source code. However, having some level of understanding of the underlying math can often be very useful and sometimes essential. One example, Stochastic Gradient Descent (SGD), is a mathematical function used to find a minima or maxima by iteration. It's used in a number of ML/AI models to iteratively improve the accuracy of output functions such as identifying objects in an input image. At a high level, the formula for SGD looks like this:

The components of this equation are:

  • Q( ): A function whose value is to be maximized or minimized
  • n: The number of times the function Q is recalculated
  • /: A division function used to find the average of the recalculated values of the Q function
  • i: A number indicating the individual version of the Q function 
  • w: A parameter that's used to find the minimal or maximal values for the function Q
  • summation: Adds up all the values of the individual Q function calculations and is represented by this symbol:
summation_symbol.png

Below is a list of some of typical mathematical concepts and functions used in ML/AI. Wikipedia is a good source of articles to start delving into these topics: 

Bayesian Probability and Statistics - Calculus - Classification - Cluster Analysis - Convolution - Deviation Analysis - Dimensional Analysis - Eigenvalues, Eigenvectors - Error Analysis, Accuracy, Precision, Sensitivity, Specificity - Functional Analysis, Activation Functions, Sigmoid Function, Rectified Linear Unit - Geometry, Geometric Transformations - Gradients, Stochastic Gradient Descent, Gradient Boosting - Graph Theory - Hyperparameter Optimization - Information Theory, Entropy, Cross Entropy - K-means Clustering - Linear Algebra - Logistic Regression - Loss/Cost Functions - Markov Chains - Mathematical Constants - Matrix Mathematics - Model Fitting, Underfitting, Overfitting, Regularization - Monte Carlo Algorithms - Pattern Recognition - Probability Theory - Regression Analysis, Linear, Non-Linear, Softmax - Sampling - Statistical Analysis, Bias, Correlation, Hypothesis Testing, Inference, Validation, Cross Validation - Time Series Analysis - Variation Analysis, Coefficient of Determination - Vector Spaces, Vector, Algebra, Scalars - Weights, Synaptic Weights

Models

Models are the embodiment in computer code of the mathematical representations used to perform ML/AI functions. In our example of a computer recognizing a cat in a photo, the ML/AI model represents the layers of processing needed to differentiate the image of a cat from all other possibilities.

Below is a conceptual model of an Artificial Neural Network (ANN), one of the types of ML/AI mathematical models. Data (shown as lines) is passed in a forward left to right direction between processing nodes (shown as circles). Numerical weights (w) are applied to individual data flows and biases (b) are applied to nodes in order to shape the output, such as the identification of a cat in an input image. Mathematical methods such as Stochastic Gradient Descent (discussed above) are used to adjust the weights and biases as data is repeatedly passed through the ANN.

In this diagram, the shapes and letters represent:

  • i: input layer node
  • h: hidden layer node
  • o: output layer node
  • w: weights applied to data going across layers
  • b: biases applied to node values

Below is a list of some of the mathematical models used in ML/AI. Wikipedia is a good source of basic information about these models:

Artificial Neural Networks - Association Rule Learning - Bayesian Networks - Decision Tree Learning - Deep Learning - Ensemble Learning - Hierarchical Clustering - Learning Classifier Systems - Learning to Rank - Long Short-Term Memory Neural Networks - Nearest Neighbors Algorithms - Recurrent Neural Networks - Reinforcement Learning - Sequence-to-Sequence Neural Networks - Similarity Learning - Sparse Dictionary Learning - Stochastic Neural Networks - Support Vector Machines - Unsupervised Learning

Applications

ML/AI applications use mathematical models, such as those discussed above, to perform meaningful tasks and produce meaningful results. Raw ML/AI results from mathematical models can be very interesting, but by themselves offer little utility. ML/AI applications provide that utility.

As an example, let's say we wanted to use our cat detecting Artificial Neural Network to let users of our smartphone app take a photo of a cat and determine what breed it belongs to. Our development team would need to:

  • Collect cat images from the internet
  • Sort the images into known breeds
  • Use the grouped images to train the ANN to recognize different breeds of cats
  • Test the trained ANN on images of cats of unknown breeds
  • Test the trained ANN on recognizing cats in images of many different types
  • Decide on the minimum acceptable probability from the ANN for determining a cat is really a member of the indicated breed
  • Maintain a table of the minimum acceptable probability for each breed of cat
  • Develop the user interface functions that allow the app user to photograph their cat and get the determination of which breed the application thinks it belongs to
  • Develop the server code to host the ANN and application software
  • Develop the Application Programming Interfaces (APIs) to connect client applications with the server code
  • Track ongoing performance results

ML/AI applications are appearing in every imaginable area of computing. If you do an internet search on almost any topic and include the term 'machine learning' you'll likely find results. Below are just a few examples of areas of active ML/AI applications:

Biometrics - DNA Classification - Computer Vision - Fraud Detection - Marketing - Medical Diagnosis - Economics - Natural Language Processing - Language Translation - Online Advertising - Search Engines - Handwriting Recognition - Speaker Recognition - Speech Recognition - Financial Market Analysis and Trading - Customer Service - Systems Monitoring - Recommender Systems - Self-driving Vehicles - Robotics - Cybersecurity - Legal Research - Criminal Investigations - Security Screening - Mapping - Healthcare - Face Detection and Recognition - Object Recognition - Weather Forecasting - Image Processing

Java vs. Python Programming Language Comparison

Java and Python are two popular programming languages that represent two very different approaches to structure and syntax. Java has a more formal, strict syntax. Python syntax is more forgiving and provides many shortcuts and abbreviations. Java is compiled and Python is interpreted.

The table below shows a sampling of Java and Python programming language elements that highlight these differences.

JavaPython
Block {
   . . .
}
def my_block( ):
      . . .
      CR
Class
Definition
public class Hello {
   . . .
}
class Hello:
      . . .
      CR
Class
Constructor
public Hello(Strng msg) {
    defaultMsg=msg;
}
def __init__(self, param1, param2, ...)
      self.p1=param1
      self.p2=param2
      CR
Class
Instantiation
Hello mHello=new Hello();
mHello=Hello( )
Class
Variable
static String myVariable; class MyClass:
      my_class_variable = 0
Comment // Comment text. # Comment text.
Constant final static MY_CONSTANT; MY_CONSTANT
Conditional if (a>b) {
   . . .
}  else {
   . . .
}
if (a>b):
      . . .
else:
      . . .
Exception
Handling
try { . . . }
catch { . . . }
try:
      . . .
except Error, e:
      . . .
Global
Variable
public class MyGlobals {
   public static String mG1
}
global my_global_variable
Importing import java.sql.*; import apackage as ap
from apackage import amodule
Inheritance class Child extends Parent{...} class Child(Parent):
Instance
Variable
// Declared outside methods
String mVariable;
class Hello:
      def __init__(self, param1)
            self.param1=param1
Iteration for (i=0; i<5; i++) {
    . . .
}

for (myElement : myCollection){
    . . .
}
for x in range(0, 5):
      . . .

for my_element in my_collection:
       . . .

for key, value in my_dictionary:
       . . .
Local
Variable
String myVariable; my_variable
Method
Definition
public void myIdea(String param) {
   . . .
}
def my_idea(my_parameter):
      . . .
      CR
Method
Use
myIdea(mParameter); my_idea(my_parameter)
Namespace
Reference
packageName;
my_namespace={'a':a_object, ...}
Null Value null
None
Statement
Separator
;
new line
Variable String mString="Hello Java";
my_string="Hello Python"

Software Components Overview

Below is a list of links to and brief descriptions of common software components. It's useful to keep these in mind and reference them during software design as a shorthand for code that will be written to implement the design. Implementing a component could involve just a few or many lines of code.

A suggested way to use these components in solving/coding a computing problem is to include them using a Separation of Concerns design pattern folded into what I call Layered Logic Problem Solving that includes these steps:

  1. Describe in words the problem to be solved. This might include references to software components listed below. You might also include solution acceptance criteria, possibly in the form of formal acceptance tests.
  2. Draw a block diagram of the main problem solution pieces. For more complex problems, other types of diagrams can be used.
  3. Annotate the block diagram with references to components such as those below.
  4. Code the solution in your chosen programming language.

Communications

  • Client-Server Architecture: components include:
  • HTTP Requestindicates the desired action to be performed on an identified resource - actions include: 
    • GET: retrieve data
    • HEAD: retrieve without response body
    • POST: create new subordinate data
    • OPTIONS: retrieve supported actions
    • PUT: create/replace data
    • DELETE: delete the resource
    • CONNECT: convert connection to TCP/IP tunnel, usually to facilitate HTTPS SSL
  • Internet Protocol Suite:
    • Layers: Application/Transport/Internet/Link
    • Levels: Send/Receive, Controls/Routing, Values/Translations
  • Firewall: monitor/control of incoming/outgoing traffic
  • JSON: JavaScript Object Notation, Human Readable, Attribute-Value Pairs, Java JsonObject
  • Load Balancer: distributes workload across computing resources
  • Message: data sent across processes
  • Network: allows computers to exchange data
  • Protocol: Data Formats, Address Formats, Address Mapping, Routing, Error Detection, Acknowledgements, Sequence Control, Flow Control
  • REST: Representational State Transfer, Stateless, Client-Server, JSON data
  • Socket: endpoint of a connection across a computer network

Data

Algorithms & Processes

Objects

  • Class: object template
  • Container: collection of other objects
  • Design Patterns: reusable solutions to common software problems  
  • Object Oriented Design Patternsreusable solutions to common object oriented software problems
  • Generics: specify type or method to operate on objects
  • Cloud Computing: internet based computing that provides shared processing resources
  • Interface : all abstract methods
  • Mutability: mutable, immutable, strong vs. weak
  • Objects: variables, data structure or function referenced by an identifier
  • OOD: uses inheritance, abstraction, polymorphism, encapsulation, other design patterns

Views

  • Ajax: groups of technologies for client-side asynchronous web applications
  • Android Fragments: UI segmenting, own lifecycle, FragmentManager
  • HTML5 Canvas:  bitmap, javascript
  • CSS:  describes the presentation of information
  • HTML:  head, body, div, script
  • Widget: simple, easy to use applicator
  • XML: markup language that defines a set of rules for encoding documents

Java Data Structures

There are a number of commonly used Java data structures. Here are links to additional documentation and highlights of structural aspects: 

  • Array: fixed size, best for primitives 
  • List: fixed size, interface, ordered, allows duplicate
  • ArrayList: resizable , add to top, preferred unless need the capabilities of another structure
  • Vector: resizable, synchronized, add to top
  • Stack: LIFO, push/pop
  • Queue: FIFO, add to bottom/remove from top, interface
  • LinkedList: doubly-linked, push/pop, many other methods
  • Set: no duplicates, interface
  • HashMap: random access
  • TreeMap: sorted, efficient search
  • Binary Tree: each node has <=2 children
  • Binary Search Tree: sorted, fast lookup/add/remove
  • k-d Tree: k dimensional, space-partitioning, nearest neighbor search
  • Red-Black Tree: self-balancing, binary search tree, extra bit per node
  • Iterator: move forward and backward through data
  • Collections: perform operations on collections of data
  • Working with Java Lists: methods, iterators, collections
  • Data Structure Decisions: change, access, indexing, sizing
  • Common Java Array Manipulation Constructs: split, sort, binary search, iteration
  • Common Java ArrayList Manipulation Constructs: add, indexOf, remove, sort, binary search, interator
  • B-tree and Binary Search Tree Data Structures: like TreeMap
  • Sorting Algorithms: Collections sort, exchange, hybrid, insertion, merge
  • Big O Notation: O(1), O(log (n)), O(n), O(n log(n))
  • Update and Access Overview: The diagram below indicates how elements and values are updated and accessed. This is a broad overview of commonly used data structure classes, interfaces and objects ... please see the links above and below for more details. Some general observations are:
    • Arrays are different than the other structures in that they are accessed using bracketed index [n] references, such as myStringArray[3] instead of methods and can only contain primitives, not objects.
    • ArrayLists are generally preferred over Lists as they allow resizing. It's a very commonly used structure.
    • Vectors are much like ArrayLists with the additional characteristic that they are synchronized.
    • Queues and Stacks are specialized for LIFO and FIFO access.
    • LinkedLists are powerful structures that require more space for storage and time to execute some operations but are efficient for inserting and deleting objects in the existing order.
    • Sets are simple structures that don't allow duplicates.
    • HashMaps are commonly used when rapid, direct access to elements is the primary requirement.
    • TreeMaps are preferred when rapid search is the primary requirement.
    • Iterators and Collections operate on whole data structures.
    • ( ) empty parameter methods generally operate on the ends of a structure.
    • (element | object) only parameter methods generally operate on sets or the ends of structures.
    • (index | key) and (index | key, element | object) parameter methods generally operate on specific places within a structure.

Working with Java Lists

As shown in the diagram below, there are three major Java class groups used for working with lists: Lists (such as List, ArrayList, LinkedList, AbstractList, Stack and Vector), Iterators (Iterator and ListIterator) and Collections. Together, these classes and their methods provide a wide spectrum options for list construction, examination and manipulation. For an example of using these classes, look here.

Common Java ArrayList Manipulation Constructs

ArrayList data structures (also called Dynamic Arrays) are a frequently used programming function. ArrayLists have an advantage over arrays - ArrayLists are not fixed in size and can be dynamically changed by adding and deleting elements. Below are some common Java array manipulation constructs. For an overview of working with Java lists, look here.

Creating a new ArrayList

Creating a new ArrayList is coded as shown below using the String type with an initial capacity of 20 entries:

ArrayList mArrayList = new ArrayList<String>(int 20);

Constructing an ArrayList from an Existing List

The example below shows how to construct an ArrayList from the individual words in a String using an intermediary List object. Notice that the sequence of objects created is: String -> String array -> List -> ArrayList

String wordString = "this is a string of words";
String[] wordsArray = wordString.split(" ");
List<String> wordsList = Arrays.asList(wordsArray);
ArrayList wordsArrayList = new ArrayList<String>(wordsList);

add( )

The example below shows how to use the ArrayList add() method to add a String to wordsArrayList::

wordsArrayList.add("Example2");

indexOf( )

The example below shows how to use the indexOf() ArrayList method find the index of an entry:

int index = wordsArrayList.indexOf("Example2");

remove( )

The example below shows how to use the ArrayList remove() method using the entry index or the entry itself:

wordsArrayList.remove(index);
wordsArrayList.remove("Example2");

sort( )

The Collections sort() methods provide a variety of options for sorting ArrayList entries. Note that the ArrayList is sorted in place without returning a new ArrayList. This can be done because the array parameter is a value pointing to the ArrayList of objects. For example, the following statement would sort the words ArrayList from the example above using a modified MergeSort algorithm in an average O(n log(n)) time performance:

Collections.sort(wordsArrayList);

binarySearch( )

The Collections binarySearch() methods provide an efficient way to find an entry in a sorted ArrayList. For example, the following statement would find the index of the wordsArrayList entry for the String Example1 in an average of O(log(n)) time performance:

int entryIndex = Collections.binarySearch(wordsArrayList, "Example1");

iterator( )

The Iterator Class and ArrayList interator() method can be used to iterate over the entries of an ArrayList as shown in the example below :

Iterator mIterator = wordsArrayList.iterator();
while(mIterator.hasNext()){
System.out.println(mIterator.next());
};

Common Java Array Manipulation Constructs

Working with array data structures is one of the most frequently used programming functions. Arrays are implemented in a number of Java classes, such as String, Integer, and Boolean. Those arrays can be manipulated using the Java Arrays class (note that the Arrays class name is a plural). Below are some common Java array manipulation constructs.

split( )

The String split() method separates string characters into array entries using a supplied regular expression. For example, the following statement would create entries in the String array wordsArray using a blank character as a regular expression separator for processing the String wordString:

String wordString = "this is a string of words";
String[] wordsArray = wordString.split(" ");

sort( )

The Arrays sort() methods provide a variety of options for sorting array entries. Note that the array is sorted in place without returning a new array. This can be done because the array parameter is a value pointing to the array of objects. For example, the following statement would sort the words array from the split() example above using a Quicksort process in an average O(n log(n)) time performance:

Arrays.sort(wordsArray);

binarySearch( )

The Arrays binarySearch() methods provide an efficient way to find an entry in a sorted array. For example, the following statement would find the index of the array wordsArray entry for the String entryValue in an average of O(log(n)) time performance:

int entryIndex = Arrays.binarySearch(wordsArray, entryValue);

for( )

The for() construct can be used to iterate over the entries in an array. For example, the following statement would iterate over and print every entry in wordsArray:

for (String word : wordsArray) {System.out.print(word);}

If you want to know and use the index of each entry, then this construct can be used:

for (int i=0; i<wordsArray.length; i++) {System.out.print(wordsArray(i);}

Android Data View Adapters Overview

Android APIs provide classes and methods to facilitate displaying data in various forms, such as lists, arrays and custom layouts. The graphic below shows how the various classes and methods interact to produce the desired result.

Some examples of coding and use are:

Data

The data to be displayed can be in such forms as an Array, List, File or SQLite database. If a database is used, a Cursor object is also employed. A simple array of String values might be created and converted to an ArrayList like this:

String[] mStringArray = new String[] { "blue", "green", "yellow",
        "red", "orange", "black", "white", "purple"};
List<String> mList = Arrays.asList(mStringArray);
ArrayList<String> mArrayList = new ArrayList<String>(mList);

Cursor

Cursor is an interface that provides random read-write access to the result set returned by a database query. Setting up a Cursor for an SQLite database might look like this:

MySQLiteOpenHelper mDatabaseHelper = new MySQLiteOpenHelper(this);
Cursor mCursor = mDatabaseHelper.getDataIntoCursor();
ListView mListView = (ListView) findViewById(R.id.mListView);
MyCursorAdapter mCursorAdapter = new MyCursorAdapter(this, mCursor);
mListView.setAdapter(mCursorAdapter);

class MyCursorAdapter extends CursorAdapter {

    public MyCursorAdapter(Context context, Cursor c) {
        super(context, c);
    }
    // Implement CursorAdapter bindView method.
    public void bindView(View view, Context context, Cursor cursor) {
        String name = cursor.getString(1);
        TextView textView = (TextView) view;
        textView.setText(name);
    }
    // Implement CursorAdapter newView method.
    public View newView(Context context, 
                         Cursor cursor, ViewGroup parent) {
        TextView view = new TextView(context);
        return view;
    }
}
private final class MySQLiteOpenHelper extends SQLiteOpenHelper {

    private static final String DATABASE_NAME = "myDatabase";
    private static final int DATABASE_VERSION = 1;
    private static final String CREATE_TABLE_TIMELINE = 
        "CREATE TABLE IF NOT EXISTS table_name 
        (_id INTEGER PRIMARY KEY AUTOINCREMENT, name varchar);";

    public DatabaseHelper(Context context) {
        super(context, DATABASE_NAME, null, DATABASE_VERSION);
    }
    @Override
    public void onCreate(SQLiteDatabase db) {
        db.execSQL(CREATE_TABLE_TIMELINE);
        db.execSQL("INSERT INTO ddd (name) VALUES ('Name1')");
        db.execSQL("INSERT INTO ddd (name) VALUES ('Name2')");
        db.execSQL("INSERT INTO ddd (name) VALUES ('Name3')");
    }
    @Override
    public void onUpgrade(SQLiteDatabase db, 
                          int oldVersion, int newVersion) {
    }
    public Cursor getDataIntoCursor() {
        String selectQuery = "SELECT  * FROM table_name;
        SQLiteDatabase db = this.getReadableDatabase();
        Cursor cursor = db.rawQuery(selectQuery, null);
        return cursor;
    }
}

Adapters

An Adapter acts as a bridge between an AdapterView and the underlying data for that view. A custom array adapter defined in Java might look like this:

class MyArrayAdapter extends ArrayAdapter<String> {
    HashMap<String, Integer> mHashMap = new HashMap<String, Integer>();
    public MyArrayAdapter(Context context, int textViewResourceId,
        List<String> objects) {
      super(context, textViewResourceId, objects);
      for (int i = 0; i < objects.size(); ++i) {
        mHashMap.put(objects.get(i), i);
      }
    }
    @Override
    public long getItemId(int position) {
      String item = getItem(position);
      return mHashMap.get(item);
    }
    @Override
    public boolean hasStableIds() {
      return true;
    }
 }

The custom array adapter mArrayAdapter would be instantiated and linked to a ListView mListView with Java code like this:

setContentView(R.layout.mLayout);
final ListView mListView = (ListView) findViewById(R.id.listview);
final MyArrayAdapter mArrayAdapter = new MyArrayAdapter(this,
        android.R.layout.simple_list_item_1, mArrayList);
    mListView.setAdapter(mArrayAdapter);

AdapterView

An AdapterView is a view whose children are determined by an Adapter. You might use an AdapterView like this:

private OnItemClickListener mMessageClickedHandler = 
  new OnItemClickListener() {
    public void onItemClick(AdapterView parent, 
                            View v, int position, long id) {
        // Do something in response to the click
    }
};
listView.setOnItemClickListener(mMessageClickedHandler);

View

View is the basic building block for user interface components. A view occupies a rectangular area on the screen and is responsible for drawing and event handling. A ListView contained in a layout might look like this:

<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/mLayout"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical" >
    <ListView
        android:id="@+id/mListView"
        android:layout_width="match_parent"
        android:layout_height="wrap_content" >
    </ListView>
</LinearLayout>

ViewGroup

ViewGroup is a special view that can contain other views called children. A ViewGroup defined in XML might look like this:

<ViewGroup xmlns:android="http://schemas.android.com/apk/res/android"
    android:id="@id/mViewGroup"
    android:layout_height="wrap_content"
    android:layout_width="fill_parent" >
    <TextView
        android:id="@id/mTextView"
        android:layout_height="wrap_content"
        android:layout_width="fill_parent"
    </TextView>
</ViewGroup>

Layout

A layout defines the visual structure for a user interface. A layout might look like this:

<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/mLayout"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical" >
    <ListView
        android:id="@+id/mListView"
        android:layout_width="match_parent"
        android:layout_height="wrap_content" >
    </ListView>
</LinearLayout>

Activity

An Activity provides a screen with which users can interact.

public class MyActivity extends Activity {
  @Override
  protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    . . .
  }
}

Fragment

A Fragment represents a behavior or a portion of user interface an an Activity. Fragment code might look like this:

public class ArticleFragment extends Fragment {
    @Override
    public View onCreateView(LayoutInflater inflater, 
                             ViewGroup container,
        Bundle savedInstanceState) {
        // Inflate the layout for this fragment
        return inflater.inflate(R.layout.article_view, 
                                container, false);
    }
}

Programming Language Constructs

There are hundreds of programming languages. Although most aren't commonly used, a software developer might use a number of them during their career. It's useful to understand the concepts that underlie these languages. Click here for a comparison of programming languages

Below are brief descriptions of some common and important programming constructs with links to more details.

Abstraction

Separating ideas from specific instances of those ideas. Click here for more details.

Access Modifier

Define characteristics of constructs such as classes and methods. Examples of modifiers are: public, private, package and protected:  Click here for more details.

Array

A data structure consisting of a collection of elements, each identified by at least one array index or key. Click here for more details.

Attribute

Defines a property of an object, element, or file. Click here for more details.

Block

Section of code grouped together. Click here for more information.

Branch

Sequence of statements triggered by a conditional. Click here for more information.

Callback

Pointer to a piece of executable code that is passed as an argument to other code, which is expected to call back (execute) the argument at some appropriate time. Click here for more details.

Class

Code template for creating objects. Think of architect's drawings. Click here for more details.

Conditional

Performs different actions depending on whether a condition is true or false. Click here for more details.

Constructor

In Object Oriented Programming, a block of code that's executed when an object is created. Click here for more details.

Container / Collection

An object made up of other objects. Click here for more details.

DOM (Document Object Module)

Convention for representation and interaction between objects in HTML documents. Click here for more details.

Dynamic Array

Variable sized data structure that allows adding and deleting elements. In Java, an ArrayList is one type of Dynamic Array. Click here for more information.

Encapsulation

Packing of data and functions into a single component. Click here for more details

Exception

Anomalous or failure event that may require special handling. Click here for more details

Expression

Combination of elements that produces a result. Click here for more details.

Garbage Collection

Reclaiming of unused memory. In some operating systems, such as Android, Garbage Collection is automatic. Click here for more details.

Hash

Used to provide direct access to data based on a calculated key. Click here for more details.

HTML (HyperText Markup Language)

A set of elements that can read by web browsers for displaying web pages. Click here for more details.

HTML Element

Individual component of an HTML document. Click here for more details.

HTTP Request

Indicates the desired action to be performed on an identified resource. Actions include: GET, POST, HEAD, OPTIONS, PUT, DELETE, TRACE, PATCH and CONNECT. Click here for more details.

Identifier

Names for objects and entities. Click here for more details.

Inheritance

Obtaining the capabilities on an object. Click here for more details.

Inner Class

A Class that is declared entirely within the body of another class or interface. An inner class cannot be instantiated without being bound to a top-level class. Click here for more details.

Instance

Specific realization of an object. Think of a house vs. the plans for a house. Click here for more details.

Iterator

An object that enables traversing a container, such as lists. Click here for more details.

JSON (JavaScript Object Notation)

Human-readable text used to transmit data objects consisting of attribute–value pairs. Often used to transmit data between a server and web application. Click here for more details.

Keyword

Word with a special meaning. Click here for more details.

List

A sequence of values, where the same value may occur more than once. Click here for more details.

Linked List

A data structure consisting of a group of nodes which together represent a sequence. Click here for more details.

Literal

Notation representing a fixed value. Click here for more details.

Loop

A sequence of statements which is specified once but can be carried out multiple times in succession. Click here for more details.

Metaclass

A class whose instances are classes. Click here for more details.

Method

Code that defines the run time behavior of objects. Click here for more details.

Mixin

A class which contains a combination of methods from other classes without using inheritance. Click here for more details. Not available in pure Java.

Object

In Object Oriented Programming, an object is an instance of a class. Click here for more details.

Operator

Perform actions on elements such as variables. Click here for more details.

Overloading

Ability to create multiple methods of the same name with different implementations. Click here for more details.

Overriding

In object oriented programming, is a language feature that allows a subclass or child class to provide a specific implementation of a method that is already provided by one of its superclasses or parent classes. Click here for more details.

Package

A Java package is a mechanism for organizing Java classes into namespace groups. Click here for more information.

Parameter

A reference or value passed to a function, procedure, subroutine, command, or program. Click here for more details.

Polymorphism

Provision of a single interface to entities of different types. Click here for more details.

Primitive

Smallest 'unit of processing' available to a programmer of a particular machine, or can be an atomic element of an expression in a language. Click here for more details. For example, in Java, primitive data types are: byte, short, int, long, float, double, boolean and char.

Reflection

Ability to modify an object's own properties at runtime. Click here for more details.

Regular Expression

Sequence of characters that can be used as a search pattern. Sometimes referred to as Regex or Regexen. Click here for more details.

Reserved Word

A word that cannot be used as an identifier, such as the name of a variable or function. Click here for more details.

Return

A value that is passed from a calculating function to an invoking function. Click here for more details.

Sort

Functions that put elements in a certain order. Sorting is used so often that many programming languages have built-in sort functions. Click here for more information.

Statement

Expresses some action to be carried out. Click here for more details.

Switch

Control mechanism used to allow the value of a variable or expression to change the control flow of program execution. Click here for more details.

Table

A collection of related data held in a structured format within a database. It consists of fields (columns), and rows. Click here for more details.

This

Refers to the object, class, or other entity that the currently running code is part of. Click here for more details.

Token

An object which represents the right to perform an operation. Click here for more details.

Type

Collection of rules for constructs such as variables and functions. Untyped languages allow any operation to be performed on any data type.  Click here for more details.

Variable

A storage location and associated name which contains a modifiable value. Click here for more details.

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.

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 sortstakes 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