Find it on GitHub
Tag Archives: algorithms
Computer Algorithms: Multiplication
Introduction
Perhaps right after the addition at school we’ve learned how to multiply two numbers. This algorithm isn’t as easy as addition, but besides that we’re so familiar with it and that we even don’t recognize it as an “algorithm”. We just know it by heart.
However, as I already said, multiplication is a bit more difficult than addition. This algorithm is interesting because for several reasons. First of all, let’s compare multiplication in binary and decimal.
So, let’s see how to multiply two numbers.
Overview
Multiplying and adding is practically the same thing, so where’s the difference?
It’s clear that a product of two numbers (each with N digits) can be represented as N sums, as we can see on the next picture.
Now, for larger integers each time we shift left the next intermediate sum.
Computer Algorithms: Detecting and Breaking a Loop in a Linked List
Introduction
Linked lists are one very common and handy data structure that can be used in many cases of the practical programming. In this post we’ll assume that we’re talking about singly linked list. This means that each item is pointed by it’s previous item and it points to it’s next item. In this scenario the first item of the list, its head, doesn’t have an ancestor and the last item doesn’t have a successor.
Sometimes, due to bugs or bad architecture or complexity of the applications we can have problems with lists. One very typical problem is having a loop, which in breve means that some of the items of the list is pointed twice, as shown on the image below.
So in first place we need to be sure that there is a loop and then: how can we break it!
There are several algorithms on finding a loop, but here’s one very basic. It’s known as the Floyd’s algorithm or the algorithm of the tortoise and hare. Continue reading Computer Algorithms: Detecting and Breaking a Loop in a Linked List
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
You think you know … algorithms?
Note!– By reading this blog you can get the right answers!
The answers will be published a week after the quiz has started!