Analysis of Algorithms

- due September 10, 2010
- Chapter 2 Problems #1, #2, #3, #4, #5, #6, #8, due Wednesday, Sept. 22, 2010
**Extra Problem for CSC 5400 students**: #7

- due September 27, 2010
- due October 15, 2010
- due November 19, 2010
- due December 12, 2010

- 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
- 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
- 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