@TeriRadichel | Cloud. Security. Software.

Thursday, March 06, 2014

Videos - Algorithms & Data Structures

Java Videos

Some interesting Java videos

Java Heap (Memory)
http://www.youtube.com/watch?v=FLcXf9pO27w

Class Loaders
http://www.youtube.com/watch?v=t8sQw3pGJzM

Effective Java
http://www.youtube.com/watch?v=V1vQf4qyMXg

JVM and Low Latency
http://www.youtube.com/watch?v=CZytwF_y_x8

I had an interesting discussion with one of my geek buddies last night. Someone told him to run something against a NAS that resulted in many small input and output operations (think map reduce reads and writes) and had some issues with that ...let's just say performance issues no big company wants to experience.

In the example above the NAS was not designed for a lot of small reads and writes.

This brings up an interesting point when considering performance of systems and determining how to architect the systems and write the software used by a particular piece of hardware. You have to understand the reads and writes your application requires and how the hardware you are running it on will handle it. For example if you are backing up data, you have large writes and minimal reads. A database or map reduce application will probably have a lot of small reads and writes.

Reading and writing data to/from disk is affected by IOPS.

IOPS = Input/Output Operations Per Second, pronounced eye-ops
http://en.wikipedia.org/wiki/IOPS

When you get an EC2 instance on AWS, for example, you can specified the IOPS. Understanding the reads and writes your application is doing will help you provision the correct amount of IOPS.

Understanding the devices in your network you are reading from and writing to will help you use the technology appropriately for a given application requirement.

Tuesday, March 04, 2014

Data Structures

Memory Use of Data Structures - Most to Least

HashSet
-- a wrapper around a HashMap with less functionality
-- default 16 elements
-- default size is 144 bytes
-- 128 bits to wrap hashmap
-- argument - why use because more memory, less functionality

HashMap
-- default size of 16
-- empty size is 128 bytes
-- each object 46 bytes + 36 bytes per entry
-- overhead ~360k (1/3MB to do nothing on creation)
-- not synchronized

Hashtable
-- same as HashMap in terms of memory on creation
-- 11 default entries
-- synchronized by default

LinkedList
--default size is 1
-- default size 48 bytes
-- 24 bytes per entry (no key/hash)

ArrayList
-- default size is 10
-- empty size is 88 bytes
-- for 10,000 item list overehead ~40k

Compresses references reduces amount of ram increase on 64 bit OS over 32 bit.

Speed of Collections

HashMaps offer faster access - you have the key to determine the location - but use more memory

LinkedLists and ArrayLists slower to search but use less memory

LinkedList - insertion and deletion are fast because you simply move the pointers at the point of insertion or deletion rather than moving the whole list. Search is slow.

Arrays are bad for insertion because you have to move all the items after the insertion point +1 on insert.

HashTables offer fast insertion and searching. Limited in size because based on arrays (should avoid resizing). Hard to sort.

Implementations

Binary Tree

O (log n)

a data structure where each node has at most two children
left node is less than right
children less than parent

Good for:
- insert, update, delete, search

Implementation

Three classes:

1. Node (key value pair)
2. Binary Node (extends node with right and left child)
3. Binary Tree

package com.radicalsoftware.datastructure;

public class Node {

    protected int key;
    protected String value;

    public Node(int key, String name){
       this.key = key;
       this.value = name;
    }

    public String getString(){
       return value;
    }

    public int getKey(){
       return key;
    }
}

package com.radicalsoftware.datastructure;

public class BinaryNode extends Node {

    private BinaryNode leftChild;
    private BinaryNode rightChild;

    public BinaryNode(int key, String name){
        super(key, name);
    }

    public void setRightChild(BinaryNode rightChild){
        this.rightChild = rightChild;
    }

    public void setLeftChild(BinaryNode leftChild){
        this.leftChild = leftChild;
    }

    public BinaryNode getRightChild(){
        return rightChild;
    }

    public BinaryNode getLeftChild(){
        return leftChild;
    }

    public String toString(){
        return key + " " + value;
    }

    public boolean hasChildren(){
        return leftChild != null && rightChild != null;
    }
}

public class BinaryTree {

    private static BinaryNode root;

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.addNode(4, "Mickey");
        bt.addNode(2, "Goofy");
        bt.addNode(3, "Minnie");
        bt.addNode(1, "Donald");

        BinaryNode node = root;

        System.out.println("*******************");
        System.out.println("in order traversal");
        inOrderTraversal(node);

        System.out.println("*******************");
        System.out.println("pre order traversal");
        preOrderTraversal(node);

        System.out.println("*******************");
        System.out.println("post order traversal");
        postOrderTraversal(node);

        System.out.println("*******************");
        System.out.println("find 3");
        System.out.print(find(3));
    }

    public static BinaryNode find(int key){

        BinaryNode searchNode = root;

        while(searchNode.key != key){

            if (key < searchNode.key){
                searchNode = searchNode.getLeftChild();
            }
            else{
                searchNode = searchNode.getRightChild();
            }

            if (searchNode == null) return null;
        }

        return searchNode;
    }
    public static void inOrderTraversal(BinaryNode node){

        if (node != null){
            inOrderTraversal(node.getLeftChild());
            System.out.println(node);
            inOrderTraversal(node.getRightChild());
        }

    }

    public static void preOrderTraversal(BinaryNode node){

        if (node != null){
            System.out.println(node);
            preOrderTraversal(node.getLeftChild());
            preOrderTraversal(node.getRightChild());
        }

    }

    public static void postOrderTraversal(BinaryNode node){

        if (node != null){
            postOrderTraversal(node.getLeftChild());
            postOrderTraversal(node.getRightChild());
            System.out.println(node);
        }
    }

    public BinaryNode getRoot(){
        return root;
    }

    public void addNode(int key, String name){

        BinaryNode newNode = new BinaryNode(key, name);

        if (root == null){
            root = newNode;
        }else{

            BinaryNode parent = root;

            while(true){


                if (key < parent.getKey()){
                    if (parent.getLeftChild() == null){
                        parent.setLeftChild(newNode);
                        break;
                    }
                    else{
                        parent = parent.getLeftChild();
                    }
                }else{
                    if (parent.getRightChild() == null){
                        parent.setRightChild(newNode);
                        break;
                    }else{
                        parent = parent.getRightChild();
                    }

                }
            }
        }
    }
}

Hash Table
- key values are assigned using a hash function
- hash determines best index
- IDs used to generate hash must be unique
- hashes must be unique (duplicate hashes when generating called collisions and can affect performance)
- hash must be small enough to fit within the bounds of the array
- hashes make it possible to find the value in the array using a calculation vs. search which means it takes one operation to access the data vs having to go through every element in the worst case search

Avoiding to collisions
- To avoid collisions you want your table storing hashes to be at least twice as big as size of array if you are using a mod has function
- using prime number for array size helps minimize collisions
- also avoid clustering by using a double hash function

To resize
- store values in current array and empty spaces
- get prime number bigger than array size
- use a hash function to fill new array with new hashes

To hash strings
hash value starts at 0
for each character hash = (hash * 27 + charCode) % arraySize

Separate chaining
- if there is already a value in a spot in the array add it to a list instead of searching for an open spot

Sample Code

Classes:
1. ArrayTools - some toools for arrays such as remove spaces & print elements
2. RadMath - some math functions
3. Hash - some hash functions (note string hash not used below)
4. HashTable - assumes all elements added to array are Strings that convert to unique integers

package com.radicalsoftware.datastructure;

import com.radicalsoftware.util.ArrayTools;
import com.radicalsoftware.util.Hash;
import com.radicalsoftware.util.RadMath;

//This class assumes the values are Strings that can be convereted
//to integers
public class HashTable {

    private String[] array;

    HashTable(int size){
       array = new String[size];
    }

    /*************************************************
    * Methods to fill hash table
    *************************************************/

    //the hash calculation = parse integer from String value
    public void fillTableHash1(String[] strings){

       for (int n = 0; n < strings.length; n++){
           String s = strings[n];
           int hash = Hash.keyToInt(s);
           array[hash] = s;
       }

    }

    public void fillTableHash2ShowCollisions(String[] strings){

       for (int i = 0; i < strings.length; i++){

           String s = strings[i];
           int hash = Hash.modHashShowCollisions(s, array);
           System.out.println("hash: " + hash);
           array[hash] = s;
       }

    }

    //hash 2, don't show collisions
    public void fillTableHash2(String[] strings){

       for (int i = 0; i < strings.length; i++){

           String s = strings[i];
           int hash = Hash.modHash(s, array);
           array[hash] = s;
       }

    }

    public void fillTableDoubleHashShowCollisions(String[] strings){

       for (int i = 0; i < strings.length; i++){

           String s = strings[i];
           int hash = Hash.doubleHash(s, array, 5);
           System.out.println("hash: " + hash);
           array[hash] = s;
       }

    }

    /*************************************************
    * Find value in hash table
    *************************************************/

    public int find(String key){

       int hash = Hash.modHashBase(key, array);
       int count = 1;

       //Exit on null or checked entire array
       while (this.array[hash] != null &&
               count != this.array.length){

           if (this.array[hash].equals(key))
               return hash;

           hash++;
           hash %= this.array.length;
           count ++;
       }

       return -1;

    }

    public int findDoubleHash(String key){

       int hash = Hash.doubleHashBase(key, array, 5);
       int count = 1;

       //Exit on null or checked entire array
       while (   this.array[hash] != null &&
               count != this.array.length){

           if (this.array[hash].equals(key))
               return hash;

           hash++;
           hash %= this.array.length;
           count ++;
       }

       return -1;

    }


    /*************************************************
    * Resize HashTable
    *************************************************/
    public void resize(int size){

       ArrayTools.removeSpacesInArray(array);
        size = RadMath.getNextPrime(size);
        String[] newArray = new String[size];

        for(int i = 0; i < array.length; i++){

            if(array[i] == null){
                array = newArray;
                return;
            }

            String s= array[i];
            int hash = Hash.modHash(s, newArray);

            while(newArray[hash]!= null){
                hash++;
                hash %= newArray.length;
            }

            newArray[hash] = s;
        }

    }

    /*************************************************
    * Print hash table
    *************************************************/
    public void print(){
       ArrayTools.print(array);
    }

}

package com.radicalsoftware.util;

public class ArrayTools {

    //remove spaces in original array
    //could also create an array list and copy
    //everything over but this uses the existing
    //allocated array
    public static void removeSpacesInArray(String[] array){

        int pointer = 0;

        for(int i = 0; i < array.length; i++){

            if (array[i] != null){
                if (i > pointer){
                    array[pointer] = array[i];
                    array[i] = null;

                    while (array[pointer] != null
                            && pointer < array.length){
                        pointer ++;
                        pointer %= array.length;
                    }
                }
            }
        }
    }


    public static void print(String[] array){

        for (int i = 0; i < array.length; i++){

            System.out.print(i);
            System.out.print(" ");
            if(array[i]!= null){
                System.out.print(array[i]);
            }

            System.out.print(System.lineSeparator());

        }

        System.out.println(System.lineSeparator());

    }
}

package com.radicalsoftware.util;

public class Hash {


    /*************************************************
    * Hash calculations
    *************************************************/

    //calculate hash by converting to int
    //assumes all input strings for table are unique
    //and only up to size of array
    public static int keyToInt(String s){
       return Integer.parseInt(s);
    }


    //let's say we have 900 potential values but only ever store
    //up to 25 values - it is not efficient to create a 900 item array.
    //make the array size of number of values we need to store and hash
    //on up to 900 values in a way that won't cause collisions
    //Solution: use mod size of array

    public static int modHashBase(String s, String[] array){
       int hash = Integer.parseInt(s) % array.length;

       return hash;
    }
    public static int modHash(String s, String[] array){

       int hash = modHashBase(s, array);

       while(array[hash]!= null){
           System.out.print("collision: array index (" + hash + ") has a value.");

           hash++;
           //if end of array start over at 0
           hash %= array.length;

           System.out.println(" Try: " + hash);
       }

       return hash;
    }



    public static int modHashShowCollisions(String s, String[] array){

       int hash = Integer.parseInt(s) % array.length;

       //if collision add 1 to hash until no more collisions
       while(array[hash]!= null){
           System.out.print("collision: array index (" + hash + ") has a value.");

           hash++;
           //if end of array start over at 0
           hash %= array.length;

           System.out.println(" Try: " + hash);
       }

       return hash;
    }

    //avoid clusters
    public static int doubleHashBase(String s, String[] hashArray, int step){
       int val = Integer.parseInt(s);
       int hash = val % hashArray.length;
       int stepDistance = step -(val % step);
       hash = hash + stepDistance;
       hash %= hashArray.length;
       return hash;
    }

    public static int doubleHash(String s, String[] array, int step){

       int hash = doubleHashBase(s, array, step);

       while(array[hash]!= null){
           hash ++;
           hash %= array.length;
       }

       return hash;
    }

    public static int hashString(String s, String[] array){
       int hash = 0;

       for (int i = 0; i < s.length(); i++){
           int charCode = s.charAt(i) - 96;
           hash += hashCharacter(charCode, hash, array.length);
       }

       return hash;
    }

    public static int hashCharacter(int charCode, int hash, int arrayLength){

       return (hash * 27 + charCode) % arrayLength;
    }
}

Graph

O(V+E)

- collection of verticies and edges
- undirected - no directions on edges, pairs are unordered
- directed - edges associated with directions - edges are ordered pairs
- two vertices are adjacent if connected by an edge
- edge is incident to a vertex if the vertex is one of the two vertices that the edge connects
- degree is number of edges
- directed graphs - in degree (edges in), out degree (edges out)
- path - sequence of vertices between to vertexes connected by edges
- length of path -- last node is length minus one so in the case of three nodes the first node is 0, second is 1, 3rd is 2 (length -1) so length = 3
- cycle - path that begins and ends at the same point
- simple path - path with no repeating vertices
- simple cycle - simple path plus the original point
- connectedness - connected if path between every single pair of verticies
- complete - an edge connecting every pair of vertices, not just a path
- adjacency list - better for less complete
- adjacency matrix - better for fuller graphs
- diameter of graph - from start to final state you are seeking (i.e. like solving a 2 x 2 Rubik's cube)

Adjacency Lists:
Used to represent a graph
Array - each element is a pointer to a linked list
Array is indexed by a vertex
Index arrays by verticies
Your array could be a hash table
For each vertex store it's neighbors

Array[a] = {b}
Array[b] = {a, c}
Array[c] = {a, b}

Undirected uses parentheses (I think)

So that would mean vertex a connects to b, b connects to a and c, c connects to a and b

http://www.youtube.com/watch?v=vfCo5A4HGKc
http://www.youtube.com/watch?v=s-CYnVz-uh4

Other Data Structures

Tries

Stack

Queue

Vector/ArrayLists

Array
Linked List

StringBuffer
default size is 16 characters
empty size is 72 bytes

Monday, March 03, 2014

Videos - Discrete Mathmematics and Linear Algebra

Discrete mathematics

Arsdigita 02 (Discrete Mathematics) Lecture 1/20
http://www.youtube.com/watch?v=h_9WjWENWV8

Arsdigita 02 (Discrete Mathematics) Lecture 2/20
http://www.youtube.com/watch?v=BrDto0heyaQ

Arsdigita 02 (Discrete Mathematics) Lecture 3/20
http://www.youtube.com/watch?v=t3XdRbPNtdg

Arsdigita 02 (Discrete Mathematics) Lecture 4/20
http://www.youtube.com/watch?v=J_vXRNMu1yQ

Lecture 5 not found

Arsdigita 02 (Discrete Mathematics) Lecture 6/20
http://www.youtube.com/watch?v=_FG9hhiZipo

Arsdigita 02 (Discrete Mathematics) Lecture 7/20
http://www.youtube.com/watch?v=uBKb1I70PhA

Arsdigita 02 (Discrete Mathematics) Lecture 8/20
http://www.youtube.com/watch?v=iT_Scp0hWWU

Arsdigita 02 (Discrete Mathematics) Lecture 9/20
http://www.youtube.com/watch?v=9C_ZD8Bqyjk

Arsdigita 02 (Discrete Mathematics) Lecture 10/20
http://www.youtube.com/watch?v=ZJqFHvBQthI

Arsdigita 02 (Discrete Mathematics) Lecture 11/20
http://www.youtube.com/watch?v=MLGTi0ewfBE

Arsdigita 02 (Discrete Mathematics) Lecture 12/20
http://www.youtube.com/watch?v=vWo892ut5Qo

Arsdigita 02 (Discrete Mathematics) Lecture 13/20
http://www.youtube.com/watch?v=0x_b_zPHy3c

Arsdigita 02 (Discrete Mathematics) Lecture 14/20
http://www.youtube.com/watch?v=ikRtC0FTv1k

Arsdigita 02 (Discrete Mathematics) Lecture 15/20
http://www.youtube.com/watch?v=oDEgQTxEjJ0

Arsdigita 02 (Discrete Mathematics) Lecture 16/20
http://www.youtube.com/watch?v=LzD4MqgGBJE

Arsdigita 02 (Discrete Mathematics) Lecture 17/20
http://www.youtube.com/watch?v=5gqQatmQvIc

Arsdigita 02 (Discrete Mathematics) Lecture 18/20
http://www.youtube.com/watch?v=WOZacrs5vT0

Arsdigita 02 (Discrete Mathematics) Lecture 19/20http://www.youtube.com/watch?v=z5vSAC9i3yo

Arsdigita 02 (Discrete Mathematics) Lecture 20/20
http://www.youtube.com/watch?v=Nt7JeGCZL5M

Linear Algebra

MIT - Linear Algebra 18.06

http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/

Sorting Algorithms

Some Notes on Sorting Algorithms...

Big O Complexity Cheat Sheet
http://bigocheatsheet.com/

Comparator Interface

When comparing two objects we'll be using the Comparator interface:
http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

Comparator takes two arguments: left and right. Implementation is typically:

left < right = -1
left > right = 1
left = right = 0

String implements the Comparable interface and the examples below use Strings.
http://docs.oracle.com/javase/7/docs/api/java/lang/String.html

So you can compare strings like this:

String s1 = "A";
String s2 = "B";
s1.compareTo(s2);

A < B = -1
A > B = 1
A = B = 0

This could be more generic than using Strings but using a particular data type makes the examples shorter for the moment.

Terminology

Stability: When two items with the same value stay in the same relative position after sort

In Place: Whether or not algorithm uses separate data structure to sort

Bubble Sort

Implementation:

- start at the beginning of the list
- compare the first and second items
- if the first is bigger than the second, swap
- repeat with each subsequent pair until end of list
- biggest item will be at the bottom
- start again at the beginning of the list and skip the last item as already sorted
- continue starting over at beginning of list and skipping already sorted items until all items sorted

Sample Code:

package com.radicalsoftware.example.sort;

import java.util.ArrayList;
import java.util.List;

public class BubbleSort {

   public static void main(String[] args) {

       ArrayList<String> list = new ArrayList<String>();
        list.add("Zero");
        list.add("Alpha");
        list.add("Cat");
        list.add("Boy");
        list.add("Dog");
        list.add("Rose");
        list.add("Lion");
        list.add("Fire");
        list.add("Dragon");
        list.add("Math");
        list.add("Logic");
       sort(list);

       for (String s: list){
           System.out.println(s);
       }

   }

   public static List<String> sort(List<String> list){

       assert list != null : "list cannot be null";

       int size = list.size();

       for (int pass = 1; pass < size; ++pass){
           for (int left = 0; left < (size - pass); ++left){
               int right = left + 1;
               if (list.get(left).compareTo(list.get(right)) > 0){
                   swap(list, left, right);
               }
           }
       }

       return list;

   }

   private static <T> void swap(List<T> list, int left, int right){
       T obj = list.get(left);
       list.set(left, list.get(right));
       list.set(right, obj);
   }


}

Selection Sort

- similar to sorting books on a book shelf
- unstable
- for each spot in the list
- scan all items in list to find the smallest (or largest) item
- put the smallest (or largest) item in that spot
- move to the next spot and repeat skipping already sorted items

Sample Code:

package com.radicalsoftware.sort;

import java.util.ArrayList;
import java.util.List;

public class SelectionSort {

    public static void main(String[] args) {

        ArrayList<String> list = new ArrayList<String>();
        list.add("Zero");
        list.add("Alpha");
        list.add("Cat");
        list.add("Boy");
        list.add("Dog");
        list.add("Rose");
        list.add("Lion");
        list.add("Fire");
        list.add("Dragon");
        list.add("Math");
        list.add("Logic");
        sort(list);

        for (String s: list){
            System.out.println(s);
        }


    }

    public static List<String> sort(List<String> list){

        assert list != null : "list cannot be null";

        int size = list.size();

        for (int slot = 0; slot < size-1; ++slot){

            int smallest = slot;

            //find the smallest in remaining items
            for (int checkSlot = slot + 1; checkSlot < size; ++checkSlot){
                if (list.get(slot).compareTo(list.get(checkSlot)) > 0){
                    smallest = checkSlot;
                    break;
                }
            }

            //if smallest does not equal current slot then swap
            if (smallest != slot)
                swap(list, smallest, slot);
        }

        return list;

    }

    private static <T> void swap(List<T> list, int left, int right){

        T obj = list.get(left);
        list.set(left, list.get(right));
        list.set(right, obj);

    }

}

Insertion Sort

- similar to sorting cards where you sort all the numbers within each suit
- create a new list and insert items into it
- use an iterator instead of an index
- insert the first item into the list
- use linked list so can scan and insert each item into correct relative location

Sample Code:

package com.radicalsoftware.sort;

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

public class InsertionSort {

    public static void main(String[] args) {

       ArrayList<String> list = new ArrayList<String>();

       list.add("Zero");
       list.add("Alpha");
       list.add("Cat");
       list.add("Boy");
       list.add("Dog");
       list.add("Rose");
       list.add("Lion");
       list.add("Fire");
       list.add("Dragon");
       list.add("Math");
       list.add("Logic");

       List<String> sortedList = sort(list);

       for (String s: sortedList){
           System.out.println(s);
       }


    }

    public static List<String> sort(List<String> list){

       assert list != null : "list cannot be null";

       final List<String> sortedList = new LinkedList<String>();

       for (String s: list){

           int slot = sortedList.size();

           while (slot > 0){
               if (s.compareTo(sortedList.get(slot - 1)) >= 0){
                   break;
               }
               --slot;
           }


           sortedList.add(slot, s);
       }


       return sortedList;

    }

}

Shell Sort

- breaks large lists into smaller lists
- based on concept of H-sorting - every Hth item is sorted relative to other items
- not stable

Sample Code:

package com.radicalsoftware.sort;

import java.util.ArrayList;
import java.util.List;

public class ShellSort {

    private static final int[] _increments = {1, 3, 5, 7, 11, 20};

    public static void main(String[] args) {

        ArrayList<String> list = new ArrayList<String>();

        list.add("Zero");
        list.add("Alpha");
        list.add("Cat");
        list.add("Boy");
        list.add("Dog");
        list.add("Rose");
        list.add("Lion");
        list.add("Fire");
        list.add("Dragon");
        list.add("Math");
        list.add("Logic");
        list.add("Money");
        list.add("Food");
        list.add("Stars");
        list.add("Moon");
        sort(list);

        for (String s: list){
            System.out.println(s);
        }


    }

    public static List<String> sort(List<String> list){

        assert list != null : "list cannot be null";

        for (int i = 0; i < _increments.length; i++){
            int increment = _increments[i];
            if (list.size() < increment * 2)
                break;
            hSort(list, increment);
        }

        return list;

    }

    private static void hSort(List<String> list, int increment){

        for (int startIndex = 0; startIndex < increment; ++startIndex){
            for (int i = startIndex + increment; i < list.size(); i += increment){

                String value = list.get(i);

                int j;

                for (j = i; j > startIndex; j -= increment){

                    String previousValue = list.get(j - increment);

                    if (value.compareTo(previousValue) >=0)
                        break;

                    list.set(j, previousValue);

                }

                list.set(j, value);

            }
        }
    }

}

Quick Sort

- uses recursion
- does the work first, then the recursion
- divide and conquer, recursively sorting smaller parts of list
- place an item in final position, smaller items left, larger items right
- divided into two parts (not necessarily two halves)
- not stable
- use quick sort until length of list is 10 or less and then use insertion sort

Best case: O(n Log(n)) -- partition element is middle element

Worst Case: O(n²) -- completely unbalanced

Implementation

- Choose partition item (last, mean of first, last and middle, etc.)
- indexes start at beginning and end (less the partition item) and advance towards each other
- left index stops when finds item larger than partitioning item
- right index stops when finds item smaller than partitioning item
- when both stop swap items
- point where indexes meet - insert partitioning item
- then sort the sublists to the right and left of the partitioning item

Sample Code:

package com.radicalsoftware.sort;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

    public static void main(String[] args) {

       ArrayList<String> list = new ArrayList<String>();
       list.add("Alpha");
       list.add("Zero");
       list.add("Cat");
       list.add("Boy");
       list.add("Dog");
       list.add("Rose");
       list.add("Lion");
       list.add("Fire");
       list.add("Dragon");
       list.add("Math");
       list.add("Logic");
       sort(list);

       for (String s: list){
           System.out.println(s);
       }


    }

    public static void sort(List<String> list){

       assert list != null : "list cannot be null";

       quicksort(list, 0, list.size()-1);

    }

    public static void quicksort(List<String> list, int startIndex, int endIndex){

       if (startIndex < 0 || endIndex >= list.size())
           return;

       if (endIndex <= startIndex)
           return;

       String value = list.get(endIndex);

       int partition = partition(list, value, startIndex, endIndex -1);

       if (list.get(partition).compareTo(value) < 0)
           ++partition;

       if (partition != endIndex)
           swap(list, partition, endIndex);

       //sort right and left of partition
       quicksort(list, startIndex, partition -1);
       quicksort(list, partition + 1, endIndex);

    }

    private static int partition(List<String> list, String value,
           int leftIndex, int rightIndex) {
       int left = leftIndex;
       int right = rightIndex;

       while (left < right){

           if(list.get(left).compareTo(value)< 0){
               ++left;
               continue;
           }

           if(list.get(right).compareTo(value)>=0){
               --right;
               continue;
           }

           swap(list, left, right);
           ++left;
       }

       return left;
    }

    private static void swap(List<String> list, int left, int right){
       String obj = list.get(left);
       list.set(left, list.get(right));
       list.set(right, obj);
    }
}

Merge Sort
- not in place

Implementation:

- divide the list in half recursively until you get to one item arrays
- merge each array together two at a time
-- pointer at the beginning of each two array merging
-- compare elements and put the smaller into a new array
-- move pointer of array you took element from +1
-- repeat for all elements
-- repeat for all arrays

package com.radicalsoftware.sort;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {

    public static void main(String[] args) {

       ArrayList<String> list = new ArrayList<String>();

       list.add("Zero");
       list.add("Alpha");
       list.add("Cat");
       list.add("Boy");
       list.add("Dog");
       list.add("Rose");
       list.add("Lion");
       list.add("Fire");
       list.add("Dragon");
       list.add("Math");
       list.add("Logic");
       list.add("Salmon");

       List<String> sortedList = sort(list);

       for (String s: sortedList){
           System.out.println(s);
       }
    }

    public static List<String> sort(List<String> list){

       assert list != null : "list cannot be null";

       return mergesort(list, 0, list.size()-1);

    }

    private static List<String> mergesort(List<String> list, int startIndex,
        int endIndex) {



       int middleIndex = (startIndex + endIndex)/2;

       if (startIndex < endIndex){

           List<String> left = mergesort(list, startIndex, middleIndex);
           List<String> right = mergesort(list, middleIndex + 1, endIndex);

           return merge(left, right);

       }

       List<String> mergedList = new ArrayList<String>();
       mergedList.add(list.get(startIndex));
       return mergedList;



    }

    private static List<String> merge(List<String> left, List<String> right) {


       List<String> mergedList = new ArrayList<String>();

       int rightIndex = 0;
       int leftIndex = 0;

       while(leftIndex < left.size() || rightIndex < right.size()){

           boolean rightHasMore = rightIndex < right.size();
           boolean leftHasMore = leftIndex < left.size();

           if (!rightHasMore ||
                (leftHasMore &&
                left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0)){
               mergedList.add(left.get(leftIndex));
               leftIndex++;
           }else{
               if(rightHasMore){
                   mergedList.add(right.get(rightIndex));
                   rightIndex++;
               }
           }


       }

       return mergedList;
    }


}

Heap Sort
- in place (uses less memory than mergesort which has to allocate additional storage)
- comparison based sort
- selection sort family
- slower than well implemented quick sort, but better worst case
- in place
- not stable

Implementation

An array viewed as a nearly complete binary tree (meaning a subsequent level is not started until the previous level is completely filled).

http://www.youtube.com/watch?v=B7hVxCmfPtM

Bucket, counting and radix sort:
http://www.youtube.com/watch?v=woTbZMli6z4

Bucket Sort
- stable sort
- range of keys can't be too big
- linear time

Counting Sort
- stable sort
- range of keys can't be too big
- linear time

Implementation:
- histogram
- indicies
- place

Radix sort
- stable
- only good when
- use counting sort trick on the least significant digit
- not in place
- linear time
- unlimited number of keys
- uses the stability of bucket sort and counting sort

Sunday, March 02, 2014

Logarithms

Logarithms are used to describe the complexity of algorithms and in public-key crytpography.

Logarithms are just exponents rearranged.

Let's take these variables:

T = Total
b = Base
e = exponent

Using an exponent we can say:

T = b^e

So let's assign numbers.

b =2
e = 3

2 x 2 x 2 = 8

Therefore

T = 8

The logarithm is just where the exponent (e) is the answer to the equation. In other words e is the exponent when applied to the base (b) that produces the total (T).

So we can rearrange the above formula like this:

e =log_b(T)

or

3 = log₂(8)

Since b = T^e we can also say:

e = log_b(b^e)

or

3 = log₂(2³)

And why do we care anyway? Ah. Because we can shorten up numbers to do calculations.

Because:

log_b(xy) = log_b(x) + log_b(y)

More on logarithm:
http://en.wikipedia.org/wiki/Logarithm

Saturday, March 01, 2014

IP (Internet Protocol)

IP (Internet Protocol) Notes

IP (Internet Protocol) sends data in packets called datagrams.
Routes packets between two points.
Points have addresses (IP Addresses)
Internet layer (2) of the TCP/IP model and the Network layer (3) of the OSI model.
IPv4 is the most widely used version at this time
IPv6 is starting to be used - more addresses available using IPv6

Internet Addresses

Every computer attached to IPv4 network has unique address
Part of the address defines the network and part defines the host
Subnet masks define which part of the address is the network and which part is the host

IP addresses can be dynamic or static and reassigned over time - so don't count on them remaining the same for a particular destination device

IPv4 - current version of IP most widely used
IPv6 - next version in use by some but not as common (only supported by Java 1.4 or later)

DNS is used to assign human-friendly domain names to IP addresses; domain names can remain constant when underlying IP addresses change

Addresses on internal networks are translated to external addresses using NAT.

IPv4Addresses:

IPv4 address is 4 byte number / 32 bits
Written in dotted quad format (111.111.111.111)
0.0 refers to host on same local network in source address (not used in destination)
MAC and IP addresses are not directly related
4.2 billion addresses
No encryption, authentication, QOS (Quality of Service) features

Address classes:

Address class determines part of address that pertains to the public network, the remainder indicates the host within that network

Class A address block includes all addresses associated with the first byte (e.g. 111.x.x.x)
Class B address block includes all addresses associated with first two bytes (111.111.x.x)
Class C address block includes all addresses associated with first three bytes (111.111.111.x)
Class D addresses are used for multicast groups
Class E addresses begin with five bits and are reserved for future extensions

Classless Inter-Domain Routing (CIDR)

Instead of classes uses 2 digit number indicating bits in network portion of address
Uses variable length subnet masks (VLSM)

2 digit numbers for classes:
Class A /8
Class B /16
Class C /24

http://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing

Unassigned Address Blocks Used on Internal Networks

10.x.x.x
172.16.x.x
172.31.x.x
192.168.x.x

Unassigned Loopback Address

127.x.x.x

host name will typically be localhost

Directed Broadcast

Host bits of address set to 1 (255)
x.x.x.255
Passed by routers
Sent to hosts with specified network address

Limited Broadcast

255.255.255.255 (all 1's)
Not passed by routers

IPv4 Packet:

Length is between 20-60 bytes.
Length greater than 20 means header has (optional header values) *
Payload contains up to 65,515 bytes.
All bits and bytes are big-endian.
Header checksum can only verify the header contents, not the payload.
Order is not guaranteed.

* Up to Java 5.0 options not supported - need to check later versions.

IPv4 Header:

4 bit version number: always 0100 (4) for IPv4; will be 0110 (6) for IPv6

4 bit header length: unsigned integer between 0 and 15 specifying number of 4 byte words in header.

1 byte type of service: No longer used. Most routers ignore.

2 byte datagram length: unsigned length of header + payload

2 byte ID: unique identification number which allows duplicate packets to be discarded.

3 bit flags: First is 0, second is 1 if datagram may be fragmented else 0, Third is 1 if more fragments else 0

13 bit fragment offset: identifies the position in datagram of the current fragment (i.e. this packet is part of a larger message that needs to be pieced back together and this field identifies position of this fragment in the message)

1 byte TTL (Time To Live): Number of nodes which datagram can pass before discarding; when discarded router sends back ICMP unreachable response. Protects against infinite loops.

1 byte Protocol: number between 0 and 255 identifying protocol (TCP, UDP, etc)

2 byte header checksum: 16-bit ones complement sum

4 byte source address: IP of sending node

4 byte destination address: IP where packet is being sent

Tabular representation of an IPv4 Header:

0	4	8	12	16	20	24	28	31
version	header length	type of service		datagram length
identification				flags	fragment offset
time-to-live (TTL)		protocol		header checksum
source address
destination address
options
payload

IPv6

IPv6 will be a 16 byte address / 128 bits
8 blocks of 4 hexadecimal digits (FEDC:BAA98:7654:3210:FEDC:BA98:7654:3210)
- Network: 48 bits
- Subnet: 16 bits
- Interface ID: 64 bits

Leading zeros not required
Double colon (1 at most) indicates multiple 0 blocks
FEDC:0000:0000:0000:00DC:0000:7076:0010 could be written as FEDC::DC:0:7076:10
In networks using v4 and v6 the last four bytes may be written in dotted notation
local host is 0:0:0:0:0:0:0:1 (or ::1)
0.0.0.0 always refers to original host when used as source,6 not destination
340 udecillion addresses
Authentication, encryption, QOS included

http://en.wikipedia.org/wiki/IPv4

IPv6 Header

4-bit version number
1 byte/8-bit traffic class: priority for QOS
20 bit flow label: QOS - special handling for packet
2 bytes/16 bits: payload length
1 byte/8 bit next header: next protocol in the payload (e.g. TCP, UDP, ICMP)
1 byte/8 bit hop limit: similar to TTL prevents recursive loops
16 byte/128 bit source address
16 byte/128 bit destination address

Tabular representation of an IPv6 Header:

0										1										2										3
0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1
Version (.5)				Traffic Class (1)								Flow Label (2.5)
Payload length (2)																Next Header (1)								Hop Limit (1)
source address (16)
destination address (16)

http://en.wikipedia.org/wiki/IPv6

IP Routing

Routers determine the best route to get packet to destination address

Other devices transmit network traffic but do not operate at the network layer.

Network Equipment:

Router:
Forwards traffic between networks
OSI Model Layer 3
http://en.wikipedia.org/wiki/Router_%28computing%29
http://compnetworking.about.com/od/hardwarenetworkgear/f/layer3switches.htm

Hub
Pass through - rebroadcasts traffic - no examination or management of traffic
OSI Model Layer 1
http://en.wikipedia.org/wiki/Ethernet_hub
http://compnetworking.about.com/cs/internetworking/g/bldef_hub.htm

Bridge
Inspects traffic and determines whether to forward or discard
OSI Model Layer 2
http://en.wikipedia.org/wiki/Bridging_%28networking%29
http://compnetworking.about.com/cs/internetworking/g/bldef_bridge.htm

Switch
Sends network to the specific destination device
OSI Model layer 2
http://en.wikipedia.org/wiki/Network_switch
http://compnetworking.about.com/od/hardwarenetworkgear/g/bldef_switch.htm

Potential Attacks

Fragmentation Attacks: http://en.wikipedia.org/wiki/IP_fragmentation_attacks

Related

Lots of good address calculations:

https://erikberg.com/notes/networks.html

Sources:

Java Network Programming
Elliott Rusty Harold
O'Reilly

Sans Technology Institute - class notes
Security 401: SANS Security Essentials Bootcamp Style

Well Known TCP and UDP Ports

Most people involved in any sort of network connectivity or monitoring are familiar with these well known ports. I'm just listing them here as a reference when needed.

TCP is called reliable because it sends a response confirming transmission.

UDP is called unreliable because it is asynchronous. This is not synonymous with not useful however verification of transmission can be done at the application layer and in some cases with repetitive data or otherwise verification of transmission is not as critical as speed or other factors.

echo	7	TCP/UDP
discard	9	TCP/UDP
daytime	13	TCP/UDP
FTP data	20	TCP
FTP	21	TCP
SSH	22	TCP
Telnet	23	TCP
SMTP	25	TCP
time	37	TCP/UDP
whois	43	TCP
finger	79	TCP
HTTP	80	TCP
POP3	110	TCP
NNTP	119	TCP
IMAP	143	TCP
RMI Registry	1099	TCP

Teri Radichel - Software Programmer and System Architect - Cloud + Security

Thursday, March 06, 2014

Tuesday, March 04, 2014

Monday, March 03, 2014

Sunday, March 02, 2014

Saturday, March 01, 2014