Category: Computer Science


Sieve of Eratosthenes

This is a simple and ancient algorithm for finding all prime numbers up to a given number, say n. Although it is a very, very old algorithm, it works fairly efficiently for numbers under 10 million. As the name suggests, this algorithm was created by a Greek mathematician by the name of Eratosthenes…

The following is the algorithm he suggested:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime…

Therefore, in essence, we keep removing elements over and over using one number at a time to choose the numbers that must be removed.

Here’s a working version of the algorithm. Say we want all prime numbers from 1 to 20.

Step 1: Make a list of all numbers from 2 to 20

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Step 2: Take the first number i.e. 2 and remove all its multiples from the list starting from 4.

2  3  5  7  9  11  13  15  17  19

Step 2: Take the next number (2nd number) i.e. 3 and remove all its multiples from the list starting from 9

2  3  5  7  11  13  17  19

Step 3: Take the next number (3rd number) i.e. 5 and remove all its multiples from the list starting from 25. But, since 25 is greater than our n = 20, the process stops at this step.

Therefore, our final list of prime numbers is:

2  3  5  7  11  13  17  19

And yay! that’s the right answer… and computationally easy and efficient!

Advertisements

So, I’ve been working on some small iphone applications for a while. Today, another computer science major asked me how you set up the icon and I figured it’s blog-worthy.

I take it for granted that you are familiar with the files that a new project in xcode holds. Basically, once you open your project using xcode, the following are the steps you need to take:

– Name your icon – icon.png and copy it/move it to the Resources folder for your project which shows up on the left-most area of the development environment.

– Now, open the info.plist file for your project which should be within “Classes” for your project. Somewhere down the list on info.plist, you will see icon… set the value of this key to the name of your icon i.e. icon.png.

Ta da! It’s done!

Wrote some “functions” in Function Programming (FP) the other day. Interesting, to say the least. It was for a class but it was really my first hands on experience with a functional language.

Although there is an interpreter for this language, it isn’t as developed as it could be and it definitely needs a debugger. Anyway, interesting first experience.

Now onto Haskell. Oh fun. At least there’s a huge amount of documentation and books on how to program in Haskell =) It’s always good to have resources. Will write more about it when I know what I’m doing!

Random Shuffle

So, I’m sure that if you are familiar with C++, you are probably also familiar with the random_shuffle that can be used with vectors and stuff.

So, where is random_shuffle used anyway? Here are some examples of its possible use:

1) It can be used when you need one particular element of a vector (etc). One can random_shuffle the vector and then pick the first element of this shuffled array.

2) In Card games! It is one of the easiest ways to actually shuffle a deck of cards or anything else for that matter. Even to change the order of the enemies a player will come across at a certain game level.

It basically allows the randomization and change, making the program more interesting specially if its a game… it adds a certain level of uncertainty and thus, surprise.

I recently had a conversation with a friend about the distance between words. Yes, it sounds absurd but it is a rather interesting concept and ended up being my “CS fact of the day”

Lavenshtein Distance is the most commonly used technique to determine the distance between two words and it basically measures the minimum number of changes required to transform one word into the other.It can be used to check for possible spelling errors etc. by minimizing the distance.

Let’s say word A is ‘meteor’ and word B is ‘enter’. There isn’t any spelling mistake here per se, but we can still measure the distance.

Transforming A into B involves identifying the minimum number of changes. In this case, it is LD(A,B) = 3.

This is because we can make the following changes:

meteor
eteor (delete m)
enteor (insert n)
enter (delete o)

There are obviously infinite number of sequences that will go from A to B, but the objective here is to calculate the minimum one (sort of like the linear distance concept because linear distance is the shortest)

Interestingly enough, this LD (or Lavenshtein Distance) happens to form a metric space. That is, if LD(A, B) = x and LD(B, C) = y, then LD(A, C) = z and (x+y) >= z. This is basically the triangle inequality. So, it enables you to build spacial partitioning trees.

Pretty neat, huh?

So, there’s more than a difference between words… there is a distance… 😀

Strong AI, according to the famous philosopher John Searle, is the claim that a computer can be a complete parallel and equal to a human mind and can not just simulate human intelligence, but also explain it. Even though I am a computer science student and would love the notion of something of the sort taking place, I feel that it is important to note which kind of intelligence a computer can simulate.

It isn’t my “intelligence” per say that gives me feelings, beliefs and ideas. Although, they do play a big role in our decision making process. Of course, strong AI cannot be termed completely human because it is devoid of all human characteristics except computational intelligence. One such characteristic is the presence of emotions and non-computational reactions to input or, in the human sense, perception and response to perception. It lacks intentionality, emotions, random responses, thoughts about topics etc. It is basically a machine that spits out the answer by accumulation of enough information and execution of enough algorithms, but it does not UNDERSTAND what it’s doing.

As they often say, a computer is only as intelligent as the programmer who programs it. Thus, although the computational ability of a computer may just be enough to give the answers a human would give, it still lacks the human touch. My view on this is that a computer can simulate a human’s computational intelligence, but cannot explain it and it lacks any other kind of “intelligence” per say.

So, I agree and disagree with Searle.. I agree that there isn’t an entirely human computer, but I do believe that it can simulate (not explain) human computational intelligence.

Most of us love loading or downloading pictures on our computer and often see the suffixes such as .gif or .jpg/.jpeg. These are the two most common inline image formats or file types.

GIFs: (.gif)
GIF stands for General Image Format. This format was invented by Compuserve and is the most common format on the World Wide Web. It is basically a collection of pixels that together form a picture.
With images in this particular format, you are limited to a maximum of 256 colours for each picture. Of course, these colours are not fixed and for a picture of an elephant, the colour-table would have only the shades of grey. Since, each of the original colours are represented by the closest shade to it, the picture created is very close to the original colours. Therefore, GIF format is good for pictures with large single shade areas (a maximum of 256) such as buttons and lines etc.

JPEG or JPG: (.jpeg or .jpg)
This stands for Joint Photographic Experts Group. We must remember that IBM and IBM compatibles running lower than Windows 95 only allow 3 letter suffixes (.jpg) whereas others such Amiga, Unix and Windows 95 and higher allow 4 letter suffixes (.jpeg). The advantage of this over the GIF is that it is not limited to 256 colours but can incorporate millions more. Thus, it supports images with no large mono-coloured images.
This is why, for photogaphs, JPEG or JPG is preferred over GIF.

Other Facts:
* JPEG file size is not determined by number of shades.
* Extremely compressed JPG images can look very blotchy, if not grainy.
* A compressed file must be decompressed to display and for this process, JPEG files can take much longer than GIF files.
* There are two formats of GIF – GIF87 and GIF89
The GIF89 format allows you to make one of the colours in the image transparent = that of the background.

Here’s the background info for newbies to understand what this blog is talking of –

Algorithms is set of code lines in programming.. a very basic definition for those of you who are not very familiar with programming. And, everytime you program.. there can be certain trade-offs u need to take care of and make decisions on. For example, is time of execution more important than memory space or vice versa? The coding is based on such decisions.

Now that you know what an algorithm is, here’s what I came across a while back… its a programming joke, but it is very true because as rewarding as coding can be, is also is highly frustrating.

Consider the thought that whenever you choose which algorithm to use to solve a problem, you usually only get to choose to conserve at most one of:

(i) time

(ii) space

(iii) sanity

and that eliminating the last one up front usually saves you a lot of grief.

Fractal Recursions

trad_thumb.jpg

www.fractal-recursions.com

Hopefully, just like me… you would find the looks of that page rather interesting. At first it seems like someone sat down and spent a few lifetimes staring at a canvas and doing modern art with a very zealous attitude.

But then, being a computer science major makes me turn around and find the words “fractal” and “recursions” rather contradictory to the whole artistic thing going on there. I don’t know much about art, but I do know that both the terms are often used in Computer Science.

So, I discussed this with the friend who shared that link with me… and this is what I understood and gathered, after a very engrossing conversation and some googling!

I would define fractal recursions as a rather interesting blend of math and computer science. All the images on that website were generated from simple math equations instead of a paint brush! Well, to be more precise, each one of those images in some way are extracted from an explicit or implicit mathematical operation that is recursive (or repetitive). Recursion is what happens when each part of a thing resembles the whole thing, only smaller and slightly altered.

(Logic and computer science are basically two different branches of math. Every computer program can be represented in a tightly definable mathematical form. )

An example that made it easy for me to understand this concept was that of a wall and bricks. Each of the fractal recursions are basically like a wall… made of bricks of similar dimensions (or smaller “walls” in a weird manner of saying).

For those who find stuff like this interesting, you should look up: Mandelbrot Set.

I need to get back to studying a random Software Engineering book, but shall get back to explaining more about this in another blog. Ciao!