CIS Planet

In this post, I’m going to briefly explain three very basic sorting algorithms: Bubble sort, Selection sort & Insertion sort.

Bubble Sort:

Assume that we have an array of integers that we want to sort:  4,5,1,2,7,8

What would be the most basic thought that would cross your mind? Well, simply to take each pair & see if they are in a wrong order & then re-arrange them.

Why “bubble”?

As we said we exchange each two numbers if they have an incorrect order, so whoever invented this algorithm saw this exchange as some water bubbles that float to change their position!

Let’s do it:

4,5,1,2,7,8–> correct order no change

4,5,1,2,7,8 –> 4,1,5,2,7,8

4,1,5,2,7,8 –>4,1,2,5,7,8

4,1,5,2,7,8–> correct order no change

4,1,5,2,7,8 –> correct order no change

It’s clear that we’re not done though we’ve iterated on the whole set. So we need to loop again & not just once but till n-1 .. which is the count of the number -1.

Again:

4,1,5,2,7,8 –> 1,4,5,2,7,8

1,4,5,2,7,8 –> correct order no change

1,4,5,2,7,8 –> 1,4,2,5,7,8

1,4,2,5,7,8 –> correct order no change

1,4,2,5,7,8 –> correct order no change

Third iteration:

1,4,2,5,7,8 –> correct order no change

1,4,2,5,7,8 –> 1,2,4,5,7,8

and we’re done! .. yet there’s one problem .. Bubble sort never knows when it’s done .. so it will just continue iterating until n-1 with each time comparing adjacent numbers. This lead to the introduction of the Modified Bubble Sort algorithm which checks every time if the position of any number has changed, if not it quits.

The complexity of this algorithm is O(n^2). For those who don’t know this means that it needs 2 for loops each of a stopping condition (< length of numbers) to finish sorting at the worst case. Try sorting the numbers when they’re totally reversed 8,7,5,4,2,1 & count the number of steps.

Code (unmodified):

Selection Sort:

This algorithm simply selects the smallest number in the unsorted array & place it in the first place (index =0), then selects the second smallest number & place it in the second  place (index =1) .. etc. I guess you concluded why it’s called selection!

Example:

Let’s stick with the same set of numbers:

We have two cursors, the first one is set to the index of the first element (index = 0, we initially assume that it’s the min value) & the second one selects the min value & swaps them

4,1,5,2,7,8 –> 1,4,5,2,7,8

then the first cursor moves to index =1 and assumes that its the min then does the same with the remaining numbers from (4,5,2,7,8)..

<1,4,5,2,7,8 –> 1,2,5,4,7,8

1,2,5,4,7,8 –> 1,2,4,5,7,8 .. Done!

but it will just continue as the bubble sort ..

Code:

Insertion Sort:

This is the most realistic search you would ever meet. It just analogues the way you might sort some cards. Assume that we have 4 cards that are randomly sorted: 7,3,5,9 & that we have a table that we would like to put them sorted on (left to right).

Trace:

You hold the first card: 7 .. well it’s the smallest so far .. so we’ll put it on the left side. The second card is 3 .. OK smaller than 7 .. move 7 to the right and put 3 in the left most place.

Numbers so far: 3,7,5,9

Next, 5 .. smaller than 7, move 7 to the right & put 5 in it’s place .. continue with 3 .. 3 is smaller than 5 .. so we’re no more exchanging [3,5,7,9]. Same will happen with 9 but no change would happen .. although it will check anyway.

Implementation:

Now we need to loops .. one to that moves element by element in the array, and the other to compare the element chosen by the first loop to the element next to it. if the element selected by the first loop is smaller than the element selected by the second loop .. we shift the elements to the right to make room for the element selected from the second loop.

Code:

*This post is inspired by: Data Structure & Algorithms using C#, Michael McMillan

We will talk about one way of managing data in Android Applications (http://d.android.com/guide/topics/data/data-storage.html).

(Note : This tutorial isnt for learning learn SQLite Syntax.)

First, We will create a helper class to manage creation of our DataBase and manage it’s Operations,

where it will be accessible only through our application Only. we will define our class that will extends SQLiteOpenHelper (http://developer.android.com/reference/android/database/sqlite/SQLiteOpenHelper.html).

import java.util.ArrayList; //used to store our data later.

import android.content.ContentValues;

import android.content.Context;

import android.database.Cursor;

import android.database.SQLException;

import android.database.sqlite.*;

import android.util.Log;

public class MyDBOpenHelper extends SQLiteOpenHelper{

private static final int DATABASE_VERSION = 2;

private static final String Order_TABLE_NAME = “Orders_Table”;

private static final String KEY_NAME = “order_name”;

private static final String KEY_STATUS = “status_name”;

private static final String Order_TABLE_CREATE =

“CREATE TABLE “ + Order_TABLE_NAME + ” (“ +

KEY_NAME + ” TEXT, “ +

KEY_STATUS + ” TEXT);”; //Query string to create our table.

public MyDBOpenHelper(Context context) {

super(context, Order_TABLE_NAME, null, DATABASE_VERSION);

}

@Override

public void onCreate(SQLiteDatabase db) {

db.execSQL(Order_TABLE_CREATE);

}

@Override

public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {

// TODO Auto-generated method stub

}

Next step we will start querying data, our resulted data will be returned in ArrayList<Order> type

(where Order is an already defined class in our application).

You can then get an instance of your SQLiteOpenHelper implementation using the constructor you’ve defined. To write to and read from the database, call getWritableDatabase() and getReadableDatabase(), respectively. These both return a SQLiteDatabase object that represents the database and provides methods for SQLite operations.

public static class OrderManager

{

private MyDBOpenHelper _db_Orders;

private static final String GET_Orders = “SELECT * FROM “+Order_TABLE_NAME ;

public OrderManager(Context context)

{

_db_Orders = new MyDBOpenHelper(context);

}

public boolean insert(String orderName, String orderStatus)

{

try

{

SQLiteDatabase sqlite = _db_Orders.getWritableDatabase();

/*

sqlite.execSQL(“INSERT INTO “+ Order_TABLE_NAME +

” (” + KEY_NAME +”, “+ KEY_STATUS + “)” +

” VALUES (‘” + orderName + “‘, ‘” + orderStatus + “‘)”);

*/

ContentValues initialValues = new ContentValues();

initialValues.put(KEY_NAME, orderName);

initialValues.put(KEY_STATUS, orderStatus);

sqlite.insert(Order_TABLE_NAME, null, initialValues);

}

catch(SQLException sqlerror)

{

Log.v(“Insert ERROR”, sqlerror.getMessage());

return false;

}

return true;

}

public ArrayList<Order> getOrders()

{

ArrayList<Order> orders = new ArrayList<Order>();

SQLiteDatabase sqliteDB = _db_Orders.getReadableDatabase();

Cursor crsr = sqliteDB.rawQuery(GET_Orders, null);

Log.v(“Select Query result”, String.valueOf(crsr.getCount()) );

crsr.moveToFirst();

for(int i=0; i < crsr.getCount(); i++)

{

orders.add(new Order(crsr.getString(0), crsr.getString(1)));

//Log.v(“DATA”, crsr.getString(0) + ” ” +crsr.getString(1));

crsr.moveToNext();

}

return orders;

}

}

References :

similar code source :

http://developer.android.com/guide/topics/data/data-storage.html#db

http://hackaday.com/2010/07/21/android-development-101-part-3introduction-to-databases/

getWritableDataBase():

http://developer.android.com/reference/android/database/sqlite/SQLiteOpenHelper.html#getWritableDatabase%28%29

getReadableDataBase():

http://developer.android.com/reference/android/database/sqlite/SQLiteOpenHelper.html#getReadableDatabase%28%29

rawquery:

http://developer.android.com/reference/android/database/sqlite/SQLiteDatabase.html#rawQuery%28java.lang.String,%20java.lang.String[]%29

Cursor:

http://developer.android.com/reference/android/database/Cursor.html

Introduction

Since I’m personally in hunger for big pictures for everything around me, and since natural language processing (NLP) is highly important for computers to control human kind, and since many of the AI-related careers depend on it, and since it is used extensively for commercial uses, For all those reasons, I will give a big picture about it (Yes, I mean NLP).

What’s Natural Language Processing?

The simple definition is obvious : making computers understand or generate a human text in a certain language, however, the complete definition is : a set of computational techniques for analyzing and representing naturally occurring texts (at one or more levels) for the purpose of achieving human-like language processing for a range of applications.

NLP can be done for any language of any mode or genre, for oral or written texts. It works over multiple types or levels of language processing starting from the level of understanding a word to the level of understanding the big picture of a complete book.

A brain with language samples. (Image courtesy of MIT OCW.)

Related Sciences?

Linguistics: focuses on formal, structural models of language and the discovery of language universals – in fact the field of NLP was originally referred to as Computational Linguistics.

Computer Science: is concerned with developing internal representations of data and efficient processing of these structures.

Cognitive Psychology: looks at language usage as a window into human cognitive processes, and has the goal of modeling the use of language in a psychologically plausible way.

Language Processing VS Language Generation

NLP may focus on language processing or generation. The first of these refers to the analysis of language for the purpose of producing a meaningful representation, while the latter refers to the production of language from a representation. The task of language processing is equivalent to the role of reader/listener, while the task of language generation is that of the writer/speaker. While much of the theory and technology are shared by these two divisions, Natural Language Generation also requires a planning capability. That is, the generation system requires a plan or model of the goal of the interaction in order to decide what the system should generate at each point in an interaction.

What are its sub-problems?

NLP’s performed by solving a number of sub-problems, where each sub-problem constitute a level (mentioned earlier). Note that, a portion of those levels could be applied, not necessarily all of them. For example some applications require the first 3 levels only. Also, the levels could be applied in a different order independent of their granularity.

Level 1 – Phonology : This level is applied only if the text origin is a speech. It deals with the interpretation of speech sounds within and across words. Speech sound might give a big hint about the meaning of a word or a sentence.

Level 2 -  Morphology : Deals with understanding distinct words according to their morphemes ( the smallest units of meanings) . For example, the word preregistration can be morphologically analyzed into three separate morphemes: the prefix “pre”, the root “registra”, and the suffix “tion”.

Level 3 – Lexical : Deals with understanding everything about distinct words according to their position in the speech, their meanings and their relation to other words.

Level 4 – Syntactic : Deals with analyzing the words of a sentence so as to uncover the grammatical structure of the sentence.

Level 5- Semantic : Determines the possible meanings of a sentence by focusing on the interactions among word-level meanings in the sentence. Some people may thing its the level which determines the meaning, but actually all the level do.

Level 6 – Discourse : Focuses on the properties of the text as a whole that convey meaning by making connections between component sentences.

Level 7 – Pragmatic : Explains how extra meaning is read into texts without actually being encoded in them. This requires much world knowledge, including the understanding of intentions, plans, and goals. Consider the following 2 sentences:

• The city councilors refused the demonstrators a permit because they feared violence.
• The city councilors refused the demonstrators a permit because they advocated revolution.

The meaning of “they” in the 2 sentences is different. In order to figure out the difference, world knowledge in knowledge bases and inferencing modules should be utilized.

What are the approaches for performing NLP?

Natural language processing approaches fall roughly into four categories: symbolic, statistical, connectionist, and hybrid. Symbolic and statistical approaches have coexisted since the early days of this field. Connectionist NLP work first appeared in the 1960’s.

Symbolic Approach: Symbolic approaches perform deep analysis of linguistic phenomena and are based on explicit representation of facts about language through well-understood knowledge representation schemes and associated algorithms. The primary source of evidence in symbolic systems comes from human-developed rules.

Statistical Approach: Statistical approaches employ various mathematical techniques and often use large text input to develop approximate generalized models of linguistic phenomena based on actual examples of these phenomena provided by the text input without adding significant linguistic or world knowledge. In contrast to symbolic approaches, statistical approaches use observable data as the primary source of evidence.

Connectionist Approach: Similar to the statistical approaches, connectionist approaches also develop generalized models from examples of linguistic phenomena. What separates connectionism from other statistical methods is that connectionist models combine statistical learning with various theories of representation – thus the connectionist representations allow transformation, inference, and manipulation of logic formulae. In addition, in connectionist systems, linguistic models are harder to observe due to the fact that connectionist architectures are less constrained than statistical ones.

NLP Applications

Information Retrieval – Information Extraction – Question-Answering – Summarization – Machine Translation – Dialogue Systems

References

Liddy, E. D. Natural Language Processing. In Encyclopedia of Library and Information Science. 2nd Ed. Marcel Decker, Inc.

So, social media is now everywhere with different types, methods and apps, so what does it mean - at least for me – about every app I use

1-Facebook

having friends on Facebook is like being with them in a huge playground watching what are they doing and may be watching how they are interacting with each other and may be I go poke him or tell him a comment about something he has done, the main difference between this and being with him in the real world that I can more often tell him that I’ve “liked” something he has done or some news he has shared.

2-Twitter

Following some people (tweeps) on Twitter is like creating intersection points between your daily circles of life, where you can see his comments on something he has experienced or his opinion about anything while you are there listening to his time line, Twitter interaction might be less often than Facebook but sometimes it’s a bit more realtime interaction depending on how addict is your tweep

3-Google BUZZ

It’s a place where you can find what you have missed about some one’s tweets, may be Facebook shares, diggs or reddits and google reader shares, so it’s the place to gather all info of all sorts but still I think it needs some time.

4-Google Wave

It’s a place where you can rarely see some body there

5-Messengers (MSN, Yahoo, GTalk…etc)

A place  where you can find somebody when you need him at the moment, of course he might not be there now, but you can wait for a while, or try to send him an offline message to see whether he is hiding or not (invisible or something from that crap)

6-Sitting next to your desk

What ?!! how long has he been there ?!!

Introduction

OK !, Today I give a very big picture about that crucial term called “Ubiquitous Computing” and it’s relation to AI (YES, I mean Artificial Intelligence) . Actually, it’s a shame that any AI geek doesn’t know it. Just remember that, the word “Ubiquitous” means “Existing or being everywhere, or in all places, at the same time”.

What is Ubiquitous Computing?

I can say about Ubiquitous Computing (UbiComp) as “The Incorporation of computers into the background of human life without any physical interaction with them”. It’s considered the future third era of computing where the first era was the mainframes era and the second era is the personal computers era (what we are living now).   The term Ubiquitous Computing – also known as Calm Technology- was found by Mark Weiser -The father of Ubiquitous Computing- in the late 80s (so it’s not a new thing).

Ubiquitous Computing involves tens, hundreds or even thousands of different sized (often tiny) computers sensing the environment, deducing stuff, communicating and performing actions to help a human without actually using any interface. Thousands of computers should be embedded in everyday’s objects such as paper, pens, books, doors, buildings, walls, food containers, clothes, furniture, equipment … etc. to maintain a human’s life.

Even the most powerful notebook computer, with access to a worldwide information network, still focuses attention on a single box (the computer itself). However, Ubiquitous Computing means no human attention to any computer interface when using it. Take a look at motors technology which is considered ubiquitous; a glance through the shop manual of a typical automobile, for example, reveals twenty-two motors and twenty-five more solenoids. They start the engine, clean the windshield, lock and unlock the doors, and so on. By paying careful attention it might be possible to know whenever one activated a motor, but there would be no point to it. Similarly, computers in the Ubiquitous Computing era should be like that.

Suppose you want to lift a heavy object. You can call in your strong assistant to lift it for you, or you can be yourself made effortlessly, unconsciously, stronger and just lift it. There are times when both are good. Much of the past and current effort for better computers has been aimed at the former; ubiquitous computing aims at the latter.

An Example for life with Ubiquitous Computing.

AI and UbiComp ?

According to this essay, AI will play a major role in UbiComp in 3 different ways:

1. Ubiquitous Computing needs a transparent interface to work, which means a natural way for communication with human-kind. This involves a lot of artificial intelligence such as gesture recognition, sound and speech recognition and computer vision.
2. Ubiquitous Computing needs computers to be aware of their context such as location and time. Artificial Intelligence plays an important role in context awareness where it helps the computer perceive people’s location and generate proper service accordingly. For example, when you are at office, you may want to read some business reports, but when you go back home, you want to watch movie and enjoy coffee for a rest. These scenarios impose requirements to artificial intelligence agents.
3. Ubiquitous Computing will also favor from automated learning from their past experience and capturing people’s experience. Learning agents are introduced into this framework to perceive people’s behavior and make decision based on people’s preference.

References

Shang, Yu Liang, The Role and Possibility of Artificial Intelligence in Ubiquitous Computing, 1993

Mark Weiser, “The Computer for the Twenty-First Century,” Scientific American, pp. 94-10, September 1991

http://www.peterindia.net/UbiquitousComputingLinks.html