Sorting and data structures

[Kmax]

Greetings all,
There is a class in the graduate school at Dartmouth college that lists the following:

The main topics of the course are paradigms for designing algorithms (e.g., divide and conquer, greedy method, structured search, balancing, dynamic programming, scaling, problem reductions), and the criteria for their analysis (e.g., worst-case, average case, lower bounds, sensitivity, amortization, resource tradeoffs, NP-completeness). The course deals primarily with the classical sequential algorithms, but also introduces parallel, distributed, random, probabilistic, and approximation algorithms as time permits. The techniques are illustrated with algorithms for several domains, drawn from among information retrieval, graphs, networks, matroids, string matching, cryptology, arithmetic, matrices, and algebra. Many examples of important data structure and algorithms are described.

I think it would be fun to work on some problems like these. Does anyone have some semi-readable material that covers these topics. It would be cool to do some tutorials as well. I bought the actual text book for the class, but it is not written to be used without a class, and thus goes over my head.

Topic material for data structures:

Binary Search Tree
Red-Black Trees
and Augmenting Data structures (Interval trees, dynamic order statices)

Topic material for Sorting and order Statistics

Heapsort
Quick sort
Sorting in Linear Time
Median and order statistics

Any input would be appreciated. Thanks!

 

[Nerseus]

That class sounds like 50% code, 50% analysis. There are entire studies on algorithm efficiency, the bases for the class (more or less). I'd guess if you want to learn it, you'd be better off taking the course than trying to do too much by hand. The efficiency (the Big O factor or whatever it's called) is very hard to come by and requires solving a lot of equations using log (which I never quite remembered).

They help teach you how to analyze an algorithm to see how fast it will run in best/worst/average case scenarios. While a good thing to know, you're not likely to be coding a lot of complex algorithms in the real world. You may need to code a sort and I'd bet 90% of the people choose either bubble (no!) or insertion (yes!). Searching algorithms are more complex and varied, but again, you'll generally end up falling back on one or two.

In my opinion, this is really good if you want to be a math or CS professor OR if your job is in dealing with a TON of data and you'll be writing custom code (possibly assembly) to optimize your algorithms for real-time systems. For the other 99% of the world, analyzing an algorithm to figure out which one is the best for a job is impractical and you'll never do it (outside of college). If you're sorting a grid, for instance, you've probably got 100 items or so max and you don't care if it takes O(n^2) or O - you'll care that it DOESN'T take more than a half second on any given computer

Sorry I don't have any links or such to help you out - I thought my opinion might help though...

-Nerseus

 

[Heiko]

Oh yes. I remember all that from university.

B*Trees. Balancing Trees. Sorting algorithms. NP-Completeness ..

I really liked that stuff.

That was in the early 90ies.

Ever since I have never ever used it again (knowingly, of course).
A good understanding of complexity issues may help a lot, though.


From what I've seen in my projects, there's a lot of people who have a problem with programming recursive code. Or with porting recursive algorithms to iterative ones. Or with keeping the code in loops as light as possible.

If you look for a good practise in both recursive algorithms and complexity issues, then I suggest the following (it opened *my* eyes big time).

Write a programm that solves the "queens on a chessfield" problem and tells how many possible solutions there are - for any size from 1 to n

In other words:

For n= 1 to 100

  determine how many ways there are to place n queens on a n x n chess field so that they can't beat (right expression?) each other.


next size