Algorithms-HOWTO tentative outline

[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.
  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.
  Here's the outline; items marked with ? are tentative:

Introduction
    Copyright
    Intent & scope
    Design advice?
    Big-O analysis??
    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
    Search space problems?
    Geometric algorithms
    Graph algorithms
    Unreliable algorithms?? [Miller-Rabin, and ... ?]
    Multiprocessing
    Cryptography
    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. 


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