- Exam 2
- Nominally Thursday, Nov. 5
- We could move it later, e.g., Nov. 10 through Nov. 19
- Trade-off: not so soon after 1st exam vs more material (will cover things from 1st exam to date of 2nd)
- Let me know if you have preferences (default action will be to keep exam on the 5th)
- Lower bound = smallest asymptotic worst-case time for any algorithm that solves the problem
- Adversary arguments
- 0. Imagine adversary who controls input to problem wants to make you take a long time
- 1. Devise strategy for adversary
- 2. What is least time you could need to solve problem
- Examples
- Search in sorted list
- Adding n-by-n matrices (assuming all constant-time arithmetic operates
on constant number of operands)
- (This is really just the “must look at all input elements” argument, but with a more rigorous argument for why you have to look at all of them)
- Search in sorted list
- Information-theory interpretation
- How much information you (can be forced to) need to solve problem?
- Bit = amount of information in yes/no answer
- m bits can distinguish 2m possibilities
- Searching sorted list: need to find position of k among n possibilities
- Therefore log2n bits
- Problem set
- Decision trees
- Lower bound for sorting
- Given input vector of n elements, output rearrangement A such that A[i] ≤ A[i+1] for all 1 ≤ i ≤ n-1
- Basic operations are comparisons and swaps
- What do you need to know to solve sorting?
- What permutation you started with
- How many bits does that take?
- log2(n!)
- Read section 8.1