Category Archives: algorithms

A process or set of rules to be followed in calculations or other problem-solving operations, esp. by a computer.

Computer Algorithms: Stack and Queue

algorithms, data structures, , , , , , , , , , , , , , , , , ,

Introduction

Every developer knows that computer algorithms are tightly related to data structures. Indeed many of the algorithms depend on a data structures and can be very effective for some data structures and ineffective for others. A typical example of this is the heapsort algorithm, which depends on a data structure called “heap”. In this case although the stack and the queue are data structures instead of pure algorithms it’s imporant to understand their structure and the way they operate over data.

However, before we continue with the concrete realization of the stack and the queue, let’s first take a look on the definition of this term. A data structure is a logical abstraction that “models” the real world and presents (stores) our data in a specific format. The access to this data structure is often predefined thus we can access directly every item containing data. This help us to perform a different kind of tasks and operations over different kind of data structures – insert, delete, search, etc.. A typical data structures are the stack, the queue, the linked list and the tree.

All these structures help us perform specific operations effectively. For instance searching in a balanced tree is faster than searching in a linked list.

It is also very important to note that data structures can be represented in many different ways. We can model them using arrays or pointers, as shown in this post. In fact the most important thing is to represent the logical structure of the data structure you’re modeling. Thus the stack is a structure that follows the LIFO (Last In First Out) principle and it doesn’t matter how it is represented in our program (whether it will be coded with an array or with pointers). The important thing into a stack representation is to follow the LIFO principle correctly. In this case if the stack is an array only its top should be accessible and the only operation must be inserting new top of the stack.
Continue reading Computer Algorithms: Stack and Queue →

Computer Algorithms: Order Statistics

algorithms, , , , , , , ,

Introduction

We know that finding the minimum in a list of integers is a fairly simple task, but what about finding the i-th smallest element? Then the task isn’t that trivial and we have to think for a different approach.

First of all there are some very basic and intuitive approaches. Since finding the minimum is so easy, can we just find the minimum, than exclude it from the list and then search the minimum again until we find the i-th smallest element.

Finding the Minimums
Continue reading Computer Algorithms: Order Statistics →

Computer Algorithms: Minimum and Maximum

algorithms, , , , , , , , , , , ,

Introduction

To find the minimum value into an array of items itsn’t difficult. There are not many options to do that. The most natural approach is to take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

Find a Minimum

First thing to note is that we pass through the array with n steps and we need exactly n-1 comparisons. It’s clear that this is the optimal solution, because we must check all the elements. For sure we can’t be sure that we’ve found the minimum (maximum) value without checking every single value.
Continue reading Computer Algorithms: Minimum and Maximum →

Computer Algorithms: Karatsuba Fast Multiplication

algorithms, , , , , , , , ,

Introduction

Typically multiplying two n-digit numbers require n2 multiplications. That is actually how we, humans, multiply numbers. Let’s take a look of an example in case we’ve to multiply two 2-digit numbers.

12 x 15 = ?

OK, we know that the answer is 180 and there are lots of intuitive methods that help us get the right answer. Indeed 12 x 15 it’s just a bit more difficult to calculate than 10 x 15, because multiplying by 10 it really easy – we just add one 0 at the end of the number. Thus 15 x 10 equals 150. But now again on 12 x 15 – we know that this equals 10 x 15 (which is 150) and 2 x 15, which is also very easy to calculate and it is 30. The result of 12×15 will be 150 + 30, which fortunately isn’t difficult to get and equals to 180.

That was easy but in some cases the calculations are a bit more difficult and we need a structured algorithm to get the right answer. What about 65 x 97? That is not so easy as 12 x 15, right?

The algorithm we know from the primary school, described on the diagram below, is well structured and help us multiply two numbers.

Typical Multiplication

We see that even for two-digit numbers this is quite difficult – we have 4 multiplications and some additions. Continue reading Computer Algorithms: Karatsuba Fast Multiplication →

Computer Algorithms: Determine if a Number is Prime

algorithms, javascript, PHP, , , , , , , , , , ,

Introduction

Each natural number that is divisible only by 1 and itself is prime. Prime numbers appear to be more interesting to humans than other numbers. Why is that and why prime numbers are more important than the numbers that are divisible by 2, for instance? Perhaps the answer is that prime numbers are largely used in cryptography, although they were interesting for the ancient Egyptians and Greeks (Euclid has proved that the prime numbers are infinite circa 300 BC). The problem is that there is not a formula that can tell us which is the next prime number, although there are algorithms that check whether a given natural number is prime. It’s very important these algorithms to be very effective, especially for big numbers.

Overview

As I said each natural number that is divisible only by 1 and itself is prime. That means that 2 is the first prime number and 1 is not considered prime. It’s easy to say that 2, 3, 5 and 7 are prime numbers, but what about 983? Well, yes 983 is prime, but how do we check that? If we want to know whether n is prime the very basic approach is to check every single number between 2 and n. It’s kind of a brute force.

Implementation

The basic implementation in PHP for the very basic (brute force) approach is as follows.

Unfortunately this is one very ineffective algorithm. We don’t have to check every single number between 1 and n, it’s enough to check only the numbers between 1 and n/2-1. If we find such a divisor that will be enough to say that n isn’t prime.

Although that code above optimizes a lot our first prime checker, it’s clear that for large numbers it won’t be very effective. Indeed checking against the interval [2, n/2 -1] isn’t the optimal solution. A better approach is to check against [2, sqrt(n)]. This is correct, because if n isn’t prime it can be represented as p*q = n. Of course if p > sqrt(n), which we assume can’t be true, that will mean that q < sqrt(n).

Beside that these implementations shows how we can find prime number, they are a very good example of how an algorithm can be optimized a lot with some small changes.

Sieve of Eratosthenes

Although the sieve of Eratosthenes isn’t the exact same approach (to check whether a number is prime) it can give us a list of prime numbers quite easily. To remove numbers that aren’t prime, we start with 2 and we remove every single item from the list that is divisible by two. Then we check for the rest items of the list, as shown on the picture below.

http://www.stoimen.com/blog/wp-content/uploads/2012/05/SieveofEratosthenes.png

The PHP implementation of the Eratosthenes sieve isn’t difficult.

Application

As I said prime numbers are widely used in cryptography, so they are always of a greater interest in computer science. In fact every number can be represented by the product of two prime numbers and that fact is used in cryptography as well. That’s because if we know that number, which is usually very very big, it is still very difficult to find out what are its prime multipliers. Unfortunately the algorithms in this article are very basic and can be handy only if we work with small numbers or if our machines are tremendously powerful. Fortunately in practice there are more complex algorithms for finding prime numbers. Such are the sieves of Euler, Atkin and Sundaram.