Prev: Software for "Regular Expression" <=> NFA <=> DFA
Next: Complexity Theory for Simpletons
From: al pacino on 26 Feb 2006 08:45
Hi Ben,
i think 'ullmann ' is very difficult for a bigginer to understand,
instead 'algorithms in c++' by robert sedgewick is much easier read and
terrafic too.

Ben Bacarisse wrote:
> On Fri, 24 Feb 2006 13:35:50 -0800, Radha wrote:
>
> > Thank you Chris and Ben. I need to write a proof that the worst case is
> > O(nlogn). I was hoping somebody could help me with that.
>
> Sounds like a teaching exercise. Your library should have at least one
> book with such a proof. I used to use Aho, Hopcroft and Ullman: "The
> Design and Analysis of Computer Algorithms" but there must be 100s of
> texts with such a proof in them.
>
> --
> Ben.

From: Rogério Brito on 4 Mar 2006 02:48
Hi, Al Pacino. :-)

al pacino wrote:
> i think 'ullmann ' is very difficult for a bigginer to understand,
> instead 'algorithms in c++' by robert sedgewick is much easier read and
> terrafic too.

Well, I don't know if seeing the algorithm for the first time with all
de details of a language like C++ is the way to go. For a clean
analysis, I would recommend "Introduction to Algorithms", by Cormen et.al.

This is, by the way, the reference that I use when I teach introductory
courses on analysis of algorithms. Actually, I define a binary heap in a
way that is somewhat different than the norm---which I think is better
for the students, but, in the end, the algorithm remains the same (of
course).

The only part of the analysis of Heapsort that may not be that obvious
is the construction of a heap in linear time. But given the fact that
the extraction of the elements from the heap takes time n\lg n, then it
doesn't matter that much if the initial heap is constructed in time
o(n\lg n).


Regards, Rog?rio Brito.

--
Rog?rio Brito : rbrito(a)ime.usp.br : http://www.ime.usp.br/~rbrito
Homepage of the algorithms package : http://algorithms.berlios.de
Homepage on freshmeat: http://freshmeat.net/projects/algorithms/
From: Radha on 6 Mar 2006 19:26
Thank you so much Rogerio. I will go through the links and the book.

Regards

First  |  Prev  | 
Pages: 1 2
Prev: Software for "Regular Expression" <=> NFA <=> DFA
Next: Complexity Theory for Simpletons