Topic: Algorithms and Tractability
Monday: algorithms, algorithm analysis, efficiency.
Wednesday: intractability, NP-completeness.
Discussion Questions:
Monday
- Come up with a task that can be solved via several algorithms. Come up with a very bad algorithm. Come up with a good algorithm. Why is one algorithm bad and the other good?
- What is Arthur Benjamin’s multiplication algorithm? How does it compare to algorithms you know for long multiplication?
- Come up with a scenario like Don Norman’s ‘toilet paper algorithms’ scenario where choice of algorithms is important.
Wednesday
- Come up with a problem (not mentioned in any of the readings) where a solution is easy to check, but finding a solution is hard. Bonus points if your problem is important to some academic interest of yours.
- Do you think P equals NP or not?
- What is the positive impact of P not equal to NP? Negative impact?
- What is the positive impact of P equal NP? Negative impact?
Readings and Media:
Monday
Arthur Benjamin does Mathemagic, Arthur Benjamin, TED talk, February 2005.
Toilet Paper Algorithms: I didn’t know you had to be a computer scientist to use toilet paper, Don Norman, jnd.org, 2002.
[optional] Prime Facts: from Euclid to AKS, Scott Aaronson, scottaaronson.com, 2003.
Wednesday
Million Dollar Minesweeper, Ian Stewart, Scientific American, October 2000.
[skim] Knowledge, Creativity, and P versus NP, Avi Wigderson, April 2009.
XKCD: Travelling Salesman Problems
