CS 1410-20 Lab 6

From Exponential to Linear

The following add-up-to function takes a number and a list of numbers. It adds up the numbers in the list, but it leaves off elements near the front of the list to keep them sum less than the given number.

(Imagine that the numbers represent block heights, and the goal is to stack the blocks as high as posisble, but without hitting the ceiling. To keep it simple, you always start with blocks at the end of the list and try to add the next earlier block.)

  ;; add-up-to : list-of-num num -> num
  ;;  To add elements of l, dropping
  ;;  elements of l to stay below max-n
  ;;  when adding from the end of the list back.
  (define (add-up-to l max-n)
    (cond
      [(empty? l) 0]
      [(cons? l)
       (local [(define maybe-total
                 (+ (first l) (add-up-to (rest l) max-n)))]
         (cond
           [(<= maybe-total max-n) maybe-total]
           [else (add-up-to (rest l) max-n)]))]))
  
  (check-expect (add-up-to empty 10) 0)
  (check-expect (add-up-to '(1 2 3) 10) 6)
  (check-expect (add-up-to '(1 2 3 4) 10) 10)
  (check-expect (add-up-to '(2 3 4 5) 10) 9)

What kinds of inputs cause this function to take time proportional to 2ⁿ for a list of length n? Fix add-up-to to avoid the problem and produce a function whose running time is propotional to n.

(If you generalize the problem so that you’re allowed to leave out blocks at the end of the list to better fit blocks from the beginning of the list, then the problem becomes harder.)

Start on Homework

Start working in HW 7.