Daily Algo: Primality of a given n

There are various questions one can ask while investigating primes algorithmically. One might be : Given a number n, is it prime ? A naive, brute force approach would be to iterate through all the numbers i from 0 to n-1, and test if n%i ==0. However, this approach would be naive in the extreme, and a more efficient approach can be devised by noting a few points.

  1. 0 and 1 are not primes
  2. 2 is a prime. However, all multiples of 2 are not prime. Hence we can reduce the numbers we have to inspect by 50%.
  3. If a number m divides n, then n/m also divides n, and n/m <=m or vice-versa. Hence all we need is to examine numbers up to sqrt(n) and no further.

The Python code is shown below:

In [15]: import math
def isPrime(n):
    if n <= 1 or n%2==0: return False 
    if n==2: return True
    ulim = int(math.sqrt(n))+1
    for i in range(3,ulim+1,2):
        if n%i ==0:
            return False
    return True

In [16]: isPrime(6767)
Out[16]: False
In [17]: isPrime(62417)
Out[17]: True

The code is available for download here : primes.py

Depth First Search


The goal of Depth First Search is to search as ‘deep’ into the graph as possible, which is opposed to Breadth First Search which is to search as ‘wide’ as possible. In DFS, edges are explored out of the most recently discovered vertex v that has unexplored edges out of it. When all of v’s edges have been explored, the search “backtracks” to explore other edges leaving the source vertex from which v was discovered. This process is continued until all the vertices reachable from the original source vertex have been discovered. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source. This process is repeated until all vertices have been discovered.
Unlike BFS, where the predecessor subgraph forms a tree, the predecessor subgraph formed by a DFS may be composed of several trees to form a DFS forest. This is because the search may be repeated from multiple sources.


As in BFS, vertices are colored during ths search to indicate their state. Each vertex is initially white, is grayed when it is discovered in the search and blackened when finished, i.e. when it’s adjacency list/neighbor set has been examined completely. This guarantees that each vertex ends up in exactly one depth-first tree so that these trees are disjoint.
Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex v has 2 timestamps: the 1st timestamp disc[v] records when v is first discovered and grayed, and the 2nd timestamp fin[v] records when the search finishes examining v’s adjacency list and blackens v.


The pseudocode is as follows:

1 for each vertex u in V[G]
2      do color[u] <--- WHITE
3           pred[u] <--- NULL
4 time <--- 0
5  for each vertex u in V[G]
6        do if color[u] == WHITE
7             then DFS-VISIT(u)

1 color[u] <--- WHITE  // White vertex u has just been discovered.
2 time <--- time + 1
3 disc[u] <-- time
4 for each v in Adj[u]     // Explore edge (u,v)
5       do if color[v] == WHITE
6       then pred[v] <--- u
7               DFS-VISIT(v)
8 color[u] <-- BLACK     // Blacken u; it is finished
9 fin[u] <--- time <--- time +1


Total running time is: θ(V+E). DFS runs linear in the size of the adjacency list representation of the graph G.

Binary Search Trees


A binary search tree is a binary tree whose keys satisfy the binary search tree property:
Let x be a node in the BST.
If y is a node in the left subtree of x, then key[y] <= key[x].
If y is a node in the right subtree of x then key[y] >= key[x].

Basic operations on a binary search tree (BST) take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in
O(lg n) worst-case time.
If the tree is a linear chain of n nodes, the same operations take O(n) worst case time. The expected height of a randomly built BST is O(lg n), so that basic dynamic set operations on such a tree take θ(lg n) time on average. There are variations of BSTs whose worst-case performance can be guaranteed to be good – red-black and B-trees are 2 such examples.

Basic operations on BSTs include:

The BST property allows us to print out all the keys in 3 different ways:

  1. InOrder Tree Walk – the key of the root of a subtree is printed between the values in its left subtree and those in its right subtree – LPR
  2. PreOrder Tree walk – root is printed before values in either subtree
  3. PostOrder Treee walk – root is printed after values in its subtrees.

It takes θ(n) time to walk an n -node binary tree.

Querying a binary search tree


We wishto search for a node with a given key in a BST. Given a pointer to the root of the tree and a key k, TREE_SEARCH returns a pointer to a node with key k if one exists, else it returns NULL. The search begins at the root and moves downward in the tree. For each node x it encounters, it compares the key k with key[x]. if the 2 keys are equal, the search terminates. If k < key[x] the search continues in the left subtree, else it continues in the right subtree. The running time of TREE_SEARCH is O(h), where h is the height of the tree.

1 if x==NULL or k=key[x]
2    then return x
3 if k < key[x]
4    then return TREE_SEARCH(left[x],k)
5    else return TREE_SEARCH(right[x],k)

1 while x!=NULL && k != key[x]
2   do if k < key[x]
3      then x <-- left[x]
4      else x <-- right[x]
5 return x

Maximum and Minimum

A minimum can always be found by following left child pointers down from the rroot until a NULL is reached :

1 while left[x] != NULL
2  do x <--- left[x]
3 return x

The pseudo-code for TREE_MAXIMUM is symmetric:

1 while right[x] != NULL
2  do x <--- right[x]
3 return x

Both of these procedures run in O(h) time.

SuCcessor and predecessoR

It is sometimes important to be able to find the successor to a node in the sorted order determined by an inorder tree walk. There are 2 cases:

  1. If the right subtree of node x is nonempty, then the successor of x is the leftmost node in the right subtree, given by TREE_MINIMUM(right[x]).
  2. If the right subtree of x is empty, and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.
1 if right[x] != NULL
2   then return TREE_MINIMUM(right[x])
3 y <-- p[x]
4 while y!=NULL && x=right[y]
5      do x <--- y
6         y <--- p[y]
7 return y

TREE_PREDECESSOR is symmetric to TREE_SUCCESSOR and both run in time O(h),

Insertion and Deletion


The TREE_INSERT procedure works as follows – walk down the tree from the root, choosing the left or right child until we find an appropriate leaf node from which to hang the new node. Hence if our new node is z, for each node x if key[z] < key [x], we know that z must hang somewhere off the left subtree of x, and set x as left[x] and as right[x] if NOT.
When we reach a leaf node we have found the node y to hang off and we assign this node y as parent[z]. We then determine if key[z] < key[y]. If so, then z becomes left[y] and if not, it becomes right[y].

1 y <--- NULL
2 x <--- root[T]
3 while x !=NULL
4  do y <-- x
5     if key[z] < key[x]
6     then x <--- left[x]
7     else x <--- right[x]
8 parent[z] <--- y        //At this point y=parent[x] from loop above
9 if y == NULL
10   then root[T] <--- z
11   else if key[z] < key[y]
12        then left[y] <--- z
13        else right[y] <--- z


There are 3 cases to consider when deleting a node z from a BST.

  1. Node z is a leaf node and has no children In this case we modify parent[z] to replace z as its child with NULL.
  2. Node z has only 1 child. In this case we “splice out” z by making a new link between child[z] and parent[z].
  3. Node z has 2 children. In this case we splice out z ‘s successor y, which has no left child (else it wouldn’t be the successor) and replace z ‘s key and satellite data with y ‘s key and satellite data.
1 if left[z]==NULL or right[z]==NULL // Cases 1 && 2
2     then y <--- z                     // Cases 1 && 2
3     else y <--- TREE_SUCCESSOR(z)     // Case 3
4 if left[y] != NULL                    // Lines 4-6 set x to non-NULL child of y, or NULL
5     then x <--- left[y]               // if y has no children 
6     else x <--- right[y]
7 if x != NULL                          // Line 7-13 splice out y
8    then parent[x] <--- parent[y]
9 if parent[y]==NULL                    // y is root,splice it out and set its child as
10   then root[T] <--- x                // root
11   else if y==left[parent[y]]          // If y is the left child of its parent, 
12         then left[parent[y]]  <--- x // splice it out and replace it with it's child x
13         else right[parent[y]] <--- x // else replace the right child of y's parent  
14 if y != z                             // In lines 14-16, if the successor of z y was the
15    then key[z] <--- key[y]           // node spliced out, replace z's key and data with
16       copy y's satellite data into z // that of y
17 return y 

Both insertion and deletion procedures run in O(h) time on a tree of height h.
References :