Terence Schumacher
Menu

Algorithms in a Nutshell

4 min read

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.

{% highlight java %} 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; } } {% endhighlight %}

Median Sort

{% highlight java %} 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); } } {% endhighlight %}

Quicksort

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

{% highlight java %} 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; } {% endhighlight %}

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.

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

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.

{% highlight java %}

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; }

{% endhighlight %}

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

{% highlight java %}

// loading the table List[] loadTable(int [] arr) { List[] 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[] hashTbl, int t) { int h = hash(t); List 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 }

{% endhighlight %}

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

Basic Search {% highlight java %} //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; } {% endhighlight %}

Graph Algorithms

Graph Data Structure

{% highlight java %} 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> 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 getEdges(int u){}

} {% endhighlight%}

Useful in backtracking problems and pathfinding.

{% highlight java %} 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; }

{% endhighlight %}

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

{% highlight java %} 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 Q = new LinkedList<>(); //empty queue Q.add(s); while(!Q.isEmpty()) { int u = Q.element(); List 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; } }

{% endhighlight %}

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

{% highlight java %}

void singleSourceShortest(Graph G, int s) { Queue 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 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 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 ; } } } {% endhighlight %}

Dijkstra’s Algorithm Dense Graph {% highlight java %} 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; } } } } {% endhighlight %}

Bellman-Ford Best: O(VE), Worst: O(VE), Average: O(V*E) Keywords: Weighted Graph, Shortest Path, Array, Overflow {% highlight java %} 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 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”; } } } } } {% endhighlight %}

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.

{% highlight java %}

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 validMoves(GameState state){} } public interface GameMove { boolean isValid(GameState state){} boolean execute(GameState state){} boolean undo(GameState state){} }

{% endhighlight %}

Search Trees

{% highlight java %}

public inteface Node { List 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 iterator(){} } public Solution { final Node initial; final Node goal; List moves(){} boolean succeeded(){} String toString(){} }

{% endhighlight %}

Depth-First Search

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

{% highlight java %} 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”; } } {% endhighlight %}

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

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

{% endhighlight %}

Computational Geometry

Convex Hull Scan

{% highlight java %} List convexHull(int[][] P){ //todo } {% endhighlight %}

{% highlight java %} // highlight template {% endhighlight %}