Running 47906Proxy as an Applet

This article describes running the 47906Proxy as an Applet:

Brief History of the 47906Proxy:  The proxy was developed initially as a port forwarder, or simply a forwarding proxy.  What is a forwarder proxy, and how is it used?  Three use cases are included below the 47906Proxy demonstration applet (the use cases include Tunneling, Application level Protocol Sniffing, and Network Latency Trending).  In addition a code snip-it has been included below the proxy to allow for a cut and paste usage on your website.

USE CASE 1:  

Firewall hopping.

Firewall hopping is some times called tunneling, this will allow an application to access a port on a remote machine behind a firewall, without the need or requirement to poke a hole in the firewall.  Additionally, forwarding proxies can add additional checking and validation to ensure that the individual trying to tunnel has the privileges and rights to do that.

USE CASE 2:  

Protocol Sniffing

This allows a very high level of stream sniffing, or application layer protocol sniffing.  Frequently this is much more desirable than low level packet capture sniffing.

USE CASE 3:  

Performance Monitoring

This allows for data flow rate analysis, and latency analysis at a much higher level than a packet sniffer.

Software Entrepreneur Round-Table

What: A Software Entrepreneur Round-Table
When: October 24 from 6:30 PM - 8:30 PM CST
Venue: TBD (Skype/google-voice/ tele-video conference)
Who: We are looking for a global perspective, In particular looking for Entrepreneur's from China, India, Europe/Russia, US and South America
Format: Informal Moderated Discussion.
Language: English

Goal group size 6-10 Entrepreneurs or perspective entrepreneurs:

Agenda:
1. Welcome and Introductions
2. Discussion Rules
3. Each Idea is presented and Brainstormed (semi open)
4. 10/4 voting on difficulty, competition, and feasibility
5. Exchange of contact info
6. Business plan partner assignment
7. Followups

To Sign Up, Email: October.RoundTable@ecocrypt.com
Include: your name
your country
your phone
your email

You will receive either a phone call, or an email within 72 hours.

Ecocrypt's RegEx Testing Applet and Java-Regex Source Generator

This is the Discussion Board For EcoCrypt's RegEx Testing Applet.

Feel free to use this, or bookmark the actual link http://www.ecocrypt.com/regex
*Features:

• Test your regex pattern against text input.
• Generate the Java source code for the regex matcher.
• Run your regex against a file on your local harddrive.

Please Leave Comments! Comments Can Be Related To Wish List, Usability, Or Other RegEx Thoughts.

Creating an SVN repository on Bluehost

Motivation:
There are many free svn repository providers.  If you are an individual developer, you may choose to use one of those.  Some have the restriction that repository is publicly accessible such as google code and sourceforge, while others keep the repository private such as projectlocker and sliksvn.  After reading the license agreements and contracts, I decided to maintain my own repository.

Warning:
This discusses how to set up and configured a svn repository on BlueHost using a windows 7 as the client machine: This setup is not for the faint of heart.  It requires modifying configuration settings, compiling source code with multiple complex config options, generating ssh keys, setting up ssh, and properly configuring the windows environment.  (NOTE:  All of these steps can be followed for linux/bsd/mac.  Slight modifications to the commands may be required, such as using forward-slashes for paths instead of back-slashes; using : for path separators instead of ';'; and other OS specific idiosyncrasies)

Quick Overview:

1. Install SSH on the client
2. Setup SSH Keys (you will have to contact bluehost directly to get permission to use SSH to access your server)
3. Install an SVN Client
4. Compile and Install the SVN Server from source on your bluehost box.
5. Setup an ssh-svn service bridge (sshsvnserve)
6. Instruct svn to use the service bridge when connecting to your repo.
7. Using the repository.
8. Properly backing up the repository (don't trust bluehost to back up the repository for you).

Getting Started:

Install SSH On Windows 7 (or any other version of windows)

I use mingw (which is minimal gnu for windows).  This is an excellent package, and does not have all the complexities of cygwin.  However, cygwin might work just fine.  I don't use it because it tends to mess up gmake/gnu's make program.

• Download and install mingw from http://www.mingw.org/
• Assuming you installed at c:\MinGW, then add C:\MinGW\msys\1.0\bin to your system path environment variable.
• Confirm all is working by typing svn -v from any directory on your box, you should get:
• 
  

  C:\>ssh -v
  
  OpenSSH_5.4p1, OpenSSL 1.0.0 29 Mar 2010
  usage: ssh [-1246AaCfgKkMNnqsTtVvXxYy] [-b bind_address] [-c cipher_spec]
             [-D [bind_address:]port] [-e escape_char] [-F configfile]
             [-I pkcs11] [-i identity_file]
             [-L [bind_address:]port:host:hostport]
             [-l login_name] [-m mac_spec] [-O ctl_cmd] [-o option] [-p port]
             [-R [bind_address:]port:host:hostport] [-S ctl_path]
             [-W host:port] [-w local_tun[:remote_tun]]
             [user@]hostname [command]
  

• Congrats! step 1 is done

Setup SSH Keys
SSH keys allow you to login to your account on BlueHost without the need for a password.  It works by storing a private key on your computer, and you upload a public key to your account on the BlueHost box.  You can then login using ssh, or interact using scp without specifying a password, by specifying the ssh private key file.  The public and  private keys are asymmetric keys.  This means that which ever key is used to encrypt the data, the other key must be used to decrypt data.  Authentication is accomplished by providing a challenge to the requesting client.
Assuming Step 1 was completed successfully, the ssh-keygen program should be in your path.

• pick a directory to store your public and private key, and switch to that directory
  A good choice would be -> c:\Users\[Windows User]\.ssh
• Generate the public and private key, there are many options, choosing all defaults (with the exception of the file name) is typically good.

C:\Users\[My Account]\.ssh>ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (//.ssh/id_rsa): id_rsa_svn
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in id_rsa_svn.
Your public key has been saved in id_rsa_svn.pub.
The key fingerprint is:
04:a3:1a:b7:5d:6f:29:39:bc:30:a3:c7:c6:b0:2f:49 [My Account]@[mycomputer's name]
The key's randomart image is:
+--[ RSA 2048]----+
|      o          |
|     . o         |
|  . o   o        |
|   + o + o .     |
|  . o = S +      |
|    E* + =       |
|   .o.= .        |
|    o+           |
|     ..          |
+-----------------+

Test out your SSH Key

• upload the public key to the bluehost server, KEEP the private key private! This is important because this protects the bluehost account from unauthorized access.
• Install the key in your authorized_keys file
• Test the access.

From your windows box:

C:\Users\[Windows User]\.ssh>ls
id_rsa  id_rsa.pub  id_rsa_svn  id_rsa_svn.pub

C:\Users\[Windows User]\.ssh>scp id_rsa_svn.pub [bluehost account]@[bluehost machine]:~/.ssh
[bluehost account]@[bluehost machine]'s password:
id_rsa_svn.pub                                                                                            100%  401     0.4KB/s   00:00

You will now need to log into the bluehost box, and manually add the public key to the authorized_keys file. To do this, log on to your bluehost account, and follow the following steps.

[bluehost account]@[bluehost machine] [~]# cd .ssh
[bluehost account]@[bluehost machine] [~/.ssh]# dir
./  ../  authorized_keys2  environment  id_rsa_svn.pub
[bluehost account]@[bluehost machine] [~/.ssh]# cat id_rsa_svn.pub >> authorized_keys2

NOTE to see the changed file:
[~/.ssh]# cat authorized_keys2

Finally From the windows box, test out the key to make sure that it works:

C:\>ssh -i "c:\Users\[Windows User]\.ssh\id_rsa_svn" [bluehost account]@[bluehost machine]
Last login: Thu Apr 28 17:08:06 2011 from 32.178.80.204
[bluehost account]@[bluehost machine] [~]#

Install An SVN client
Any svn client should do the job, SlikSVN seems to be a good distribution.  However, many others will do the job.  SlikSvn comes as a standard windows installer, it will typically add the subversion client tools to your path.  Once it is installed on your windows box, test to make sure the svn.exe file is executable from any directory.

C:\>svn --version
svn, version 1.6.16 (SlikSvn/1.6.16) X64
   compiled Mar  3 2011, 22:35:47

Copyright (C) 2000-2009 CollabNet.
Subversion is open source software, see http://subversion.apache.org/
This product includes software developed by CollabNet (http://www.Collab.Net/).

The following repository access (RA) modules are available:

* ra_neon : Module for accessing a repository via WebDAV protocol using Neon.
  - handles 'http' scheme
  - handles 'https' scheme
* ra_svn : Module for accessing a repository using the svn network protocol.
  - with Cyrus SASL authentication
  - handles 'svn' scheme
* ra_local : Module for accessing a repository on local disk.
  - handles 'file' scheme
* ra_serf : Module for accessing a repository via WebDAV protocol using serf.
  - handles 'http' scheme
  - handles 'https' scheme

Compiling SVN Server on BlueHost

1. Download the latest version of Subversion from sourceforge.
2. copy it up to the BlueHost Account
3. configure the compilation process for BlueHost
4. make the components
5. install the svn server and libraries

I will outline these steps in the following shell capture.  Note that config and compiling take several minutes each.

[~]# cd src
[~/src]# cd subversion-1.6.16
[~/src/subversion-1.6.16]# ./configure --prefix=$HOME/svn/bin --without-apxs --exec-prefix=$HOME/svn/lib --disable-mod-activation
[~/src/subversion-1.6.16]# nohup make &
[~/src/subversion-1.6.16]# tail -f nohup.out
[~/src/subversion-1.6.16]# make install

Subversion server is now installed on BlueHost. At this point, it must be tested.
The following shell snippet shows the testing expectation:

[~]# cd svn/lib/bin
[~/svn/lib/bin]# ./svnserve --version
svnserve, version 1.6.16 (r1073529)
   compiled Apr 27 2011, 17:27:09

Copyright (C) 2000-2009 CollabNet.
Subversion is open source software, see http://subversion.apache.org/
This product includes software developed by CollabNet (http://www.Collab.Net/).

The following repository back-end (FS) modules are available:

* fs_fs : Module for working with a plain file (FSFS) repository.

Cyrus SASL authentication is available.

Setting up an ssh-svn service bridge:
In this step a bridge will be set up.  The purpose of this bridge will be two things:

• Set up enough of an environment to execute svnserve command (by default and for security purposes bluehost disables shells and environments for remote logins)
• Instruct ssh to invoke a temporary service immediately on connect.  (this service will of course be the svnserve command which serves content from an svn repository)

Log into your BlueHost machine, change to the .ssh directory, open the authorized_keys2 file with a text editor, vi or pico should do. Find the public key entry that was added to this file in the step above.  This key is going to be modified by adding some instructions to the front of the key.  the instructions to be added are: command="/home1/[your bluehost account]/sshsvnserve -t" see the code snippet below for an example of what things should look like:

command="/home1/[your bluehost account]/sshsvnserve -t" ssh-rsa AAAABCCCCCCDDDDDDDD3NzaC1yc2EAAAADAQABAAABAQDJezPXNZb8rls8GrxH46zZwUO6vm1bkgxD2jma4RJMlXH0ADTDsQ2PGZAW80hVamojBsKGUN8zYH2i3LiEYiNSqL2d6mvFZAxIGH4mxhQQZdImyIWEnAK5a9HL9SQlIRnKa0ZEEsi/KWmiyB/gOXtKxxW7aU9KIsk2mjG0UZfmRHE4OhvXQqguAZCScOHh/WDRXiC2t2WbmfSXJK7KNz2sjla8Y62Z+u3Lg0m4SlmNqLgllh+tY0Nbxd623sJSQVqNwutPPMd1IhybjQskXUv8OlSmVepkhnGpSteRIzI99MocX8LzrZefHSaPsyMeHri52VzTb0
3 [windows usr]@[windows machine name]

The only thing added is the first command=..... up to the 'ssh-rsa' of course modified to match your account.

Now create the sshsvnserve shell script.  This is a very simple shell script.  Switch back to the home directory on the bluehost machine, and create a file with the following content.  Note that you will have to change this file to executable before it can be used.

#!/bin/sh
/home1/[your bluehost account]/svn/lib/bin/svnserve $*

Instruct svn to use the service bridge when connecting to your repo.
This is done by adding an ssh directive to your tunnels command.  On the windows box, create a subversion config file as bellow.

C:\Users\[Windows Account]\.subversion>cat config


[tunnels]
ssh = ssh -i "c:\\Users\\[Windows Account]\\.ssh\\id_rsa_svn"

USING your new repository:

C:\repos>svn --config-dir="c:\Users\[Your Windows Account]\.subversion" co svn+ssh://[your bluehost account]@[your bluehost machine/ip]/home1/[your bluehost account]/repos

Using the repository
The repository can be used by simply making sure that the --config-dir option is specified, and points to the directory that contains your config file with the [tunnels] entry.

Backing up the Repository:
Assuming that you are using BlueHost for a single user or very small number of users, you can simply create a synchronized repository on your local machine. The steps will be outlined in a code snippet block, with comments.

#  First create the repository.
C:\repos>svnadmin create .

#  Modify the hooks so the repos can accept
#  backup requests from other repositories.
C:\repos>cd hooks
C:\repos\hooks>echo exit 0 > pre-revprop-change.bat
C:\repos\hooks>cat pre-revprop-change.bat
exit 0

# 
C:\repos>svnsync initialize file:///repos svn+ssh://[bluehost caccount]@[bluehost machine]/home1/[bluehost account]/repos --config-dir="c:\Users\[Windows Account]\.subversion"
Copied properties for revision 0.

C:\repos>svnsync synchronize file:///repos --config-dir="c:\Users\[Windows Account]\.subversion"
Committed revision 1.
Copied properties for revision 1.
Committed revision 2.
Copied properties for revision 2.
Transmitting file data .......................................................................
..............................................................................................
...........
Committed revision 3.
Copied properties for revision 3.
Transmitting file data .......................................................................
..............................................................................................
...
Committed revision 4.
Copied properties for revision 4.
Transmitting file data .

Python - Insertion Sort Impl

This article will discuss a simple insertion sort algorithm for python.
See ALL Python postings  |  Insertion Sort By Language Java Scala Go C++ Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural wayTs of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the Python Solution:
In python this solution relied a bit on creativity.  The solution is clearly not $O(n^2)$,  however it may take a bit to understand why.  The reason lies in the fact that python does not have a linked list that allows insert at a given point in the list.  Therefore, to simulate that behavior, this solution rotates the list until it cat append to the left side of the list, and then rotates back.  This ensures that the order is correct.  What would be the big O of this solution assuming that each rotation is O(n)? Some additional inline comments have been included.

If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward. Python Solution:

#!/opt/python
from collections import deque
import random

dq = deque()
for i in range(20):
    dq.append(random.randrange(1001))

for elem in dq:
    print(elem)

sortedQueue = deque()
j=int(0)
k=int(0)
for elem in dq:


    for sortedElem in sortedQueue :
        if elem>sortedElem:
            sortedQueue.rotate(-j)
            sortedQueue.appendleft(elem)
            sortedQueue.rotate(j)
            k=1+k
            break
        j=j+1
    if (k == 0):
        sortedQueue.append(elem)
    else:
        k=0
    j=0

print (sortedQueue)

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

C++ - Insertion Sort Implementation w/ Make file Introduction

This article will discuss a simple insertion sort algorithm in C++. Unlike any of the other languages in this series on the insertion sort algorithm. C++ has for more caveats and options. While the algorithm is exactly the same the implementation details are filled with pitfalls.
See ALL C++ postings   |  Insertion Sort By Language Java Scala Go C++ Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural ways of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the C++ Solution:
There are several caveats to the C++ solution.  Therefore the source file will simply be discussed from top to bottom, with each decision discussed in turn.

1. Imports: The first thing to notice is the choice of the imports, this solution imports the iostream, list, and cstdlib.  
1. The iostream should be familiar as it is used for I/O.  
2. The list chosen here is from the STL of C++ and is included with the #import <list> directive.
3. The cstdlib is imported to expose the rand function which is a sudo random number generator.
2. using namespace std - this allows reference without the need for adding std:: to methods or objects included from std libraries.
3. Forward Declarations- C++ requires knowledge of all methods and classes before they are used.  That means that the compiler must know what each class/methods signature is before first use.  (see inline comment)
4. Pointers Vs Automatics - In this simple example, two lists of ints are created, the unsorted list, and the sorted list.  For pedagogical purposes, one was created on the heap, and the other as an "automatic" on the stack.  Heap allocated objects must be explicitly freed, or there might be a memory leak.  In C++ malloc and free go together, and new/delete go together, where delete releases the memory back to the operating system.  Objects that are stack allocated (created without a call to new or malloc/calloc) will be automatically released once the object goes out of scope.  Note that it might be possible to blow your stack if you allocate to many automatics.
5. Iterators - This code example is using the concept of a C++ STL iterator.  The concept of an iterator actually warrants multiple posts.  Basically from a very simplistic point of view, an iterator will visit each member of the list in turn.

The code has comments that are non-verbose, and useful.  Reading the code and comments along with compiling and running the code will help in the understanding of this exercise.  If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward.
C++ Solution:



The make file:
The make file is presented twice, once with inline comments, and once without.  Make files have many interesting caveats that may make direct cutting and pasting of the file difficult, but I will explain.
in a make file, targets are the commands that can be executed.  Each target line contains instructions to be carried out.  The instruction lines are on the line(s) immediately following the target line.  Each target knows it's instructions ONLY by looking for the consecutive lines that immediately follow it, AND are indented with a single TAB '\t' character.  Therefore, if you text editor converts tabs to spaces or something like that, it will mangle the make file because the tab characters are significant and have meaning.

first without comments, then with comments for reference:

#--------------------------------------
#
#  Copyright (c) 2011 EcoCrypt.com 
# 
#--------------------------------------

CPP=g++

MAIN=InsertionSort

.SUFFIXES : .exe .cpp

ifeq (${OS},Windows_NT)
EXES=${MAIN}.exe
RM=del /S 
else
EXES=${MAIN}
RM=rm -f # implicitly defined on unix
endif

ALL: ${EXES}

.cpp.exe: 
 echo ${CPP} ${DIRECTIVES} $? -o $@ 
 ${CPP} ${DIRECTIVES} $? -o $@ 

clean:
 ${RM} ${EXES}

Find below the make file with comments:

#--------------------------------------
#
#  Copyright (c) 2011 EcoCrypt.com 
# 
#--------------------------------------

#---------------------------------------
#  Set your compiler
#  On Windows Microsoftt compiler:
#  (i.e. CPP=cl)
#  On Linux, GUN compiler:
#  CPP=g++
#  On Windows MinGW (Minimal GNU for Windows):
#  CPP=g++.exe
#

CPP=g++
#CPP=cl.exe

#  The name of the main output
MAIN=InsertionSort

#  WE have to pass in VC98 and -GX if the compiler
#  is the cl compiler from Microsoft.
ifeq ($(CPP),cl.exe)
DIRECTIVES= -DVC98 -GX
else
endif

.SUFFIXES : .exe .cpp
#---------------------------------------
#  The windows version will contain a .exe
#  extention for each file.
#
#  List the executables.
#  here we have 2 mains that we 
#  will make: test and greetings.
#
#  Also redefine the implicit RM var.
ifeq (${OS},Windows_NT)
EXES=${MAIN}.exe
RM=del /S 
else
EXES=${MAIN}
RM=rm -f # implicitly defined on unix
endif

#---------------------------------------
#  The first target will create all
#  the EXES and recreate any that are 
#  out of Date.
#
#  This is also important because it is 
#  the default target, if you just invoke
#  make from the command like, the first 
#  dependency line becomes the default target.
#
ALL: ${EXES}

#---------------------------------------
#  Suffix rules are powerful and cryptic.
#  This states, for any target with no  (or .exe on windows)
#  suffix, look for a like named file with
#  an extension of .cpp, and perform the command
#  
#  (e.g.  for a file/dependecy named 'test.exe'
#         look for test.cpp, and perform
#         g++ test.cpp -o test.exe)
.cpp.exe: 
 echo ${CPP} ${DIRECTIVES} $? -o $@ 
 ${CPP} ${DIRECTIVES} $? -o $@ 

#---------------------------------------
#  clean the targets so you can force a 
#  rebuild

clean:
 ${RM} ${EXES}

Common Issues:
Forgetting to add the "using namespace std"
This is a common issue because older C++ books did not discuss this as it was added to C++ some time after the ansi standard was initially finalized.
Typically Error:

EcoCryptCppExamples\src\InsertionSort % make
echo g++  InsertionSort.cpp -o InsertionSort.exe
g++  InsertionSort.cpp -o InsertionSort.exe
g++  InsertionSort.cpp -o InsertionSort.exe
InsertionSort.cpp: In function 'void printList(std::list)':
InsertionSort.cpp:57:48: error: 'endl' was not declared in this scope
make: *** [InsertionSort.exe] Error 1

Leaving off one of the import statements. This demonstrates the error if the cstdlib is not imported, which defines the rand and srand functions.

EcoCryptCppExamples\src\InsertionSort % make
echo g++  InsertionSort.cpp -o InsertionSort.exe
g++  InsertionSort.cpp -o InsertionSort.exe
g++  InsertionSort.cpp -o InsertionSort.exe
InsertionSort.cpp: In function 'void printList(std::list)':
InsertionSort.cpp:57:48: error: 'endl' was not declared in this scope
make: *** [InsertionSort.exe] Error 1

The make file is missing key tabs:

C:\47906Proxy\EcoCryptCppExamples\src\InsertionSort>make
Makefile:70: *** missing separator.  Stop.

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

GoLang - Insertion Sort Implimentaion w/ google go

This article will discuss a simple insertion sort algorithm in golang (google go).
See ALL golang interest postings   |  Insertion Sort By Language Java Scala Go Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural wayTs of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the GoLang Solution:
Inline comments have been added to the code to discuss some of the syntax and code structure.
If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward.
GoLang Solution:

package main

/*------------------------------------------------------------------------------
  Copyright (c) 2011 ecocrypt.com

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the spe\]cific language governing permissions and
  limitations under the License.
-----------------------------------------------------------------------------*/
import fmt "fmt"  
import "container/list" 
import "rand"

//  The main entry point.
func main() {
    // create a list of integers randomly ordered.
    var  randomOrderedList = createRandomUnsortedList() 

    //  Perform the insertion sort.
    //  return a new sorted list.
    var sortedList = insertionSort(randomOrderedList)


    //  display the list to standard out.
    displayListToStandardOut(sortedList) 

}


//  private function takes unsortedList, returns sortedList
func insertionSort(unsortedList *list.List) (sortedList *list.List){
    sortedList = list.New()
    for e :=unsortedList.Front();e!=nil; e=e.Next() {
        var found = 0
        for s := sortedList.Front();s!=nil;s=s.Next(){
            if(e.Value.(int)>s.Value.(int)){
                found=1
                sortedList.InsertBefore(e.Value,s)
                s=sortedList.Back()
            }
        }
        if(found==0){
            sortedList.PushBack(e.Value)
        }
    }
    return sortedList
}


//  private method displays the lList to standard out.
func displayListToStandardOut(lList *list.List) {
    counter := 0
    for y :=lList.Front();y!=nil; y=y.Next() {
        counter += 1
        fmt.Printf("%d -> %d\n",counter,y.Value)
    }
}

// private method returns lList
func createRandomUnsortedList() (lList *list.List) {
    //  Create a New Random Generator from a Random Source
    //  with a seed of 10.
        var r = rand.New(rand.NewSource(10))

    //  create a list of random integers.
    lList = list.New()
    for i :=0; i<15; i=i + 1 {
        lList.PushFront(r.Int())
    }
    return lList
}

Answers: 1.  The best case senario would be order: $O(n)$ 2.  The worst case senario would be order: $O(n^{2})$golang postings

Scala - Insertion Sort Implementation

This article will discuss a simple insertion sort algorithm in Scala.
See ALL Scala postings   |  Insertion Sort By Language Java Scala Go Python Perl

Overview of the Insertion Sort Algorithm
Insertion sort is one of the most natural ways of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?


About the Scala Solution:
Inline comments have been added to the code to discuss some of the syntax and code structure.
If you have a question about the solution (or feel it should be improved) please leave a comment.  All comments are moderated and posted with your name/Identification so please be professional and straight forward.
Scala Solution:

package com.ecocrypt.scala.helloworld.com.ecocrypt.scala.algorithms.sort

import java.util.LinkedList

/*------------------------------------------------------------------------------
  Copyright (c) 2011 ecocrypt.com

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the spe\]cific language governing permissions and
  limitations under the License.
-----------------------------------------------------------------------------*/

object InsertionSort {
    var flag = 0
    var counter = 0


    def sort(unsortedList: List[Int]): LinkedList[Int] = {
        // Start with an empty LinkedList.
        // as items are added to the list, they will be
        // placed in sorted order.
        var sorted = new LinkedList[Int]()

        // Iterate over the unsorted list one Item at a time.
        for (currentItem <- unsortedList) {
            flag = 0
            counter = 0;

            //------------------------------------------------------------------------------------
            //  Scala allows us to define helper functions with scope inside of other functions.
            //        this creates some very interesting closure situation.
            //        More on this in later code samples
            //------------------------------------------------------------------------------------
            def checkRecordToRightAndInsertIfLocationFound(itemRightOfCurrentPostion: Int): Int = {
                if (itemRightOfCurrentPostion > currentItem) {
                    // flag is a var defined in an enclosed scope.
                    flag = 1
                    if (counter < 0) {
                        sorted.addFirst(currentItem)
                    } else {
                        sorted.add(counter, currentItem);
                    }
                }
                //  this is the return val of this method.
                flag
            }


            do {
                if (counter == sorted.size) {
                    sorted.addLast(currentItem)
                    flag = 1
                } else {
                    var itemRightOfCurrentPostion = sorted.get(counter)
                    flag = checkRecordToRightAndInsertIfLocationFound(itemRightOfCurrentPostion)
                }
                counter = counter + 1
            } while (flag == 0)
        }
        return sorted
    }
}

//  Here we use an application to serve as the entry point.
object EntryPointForInsertionSortExample extends Application {
    val randomOrderedList = List.fill(10)(scala.util.Random.nextInt(1000))
    println("unsorted List : " + randomOrderedList)
    val sortedList = InsertionSort.sort(randomOrderedList)
    println("sorted List : " + sortedList)
}

Answers:
1.  The best case senario would be order: $O(n)$
2.  The worst case senario would be order: $O(n^{2})$

Java - Insertion Sort Implementation and discussion.

This article will discuss a simple insertion sort algorithm in Java.
See ALL Java Postings   |  Insertion Sort By Language Java Scala Go Python Perl


Discussion of Insertion Sort
Insertion sort is one of the most natural ways of sorting a collection of comparable items.  The reason it is one of the most natural ways is because it is the way most people will sort physical items.   For example each year (about this time) I will sort all 12 of my previous years phone bills, gas bills, etc...  The algorithm used to sort them is to place the first one in stack.  Then the second one is compared to the first one to see if it goes in front of or behind the first one.  The third one is then compared to each if the two sorted items to determine where it fits in.  This procedure continues until all 12 bills are in the pile.  Once all 12 bills are in the pile it is sorted. I happen to sort form oldest to newest, my spouse does it the other way newest to oldest.

Applying this concept to a collection of objects in a computer is fundamentally the same.  The algorithm dictates that one will iterate over a collection of elements in an unsorted list 1 at a time, and place that item into it's correct location in a sorted list.

If the collection of objects to sort is n, insertion sort will take at most $O(n^2)$ operations to perform the sort, it will take on average $\frac{1}{2} O(n^2) = O(n^2)$, and in the best case senario will take $O(n)$ operations.


Questions:  


1.  What would be the initial characteristics of a list that took the worst case order $O(n^2)$ to sort?
2.  What would be the initial characteristics of a list that took the best case order $O(n)$ to sort?




Java Solution:

/*------------------------------------------------------------------------------
   Copyright (c) 2011 ecocrypt.com

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 -----------------------------------------------------------------------------*/
package insertionsort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class InsertionSortAlgorithm<type extends Comparable> {
    Collection<type> unsortedCollection;

    public InsertionSortAlgorithm(){
        unsortedCollection = new ArrayList<type>();
    }

    public InsertionSortAlgorithm(Collection<type> sourceCollection){
        unsortedCollection = new ArrayList<type>(sourceCollection);
    }
    public void add(Type element){
        unsortedCollection.add(element);
    }
    public Collection<type> getUnsortedCollection(){
        return unsortedCollection;
    }

    public List<type> sortWithInsertionSort(){
        LinkedList<type> sortedList = new LinkedList<type>();
        for (Type nextObject : unsortedCollection) {
            sortedList = placeInSortedList(sortedList,nextObject);
        }
        return sortedList;
    }

    private LinkedList<type> placeInSortedList(LinkedList<type> sortedList, Type nextObject){
        int insertionIndex = 0;
        for (Type object : sortedList) {
            if(nextObject.compareTo(object)>0){
                break;
            }
            ++insertionIndex;
        }
        sortedList.add(insertionIndex, nextObject);
        return sortedList;
    }
}

Answers:
1.  The best case senario would be order: $O(n)$
2.  The worst case senario would be order: $O(n^{2})$

Scala - Hello World

Scala's Hello World can be either similar to Java's, or simpler depending on how the problem is approached.  This article will approach the problem from both the Java style as well as the much more pure functional style.  Remember that Scala is a highly expressive functional language.  The second form of the hello world program will show this feature much more clearly.

Step 1: Create a Scala source file

Scala does not have the same restrictions on source file naming that Java has.  Therefore, you can give the Scala source file pretty much any name you like, so long as it ends in .scala.  The fist form of Hello World looks as:

__________________________________________________________________________________

object HelloWorld {
    def main(args: Array[String]) {
      println("Hello in scala from ecocrypt.blogspot.com")
    }
  }

__________________________________________________________________________________

Step 2: Compile the Scala Source

At a command prompt, type the scala compiler command:

prompt %
prompt % scalac HelloWorld.scala
prompt %

prompt % scalac HelloWorld.scala

The result of this will be to produce an output file called HelloWorld.class, this class file is a byte code version of the HelloWorld.scala source file.  This class file is identical to a Java class file, but has Scala class references embedded in it.  

Step 3: Running HelloWorld

At the command prompt, type:

prompt %
prompt % scala HelloWorld
Hello in scala from ecocrypt.blogspot.com
prompt %

prompt % scala HelloWorld

Hello in scala from ecocrypt.blogspot.com

Congratulate yourself!  You have successfully installed the Scala compiler and execution environment, created a simple scala source file compiled it to byte code, and run it inside of the Scala/Java Virtual Machine.

The exact same thing could be accomplished using a scala Application.  The source code for a Scala application based solution would look as:

__________________________________________________________________________________

object HelloWorld2 extends Application {

  println("Hello world in scala from ecocrypt.blogspot.com")

}

__________________________________________________________________________________

C++ - Hello World

C++'s Hello World is similar to Go's (golang), but there are some differences.  The similarity is that both C++ and Go create a file that is executed natively on the platform it is compiled to.  Also both C++ and Go follow a procedure of compile then link.  The main differences, for the Hello World program, are in the expressiveness and the syntax.  Writing hello world in C++ requires the following steps:

Step 1: Create a C++ source file

The source file for Hello World thus looks like the following:

__________________________________________________________________________________

#include <iostream>

using namespace std;

int main(int argc, const char** argv){

cout<<"Hello World in C++ from ecocrypt.blogspot.com"<<endl;

return 0;

}

__________________________________________________________________________________

Save this to any file name you like, but typically, you will have to have a .cpp extension on the end of the file name.  A good name to choose for this example would be helloworld.cpp.

Step 2: Compile the C++ Source

At a command prompt, type the c++ compiler-linker command:

prompt % c++ HelloWorld.cpp

This will typically do a 2 step process of compiling and linking.  Therefore no intermediate object files will be created.  The result of this will be to produce an output file called a.out, or a.exe. 

Step 3: Running HelloWorld

At the command prompt, type:

prompt % a.out      (or a.exe on windows)

Hello World in C++ from ecocrypt.blogspot.com

Congratulate yourself!  You have successfully installed a C++ compiler, and created a simple hello world executable.

Perl - Hello World

Writing hello world in perl is almost to simple to justify a post, however there are some caveats and for completeness of this group of posts, it will be included.

Step 1 Install Perl (5.x)

Once installed, make sure that you can access the perl executable.  If perl is not in the path, you will need to add it.

Step 2 Create a Perl Source file

______________________Source File____________________________

#!/opt/perl

print ("Hello World in Perl from ecocrypt.blogspot.com")

______________________End Source____________________________

save the source to a file called helloworld.pl  (or any other name of your choice)

Step 3 Tell Perl to execute the input file

prompt % perl helloworld.pl

Hello World in Perl from ecocrypt.blogspot.com

Congratulate yourself! You have successfully installed perl, create a perl source file, and executed it.

Java - Hello World

Java's Hello World is simpler than Go's (golang), but not as simple as Python's.  Also like python the output is quite portable from platform to platform.  Writing hello world in Java requires the following steps:

Step 1: Create a Java source file
There are actually quite a few caveats to this step alone because Java as some requirements that make it more restrictive  than any other language in this blog.  In Java, there everything is an "Object" and thus extends from java.lang.Object.  Therefore, you will have to create a full class definition even though we will not be instantiating any classes.  The source file for Hello World thus looks like the following:
__________________________________________________________________________________

public class HelloWorld extends java.lang.Object {
    public static void main(String args[]){
        System.out.println("Hello World in Java from ecocrypt.blogspot.com");
    }
}

__________________________________________________________________________________

There is another caveat in Java the class HelloWord must be stored in a file called HelloWorld.java. Picking another name will cause a compiler error.

Step 2: Compile the Java Source
At a command prompt, type the java compiler command:
prompt % javac HelloWorld.java

The result of this will be to produce an output file called HelloWorld.class, this class file is a byte code version of the HelloWorld.java source file.  Unlike golang, where the output of the linker can be directly executed, the java class file is not executable.  However, a java executable program and load the HelloWorld.class file, and execute the instructions.

Step 3: Running HelloWorld
At the command prompt, type:
prompt % java HelloWorld
Hello World in Java from ecocrypt.blogspot.com

Congratulate yourself!  You have successfully installed the JDK, created a simple java source file compiled it to byte code, and run it inside of the Java Virtual Machine.

Go Lang - Hello World

Starting a new language the first example is always Hello World.  Getting going with go-lang is only slightly different.  As of this writing, the current state of 'go-lang' is that you have to build the compiler first, and then write compile and run Hello World.  On UNIX/Linux you can do that pretty easily based on the instructions maintained on the golang.org website.  On windows the GOMINGW  seems to be maintaining good binary compatible version of go built with the mingw compiler collection on windows.

Step 1 Set your environment variables:

E.G. On my windows box I set:

set GOROOT=C:\golang\go
set GOOS=windows
set GOARCH=386

  (look in $GOROOT/pkg for applicable architecture and OS Options)

Step 2 Create a source file in the go language (a go source file):
Use a text editor or write a golang source file:
Sample Hello World GO Language source file:
________________________SOURCE FILE________________________________________


package main

import fmt "fmt"  // Package implementing formatted I/O.

func main() {
      fmt.Printf("Hello, world; from go to ecocrypt.blogspot.com \n")
}

________________________END SOURCE_________________________________________

Save this file to helloworld.go or any filename of your choice.

Step 3  Compile
prompt % 8g helloworld.go

Step 4 Link
prompt % 8l helloworld.go

Step 5 Run the newly created executable:
prompt % 8.out
Hello, world; from go to ecocrypt.blogspot.com

Congratulate Yourself!  You have created and run Hello World in Go.
You should now have a Go compiler successfully installed on your computer.


SOME COMMON ERRORS:
Using the wrong executable to compile go source:
prompt %  8c.exe helloworld.go

helloworld.go:1 not a function
helloworld.go:1 syntax error, last name: main

     This Error is caused because you are trying to compile a go source file with a c compiler.  8c is a c compiler embedded in the go distribution package.

Using the wrong architecture or os settings:

prompt % 8g.exe helloworld.go

helloworld.go:3: can't find import: fmt

Make sure you have set the go environment variables correctly:
Determining the GOOS, and GOARCH can be tricky, you will have to look in:
$GOROOT/pkg/
and there will be a directory of format $GOOS_$ARCH

E.G. On my windows box I set:

set GOROOT=C:\golang\go
set GOOS=windows
set GOARCH=386

Python - Hello World

Writing hello world in python is almost to simple to justify a post, however there are some caveats and for completeness of this group of posts, it will be included.

Step 1 Install Python 3.2 
Once installed, make sure that you can access the python executable.  If python is not in the path, you will need to add it.


Step 2 Create a Python Source file
______________________Source File____________________________
#!/opt/python
print ("Hello World in Python from ecocrypt.blogspot.com")
______________________End Source____________________________
save the source to a file called helloworld.py  (or any other name of your choice)


Step 3 Tell the Python Interrupter to execute the instructions in the file
prompt % python helloworld.py
Hello World in Python from ecocrypt.blogspot.com


This entire exercise could have been done from within the python interrupter.  To start the interpretor simply type 'python' at the command prompt this will give you a python interpretor prompt:


>>>
>>>print ("hello world in python from ecocyrpt.blogspot.com")
hello world in python from ecocyrpt.blogspot.com
>>>
type quit() to leave the interpretor


SOME COMMON ERRORS:
Using the wrong Python Syntax for version 3.2.

>>> print "Hello World"

  File "<stdin>", line 1
    print "Hello World"
                      ^
SyntaxError: invalid syntax

>>>

There were some syntax changes between python 2.7 and 3.2.
This fails because the print method is not enclosed in braces().
Try >>> print ("Hello World")

Using VI / VIM Tags for maintaining developer's notes

Have you ever wanted to maintain a set of developer notes, or other quick references documents, and you want to maintain private or sensitive information that should not be accessible from the internet, consider using vi or gvim with tags.

Purpose:

Maintain a set of notes related to current projects, current software systems, and other handy information that is needed quickly can be valuable.  Using vi/gvim to do this can improve the navigation of the notes files.  

Advantages:

• VIM / GVIM are free easy to learn editors.
• VIM / GVIM exist on almost all unix installs by default.
• Use of 'tags' allows quick hyper-link style navigation though a file or set of files.
• Very light weight and simple way of maintaining information.

What are tags?

Tags are bookmarks.  There are two sides to the tag:

• The hyper-link or menu identifier.  Called the identifier tag.
• The bookmarked location or tagged data.

within vim/gvim, one moves from a hyper-link or menu identifier to the tagged data or bookmark location by placing the cursor over the menu item, and pressing 'crtl-]'.

One can quickly jump back to the previous location (the hyper-link or menu identifier from which they came) by pressing the 'crtl-T'.

How do you create bookmarks, and bookmark locations?

1. Creating a bookmark or tag:
1. Use the |tagname| syntax to create a menu item or hyper-link in a text file.
2. In the tags file associated with this text file create a single line entry as follows:
   tagname filename.txt /*tagname*
3. The tags listed within the tag file will have to be sorted or the tag logic/hyper-link will not work.
2. Tagging the location/setting the bookmark:
1. within the text file, add a bookmark with the syntax *tagname*
2. You are free to use the same tagname in multiple bookmarks, so for example if you wanted to use the tag with a name section at the beginning of each section, you could.
3. You are also free to use multiple tags/bookmarks on a single line.  An example would be to include the following tags *section* *howtotags* *gvim_tags*.

Listing of Java Posts

• This post ecocrypt.blogspot.com