ListSearch.gif (446 bytes) Algorithms

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

DDJapr2000.jpg (3147 bytes)

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

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++
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 zA and zB:

zA = (1 f)z(xi, yj) + fz(xi+1, yj)

zB = (1 f)z(xi, yj+1)+ f z(xi+1, yj+1)

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

z(x,y) = (1 g)zA + gzB

Or, 

z(x,y) = (1 f)(1 g)z(xi, yj)  +   f(1 g)z(xi+1, yj)  +   (1 f)gz(xi, yj+1)  +  fgz(xi+1, yj+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 

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 Journalwww.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

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

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


Updated 15 Jun 2009
Since 30 May 1999