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