Blah, blah, blah. The big stuff is here. Challenging your mind with all sorts of knowledges and whatnot. When I first started computer science I came across this book Algorithms in a Nutshell and was very curious about the topics presented. It was much easier for me to grasp these concepts in comparison to Introduction to Algorithms, 3rd ed., which in the begining was suggested and much of a stretch for my feeble knolwedge base to grasp at the time. AIAN was a good concept starter for anyone who wants to learn more about algorithms, and then there are more comprehesive literatures for more advanced folks. Steven Skiena has a wonderful book, The Algorithm Design Manual, that I liked so much I bought the hardcopy of it. There are many others, and I could go on and on about books, but I wanted to extend understanding of concepts in AIAN.

The Domains

Sorting Algorithms

Insertion Sort

Insertion sort is the ‘one card at a time’ sort. It is good for small data sets (< 25 elements) and things that are nearly sorted.

void sort(int[] arr){
    for(int i = 1; i < arr.length; i++){
        insert(arr, i, arr[i]);
    }
}

void insert(int[] arr, int pos, int val){
    int i = pos - 1;
    while(i >= 0 && arr[i] > val){
        arr[i+1] = arr[i];
        i = i - 1;
        arr[i + 1] = val;
    }
}

Median Sort

void sort(int[] arr) {
    medianSort(arr, 0, arr.length - 1 );
}

void medianSort(int [] arr, int left, int right) {
    if (left < right) {
        //find median value
        int me = findMedian(arr);   // random, scan, or last element
        int mid = (right + left)/2;
        swap(arr, mid, me);
        for(int i = left; i < mid - 1; i++) {
            if(arr[i] > arr[mid]){
                for(int j = mid + 1; j < right; j++){
                    if (arr[j] <= arr[mid]){
                        swap(arr, i, j);
                        break; // this might not break the for loop
                    }
                }
            }
        }
        medianSort(arr, left, mid - 1);
        medianSort(arr, mid, right);
    }
}

Quicksort

Best: O(n log n), Worst: O(n^2), Average: O(n log n) Keywords: Recursion, Divide and Conquer, Array

void sort(int [] arr){
    quickSort(arr, 0, arr.length - 1);
}

void quickSort(int [] arr, int left, int right) {
    if (left < right) {
        int pi = partition(arr, left, right);
        quickSort(arr, left, pi - 1);
        quickSort(arr, pi + 1, right);
    }
}

int partition(int arr[], int left, int right) {
    int p = selectPivot( left, right);
    swap(arr, p, right);
    int store = left;
    for (int i = left; i < right; i++){
        if (arr[i] <= arr[right]){
            swap(arr, i, store);
            store++;
        }
    }
    swap(arr, store, right);
    return store;
}
int selectPivot(int left, int right) {
    // for now I just select the middle value, but you can also select
    // rightmost value, leftmost value, or some median of all values
    return (left + right)/2;
}
void swap(int [] arr, int left, right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

Searching Algorithms

Also called linear search, it is your basic brute force search of iterating through each element of a container until finding the a match or exiting.

boolean search(int[] arr, int t){
    for (int i = 0; i < arr.length; i++){
        if(arr[i] == t){
            return true;
        }
    }
    return false;
}

Classic Divide and Conquer method for finding an item in a collection. Input needs to be ordered completely. Output is true or false depending on contents of collection.

boolean binarySearch(int[] arr, int t) {
    int low = 0; 
    int high = arr.length - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(t == arr[mid]){
            return true;
        }
        else if (t < arr[mid]) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return false;
}

Searching within a hash table for a specific value. Best: O(1), Worst: O(n), Average: O(1) Keywords: Array, Hash

// loading the table
List<Integer>[] loadTable(int [] arr) {
    List<Integer>[] hashTbl = new List<>[arr.length];
    for(int i = 0; i < arr.length; i++) {
        int h = hash(arr[i]);
        if(hashTbl[h].isEmpty()) {
            hashTbl[h] = new ArrayList<>();
        }
        hashTbl[h].add(arr[i]);
    }
    return hashTbl;
}

//searching the table
boolean search(List<Integer>[] hashTbl, int t) {
    int h = hash(t);
    List<Integer> list = hashTbl[h];
    if(list.isEmpty()){
        return false;
    }
    if(list.contains(t)) {
        return true;
    }
    return false;
}
int hash(int n) {
    int h = n.hashCode();
    if (h < 0) {
        h = 0 - h;  //make positive
    }
    return h % tableSize;   //table size needs to be global
}

Best: O(log n), Worst: O(log n), Average: O(log n) Keywords: Binary Tree, Recursion

Basic Search

//Node
class Node {
    int data;
    Node left, right;
}
//Tree
class BinaryTree {
    Node root;
}
Node search(int k) {
    Node p = root;
    while (p != null) {
        int cmp = compare(k, p.data);
        if (cmp == 0) {
            return p;
        }
        else if (cmp < 0) {
            p = p.left;
        }
        else {
            p = p.right;
        }
    }
    // not found
    return null;
}
int compare(int left, int right) {
    return left - right;
}

Graph Algorithms

Graph Data Structure

enum VertextColor{ White, Gray, Black};
enum EdgeType{Tree, Backward, Forward, Cross};
// for vertex u, stores information about (v,w) where edge(u,v) has the 
// designated edge weight w
public IntegerPair{
    public int u;
    public int v;
    public IntegerPair(int u, int v){
        this.u = u;
        this.v = v;
    }
    //for comparable
    public int compareTo(Object obj){
        IntegerPair that = (IntegerPair) obj;
        int a = this.v;
        int b = that.v;
        if (a < b) return 1;
        if (a > b) return -1;
        return 0;
    }
}
public Graph{
    //attributes
    private boolean directed;
    private Map<Integer, List<IntegerPair>> vertexList;
    //methods
    public Graph(){}
    public Graph(int n, bool directed){}
    public Graph(int n){}
    void load(File file){}
    boolean directed(){}
    int numVerticies(){}
    boolean isEdge(int u, int v){}
    boolean isEdge(int u, int v, int weight){}
    void addEdge(int u, int v){}
    void addEdge(int u, int v, int weight){}
    boolean removeEdge(int u, int v){}
    List<IntegerPair> getEdges(int u){}

}

Useful in backtracking problems and pathfinding.

int[] d;
int[] f;
int[] pred;
VertextColor[] color;
Graph G;    //possible to complete these methods without global
int counter;
void depthFirstSearch(Graph G, int s){
    d = new int[G.numVertices()];
    f = new int[G.numVertices()];
    pred = new int[G.numVertices()];
    color = new VertextColor[G.numVertices()];
    // setup
    for (int v = 0; v < G.numVertices(); v++){
        d[v] = f[v] = pred[v] = - 1;
        color[v] = VertextColor.White;
    }
    // begin recursion
    counter = 0;
    dfsVisit(s);
    // cleanup any stragglers
    for (int v = 0; v < G.numVertices(); v++){
        if(color[v] == VertextColor.White){
            dfsVisit(v);
        }
    }
}
void dfs(int u){
    color[u] = VertextColor.Gray;
    d[u] = ++counter;
    for(IntegerPair v: G.getEdges(u)){
        if (color[v] == VertextColor.White){
            pred[v] = u;
            dfsVisit(v);
        }
    }
    color[u] = VertextColor.Black;  //visited
    f[u] = ++counter;
}

Non-backtracking graph algorithm for finding all edges connected to a node s. This search will not find disconnected sets. Complexity: Best - O(V + E), Worst - O(V + E), Average - O(V + E) Keywords: Graph, Array, Queue

int [] pred;
int [] dist;
VertextColor color; 
void breadthFirstSearch(Graph G, int s) {
    pred = new int[G.numVertices()];
    dist = new int[G.numVertices()];
    color = new VertextColor[G.numVertices()];
    for (int v = 0; v < G.numVertices(); v++) {
        pred[v] = -1;
        dist[v] = Integer.MAX_VALUE;   // infinity
        color[v] = VertextColor.White;
    }
    color[s] = VertextColor.Gray;
    dist[s] = 0;
    Queue<Integer> Q = new LinkedList<>();  //empty queue
    Q.add(s);
    while(!Q.isEmpty()) {
        int u = Q.element();
        List<IntegerPairs> edges = G.getEdges(u);
        for(int v = 0; v < edges.size(); v++) {
            if (color[v] == VertextColor.White) {
                dist[v] = dist[u] + 1;
                pred[v] = u;
                color[v] = VertextColor.Gray;
                Q.add(edges.get(v));
            }
        }
        Q.remove();
        color[u] = VertextColor.Black;
    }
}

Single-Source Shortest Path

Dijkstra’s Algorithm Priority Queue

  • Operates in a greedy fashion in order to find the shortest path in a graph between two nodes. Best: O((V + E) * log V), Worst: O((V + E) * log V), Average: O((V + E) * log V) Keywords: Weighted Directed Graph, Priority Queue, Binary Heap Array, Overflow
void singleSourceShortest(Graph G, int s) {
    Queue<IntegerPair> PQ = new PriorityQueue<>();
    //set queue
    for (int v = 0; v <= G.numVertices(); v++){
        dist[v] = Integer.MAX_VALUE;
        pred[v] = -1;
    }
    dist[s] = 0;
    for (int v = 0; v <= G.numVertices(); v++){
        PQ.add(new IntegerPair(v, dist[v]));
    }
    while(!PQ.isEmpty()) {
        IntegerPair u = PQ.get(0);
        List<IntegerPair> edges = G.getEdges(u);
        for(int v = 0; v < edges.size(); v++){
            int w = edges.get(v).v;
            int newLen = dist[u] + w;
            if(newLen < dist[v] && newLen >= 0) {
                decreaseKey(PQ, v, newLen);
                dist[v] = newLen;
                pred[v] = u;
            }
        }
    }
}
void decreaseKey(PriorityQueue<IntegerPair> pq, int v, int newLen){
    for (int i = 0; i < pq.size(); i++) {
        IntegerPair x = pq.get(i);
        if (x.u == v){
            pq.remove(i);
            pq.add(new IntegerPair(v, newLen));
            return ;
        }
    }
}

Dijkstra’s Algorithm Dense Graph

void singleSourceShortest(int n, int[][] weight, int s) {
    boolean[] visited = new boolean[n];
    for (int v = 0; v < n; v++) {
        dist[v] = Integer.MAX_VALUE;
        pred[v] = -1;
        visited[v] = false;    
    }
    dist[s] = 0;
    while (true) {
        //determine u whose dist[u] is smallest 
        //of unvisited vertices
        int u = -1;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < min) {
                    min = dist[i];
                    u = i;
                }
            }
        }
        if (u == -1) { break; }
        if (dist[u] == Integer.MAX_VALUE) {
            return;
        }
        vistited[u] = true;
        for(int v = 0; v < n; v++) {
            int w = weight[u][v];
            if (v == u) continue;
            int newLen = dist[u] + w;
            if (newLen < dist[v]) {
                dist[v] = newLen;
                prev[v] = u;
            }
        }
    }
}

Bellman-Ford Best: O(VE), Worst: O(VE), Average: O(V*E) Keywords: Weighted Graph, Shortest Path, Array, Overflow

void singleSourceShortest(Graph G, int s, int[] dist, int[] pred) {
    int n = G.numVertices();
    for(int i = 0; i < dist.length; i++) {
        dist[i] = Integer.MAX_VALUE;
        pred[i] = -1;
    }
    dist[s] = 0;
    // n - 1 passes
    for (int i = 1; i <= n; i++) {
        boolean failOnUpdate = (i == n);
        boolean leaveEarly = true;
    }
    for (int u = 0; u < n; u++) {
        List<IntegerPair> edges = G.getEdges(u);
        for (int i = 0; i < edges.size(); i++) {
            IntegerPair v = edges.get(i);
            int newLen = dist[u] + v.v;
            if (newLen < dist[v.u]) {
                if (failOnUpdate) {
                    throw "Graph has negative cycle";
                }
            } 
        }
    }
}

Path Finding in AI

Game Trees

Represents each possible combination as a graph and utilizes traversals to nodes as moves. With each user move, the AI can determine the best state to transition to.

public inteface GameState {
    boolean isDraw(){}
    boolean isWin(){}
    GameState copy(){}
    boolean equivalent(GameState other){}
}
public interface GameScore {
    int score(GameState state, Player player){}
}
public interface Player {
    int eval(GameState state){}
    void score(GameScore score){}
    List<GameMove> validMoves(GameState state){}
}
public interface GameMove {
    boolean isValid(GameState state){}
    boolean execute(GameState state){}
    boolean undo(GameState state){}
}

Search Trees

public inteface Node {
    List<Move> validMoves(){}
    void score(int n){}
    Node copy(){}
    boolean equivalent(Node node){}
    Object key(){}
    Object storedData(Object object){}
    Object storedData(){}
}
public interface Move {
    boolean isValid(Node node){}
    boolean execute(Node node){}
    boolean undo(Node node){}
}
public inteface NodeSet {
    boolean isEmpty(){}
    int size(){}
    Node contains(Node node){}
    Node remove(Node node){}
    void insert(Node node){}
    Iterator<Node> iterator(){}
}
public Solution {
    final Node initial;
    final Node goal;
    List<Move> moves(){}
    boolean succeeded(){}
    String toString(){}
}

Depth-First Search

Best: O(b*d), Worst: O(b^d), Average: O(b^d) Keywords: Stack, Backtracking, Set

String search(initial, goal) {
    if (initial == goal) {
        return "Solution";
    }
    intial.depth = 0;
    open = new Stack<>();
    closed = new Set<>();
    insert(open, copy(initial));
    while (!open.isEmpty()) {
        Node n = open.pop();
        closed.insert(n);
        for (Move m: n.moves()) {
            Node next = n.check(m); //state when playing m at n
            if (!closed.contains(next)) {
                next.depth = n.depth + 1;
                if (next == goal) {
                    return "Solution";
                }
                if (next.depth < maxDepth) {
                    insert(open, next);
                }
            }
        }
        return "No Solution";
    }
}

Network Flow Algorithms

Maximum Flow

Computes the maximum flow between two vertices given a capacity constraint for all directed edges. This is FORD-FULKERSON algorithm. Best: O(Emf), Worst: O(Emf), Average: O(E*mf) Keywords: Weighted Directed Graph, Greedy, Array

void compute(Graph G) {
    // use a queue
    while(!paths.isEmpty()) {
        processPath(paths(0));
    }
}
void processPath(Node n){
    //todo
}

Computational Geometry

Convex Hull Scan

List<Integer> convexHull(int[][] P){
    //todo
}
// highlight template