[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Algorithms-HOWTO tentative outline
From: "Andrew P Moise" <firstname.lastname@example.org>
> Okay, it seems that the consensus is in favor of an Algorithms-HOWTO,
> and I've started writing. What follows is the outline I'm working from
> now; I'd appreciate any comments, criticisms, and suggestions.
Thanks for taking the time to post an outline. I think early feedback will
make it a better HOWTO.
> As I see it now, the HOWTO will serve a double purpose -- to
> familiarize inexperienced programmers with the tools of the trade, and
> as a reference to point experienced programmers to specific algorithms
> they need.
> I'm planning on coding the examples in C, and aiming it at people
> already fluent enough to sling mallocs, structs, and pointers around
> with relative ease. C is pretty ugly, but it's also the closest thing
> we have to a common language, and it's also a good lowest common
> denominator -- if you can implement it in C, you can implement it
> anywhere. I am amenable to a "Primer for the C-impaired" section if
> many people think it would be essential to briefly explain some of C's
> unique gotchas (returning stack structs comes to mind), but I'd like to
> keep to the flavor of the LDP and keep it as terse and focused as
Hmmmmmm. The data structures and algorithms themselves tend to be fairly
language-independent (conceptually), but obviously the implementations
vary. Perhaps some enterprising soul(s) might translate your C examples
into other languages. Are you open to the idea of providing worked
examples in multiple languages? Maybe in a later revision, since you
obviously have plenty of work ahead of you already.
I would not recommend including a primer for C. Keep your focus to the
algorithms; it's a big job in itself. If you *do* write a C primer, I'd
like to see it as a separate document that might eventually be expanded
into a full guide to C programming.
Please consider licensing the "examples" under the GPL explicitly, rather
than under whatever documentation license you use for the rest. That will
allow free software projects to cut-and-paste your code, and could make
your HOWTO into a really valuable resource for them. An interesting
side-issue this raises is that the GPL would then require said programmers
to return to you any improvements to your algorithms! Woo hoo!
> Here's the outline; items marked with ? are tentative:
I'm going to make only a few comments about the actual algorithms you've
selected. I'll try to make some more after referring to my Knuth!
> Intent & scope
> Design advice?
> Big-O analysis??
Algorithmic analysis probably deserves its own complete section, rather
than an entry in the introduction.
> Primer for the C-impaired??
> I have no idea, yet, exactly what I'm introducing.
> Linked Lists
> Singly linked lists
> Doubly linked lists
> Circular lists
> Hash Tables
> Chaining buckets
> Overflow hashing
> Sloppy hashing
> At some point, I will bother to find out the proper names for the
> different flavors of hashing, if any exist.
> Tree structures
> Heterogenous trees
> Binary trees
> Balancing trees?
> Tree structures are for weenies
> That last section is mostly a warning about the relative rarity of
> trees in real programming; I hate sounding as much like an intro CS
> class as I am, but understanding trees really is pretty vital to
> understanding heaps.
> Ordering structures
> Linked-list queues
> Array queues
> Circular buffers [of characters]
> Linked-list stacks?
> Array stacks
> Basic recursion
> Tail recursion
> Weak memoization? [caching]
> Dynamic programming?
> Sorting and searching
> Don't do it yourself
> Stable sorting?
> Binary search
> Further Reading
> Stop reading and code
> Search space problems?
> Geometric algorithms
> Graph algorithms
> Unreliable algorithms?? [Miller-Rabin, and ... ?]
Here's an entire HOWTO in itself. Your whole outline is very ambitious!
> State machines
> Lexers and parsers
> Compiler technology?
> Genetic algorithms?
> Systems programming
> Graphics algorithms?
> Miscellaneous resources
> This will be a set of pointers to good documentation on advanced
> stuff; if any of you have such pointers lying around, I'd greatly
> appreciate you emailing them to me (the same goes for good web
> documentation on any of the other sections; at present I anticipate a
> heavy "See also CLR" concentration.)
> At some point I'd like to throw in B-trees and Fibonacci heaps and all
> (the original plan called for a "Wierd Shit" chapter), but this is
> already plenty ambitious enough to keep me busy for a while.
> I'd particularly like to hear that there's an important algorithm that
> I've forgotten about. As soon as I have some sort of reasonable subset
> of this done, I'll post it here for stylistic advice; 'till then, I look
> forward to your input. Cheers.
Great outline. I look forward to seeing the first draft.
David C. Merrill, Ph.D.
Linux Documentation Project
Collection Editor & Coordinator
To UNSUBSCRIBE, email to email@example.com
with a subject of "unsubscribe". Trouble? Contact firstname.lastname@example.org