9am

Archive for the ‘Algorithms’ Category

What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on September 16, 2010 at 9:49 pm
The previous post “What’s The Number” had a non-recursive implementation. Here is a recursive way of doing the same. It’s not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.
/*
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
*/
public static class TelNumber
{
private static char[][] KeyChars = new char[10][];
static TelNumber()
{
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
..
}
public static void PrintCombination(StringBuffer prefix, int[] tel_no)
{
int index = prefix.Count;
if (index >= tel_no.Length)
{
System.Console.Writeline(prefix);
return;
}
foreach(char c in KeyChars[tel_no[index]])
{
prefix.Add(c);
PrintCombination(prefix, tel_no);
prefix.RemoveLastChar();
}
}
Advertisements

Tree Traversal Without Recursion

In Algorithms, Programming on August 15, 2010 at 7:22 pm

Tree traversal without recursion is slightly tricky using a stack especially if we want to do it without keeping track of visit state explicitly. Searching online, I could not find a good implementation. So I decided to write my own using stacks. If you are looking for a non-recursive, non-stack implementation, read up on Morris Traversal, which is based on Threaded Trees.

The following logic is largely derived from Donald Knuth’s implementation in ‘Art Of Computer Programming – 2.3.1’

In Order Traversal.

void PrintInOrder(Node root)
{

Stack stack = new Stack();
Node p = root;
while (p != null)
{

stack.Push(p);
// Update p
p = p.Left;

while (p == null && !stack.IsEmpty())
{

p = stack.Pop();
System.Console.WritelLine(p);
p = p.Right;

}

}

}

Pre Order Traversal

void PrintPreOrder(Node root)
{

Stack stack = new Stack();
Node p = root;
while (p != null)
{

System.Console.Writeline(p);
if (p.Right != null) stack.Push(p.Right);

// Update p
p = p.Left;

if (p == null && !stack.IsEmpty())
{

p = stack.Pop();

}

}

}

Post Order Traversal

void PrintPostOrder(Node root)
{

Stack result = new Stack();
Stack stack = new Stack();
Node p = root;
while (p != null)
{

result.Push(p);
if (p.Left != null) stack.Push(p.Left);
p = p.Right;
if(p == null && !stack.IsEmpty())
{

p = stack.Pop();

}

}

while(!result.IsEmpty())
{

System.Console.Writeline(result.Pop());

}

}