SUNY Geneseo Department of Computer Science

Exponential Time

Previous Lecture

Misc

Hand out Homework 2

Hand out Lab 13

I'm out of town Thursday and Friday this week

• Prof. Zollo lectures Friday
• (I run afternoon lab Tuesday)

Questions?

Limits of Computing

Read Section 15.1

• Tower of Hanoi
• 3 towers, move stack of disks (small to large) to empty tower, moving only one disk at a time
• Algorithm to solve this
• Correctness proof
• Execution time
  • Θ(2ⁿ)
  • Looks small at first
  • But grows rapidly (e.g., 64-disk stack could take 585 billion years)

Empirically examine running time for Towers of Hanoi in a Concrete Program

• n = 6; times = 795, 795, 790; avg = 793 mS
  • avg/2⁶ = 12.4
• n = 7; times = 1523, 1673, 1624; avg = 1606 mS
  • avg/2⁷ = 12.5

When someone suggests running this on 50 disks, we can extrapolate what that running time would be from the time already measured for 7 disks, using the assumption that time is proportional to 2ⁿ.

• 1.6 seconds / 2⁷ = c = ? seconds / 2⁵⁰
• 1.6 / 2⁷ = ? / 2⁵⁰
• 1.6 (2⁵⁰ / 2⁷ ) = ? = about 1.4e13 seconds = about 446000 years

Next

Is there a faster algorithm for solving the Towers of Hanoi?

• Maybe someone could look cleverly at the problem and optimize the existing algorithm to be faster
• Or maybe there is something inherent in the problem that forces it to be this slow

Read sections 16.1 and 16.2

Next Lecture