Victor R. Volkman received a BS in Computer Science from Michigan Technological University. He has been a frequent contributor to the C/C++ Users Journal since 1987. He is the author of book Windows Programming with Shareware Tools. He can be reached at sysop@hal9k.com.
Algorithms are abstract tools which describe a problem to be solved and how to do it. Algorithms in Computer Science texts are typically written in pseudo-code, a shorthand which conveys the structure of processing while leaving out obvious detail. Algorithms in the form of a small but easily adaptable demonstration source program or libraries are also valuable. My sweep of the WWW has produced both types of algorithms that I will share with you. Specifically, I'll point you towards algorithms for graphs, generic implementations, numerical methods, operations research, parallelism, and evolutionary computing (including genetic algorithms and neural networks).
Moving from pseudo-code to practical implementations, I turn next to "LEDA: The Library of Efficient Data Types and Algorithms" maintained by Christian Uhrig (leda@mpi-sb.mpg.de) at the Max Planck Institute of Computer Science. LEDA is a platform-independent C++ class library that supports most compilers including Zortech, Borland, and AT&T style "cfront" C++ compilers. Specifically, LEDA supplies efficient implementations for many data types such as Fibonacci heaps for priority queues, red-black trees, dynamic perfect hashing for dictionaries and more. LEDA contains an especially useful graph implementation including:
You can obtain LEDA by FTP from ftp.mpi-sb.mpg.de:/pub/LEDA, note that it is available BOTH in pkZIP and tgz (tar'red and gnuZipped) archive formats:
Filenames Size ----------- -------- FAQ 19 Kb GMBH 1 Kb LEDA-33b.zip 1124 Kb LEDA-R-3.2.3.tgz 717 Kb LEDA-R-3.3.b.tgz 791 Kb MANUAL-R-3.3.ps 741 Kb
"Algorithm-Oriented Generic Libraries" ( http://www.cs.rpi.edu/~zalewskk/www/ADS/Algor/Algor.html) created by alsser and Stepanov (musser@cs.rpi.edu) provides a new spin on an old subject. Their approach differentiates itself by using generic containers rather than the traditional parameterization methods of templates. By expressing the algorithms in terms of basic access operations and making the operations parameters, generic libraries permit a single expression of the algorithms to be used with any concrete representation of the container. Musser and Stepanov use C++ to demonstrate their techniques, but emphasize that other languages such as Ada are equally suited.
A completely different branch of algorithm research and design involves numerical methods. "Teaching Numerical Analysis" (http://www.netlib.org/textbook/mathews/) is meant to accompany the textbook of the same name by John Mathews mathews@fullerton.edu. Mathews covers the traditional undergraduate curriculum in Numerical Analysis, including non-linear and linear equations, differentiation and integration, differential and partial-differential equations, and eigenvalues and eigenvectors. Algorithms are presented in Ryan-McFarland FORTRAN but the concepts should be transportable to C/C++ either by transcription or perhaps using the GNU f2c (Fortran-to-C) translator ftp://netlib.bell-labs.com/netlib/f2c/
Operations Research is a business-oriented class of algorithms that are typically used to minimize costs (production) or maximize profits. You can browse a listing of packages at the "Operations Research and Mathematical Optimization - Software" page (http://www.rrz.uni-koeln.de/themen/or/soft.html). Most of these packages are oriented towards "Linear Programming".
Parallel algorithms revolve around properly exploiting the resources of multiple CPU computers. The "ICASE Parallel Algorithm Highlights" page (http://www.icase.edu/docs/hilites/index.cs.alg.html) focuses specifically on parallelism as applied to rendering of 3-D photo-realistic images. ICASE has developed a data distributed parallel algorithm for ray-traced volume rendering, which distributes not only the data but also the rendering and image compositing process.
They have also developed a parallel polygon rendering algorithm. These algorithms allow interactive visualization of the massive datasets for scientific applications. By exploiting the available parallelism to perform graphics operations in place, you can obtain visual feedback from an ongoing computation without moving the entire dataset across the network.
Many problems are difficult to parallelize into equally sized pieces that can be worked on independently and without constant communication. These so-called "irregular problems" are the subject of the "Implementations of Irregular Parallel Algorithms" page ( http://www.ius.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/www/alg/algs.html) These pages provide pseudo-code and list the pros and cons of implementations involving the following irregular problems:
The hottest area for algorithm research and design is the family of studies which fall under the category of Evolutionary Computation (EC). EC embraces all of the heuristic algorithm subtypes, including Genetic Algorithms, Neural Networks, Evolutionary Programming, Evolution Strategies, Classifier Systems, Genetic Programming, and Darwinian strategies lumped together as Evolutionary Algorithms. If you're new to EC concepts and definitions, you might as well start with the comp.ai.genetics FAQ page (http://www.cis.ohio-state.edu/hypertext/faq/usenet/ai-faq/genetic/top.html).
The "Genetic Algorithm Research Group Online Resources" page (http://www-personal.engin.umich.edu/~streak/online.html) is a great place to begin your search for GA libraries. It also provides extensive pointers to URLs describing Artificial Life and Cellular Automata. The "MSU Genetic Algorithms Research and Applications Group (the GARAGe)" (http://GARAGe.cps.msu.edu/) offers two libraries to get you started: GALOPPS and "lil-gp".
The "Genetic ALgorithm Optimized for Portability and Parallelism System" (GALOPPS) is a generic C genetic algorithm tool that provides an enormous range of options for genetic algorithm experiments. In particular:
lil-gp is a generic C genetic programming tool. It was written with several goals: speed, ease of use, and support for the following
The "CMU Artificial Intelligence Repository" page (http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/genetic/ga/systems/genlib/0.html) is the home of the Genetic Algorithms and Neural Networks Library (GENlib). This repository contains a library of functions for Genetic Algorithms together with two applications of this library to train Neural Networks: "cosine" and "vartop".
The cosine application uses a genetic algorithm to train a simple three layer Feed-Forward network to work as a cosine-function. This task is very difficult to train for a Backwards Propagation Algorithm, but the the Genetic Algorithm produces good results. The vartop applicatoin demonstrates developing a Neural Network to perform the XOR-function (a classic problem). This is done with two Genetic Algorithms, the first one develops the topology of the network, and the second one adjusts the weights.
Both applications are written in C and have been tested and verified for the IBM PC and IBM RS/6000 platforms. These programs may be used for academic research and educational purposes only. Commercial and non-academic purposes require written permission of the author.
Neural networks are pattern recognition algorithms that learn by example.
The DYSTAL Algorithm page describes the culmination of an 8 year research project a neural network based on biological associative learning with non-Hebbian learning rules. The Dynamically STable Associative Learning (DYSTAL) algorithm is based on the biophysics and electrophysiology of the changes that learning produces in a "patch" of dendritic membrane (cluster of synapses) of individual neurons.
DYSTAL, like biological associative learning, works by learning an association between two inputs, called the Conditioned Stimulus (CS) and the Unconditioned Stimulus (UCS), to conform with the usage in the associative learning literature. Recall that Pavlov's dogs learned to associate the sound of a bell (the CS) with the smell of meat (the UCS), so they salivated when they heard the bell alone. Humans (and DYSTAL) have generalized this ability to associate events consistently presented in the same sequence, so that any repeatedly paired stimuli can be associated.
"Visual Programming: The Best of Internet" by Pacific HiTech provides 163 MB (unzipped) of libraries for use with Microsoft Visual Basic, Visual C/C++, Borland C++, and other compatible environments. In all, some 250 different products are represented. Approximately 90% of the products presented are VBXs designed for use with VB, though they can of course be called from other environments.
I've done considerable research in this area for my book Windows Programming with Shareware Tools and was pleasantly surprised to find many new products here that were new to me. I recommend this disk mainly for Visual Basic users. It would require you dozens of hours to acquire this software over the Internet yourself.
The HiTech browser provides the main method of locating products of interest. You can browse by category or perform text searches against descriptions, authors, and platform (see Fig. 2). My only complaint with the browser itself was that I had difficulty reading some of the fonts in 640x480.
I found the quality of the long descriptions to be uneven. Some descriptions had as many as five exclamation points (!), a few typos, and many others referred to figures or lists that were plainly missing. Nevertheless, the descriptions do give you some idea of what each product is about.
Product: Visual Programming CD-ROM, $30 Release: Sept. 1995 Edition Vendor: Pacific HiTech 3855 South 500 W. Suite B Salt Lake City, UT 84115 ASP Member: No Phone: (800)765-8369 Email: info@pht.com or orders@pht.com FTP: ftp.pht.com WWW: http://www.pht.com/