basic famous algorithms

[unoho]

im going to university next year... so before going to university, what are some basic algorithms that i should try to learn which will help me a lot in first year of CS or SE.
the only algorithm i know is "BUBBLE SORT"

thank you...

[DemonWasp]

You don't really need any complicated knowledge of algorithms going into CS / SE. You'll learn about all sorts of fantastic algorithms over the course of your university education, but knowing any beforehand isn't really necessary.

What would be vastly preferable is to review your grade 12 math (Calculus and the other "hard" math course). Math is really going to be key for a CS degree, and if you're going to UW, then Math is the hard part of CS.

If you just want to know some algorithms, look up the following:
- quicksort (generally the fastest sort)
- mergesort (another fast sort, with some other nice properties)
- sieve method for finding prime numbers
- linked lists (and other list implementations)
- trees and common tree-traversals (prefix, infix, postfix)
- balanced trees (AVL is the easiest one)
- B-trees (important in file systems)
- tries (these are cool, but pretty specialised)
- Breadth-First Search and Depth-First Search for graph traversal

[Tony]

All of those algorithms (and data-structures) will be covered in detail (some will be covered multiple times, in multiple courses) at the University. If you self-teach yourself wrong, you could set a bad habit against the way your professors might want you to explain and trace through the algorithms.

I second the importance of Math.

I suppose reading, understanding, analyzing algorithms are important skills to have. What's the BigO of a standard Bubble Sort? How can the sort be made faster? How much better is the theoretical performance of the "improved-BubbleSort"? Does BigO improve to a faster class level?

[saltpro15]

Tony @ Wed Apr 14, 2010 wrote:

How can the sort be made faster?

use the C++ built in sort

and I agree with the other two, math is very important

[yoursecretninja]

My advice is that you learn some good pizza cutting algorithms, like described here: http://www.crm.umontreal.ca/CanaDAM2009/pdf/meszaros.pdf

You'll probably share a lot of pizza in university with fellow students, and knowing good techniques for divvying up the pie will help ensure you get (more than) your fair share

[unoho]

yoursecretninja @ Thu Apr 15, 2010 12:40 pm wrote:

You'll probably share a lot of pizza in university with fellow students, and knowing good techniques for divvying up the pie will help ensure you get (more than) your fair share

hhaaha...nicee...

but i did like the quicksort method a lot it's quite interesting..

[Insectoid]

Once you study the different types of sorts, you'll begin to see ways off optimizing your other algorithms & code. I think it's a very useful thing to study (the repercussions of studying the quicksort are much more useful than studying the quicksort itself).

[Tony]

Personally, I found the study of MergeSort to be much more applicable to other areas of application.

[Insectoid]

I studied both, the information probably mixed together in my brain.

[DemonWasp]

Mergesort has the very helpful property of being stable, which quicksort does not have, and it behaves better with very large data sets that have to span multiple levels in the memory hierarchy. For structures that support fast random access (such as arrays or arraylists entirely in RAM), quicksort is generally better.

Tony is also right: there are a lot of different ways to use the ideas behind mergesort that aren't necessarily applicable to quicksort's general idea.

[btiffin]

Old guy venting in the just because department.

I always like pointing to http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell and the following http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_C for clean and easy to grok qsort implementation.

Cheers,
Brian