Algorithms Notes – Insertion Sort

insertion-sort-example-300px

Animation depicting insertion sort

The following is the source code for insertion sort:

for i = 1 to length(A) - 1
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j - 1
    end while
    A[j+1] = x
 end for

Here is an implementation in C++ from Weiss’s book:

template void Insertion_Sort(Etype A[], const unsigned int N)
{
Etype Tmp;

A[0] = Min_Val();
for (int P = 0; P <= N; P++)
{
Tmp = A[P];
for (int j = P; Tmp < A[j-1]; j–)
A[j] = A[j-1];
A[j] = Tmp;
}
}
[/sourcecode]

Analysis:

Since it has nested loops which take at most n iterations, insertion sort is \mathcal{O}(n^2). This is a tight bound (a reverse order array as input can achieve this bound). To calculate the average case:

\sum_{P = 2}^{n} = 2 + 3 + ... + n = \Theta(n^2).

Algorithms Notes – Binary Trees

720px-binary_search_tree-svg1

A binary tree.

Def: Let T be a tree such that no node in T has more than two children. T is referred to as a binary tree.

A binary tree effectively consists of a root r and two subtrees T_{L} and T_{R}, any (or both) of which could be empty.

Since we already know the maximum number of children each node in a binary tree can have, we can implement it in a way that is very simple in comparison to the implementation of a general tree. Just store pointers for the two children in every node.

 

struct Tree_Node
{
    Element_Type Element;
    Tree_Node* Left_Child;
    Tree_Node* Right_Child;
};

Def: Let T be a binary tree such that each node has either zero or exactly two children. T is called a full binary tree.

Full Binary Tree

Full Binary Tree

Def: Let T be a binary tree such that every level of T except for possibly the last is completely filled and all nodes are as far-left as possible. T is called a complete binary tree.

Complete Binary Tree

Complete Binary Tree

 

Algorithms Notes – Implementing Trees

The simplest way to implement a tree would be something like

struct Tree_Node
{
    Element_Type Element;
    Tree_Node* Child_One;
    Tree_Node* Child_Two;
    ...
};

This approach has problems, though. To begin with, the number of children per node can vary greatly and is not known in advance, hence this causes a lot of space to be wasted. A more efficient way to implement a tree would be to store the children of each node in a linked list of nodes.

struct Tree_Node
{
    Element_Type Element;
    Tree_Node* Child_One;
    Tree_Node* Next_Sibling;
};
Tree implementation

Pictorial Representation of a tree implementation using the above-described method.

Algorithms Notes – Trees

720px-binary_search_tree-svg

Example of a tree. 8 is the root. 3 and 10 are children of 8. 1, 13, 4 and 7 are leaves. 10 is an ancestor of 13. 4 is a descendant of 3. 3 is also a descendant of 3 but not a proper descendant. 10 is an ancestor of 10 but not a proper ancestor.

 

Recursive Definition of a Tree:

Def: A tree is a collection of nodes. If the collection can be empty, in which case it is usually denoted as \Lambda. Otherwise, it consists of a node r, called the root, and zero or more (sub)-trees T_{1}, T_{2}, ... , T_{k} each of whose roots are connected by a directed edge to the r.

Def: Let r be the root of a tree with one or more subtrees connected to it. The root of any sub-tree connected to r is called a child of r.

Def: Let r_{2} be the root of a sub-tree and r_{1} be the root node the subtree is connected to. r_{1} is called the parent of r_{2}.

Recursive Definition of a Tree

Def: A node in a tree that has no children is referred to as a leaf of the tree.

Def: Let n_{1} and n_{2} be two nodes in a tree that have the same parent. n_{1} is called the sibling of n_{2} and vice versa.

Def: A sequence of nodes n_{1}, n_{2}, .... , n_{k} such that n_{i} is the parent of n_{i+1} for 1 \leq i \leq k is referred to as a path.

Def: The number of edges in a path is called the length of the path.

Assertions that have beautiful proofs which you should look up:

  • There is a path of length 0 from every node to itself in a tree.
  • In a tree, there is exactly one path from the root to each node.

Def: For any node, n in a tree, the depth of n_{i} is the length of the unique path from the root of the tree to n.

  • By definition, the depth of the root is 0.

Def: Let n be any node in a tree. The height of n is the length of of the longest path from n to a leaf.

  • By definition, all leaves have a height of 0.
  • The height of a tree is basically the height of the root.

Def: Let n_{1} and n_{2} be two nodes in a tree. If a path exists between n_{1} and n_{2} then n_{1} can be called an ancestor of n_{2}. If n_{1} \neq n_{2} then n_{1} is a proper ancestor of n_{2}.

Def: Let n_{1} and n_{2} be two nodes in a tree. If a path exists between n_{1} and n_{2} then n_{2} can be called a descendant of n_{1}. If n_{1} \neq n_{2} then n_{2} is a proper descendant of n_{1}.

tree

The Best Course I’ve Taken Yet

20120517

CS210 – Discrete Mathematics. Hands down the best course I have ever taken. I will argue my case from three different perspectives.

Discrete Mathematics as a Mathematics course

a.k.a Why Formal Math is good too, but Discrete Math is better.

I took both Discrete Mathematics and Introduction to Formal Mathematics in the same semester. I found Discrete Mathematics to be better. Why? It covers almost everything one learns in a formal mathematics course plus more exciting stuff! Formal mathematics covered proof-writing, set theory, cardinality, equivalence relations, functions and (very very) introductory group theory. Discrete Mathematics covered all of this except for the group theory part. However, it also covered introductory number theory, RSA Encryption (we missed that part, though. Due to cancellation of the last class), principles of counting and (the best and most exciting part) graph theory.

Discrete Mathematics as a Computer Science course

a.k.a Mathematics makes code fast and pretty.

Every Computer Scientist on the planet should take a course on discrete mathematics. It gives one the mathematical maturity needed for algorithm design, automata theory, data structures, computational complexity etc. On top of that, it helps one become a better programmer. It teaches one a way of thinking that enables one to write more efficient and, indeed, more beautiful code.

Discrete Mathematics as a Liberal Arts course

a.k.a One can’t argue with a sound mathematical proof

“Liberal arts and math? Lol, who is this nerd trying to kid.” I’m serious, though. To start with, Discrete Mathematics teaches logic. What’s better? It teaches quantified logic and proof writing. This helps one make better arguments and (more importantly) accept only claims backed with rational arguments, which helps one understand the world better.

Contemplations on Algorithmic Earth-Keeping

earthrise

Here’s an idea that came to me just I was about to sleep right now. Why not… computerize the earth? Create one huge planetary network?

*readers shouting* “Maybe you mean… the internet?”

I know. What I mean is something more centralized and more intelligent. I’ll give you an example. A very  simple one.

Stabilizing Climate Change

First, divide all of the land of the planet into (geographical, not political) regions and assign a node to each region in the global network. Now create a world-wide fund for forest-preservation and rehabilitation. Let’s create an algorithm like the following:

Input: Carbon contribution (= CO2 emmission – CO2 consumption) at each node

Output: Weight of each node which in this application is the percentage of the world-wide reforestation fund assigned to that node.

A smart algorithm designed for this kind of network will finally create the effective, highly organized and intelligently executed world-wide reforestation effort that is needed to save the planet right now. Regions with less fertile soil e.g the Persian Gulf will, of course, require more funds per tree than regions like Indus Plain but our theoretical algorithm is intelligent enough to consider all such factors.

Of course I have mention reforestation only just for the sake of simplicity. There is no reason not to extend this to automobile restrictions, industrial pollution regulations, mass transit funding, solar panel / wind farm subsidies etc.

World Humanitarian™ Algorithm

Input: “Disaster Reports” from every node. Quantified on a scale that is proportional to the number of people affected, land area affected, population density and demographics of the region. To be more general, the HDI of every node, the living standards, levels of oppression etc.

The algorithm analyses the urgency of the situation in case of any disaster or generally measures a quantified ‘prosperity’ property for the node. Then it does the following:

  • Publicizes donation requests on the nodes with higher prosperity for the nodes with critically low prosperity. In case of a disaster, also publicizes relief and volunteer requests.
  • Calculates amount of international development funding assigned by more prosperous nodes for less prosperous ones.
  • Creates economic simulations for best possible bail-out strategies.

Estimates of the number of relief workers

Global Smart Grid

Same concept at play. This time with energy exchange.

Maybe something like this could help our civilization reach Type 1 status on the Kardeshiv scale. That’s my two cents, anyway.

Algorithms Notes – Chapter 10

Obligatory Computer Science Comic

Depth-First Search – Analysis (continued)

White Path Theorem

Theorem: Let G be a directed or undirected graph on which a depth-first search is executed. Let u and v be two vertices in G. v is a descendant of u if and only if at the time u.d when the algorithm discovers u, there is a path from u to v that consists entirely of white vertices.

Proof: Since this is an if-and-only-if theorem, we must prove both sides of the implication.

Proof of \Rightarrow: Suppose v is a descendant of u in the depth-first forest. By corollary 1 (from the last chapter), we know that u.d < v.d. So v is not discovered before u is discovered, hence v is white at time u.d. Since v can be any descendant of u, all vertices in the unique simple path from u to v in the depth-first forest must be white at time u.d. In the case that v = u, the path just contains the vertex u which is still white when the value of u.d is set by the algorithm.

Proof of \Leftarrow: Suppose there is a path containing only white vertices from u to v at time u.d and v does not become a descendant of u. Let v be the closest non-descendant vertex to u in the path. Let w be the predecessor of v. Since v is the closest non-descendant vertex to u, w is a descendant of u. By corollary 1 from the last chapter, we know that w.f \le u.f (and w.f = u.f if u and w are the same vertex). Since v is a descendant of w, it must be discovered after u is discovered and before the adjacency list scan of w is finished. Hence, it must be true that u.d < v.d < w.f < u.f. The parenthesis theorem then implies that [v.d, v.f] is contained entirely within the interval [u.d, u.f]. By corollary 1, this means that v is still a descendant of u. \square

Note: A depth-first forest is often denoted by G_{\pi} by convention. Just like we denote a graph as G and vertices as u and v. Not necessary at all, just a convention.

math_paper

xkcd/410

G_{\pi} Edge Classification

We can use a depth-first forest to classify edges into four types:

  1. Tree Edges – Let v be a vertex discovered by a DFS. If v was first discovered by exploring any edge (u, v) then that edge is a tree edge. (i.e the edges that are part of a depth-first forest G_{\pi}.
  2. Back Edges – Let u and v be vertices in a depth-first tree such that u is a descendant of v. An edge (u, v) connecting u to its ancestor v is a back-edge. In a directed graph, a self-loop is also a back-edge.
  3. Forward Edges – Non-tree edges that connect two vertices u and v such that v is a descendant of u in a depth-first tree.
  4. Cross Edges – All edges that are not tree edges, back edges or forward edges (i.e an edge that is not in any of the above three categories is a cross edge).

Let (u, v) be an edge explored by the depth-first search algorithm. The color of the vertex v indicates the type of edge (u, v) is:

  1. White – tree edge
  2. Gray – back edge
  3. Black – forward or cross edge

Note: I do not understand the proof of this relation between vertex color and type of edge properly myself. The book doesn’t deal with it very formally, in my opinion. Anyway, onto the next theorem.

Theorem 2: Let G be any undirected graph. In a depth-first search of G, every edge of G is either a tree edge or a back edge.

Proof: Let (u, v) be any edge in G. Suppose u.d < v.d (without loss of generality). Then before the algorithm finishes u, it must discover and finish v while the color of u remains gray, since v is in the adjacency list of u. If the direction of the edge (u, v) is from u to v the first time the algorithm explores it, then the vertex v has not been discovered before that time. This is true because if it had been discovered previously, the algorithm would have already explored the edge (u,v ) in the direction from v to u.

Since, at the time (u, v) is first explored, v is undiscovered, its color is white. Hence (u, v) becomes a tree edge. If the algorithm explores (u, v) first in the direction from v to u instead then, since the color of u is gray, the edge (u, v) becomes a back edge. \square

Algorithms Notes – Chapter 9

goto

xkcd/292

Depth-First Search – Analysis

Time Complexity

Let G = (V, E) be the graph on which the Depth-First Search algorithm gets executed. Not taking into account the time taken by DFS-VISIT, the time taken by DFS is essentially of the same order as the time taken by both the for loops in DFS. Since both for loops have time $latex\Theta(|V|)$, DFS takes time \Theta(|V|) if one excludes the calls to DFS-VISIT. Since DFS-VISIT is called exactly once for each vertex in the graph G, the for loop in DFS-VISIT executes Adj[v] times for any vertex v on which it is run. Hence (by the handshaking lemma) the total time for running DFS-VISIT on all vertices in G is \sum_{v \in V} = \Theta (|E|). Hence the time complexity of the algorithm is \Theta (|V| + |E|).

Paranthesis Theorem

Theorem: Let G = (V, E) be the graph on which the Depth-First Search algorithm gets executed. Let u and v be any two vertices in G. Exactly one of the following three conditions must hold:

  1. The intervals [u.d, u.f] and [v.d, v.f] are entirely disjoint and neither u nor v are descendants of each other in the depth-first forest.
  2. The interval [u.d, u.f] is contained entirely in the interval [v.d, v.f] and u is a descendant of v in a depth-first tree.
  3. The interval [v.d, v.f] is contained entirely in the interval [u.d, u.f] and v is a descendant of u in a depth-first tree.

Proof: Proof by case analysis. We begin with the case when u.d < v.d. There can be two subcases.

Subcase 1: v.d < u.f. This means that v was discovered when u was gray and, hence, v is a descendant of u. Since v was discovered after you, its adjacency list scan has to be completed before the search returns to scanning the adjacency list of u. Hence it must be true that v.f < u.f. In other words, case 2 of the theorem is true in this subcase.

Subcase 2: u.f < v.d. Since, in a depth first search, w.d < w.f for any vertex w searched by the algorithm, it must be true that u.d < u.f < v.d < v.f. This means that the intervals [u.d, u.f] and [v.d, v.f] are disjoint. Since the intervals are disjoint, neither of the two vertices was discovered while the other was gray. In other words, neither vertex is a descendant of the other.

The proof for the case when v.d < u.d is similar. \square

Corollary 1: Let v and u be any two vertices in a depth-first forest of a graph G. v is a proper descendant of u if and only if u.d < v.d < v.f < u.f.

Proof: Immediate from the paranthesis theorem. (Once again, don’t blame me for lack of explanation. Blame the textbook Introduction to Algorithms 3rd Edition by Cormen et al.).

Algorithms Notes – Chapter 8

dfs

xkcd/761

Depth-First Search

One thing that is important to understand is that the Breadth-First Search algorithm generates a tree as it searches a graph (for a proof of this, refer to Lemma 22.6 in Chapter 22 of Introduction to Algorithms 3rd Edition by Cormen et al.). This is called a Breadth-First Tree. A Depth-First Search, on the other hand, does not generate a single tree. Instead, it generates several trees (called depth-first trees) and creates a depth-first forest.

Check this animation out to get a general understand of how a depth-first search works.

Here is the pseudocode for the Depth-First Search algorithm:


DFS(G)
    for each vertex u ϵ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u ϵ G.V
        if u.color = WHITE
            DFS-VISIT(G, u)

DFS-VISIT(G, u)
    time = time + 1    // white vertex discovered
    u.d = time
    u.color = GRAY
    for each v ϵ G.Adj[u]  // explore edge (u, v)
        if v.color == WHITE
            v.π = u
            DFS-VISIT(G, v)
    u.color = BLACK       // u is finished. Mark it black.
    time = time + 1
    u.f = time

Notation

Most of the notation is very similar to that used in the Breadth-First Search pseudocode with one key difference. Let v be a vertex in G. The property v.d does not store the distance from the source, unlike in BFS. Instead it, along with the new property v.f store time-stamps.

  • v.d stores the time when the vertex v is discovered by the algorithm
  • v.f stores the time when the algorithm finishes scanning the adjacency list of v and sets its color to black.
  • The global variable time is used for the above described time-stamping.

The following two GIFs provide a good comparison between a BFS and a DFS.

dfs

bfs