Analysis of Algorithms

- due Friday, September 7, 2012
- Chapter 2 Problems 1-6, 8
**due Wednesday, September 19, 2012** - due Wednesday, September 26, 2012
- due Friday, October 12, 2012
- due Monday, October 22, 2012
- due Monday, November 19, 2012
- due Friday, December 7, 2012

- 3SAT to 3DM Reduction
- 3SAT to Subset Sum Reduction
- A Survey of NP-Complete Puzzles by Kendall, Parkes, and Spoerer
- Million-Dollar Minesweeper
- Wikipedia article on P vs. NP
- Theory of Computation course by Dr. Gabriel Robins at the University of Virginia (has excellent material on NP-completeness)

- Mid-Central Region for the ACM International Collegiate Programming Contest
- The Algorithm that Runs the World
- 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
- College Admissions and the Stability of Marriage, by Gale and Shapley
- 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
- Wikipedia article on Karatsuba algorithm for large integer multiplication
- Implementation and experiments with Karatsuba's algorithm
- 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
- Generalizations of the Karatsuba Algorithm for Efficient Implementations, by Wiemerskirsch and Paar
- 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
- C implementation of Ford-Fulkerson Algorithm
- Potential problems with Ford-Fulkerson Algorithm involving non-integer edge capacities
- Boost (free peer-reviewed C++ source libraries)
- Sherlock of Rock, an article about using the Fast Fourier Transform on music