Design and Analysis of Algorithms
CSC 321

Algorithms

• A great resource, both as a reference/compendium and as a readable overview of algorithm design it's hard to beat Skiena's Algorithm Design Manual.
• The National Institute of Standards and Technology maintains a list of algorithms, algorithmic problems and techniques.
• The standard reference for snobs is Donald Knuth's "The Art of Computer Programming".
• There are several blogs on algorithms and computational complexity, check out Gödel's Last Letter (e.g. Why algorithms are important: Big Problems with Big Iron) and cstheory stack exchange
• Borvuka's Algorithm

Visualizations

• Sorting algorithms
• Simulated annealing at work: helping the travelling salesman
• Approximation algorithms for the Euclidean Travelling salesman

Sorting

• Jon Bentley's google talk on quicksort
• Fast algorithms for sorting and searching strings, Bentley, Sedgwick, 1997

History of Computing

• For a history of computers from the early calculating machines of Pascal to the design of the von Neumann computer, see Herman Goldstine's excellent The Computer from Pascal to von Neumann.
• There are many books about Charles Babbage and his difference and analytical engines that foreshadow the von Neumann computer. Doron Swade's account of the London's Science Museums effort to actually build parts of the difference engine makes suspenseful reading, and offers many insights into Babbage's thinking (also see his talk at authors@google).

Limits of Computation

• Kurt Gödel published his famous incompleteness theorem in 1931. Several years later, Alan Turing developed his theoretical model of computation (the Turing machine) and recast the incompleteness theorem, showing that the halting problem is undecidable. For a history of the impact of Gödel's theorem on mathematics, see Kline's "Mathematics. The Loss of Certainty".
• Popular accounts of Gödel's theorem can be found in several of Raymond Smullyan's books ("Lady or Tiger", and "Forever Undecided"), and Douglas Hofstaedter's "Goedel, Escher, Bach". Also check out Rucker's "Infinity and the Mind" which is fun reading, and makes connections to philosophy and cognitive science. It contains a full proof of Gödel's theorem. Another readable account of Gödel's theorem is by Nagel and Newman.
• Andrew Hodges' account of Turing's life also contains explanations of Turing's technical contributions to computer science. Ag good introduction to computability theory is Martin Davis's book on "Computability and Unsolvability".
• In Neil Stephenson's science fiction novel "Cryptonomicon" Alan Turing makes an appearance as a character, and an amazing number of technical details, about Turing's work on descrypting the German Enigma machine during the second world war are explained.

Interviews, Puzzles, etc.

• How would you move Mount Fuji, William Poundstone, 2003. About the Microsoft Puzzle interviews.
• Algorithms for Interviews, Aziz, Prakash, 2010.
• Puzzles for Programmers and Pros, Shasha, 2007. About puzzles more than algorithms.
• Test your Agile Mind (Deutsche Bank)
• FoldIt project
• Robozzle

Python

• Python, the web-site, comprehensive, includes
  • Python 3.2.2 downloads (for Windows, MacOS)
  • Tutorial
  • Reference
• Graphs in Python
• Processing Images with tkinter