How to learn Algorithms online?

Post Reply New Topic

Where can I learn how to do algorithms online?
I will be using it for programming.
So it will be for computer algorithms:
http://computer.howstuffworks.com/question717.htm

It kind of depends on which algorithm you want to implement... I doubt there is a site that contains documentation for every algorithm known to computing.

Something for a voting system.
Like:
IF (submitted vote gets above: 70 and is highest}{
Show the highest scoring vote, then the second highest scoring vote thats above 70 (or random submission)
}
else{
Show any random submitted vote that scores below the highest
}

This problem seems to be a standard situation that involves sorting. Sorting is a subject taught in every computer science beginners class and there are several sorting algorithms available with different levels of efficiency. One of the simplest but most innefficient sort algorithms is "BubbleSort". Better algorithms are MergeSort, QuickSort or InsertionSort. The most efficient algorithm as far as I know is HeapSort in its special variation "Bottom-Up HeapSort".

The efficiency of sorting is compared by counting the number of comparisons in relation to the size of the input set. BubbleSort involves "compare every element with every other element" and therefor comes with "input-squared" efficiency.

This is the classic algorithms book. You can download an ebook of it here: http://ifile.it/gysvte/ebooksclub.org__Introduction_to_Algorithms__Third_Edition.pdf

If that one seems difficult to understand at first, you might want to start with this which is what I used in my first data structures class:
http://ifile.it/d3l5u8/ebooksclub.org__Data_Structures_and_Algorithms_in_Java__4th_Edition.l_4zx37z4z7x2oxok.pdf

Also, I'll just leave this here because its cool: http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html

That was fun!

If you are comfortable with Java, here is an amazing source that contains downloadable example code and practice problems with solutions: ambesty dot com

There are also search and retrieve algorithms as well has pattern detection and matching algorithms.

Then there is the field of encryption and decryption which is probably the most difficult area of algorithmic development.

ruveyn

Here is a basic implementation of an insertion sort (assume first is already sorted):

for(i=1;i<n;i++)
{
j=i;
value = list[i];
while((j>0) && (list[j-1]>value)){
list[j] = list[j-1];
j--;
}
list[j] = value;
}

That's just psuedocode though.

Find an algorithm you would like to implement, work on it until it works, and then make it as efficient as possible?

I'd recommend starting with implementing some simple factorial algorithms, and then working your way up to dynamic programming. I'd personally recommend implementing a "longest increasing subsequence" algorithm (based on the Knuth - Robinson - Schendsted correspondence), but it really depends on what you're interested in. Basic encryption is also fun to play with.

There's a pretty decent book by Niklaus Wirth called Algorithms and Data Structures. There's a free ebook for it in PDF form somewhere on the internet. It uses a lot of mathematics, but you can skip over some of the details and still get the basic idea.

Interesting.... I thought you had mis-titled his book, because I have "Algorithms + Data Structures = Programs" here in front of me. Wikipedia link

However, I now gather that, eleven years later, he re-vamped it:
1975 (Pascal) http://www.inf.ethz.ch/personal/wirth/b ... gorithmE0/
1986 (Modula-2) http://www.inf.ethz.ch/personal/wirth/b ... gorithmE1/

I didn't find a PDF for either book. I thought maybe it had been removed for copyright infringement.

Then I noticed that, tucked away on his home page... he has reissued it again, now using his latest language/OS:
2004 (Oberon) http://www.inf.ethz.ch/personal/wirth/ (down near then end)

Sadly, the PDF only contains the first two sections of the book.

I think I might have to look at his updated stuff.
http://www.ethoberon.ethz.ch/

The copy I have contains five sections.
1. Fundamental Data Structures
2. Sorting
3. Recursive Algorithms
4. Dynamic Information Structures
5. Key Transformations

The appendix on the syntax of Oberon is left out.

Fascinating. My Pascal version also has five sections.

My first four sections are named exactly the same as yours. However, the fourth section merely has a final subsection named "4.6 Key Transformations (Hashing)".

My fifth section is "Language structures and compilers", which develops the full code of a compiler for "PL/0" (a subset of Pascal).

I wonder why Wirth decided no one needed to know how to write compilers any more?

Wrong, the most efficient search/sort mechanism is a hash/key pair, which is O(1). Heapsort is O(nLog(n))

You can't sort in constant time. You can use a hash table for constant time lookup (assuming there are no collisions), but hashes are not useful for sorting.

Edit: well there are bucket-type sorts but those are linear time at best and need big data structures.