Analysis of Algorithms

Syllabus

Homework Assignments

1. due Friday, September 5, 2008
2. Chapter 2 Problems #2, #3, #4, #5, #6, #8, due Wednesday, September 17, 2008
   • Compute the exact number of prints done in the algorithm for printing all distinct triples, where the values range from 1 to n.
3. due Monday, September 29, 2008
4. due Monday, October 20, 2008
5. due Friday, October 31, 2008
6. due Wednesday, December 3, 2008

November 26 and December 1, 2008

• Additional Information for 3SAT to 3DM Reduction
• Additional Information for 3SAT to Subset Sum Reduction

Programming Assignment

Interesting Links

• The Algorithm: Idiom of Modern Science, by Dr. Bernard Chazelle, Princeton University
• 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