**Instructor:****Prof. Jason Hartline****Monday (10/7/2013) [slides]:**algorithms, algorithm analysis, efficiency**Wednesday (10/9/2013) [slides]:**intractability, NP-completeness

**Instructor:****Prof. Jason Hartline****Monday (10/7/2013):****[slides]**algorithms, algorithm analysis, efficiency**Wednesday (10/9/2013):****[slides]**intractability, NP-completeness

## Discussion Questions

**Submit your answers to Monday's questions**

**Submit your answers to Wednesday's 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.
- Scott Aaronson's essay gets a bit technical, but try to understand as much as possible. What is the relationship between mathematics and algorithms? Between arithmetic and algorithms?

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

## Reading and Media

Articles for the week can be obtained individually from their sources below.

**Monday**:

- Arthur Benjamin,
**Arthur Benjamin does Mathemagic**, TED talk, February 2005. - Don Norman,
**Toilet Paper Algorithms: I didn't know you had to be a computer scientist to use toilet paper**. - (SKIM) Scott Aaronson,
**Prime Facts: from Euclid to AKS**, 2003.

**Wednesday**:

- Ian Stewart,
**Million Dollar Minesweeper**, Scientific American, October 2000. - Lance Fortnow,
**The Status of the P Versus NP Problem**, CACM, September 2009.

## XKCD: Travelling Salesman Problem