Additional NP-Completeness Information

• 3SAT to 3DM Reduction
• 3SAT to Subset Sum Reduction

Programming Assignment

Interesting Links

• Mid-Central Region for the ACM International Collegiate Programming Contest
• Pedagogically Effective Effortless Algorithm Visualization with a PCIL by Malone, Atkison, Kosa, and Hadlock
• The Algorithm: Idiom of Modern Science, by Dr. Bernard Chazelle, Princeton University
• Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken, by Joshua Bloch, Google
• Algorithms add up to big business by Teresa F. Lindeman, Pittsburgh Post-Gazette
• New Algorithm Significantly Boosts Routing Efficiency of Networks by Paul K. Mueller, University of California at San Diego
  • XL: An Efficient Network Routing Algorithm by Levchenko, Voelker, Paturi, Savage
• Instant-Messagers Really Are About Six Degrees from Kevin Bacon by Peter Whoriskey, Washington Post
  • Planetary Scale Views on a Large Instant-Messaging Network by Leskovec and Horvitz
• A tribute to the stable marriage problem by Chien-Chung Huang, Ph.D. student at Dartmouth College
• Are Medical Students Meeting Their (Best Possible) Match? by Sara Robinson, SIAM News, April 2003
• The Britney Spears Problem: Tracking who's hot and who's not presents an algorithmic challenge, American Scientist, July/August 2008
• Google reigns as world's most powerful 10-year-old, Associated Press, via MIT Technology Review
• Rivest and Smith's Three Antifraud Voting Protocols, presented at 2007 USENIX/Accurate Electronic Voting Technology Workshop
• Algorithms in the "Real World", a course at Carnegie-Mellon University, something to think about after finishing this course
• Algorithmist
• Tuning Strassen's Algorithm for Memory Efficiency by Thottethodi et al.
• Fast Matrix Multiplication on Apple G4, by Crandall and Klivington, discusses Strassen's algorithm
• Practical In-Place Mergesort, by Katajainen, Pasanen, and Teuhola
• Pancake Sorting
• Academics Sink Teeth into Yahoo Search Service
• Ford-Fulkerson Network Flow Applet
• Wikipedia article on Ford-Fulkerson algorithm
• Boost (free peer-reviewed C++ source libraries)
• Sherlock of Rock, an article about using the Fast Fourier Transform on music
• A Survey of NP-Complete Puzzles by Kendall, Parkes, and Spoerer