Category Archives: Algorithms

Fast Exponentiation Algorithms

Exponentiation is a very common part of mathematics, and it’s involved in many programming puzzles. If you don’t have a function already implemented for you, a simple algorithm to compute a^b (a to the power of b) would be: int expo(int a, int b){     int result = 1;     while (b>0){         result *= a;         b–;     } […]

Integer Partition Algorithm

The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are: 5 4+1 3+2 2+2+1 2+1+1+1 1+1+1+1+1 Notice that changing the order of the summands will not create a different partition. Now how do we find the number of different […]

Knapsack Problem Dynamic Programming Algorithm

The Knapsack problem is probably one of the most interesting and most popular in computer science, especially when we talk about dynamic programming. Here’s the description: Given a set of items, each with a weight and a value, determine which items you should pick to maximize the value while keeping the overall weight smaller than […]

The Sieve of Eratosthenes (Implemented in C)

If you like programming puzzles and challenges you’ll notice that many of them involve prime numbers in one way or another. As such it becomes handy to have a large table of prime numbers ready to go. One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of […]