SUNY Geneseo Department of Computer Science

Exponential-Time Algorithms

Previous Lecture

Misc

Reminder that Homework 3 has been assigned

Lab 11 due today

Questions?

Labs next week & week after

• Last lab will be short, easily doable

Exponential Algorithms

Sections 15.2.1, 15.2.2

Algorithm to draw a tree as extension of LineDrawing class

Recursive

• Tree = trunk + branches (smaller trees)
• or leaf

Pseudocode to concrete code

Correctness

Analysis of execution time

• Related back to Towers of Hanoi: such algorithms are correlated to cⁿ. Which execution time here was (Θ(bⁿ))
• Execution time here depends on both b and n
• But b is just constant

Multiple recursions led to exponential time

Analyzing Exponential Algorithms

Problem: what's the greatest value of objects I can fit into a box?

• (aka the knapsack problem)

    int maxValue( box, objects )
        // "box" is a box that might already contain
        // some objects, "objects" a set of objects
        if objects is empty
            return the value of the objects in box
        else
            pick an object, o, from objects
            if o fits in box
                bestYet = maxValue( box+o, objects-o )
            else
                bestYet = 0
            return max( bestYet, maxValue( box, objects - o )

What's the worst-case execution time of this algorithm, in terms of number of objects?

Count anything that reasonably represents the work the algorithm does, e.g., the tests ("objects is empty" and "o fits in box"), other actions or calculations ("pick an object...," "max"), etc.

Recurrence on n, number of objects

• f(n) = 1 (if objects empty) if n=0
• f(n) = 2 + 2 f(n-1) if n > 0

Sum of powers of 2? from 2¹ through 2ⁿ (+ 2ⁿ)

Proof

• Base case, n = 0
  • 2ⁿ⁺¹ - 2 + 2ⁿ = 2¹ - 2 + 2⁰ = 1
• Induction: assume f(k-1) = 2^k - 2 + 2^k-1 when k-1 >= 0
• Show f(k) = 2^k+1 - 2 + 2^k
  • f(k) = 2 + 2f(k-1) from recurrence
  • = 2 + 2(2^k - 2 + 2^k-1)
  • = 2 + 2^k+1 - 4 + 2^k
  • = 2^k+1 - 2 + 2^k

Empirical Significance

Recall the Towers of Hanoi

Running time to solve for n disks is...?

• 2ⁿ - 1 move operations

See if we can see this empirically

• Solving with 4 disks took 130, 165, and 130 mS, for an average of 141.67.
• Tried timing solution for 40 disks. But while waiting, we extrapolated that it would take 308 years.

Next

Performance limits to computing

Read sections 16.1 and 16.2

Next Lecture