If you found this article on the web I suppose you already know what a Priority Queue is . Of course it’s an abstract data type, that acts exactly like a queue, but additionally all the elements have priorities associated with them . So when you want to remove something from the Priority Queue, you will pull the highest priority element first .

To get better performance, we’ll going to implement the Priority Queue using a heap . Please follow the code comments:

pqueue.h

Continue reading

If you ever wondered how Credit Card Numbers, IMEI Numbers or Canadian Social Insurance Numbers are validated you can take a look at this Programming Praxis article . It’s all about a simple, tiny, patented (now public domain) algorithm invented by IBM’s computer scientist Hans Peter Luhn .

The validation is pretty simple, and works this way:

1. Given a number we will consider the last digit a check-digit .
2. Starting from the check digit backwards we will multiply by 2 every even digit .
3. We will sum all digits (both doubled and undoubled) .
4. If the sum is a multiple of 10 then the number is valid, else is invalid .

Example:

5 4 3 2 9 8 3 7 6
5 8 3 4 9 (1+6) 3 (1+4) 6 = 50 (which is a muliple of 10, thus the number is valid)

I’ve written the implementation of this simple algorithm using python 3.x . The solution can become rather elegant if we use the functional programming features that python offers us:

And the output:

Observations: Continue reading

1. Description

One of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the right result . The exact requirment:

Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.

Programming Praxis

The natural algorithm to resolve this exercise is stack-based :

The first step is to tokenize the expression .If the expression is “19 2.14 + 4.5 2 4.3 / – *” after the tokenization the resulting structure will be an array of operands and operators, for example an array of Strings {“19”, “2.14”, “+”, “4.5”, “2”, “4.3”, “/”, “-“, “*”} .
At the second step we iterate over the array of tokens .If the token:

  • Is an operand (number, variable) – we push in onto the stack .
  • Is an operator (we apriopri know the operator takes N arguments), we pop N values from the stack, we evaluate the operator with those values as input parameters, we push the result back onto the stack .
If the RPN expression is valid, after we apply the previous steps, the stack would contain only one value, which is the result of the calculation .

2. Implementation

I will implement the solutions for this challenge using three different languages: Scala, python and Java .

2.1 Scala Solution

And if we compile and run the above code: Continue reading

1. Algorithm Description

Insertion Sort is one of the simplest, but less effective, sorting algorithms . It works very similar to the way (us humans) sort a hard of playing cards:

1. At first none of our cards are sorted . So we start with an “empty” space in our hand were we are going to insert cards one at a time .
2. We take a card from our hand and we put it in the “special place” were we planned to keep our cards sorted . We do this for every card in our initial hand, until we finish them off .
3. Finding the right position for the insertion is not hard . At this point we can apply two tactics :

  • We compare the card we are planning to insert with all the cards that are already in sorted state O(n);
  • We use binary search to determine the right position (O(logn)) .

In our case that “special place” were we are going to insert cards one at a time, is not an additional array, but the array itself . We know for sure that an array of size 1 is always sorted, so we consider that first sorted sub-array, is the block composed by the first element .

For example, we want to sort the following array (with bold, are the elements already sorted):

8 0 3 11 5 -1 14 10 1 1 -2 Array is unsorted .
8 0 3 11 5 -1 14 10 1 1 -2 The first sorted block is {8} .
0 8 3 11 5 -1 14 10 1 1 -2 We compare {0} with {8} we move {0} at the new position, we shift {8} .
0 3 8 11 5 -1 14 10 1 1 -2 We compare {3} with {8}, {0}, we move {3} at the new position, we shift {8} .
0 3 8 11 5 -1 14 10 1 1 -2 We compare {11} with {8}, {11} remains at the same position .
0 3 5 8 11 -1 14 10 1 1 -2 We compare {5} with {11}, {8} and {3}, we move {5} at the new position, we shift {8}, {11} .
-1 0 3 5 8 11 14 10 1 1 -2 We compare {-1} with {11}, {8}, …, {0}, we move {-1} at the new position, we shift {0}, {3}, … {11} .
-1 0 3 5 8 11 14 10 1 1 -2 We compare {14} with {11}, we move {11} at the new position .
-1 0 3 5 8 10 11 14 1 1 -2 We compare {10} with {14}, {11}, {8}, we move {10} at the new position, we shift {11}, {14}.
-1 0 1 3 5 8 10 11 14 1 -2 We compare {1} with {14}, {11}, …, {0}, we move {1} at the new position, we shift {3}, {5}, …, {14} .
-1 0 1 1 3 5 8 10 11 14 -2 We compare {1} with {14}, {11}, …, {1}, we move {1} at the new position, we shift {3}, {5}, …, {14} .
-2 -1 0 1 1 3 5 8 10 11 14 We compare {-2} with {14}, {11}, …, {-1}, we move {-2} at the new position, we shift {-1}, {0}, …, {14} .

The pseudo-code for the algorithm can be easily written as follows:

2. Algorithm Implemenation in Java

The Java implementation of the algorithm is pretty straight-forward (follow the comments): Continue reading

1. Algorithm Description

In the last article I’ve described a recursive version of the Merge Sort Algorithm . Of course every recursive algorithm can be written in an iterative manner . So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion .

The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . During each pass the array is divided into smaller sub-arrays of a pseudo-fixed size (step) . Initially step is 1, but the value increases with every pass, as every adjacent sub-arrays are merged, thus step doubles .

Example.:

0. We consider an array with size < = 1 sorted .
1. The array that needs to be sorted is A = { 5, 2, 1, 12, 2, 10, 4, 13, 5} . At this point step = 1 .
2. At the first iteration array A is divided into blocks of size step = 1 . The resulting blocks (sub-arrays) are {5}, {2}, {1}, {12}, {2}, {10}, {4}, {13}, {5} .
3. step *= 2, thus step is now 2 . At this point we have a collection of sorted sub-arrays (because their size is = 1) . We will group the sub-arrays one-by-one and we will start merging them . After the merge, the resulting sub-arrays are: {2, 5}, {1,12}, {2,10}, {4, 13} and {5} . {5} remains unpaired as the array size is an odd number . We will take care of this block later .
4. step *= 2, thus step is now 4 . Now we have a collection of 4 blocks of size two and one block of size one . We will start to merge again the adjacent blocks, so the sub-arrays collection becomes: {1, 2, 5, 12}, {2, 4, 10, 13} and {5} .
5. step *= 2, thus step is now 8 . Now we have a collection of 2 blocks with size 4 and one block with size 1 . We will merge the adjacent blocks so the sub-arrays collection becomes {1, 2, 2, 4, 5, 10, 12, 13} and {5} .
6. We now have two blocks one of size 8 and one of size 1 . We will merge those blocks and obtain the resulting sorted array: {1, 2, 2, 4, 5, 5, 10, 12, 13} .

The pseudo code for the algorithm can be written as follows . We will start by writing the merge function . This is responsible with the merging of two already sorted blocks (sub-arrays) from a given array . The input parameters for this function are : the array itself, and the interval headers (stop, start) for the two already sorted blocks . The sentinel is a concept that simplifies the code . In our case we consider SENTINEL infinity (no value from the array is bigger or equal to the Sentinel) .

And the actual function responsible with the actual merge can be written as follows:

Where A is the unsorted-but-soon-to-be-sorted array, length represents the size of A, step is the current size of the block, startL and startR represent the starting indexes of the sorted blocks that are going to be merged .

2. Algorithm implementation in Java Continue reading