- Exam 2
- Nov. 5 (next Thursday)
- Material since 1st exam, e.g., trivial lower bounds, adversary
arguments, decision trees, basic complexity classes, etc.
- Section 8.1 covers decision trees and sorting
- Rules and format otherwise similar to 1st exam, especially open references, closed person. Maybe more detailed questions
- Math Dept. Research Weekend
- Opportunity to get some sense of what mathematics research is like through a roughly 1-day intensive project.
- Good source of recommendations and experience for REU applications.
- Led by Prof. Cooney
- Quantum games/computing
- Opening colloquium and dinner Friday Nov. 13, main project Saturday Nov. 14
- Apply at http://goo.gl/forms/MjLj2PqE9D
- Questions to Prof. Cooney (cooney@geneseoedu)
- Rules
- Goal = move tower from 1 pole to another
- Disks can only rest on poles
- Can’t have bigger disk on top of smaller
- Only move 1 disk at a time
- These rules are rigid enough that you can deduce a lower bound on solution time from them
- Are there intermediate state(s) every solution has to go through?
- Yes, involving little towers
- In particular, an n-1 disk tower
- Since it would be pointless to move the small tower using a nonoptimal strategy, you can write a recurrence for the minimum number of moves
- Solving the recurrence yields minimum time in Θ(2n)
- Are there intermediate state(s) every solution has to go through?
- Moral: there are good problems (low lower bounds) and bad problems (exponential time)
- Today’s analysis proved the existence of bad problems
- Introduction to computational complexity
- Read
- Chapter 34 introduction
- Section 34.1 up to but not including “A formal-language framework”