Re: Algorithms-HOWTO tentative outline

["David C. Merrill, Ph.D." <dcmerrill@mindspring.com>]

From: "Andrew P Moise" <moise+@andrew.cmu.edu>
>   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
> possible.

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!

> Introduction
>     Copyright
>     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
>     Overview
>     Chaining buckets
>     Overflow hashing
>     Sloppy hashing
>     Notes
>
>   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]
>     Heaps
>     Linked-list stacks?
>     Array stacks
>
> Recursion
>     Basic recursion
>     Tail recursion
>     Memoization
>     Weak memoization? [caching]
>     Dynamic programming?
>
> Sorting and searching
>     Don't do it yourself
>     Quicksort
>     Stable sorting?
>     Binary search
>
> Further Reading
>     Stop reading and code

Yeah!

>     Search space problems?
>     Geometric algorithms
>     Graph algorithms
>     Unreliable algorithms?? [Miller-Rabin, and ... ?]
>     Multiprocessing
>     Cryptography

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?
>     Optimization?
>     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.

Regards,

--
David C. Merrill, Ph.D.
Linux Documentation Project
Collection Editor & Coordinator
www.LinuxDoc.org



--  
To UNSUBSCRIBE, email to ldp-discuss-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org