## 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*^{n} 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.

Last update: Thursday, October 6th, 2011mflatt@cs.utah.edu |