Computer Science Canada

Any tutorials about Algorithm and Data Structure?

Author:  wensi [ Mon Aug 07, 2006 10:17 am ]
Post subject:  Any tutorials about Algorithm and Data Structure?

Does anyone know that where can i find some easy to understand or introductory tutorials about Algorithm and/or Data Structure?
It's the best that it used C or C++ to describe them, but I can also understand some other languages as well.

Author:  wtd [ Mon Aug 07, 2006 11:48 am ]
Post subject: 

I would highly suggest checking out languages where you can work with algebraic data types. Smile

For instance, in O'Caml we might implement a tree type as:

code:
type 'a tree = Leaf of 'a | Branch of 'a tree * 'a * 'a tree


And then we could get its number of leaves with a function like:

code:
let rec num_of_leaves a_tree =
   match a_tree with
      Leaf _ -> 1
    | Branch (branch1, _, branch2) ->
         num_of_leaves branch1 + 1 + num_of_leaves branch2


And then we'd create a tree, and print its number of leaves.

code:
let my_tree = Branch (Leaf 4, 5, Branch (Leaf 27, 42, Leaf 68)) in
   print_int (num_of_leaves my_tree)


But that type really should be structured a bit differently

code:
type 'a tree =
   Leaf
 | Branch of 'a tree * 'a * 'a tree


And let's say we want to search and see if a value is contained within the tree.

code:
let rec search_tree v t =
   match t with
      Leaf -> false
    | Branch (_, v', _) when v = v' -> true
    | Branch (b1, _, b2) -> search_tree v b1 or search_tree v b2

Author:  bugzpodder [ Mon Aug 07, 2006 3:38 pm ]
Post subject: 

why do you need this? I can help you better if you tell me your intentions.

Author:  Null [ Mon Aug 07, 2006 3:44 pm ]
Post subject: 

This person is a fantastic help to the forums she frequents, and her tutorials are top notch (at least in my opinion).

Here is a link to the first part of her binary tree tutorial: http://www.eternallyconfuzzled.com/tuts/bst1.html

And a link to her pointer tutorial: http://www.eternallyconfuzzled.com/tuts/pointers.html

Look for more under the Tutorials heading. Smile

Author:  wtd [ Mon Aug 07, 2006 4:25 pm ]
Post subject: 

I think perhaps the most important question is... do you need help understanding the concepts of data structures, or the C and C++ languages?

Author:  wensi [ Mon Aug 07, 2006 8:44 pm ]
Post subject: 

im fine with the languages, as long as i can understand the key words and operators, pseudo-code is also ok for me.
I want to learn something about trees, lists, graphs etc and algorithms for solving NP, probably NP hard and NP complete problems.

Author:  Martin [ Tue Aug 08, 2006 4:28 am ]
Post subject: 

If you're serious about it and you want to learn this stuff, Introduction to Algorithms by Cormen/Leiserson/Rivest/Stein (usually just called CLRS) is considered the quintessential book on the subject. Be warned though, it's used in upper year and graduate university courses and costs over $100, so it might be a bit of a steep place to start.

Otherwise, the best place to learn is probably by doing contest questions and just learning as you go.

Author:  McKenzie [ Tue Aug 08, 2006 7:45 am ]
Post subject: 

I would suggest "Programming Challenges - The programming contest training manual" by Skiena and Revilla. It is an excellent book, and you can find it a lot cheeper.

You need to recognize up front that "easy to understand intoductory tutorials" and "trees, lists, graphs ..." don't usually mix well together.

Author:  wensi [ Tue Aug 08, 2006 10:09 am ]
Post subject: 

Thanks guys, what i meant by easy-to-understand is the books without those mathsmetical symbols such as the big O and sigma etc, im learning these to make my programs faster and im not going to do deep research about the backgrounds of these algorithms. BTW tree, graph, list should be introductory stuffs to data structure right? compared to binary/quadro/octal trees?

Author:  Andy [ Tue Aug 08, 2006 2:03 pm ]
Post subject: 

big O, sigma and these other symbols were invented to help programmers understand how efficienty their code is. without knowing the efficiency of your current code, you cant make it faster

Author:  wensi [ Tue Aug 08, 2006 2:10 pm ]
Post subject: 

yeah, but i can throw in a large number and use a timer to test the speed -_-" jking...

Author:  Tony [ Tue Aug 08, 2006 3:05 pm ]
Post subject: 

that will give you a crude benchmark for a particular load. You wouldn't know how your algorithm scales, or works on average over many different sample cases.

Author:  Catalyst [ Tue Aug 08, 2006 7:14 pm ]
Post subject: 

MIT OCW - Algorithms
go under lecture notes for full lecture videos[/url]

Author:  wensi [ Tue Aug 08, 2006 8:48 pm ]
Post subject: 

OK thx guys, i think i get it now, so i must learn the symbols and understand these mathematical stuffs as well? in order to use these algorithm/data structures well?

Author:  Andy [ Tue Aug 08, 2006 9:34 pm ]
Post subject: 

Shocked Shocked Shocked ITS CATALYST!


: