SUNY Geneseo Department of Computer Science

Optimality

Previous Lecture

Misc

Hand out Lab 13

• Due Monday Dec. 13 (not Dec. 6)

End of Semester Stuff

• Final is Wed. Dec. 15, noon
• Comprehensive, but more emphasis on material since 2nd hour exam (trees, exponential behavior, limits of computing)
• Designed for 2 hours, you have 3
  • 8 - 10 questions
• Format and rules otherwise similar to hour exams
• Donuts and Cider

SOFI's in class next Thursday (Dec. 9)

Lab does meet Monday Dec. 13

Questions?

Performance Limits to Computing

Sections 16.1 and 16.2

• Problem = situation requiring solution
• Algorithm = process for solving problem
• Θ(f(n)) is lower bound if every algorithm for problem runs in worst-case time Θ(f(n))
• Algorithm is optimal if its worst-case execution time is lower bound
• Find lower bounds by identifying restricting features of problem

Searching

• "Play" the adversary argument

• Goal
  • Yellow: ask the fewest questions
  • Blue: get the most questions
• Questions
  • A[4]? = 3
  • A[7]? = 4
  • A[8]? = 4
  • A[9]? = 5
• Searchers did binary search
  • ceiling( log₂(n+1) ) questions
  • ceiling rounds fractions up
  • floor rounds fractions down
• Adversary picked values to force search into largest unexplored section
• Any question that doesn't split array evenly leaves a big section to search
• So binary search is optimal for searching sorted data and lower bound is Θ(logn).
• But lower bound for searching unsorted arrays is Θ(n)
• Adversary proof

Many algorithms can be optimal for a problem

Open Questions

See section 16.3

Is the lower bound for factoring integers less than exponential (in number of digits)?

• Public key cryptography
• Secret info is a key
• PKC: 2 keys, one to encode, one to decode.
• Publish encoding key without breaking code
• RSA cryptosystem

Is P = NP?

• P = set of problems with polynomial time algorithms
• NP = a subset of (apparently) exponential time problems
  • Optimization problems
  • Travelling salesperson

• NP-Complete = "universal" problems in NP

Next

Unsolvable problems

Read Sections 17.1 and 17.2

Next Lecture