Algorithmic Links

This is a list of links relevant to the algorithms courses I teach. Topics are in alphabetic order.

• Computational BiologyGenBank , the grandfather of all the databases; you can run BLAST.
  A site for doing sequence alignment
  
• Cryptography and Number TheoryOn-line Encyclopedia of Integer Sequences
  John Conway's Doomsday Algorithm for mental calendar arithmetic
  RSA.com ; factoring challenge ; SHA-1 attacks
  Peter Shor's algorithms for factoring and discrete log on quantum computers
  British secret service prediscovery of RSA (see entries for History of Non-Secret Encryption)
  Primes is in P: SIGACT's website has links to the paper and related technical and nontechnical material
  Great Internet Mersenne Prime Search (GIMPS)
  Schneier on Security "A weblog covering security and security technology", by the noted author of Applied Cryptography, "the book the National Security Agency wanted never to be published."
  
  • Attack on SHA-1 hash function and its improvement to 2^63 ops.
  • Attack on MD5: 2 X.509 certificates with the same hash.
• AES (Advanced Encryption Standard)
• Data StructuresThe Red-Black Tree Song . I couldn't resist writing another search tree song, set to Go Insane by Lindsey Buckingham of Fleetwood Mac. (More: Here's a collection of Computer Songs and Poems. If you're a Tom Lehrer fan check out The Algorithms Tango.)
  Red-black tree animation. If you follow the brief instructions this step-by-step animation works nicely.
  This citation for the 1999 Kanellakis award lists a number of well-known programs using splay trees .
  Splay tree animation . This page works with IE, maybe not Mozilla. I recommend slowing the animation down.
  
• GraphsGood Will Hunting's "stumper" problem on adjacency matrices
  Graphsong, "these are a few of my favorite things".
  BFS: The Oracle of Bacon, for exact answers to the Kevin Bacon game.
  An update to Euler's solution of the problem that started graph theory: The 7/5 Bridges of Koenigsberg/Kaliningrad
  Simple graphs aren't so simple: Pankaj Mangal's homepage
  Proof of the Strong Perfect Graph Theorem. This 1960 conjecture became a theorem in 2002.
  Graph theoretic formulation of Sudoku
  
• Numerical ComputationFastest Fourier Transform in the West , with free download.
  
• OptimizationVasek Chvatal's TSP page
  Andrew Goldberg's network optimization codes
  Harvey Greenberg's Mathematical Programming Glossary for definitions, references, examples, common misconceptions!
  RIOT Website for baseball elimination numbers and other operations research pages.
  Compendium of NP-optimization problems & approximation algorithms
  
• P vs NPThe P vs. NP page with links to many "proofs".
  The NP-Completeness Column, currently appearing in ACM Transactions on Algorithms (TALG).
  Clay Math Institute's million dollar prize list, including "P=NP?"
  Lance Fortnow's Computational Complexity weblog - check here for breaking news.
  
• Quantum ComputationFactorization of 15

Collection of Mesh Generation Links

Collections of Links

• many mesh generation links by Robert Schneiders
• many mesh generation links by Steve Owen, Carnegie Mellon/ANSYS
• meshgen links Greg Sjaardema, Sandia
• CFD Online collection of CFD links
• triangulation links Marc Vigo, Barcelona

Bibliographies

• mesh generation bibliography, Paul Heckbert and Frank Bossen
• bibliography of triangulation & mesh generation, David Eppstein

Online Conferences/Journals/Newsletters & Big Paper Collections

• Meshing Roundtable 95, many papers available in PS
• Meshing Roundtable 96, many papers available in PS
• Meshing Roundtable 97
• Numerical Analysis Digest (NA Digest) online newsletter
• NASA tech reports (try search for "triang*")
• Numerical Aerodynamic Simulation, NASA, tech reports
• MGNet multigrid repository (papers, newsletters, code)
• SEL-HPC Article Archive collection of papers. The London & South-East centre for High Performance Computing (HPC, computational math, vision, misc, multigrid)
• INRIA tech reports (France). See, in particular, Project Gamma info (English), But see also French version, as it has more info. Project Gamma tech reports index, full index, (2671, 2672, 2741, 2882, 2928)
• CERCA technical reports abstracts (Montreal)
• Mesh generation mailing list, created by Steve Owen

Offline Conferences & Journals

• McNU97 Chicago, IL, June 97, note meshing session chaired by Canann
• International Journal for Numerical Methods in Engineering (IJNME) general info
• International Journal for Numerical Methods in Engineering (IJNME) table of contents
• von Karman Institute for Fluid Dynamics, Belgium (they hold seminars on meshgen for CFD, etc)

People and Their Papers

• Frank Bossen, anisotropic mesh generation, Swiss Federal Institute of Technology, Lausanne
• Paul Heckbert, anisotropic mesh generation, Carnegie Mellon
• multiresolution modeling modeling, surface simplification, and terrain links collected by Michael Garland and Paul Heckbert, Carnegie Mellon. These methods are mostly intended for simplification of surface meshes, but many could easily be specialized or generalized for 2-D or 3-D mesh coarsening.
• Critique of Computational Geometry, discussion of mesh generation
• David Eppstein's papers computational geometry & mesh generation (prof, UC Irvine)
• David Gossard shape optimization, mesh generation, topological design (ME prof, MIT)
• Kenji Shimada's work, on bubble meshing and related topics (incl. graded, anisotropic meshes), Carnegie Mellon University; earlier bubble meshing work at IBM Japan
• SDRC FEM/mesh paper (cites Shimada's bubble mesh)
• NASA Langley Research Center, GEOLAB geometry lab (Mary Anne Posenau et al)
• Castro-Diaz et al report on MODULEF project in french (anisotropic mesh generation, viscous flow)
• Steven Vavasis Cornell CS, numerical analysis, 3-D mesh generation
• Steven Vavasis on mesh generation
• discussion of 3-D Delaunay meshgen Peter Fleischmann, Austria
• Hybrid Prismatic/Tetrahedral Grid Generation paper abstract U of Texas
• "Modeling, Mesh Generation, and Adaptive Numerical Methods for Partial Differential Equations" book has article on meshgen by Shephard
• "CUBIT Mesh Generation Environment", chapter on meshgen Sandia
• David Marcum mesh generation, viscous flow (prof, Mississippi State)
• Mark Shephard RPI Civil Eng.
• RPI Civil Eng. Research
• RPI Civil Eng. Technical Reports
• SUMAA3D, Scalable Unstructured Mesh Computation, SUMAA3D Argonne National Laboratory (Lori Freitag, Carl Ollivier-Gooch, Mark Jones, and Paul Plassmann) mesh generation and FEM
• Julien Dompierre, CERCA, U of Montreal anisotropic mesh generation for CFD
• Vallet talk on Anisotropic mesh adaptation, Edinburgh, July 1996
• Estimation a posteriori et maillage adaptatif Fortin at Laval, Vallet at CERCA, et al
• Eduardo D'Azevedo optimal triangulation, differential geometry, approximation theory, Oak Ridge
• Bruce Simpson optimal triangulation, differential geometry, approximation theory, U of Waterloo
• Ernst Mucke alpha shapes, computational geometry, ANSYS
• O.C. Zienkiewicz finite element method, Swansea
• Nigel P. Weatherill mesh generation for CFD, Swansea
• Mike Hohmeyer, ICEM CFD Engineering
• Fluid Mechanics Laboratory, EPFL, Lausanne, Switzerland (emphasis on CFD, not meshgen)
• Paul Chew, Cornell, cool postscript animation of mesh generation
• CFD group at George Mason University, Rainald Loehner et al., unstructured 3-D mesh gen, military simulations (tanks, trucks, aircraft)
• Enzo Dari, Argentina, anisotropic mesh generation, 3-D mesh optimization
• simulation of particles in liquid, Daniel Joseph, U. of Minnesota, emphasis on CFD, not meshing
• Daniel Rypl, Czech Technical University in Prague, surface mesh generation, advancing front, anisotropic
• Petr Krysl, Computational Mechanics Group, Northwestern University (surface mesh generation, meshless methods)
• George Drettakis' discontinuity meshing info, computer graphics, radiosity, Grenoble, France
• Dani Lischinski, Hebrew University, Jerusalem, discontinuity meshing for radiosity
• Daniel Tunkelang's graph layout Java program
• Ken Brakke's Surface Evolver, cool software for variational surface problems in science

Software

• ANSYS commercial finite element software
• hexahedral mesh generator, ICEM CFD Engineering (commercial software)
• Vavasis' QMG mesh generator software
• mesh generation software links from Nina Amenta, Xerox PARC
• Jonathan Shewchuk's "triangle" mesh generator software
• Turbomesh, commercial software