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.)

From Quadratic to Linear

Start with locate.rkt, which extends the filesystem code from the September 24 lecture with a locate function. The locate function finds the path to a file, if a file with the given name exists within the directory or a subdirectory.

As you will see, locate performs badly on deep directory structures. It’s not as bad as add-up-to, however, so you’ll need a helper function to make large directory trees.

1. Implement deep-file, which takes a natural number n and a file and produces a file-or-directory that contains the given file nested inside n directories named "well".

   For example, if wheel.rkt is defined as (make-file "wheel.rkt" 10), then (deep-file 0 wheel.rkt) should produce wheel.rkt, while (deep-file 2 wheel.rkt) should produce (make-dir "well" (list (make-dir "well" (list wheel.rkt)))).

2. Use results from deep-file to explore the time that locate takes to find a file that is nested under n directories.

   You can use the time form to see how long an expression takes to evaluate. So, you might try (time (locate (deep-file 20 wheel.rkt) "wheel.rkt")) to see how long it takes to find "wheel.rkt" nested inside 20 layers.

   To avoid printing long paths, you might want to wrap the locate call with something like cons?, which will check whether locate returns a path without printing the path: (time (cons? (locate (deep-file 20 wheel.rkt) "wheel.rkt"))).

3. Fix locate and its helper functions so that finding a file nested n layers deep takes time proportional to n. The key is to not use find, since a false value from locate is the same as a false value from find, while a non-false value from locate can be bound locally and used to build another locate result.