Computer Algorithms: Order Statistics

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.

Continue reading Computer Algorithms: Order Statistics

Computer Algorithms: How to Determine the Day of the Week

Introduction

Do you know what day of the week was the day you were born? Monday or maybe Saturday? Well, perhaps you know that. Everybody know the day he’s born on, but do you know what day was the 31st January 1883? No? Well, there must be some method to determine any day in any century.

We know that 2012 started at Sunday. After we know that it’s easy to determine what day is the 2nd of January. It should be Monday. But things get a little more complex if we try to guess some date distant from January the 1st. Indeed 1st of Jan was on Sunday, but what day is 9th of May the same year. This is far more difficult to say. Of course we can go with a brute force approach and count from 1/Jan till 9/May, but that is quite slow and error prone.

So what we’ll do if we have to code a program that answers this question. The most easier way is to use a library. Almost every major library has built-in functions that can answer what day is on a given date. Such are date() in PHP or getDate() in JavaScript. But the question remains. How these library functions know the answer and how can we code such library function if our library doesn’t support such functionality?

There must be some algorithm to help us. Continue reading Computer Algorithms: How to Determine the Day of the Week

Computer Algorithms: Brute Force String Matching

Introduction

String matching is something crucial for database development and text processing software. Fortunately every modern programming language and library is full of functions for string processing that help us in our everyday work. However is great to understand their principles.

String algorithms can be mainly divided into several categories. One of these categories is string matching.

When we come to string matching the most basic approach is what is known as brute force, which means just to check every single character from the text to match against the pattern. In general we have a text and a pattern (most commonly shorter than the text). What we need to do is to answer the question whether this pattern appears into the text.

Overview

The principles of brute force string matching are quite simple. We must check for a match between the first characters of the pattern with the first character of the text as on the picture bellow.

Continue reading Computer Algorithms: Brute Force String Matching