efg's Algorithms Page

general

	Dr. Dobb's Journal April 2002
	Dr. Dobb's Journal April 2001 April 2000 April 1999 April 1998 April 1997 April 1996 April 1995 Algorithms page List of Online Algorithm Articles from DDJ

	Data Structures and Algorithm Analysis in ADA Author's Page: www.cs.fiu.edu/~weiss/ada.html

Top Ten Algorithms of the Century
http://computer.org/cise/cs2000/c1toc.htm

Al-Khwarizmi
http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Al-Khwarizmi.html

Author's Web Sites:

Donald E. Knuth, Stanford
http://www-cs-faculty.stanford.edu/~knuth

Electrical Engineering and Computer Science including classes such as

Artificial Intelligence
Introduction to Algorithms
Mathematics for Computer Science
Theory of Computation
Algorithms for Computer Animation

Numbered Manuscripts by Edsger W. Dijkstra
www.cs.utexas.edu/users/EWD/indexEWDnums.html

David Gries
www.cs.cornell.edu/home/gries/gries.html

Robert Sedgewick, Princeton University, researcher in analysis of algorithms
www.cs.princeton.edu/~rs

Dokumentacja i algorytmy (Polish)
www.software.com.pl/zasoby/grafika/default.asp

ACM Collected Algorithms from Transactions on Mathematical Software

Nearly 40 years of ACM publications on mathematical algorithms.

ASCII Format:
http://www.netlib.org/toms

Arithmetic Algorithms

A Calculated Look at Fixed-Point Arithmetic
www.embedded.com/98/9804fe2.htm

Artificial Intelligence

AI Resources
www.aaai.org/Resources/resources.html

Dr. Dobb's AI page

Articial Intelligence and Game Programming
http://www-cs-students.stanford.edu/~amitp/gameprog.html#AI

Electrical Engineering and Computer Science including "Artificial Intelligence" class

Bit Manipulation

A Generic API Bit Manipulation in C
www.embedded.com/1999/9907/9907feat2.htm

Books

Handbook of Algorithms and Data Structures
www.dcc.uchile.cl/~rbaeza/handbook/hbook.html Algorithms and Data Structures in C++

Computer Science section of efg's Technical Book Store
Algorithms section of Amazon

Branch and Bound

www.cs.sandia.gov/opt/survey/branch-and-bound.html

BSP

Binary Space Partition Trees
www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html

Caching

Article by Jon Bentley in April 2000, Dr. Dobb's Journal, p. 111-116. Source Code.

Card shuffling

Card shuffling is an example of putting a fixed number of items into completely random order. Timothy examines a couple of randomizing algorithms -- one that does not generate all permutations with equal probability, and another that does. Dr. Dobb's Journal, January 2000, pp. 113-114. aa120.txt (listings) and aa120.zip (source code).

Circle

Minimum Bounding Circle
www.inf.ethz.ch/personal/gaertner/miniball.html

Classification and Clustering Algorithms

Boris Mirkin's Homepage (author of "Mathematical Classification and Clustering")
www.dcs.bbk.ac.uk/~mirkin/academic.html

Color Algorithms

efg's Color Reference Library

CRCs

The CRC Pitstop is a repository for information on CRC and other checking algorithms. Take a look at the paper A Painless Guide to CRC Error Detection Algorithms.

efg's CRC Lab Report has many links about CRCs

Data Compression

Dr. Dobb's Data Compression page

Data Structures

The Complete Collection of Algorithm Animations: Data Structures
www.cs.hope.edu/~alganim/ccaa/data.html

Digital Signal Processing

The Scientist and Engineer's Guide to Digital Signal Processing
www.dspguide.com

Spectra: Digital Signal Processing With or Without a DSP
www.embedded.com/1999/9904/9904sp.htm

See Fourier Analysis on efg's Math page

Discrete Cosine Transform

Implementing Fast DCTs. Dr. Dobb's Journal, March 1999, pp. 115-119. The Discrete Cosine Transform (DCT) is a crucial part of modern image and sound compression. Tim discusses several fast algorithms for computing the 8-point DCT and IDCT. Additional resources include aa399.txt (listings) and aa399.zip (source code). www.ddj.com/articles/1999/9903/9903toc.htm

Discrete Optimization Methods

Set Cover, Set Packing, Shortest Path, Traveling Salesman Problem, Knapsack Problem, Network Flow, Job Scheduling, Vertex Coloring, Linear Programming, Matching, Minimum Spanning Tree
www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml

Fibonacci Heap

www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algorithms

Genetic Algorithms

Genetic Algorithms Archive
www.aic.nrl.navy.mil/galist

Digital Biology
www.digitalbiology.com

Genetic Programming

Genetic Algorithm Archive
www.aic.nrl.navy.mil/galist

Genetic Programming
www.genetic-programming.org
www.genetic-programming.com

The GP Tutorial
www.geneticprogramming.com/Tutorial/index.html

Tutorial
www.genetic-programming.com/gpanimatedtutorial.html

Geometry

Geometry Algorithms
http://geometryalgorithms.com

The Complete Collection of Algorithm Animations: Geometric
www.cs.hope.edu/~alganim/ccaa/geometric.html

Computational Geometry Algorithms Library
www.cs.ruu.nl/CGAL

Computational Geometry Bibliographies
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/biblios.html

Geometrical Transformations
[Foley96, Chapter 5, pp. 201-227]

Introduction to Computing with Geometry Notes
www.cs.mtu.edu/~shene/COURSES/cs390/NOTES/notes.html

Computational Geometry Bibliographies
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/biblios.html

Graph Algorithms

The Complete Collection of Algorithm Animations: Graph
www.cs.hope.edu/~alganim/ccaa/graph.html

The Generic Graph Component Library: As good as it is, the C++ Standard Template Library doesn't address every problem domain. Consequently, our authors implemented the Generic Graph Component Library (GGCL) for use with sparse matrix ordering algorithms for scientific computing. Additional resources include ggcl.txt (listings) and ggcl21.zip (source code) from Dr. Dobb's Sept. 2000.

Graphics Algorithms

efg's Graphics page

Great Circles

Introduction to the Great Circle Navigation Formulae
www.best.com/~williams/avform.htm#Intro

Great Circle Navigation Formulae
www.best.com/~williams/avform.htm#GCF

efg's UseNet Post about computing great circle distances

Hashing

Hash Functions and Block Ciphers
http://burtleburtle.net/bob/hash/index.html

Hashing Rehashed, Dr. Dobb's Journal
www.ddj.com/articles/1996/9604/9604b/9604b.htm?topic=algorithms

Secure Hash Standard (SHS) and Secure Hash Algorithm (SHA-1)
www.itl.nist.gov/fipspubs/fip180-1.htm

Huffman

Although simple and often effective, Huffman's compression algorithm requires a lot of memory for 16-bit Unicode text files, and it doesn't adapt to varying conditions within the data. Steven and Yoshua explain how they updated Huffman's classic technique. Additional resources include aa108.txt (listings) and aa108.zip (source code). Dr. Dobb's Journal, October 1998. www.ddj.com/articles/1998/9810/9810toc.htm

Image Processing Algorithms

efg's Image Processing Algorithms Reference Library page

Interpolation

Bilinear Interpolation

Use linear interpolation along the top and bottom horizontal lines to determine z_A and z_B:

z_A = (1 � f)�z(x_i, y_j) + f�z(x_i+1, y_j)

z_B = (1 � f)�z(x_i, y_j+1)+ f� z(x_i+1, y_j+1)

Use linear interpolation along the vertical line between z_A and z_B to determine z(x,y):

z(x,y) = (1 � g)�z_A + g�z_B

Or,

z(x,y) = (1 � f)�(1 � g)�z(x_i, y_j) + f�(1 � g)�z(x_i+1, y_j) + (1 � f)�g�z(x_i, y_j+1) + f�g�z(x_i+1, y_j+1)

Inverse

Inverse and n-th roots of large numbers
http://numbers.computation.free.fr/Constants/Algorithms/inverse.html

Koch Snowflake

efg's UseNet Post about creating Koch snowflake
efg's von Koch Curve Lab Report

Links

www.iversonsoftware.com/tabularium/programming/algorithms/index.asp?area=w

Mathematics

efg's Math Reference Library

Monte Carlo

Monte Carlo Methods: A championship-level bridge program
April 2000, Dr. Dobb's Journal

Neural Networks

9. Simple Classifiers and Neural Networks
http://cgm.cs.mcgill.ca/~godfried/teaching/pr-web.html

NeuroNet: Our aim was to promote development and technology transfer in the field of Neural Networks in Europe. http://www.kcl.ac.uk/neuronet

Stuttgart Neural Network Simulator
http://www-ra.informatik.uni-tuebingen.de/SNNS

Neural networks at Pacific Northwest National Laboratory
www.emsl.pnl.gov:2080/proj/neuron/neural/homepage.html

US UK DE
Neural Networks for Pattern Recognition
www.ncrg.aston.ac.uk/NNPR (book home page)

Newton's Method

http://numbers.computation.free.fr/Constants/Algorithms/newton.html

Parallel

www.cs.hope.edu/~alganim/ccaa/parallel.html

Paths

Shortest Paths
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths

Point in Triangle Test

Dave Eberly's UseNet Post:
Let the points be (x0,y0,z0), (x1,y1,z1), (x2,y2,z2). Given (x,y), solve for s and t in (x,y) = (x0,y0)+s*(x1-x0,y1-y0)+t*(x2-x0,y2-y0). The point is inside the triangle if s >= 0, t >= 0, and s+t <= 1. Then choose z = (1-s-t)*z0+s*z1+t*z2.

Polyhedra

Polyhedra Database
www.netlib.org/polyhedra/index.html

Primes

Great Internet Prime Search
www.mersenne.org/prime.htm

Regular Expressions

Regular expressions, one of the most broadly applicable of programmer's tools, provide a compact and expressive notation for describing patterns of text. They are also algorithmically interesting, easy to implement, and highly useful. Brian and Rob, who are researchers at Bell Labs and the authors of The Practice of Programming, present a compact implementation of grep that uses regular expressions. Additional resources include regexp.txt (listings) and regexp.zip (source code).
April 1999, Dr. Dobb's Journal. www.ddj.com/articles/1999/9904/9904toc.htm

Roots

Also see Square Root

Inverse and n-th roots of large numbers
http://numbers.computation.free.fr/Constants/Algorithms/inverse.html

Sierpinski Triangle

efg's Sierpinski Triangle Lab Report

Searching

Ternary Search Trees, Dr. Dobb's Journal, April 1998
www.ddj.com/articles/1998/9804/9804a/9804a.htm

Simplex Algorithm

http://lib-www.lanl.gov/numerical/bookcpdf/c10-4.pdf

Sorting

Sorting Algorithms
www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

The Fastest Sorting Algorithm, April 2000, Dr. Dobb's Journal

Fast Algorithms for Sorting and Searching Strings
www.cs.princeton.edu/~rs/strings

A library of internal sorting routines
www.yendor.com/programming/sort

Sorting and Searching
http://mathworld.wolfram.com/topics/SortingandSearching.html

Sorting and Searching Algorithms: A Cookbook
http://members.xoom.com/_XMCM/thomasn/s_title.htm

QuickSort is nice, but it's usually implemented using statically allocated arrays, and it does not take advantage of already-sorted data. Bill's variation of the Merge Sort addresses both of these weaknesses. Additional resources include aa699.txt (listings). June 1996, Dr. Dobb's Journal.
www.ddj.com/articles/1999/9906/9906toc.htm

Jon and Robert describe a new algorithm for sorting strings that combines the best of quicksort and radix sort. Additional resources include AA118.TXT (listings) and AA118.ZIP (source code). Dr. Dobb's Journal, Nov. 1998. www.ddj.com/articles/1998/9811/9811toc.htm

Square Root

www.azillionmonkeys.com/qed/sqroot.html

"Integer Square Roots" by Jack W. Crenshaw
Embedded Systems Programming, Feb. 1998, pp. 15-32
www.embedded.com/98/9802fe2.htm

Integer Square Root
www.research.microsoft.com/~hollasch/cgindex/math/introot.html

Stony Brook Algorithm Repository

Comprehensive collection of algorithm implementations of fundamental problems in combinatorial algorithms.
www.cs.sunysb.edu/~algorith/

Supporting material drawn from the book The Algorithm Design Manual

Strings

Jewels of Stringology

Symbolic Integration

Risch Structure Theorem in Risch, R (1969), "The Problem of Integration in Finite Terms," in Transactions of the American Mathematical Society, Vol. 139, p 167.

John examines a technique for symbolic integration proposed by James Slagle over 30 years ago. In doing so, he uses CLIPS (C Language Integrated Production System), a nonprocedural language that supports system development across and among three programming paradigms -- rule-based, object-oriented, and procedural. June 1997, Dr. Dobb's Journal. www.ddj.com/articles/1997/9706/9706toc.htm

James R. Slagle. A heuristic program that solves symbolic integration problems in freshman calculus. Journal of the ACM, 10(4):507-520, October 1963.

Books:
Algorithms for computer algebra by Geddes, et al
Symbolic Integration by Manual Bronstein.

Traveling Salesman Problem

Traveling Salesman Problem
http://www.cs.sunysb.edu/~algorith/files/traveling-salesman.shtml

The Traveling Salesman Problem:
A Guided Tour of Combinatorial Optimization

Amazon: US UK

Trees

The Complete Collection of Algorithm Animations: Trees
www.cs.hope.edu/~alganim/ccaa/tree.html

B-Tree databases are very efficient with one-dimensional data. Ron shows how Hilbert curves can be used to efficiently manage multidimensional data, with no changes to the underlying database. Additional resources include aa799.txt (listings). July 1999, Dr. Dobb's Journal.
www.ddj.com/articles/1999/9907/9907toc.htm

The red-black algorithm, a twist on the classic binary search tree, uses an efficient mechanism for balancing trees. Dr. Dobb's Journal, April 1992. www.ddj.com/articles/1992/9204/9204toc.htm

Ternary Search Trees, Dr. Dobb's Journal, April 1998.
www.ddj.com/articles/1998/9804/9804a/9804a.htm