[tiffanygirl]

1.
Describe the worst-case asymptotic running time of the all-positive? Scheme procedure defined below (from the Exam 1 comments). You may assume that all elements of p have values below some bound k, so the running time of > is constant. Remember to clearly define all variables you use in your answer.
(define (all-positive? p)
(if (null? p)
true ; reached end without finding non-positive, so result is true
(if (> (car lst) 0)
(all-positive? (cdr lst)) ; keep looking
false))) ; found one non-positive

2.
Define a Scheme procedure make-cumulative! that takes as input a mutable list, and modifies the list so that each element is the cumulative total of all elements up to and including itself. For example,

>(define p (mlist 1 2 3 4 5))
>(make-cumulative! p)
>p
{1 3 6 10 15}

Also, what is the asymptotic running time of your make-cumulative! procedure. You should not assume the running time of the + procedure is constant; instead, assume that its running time is linear in the size (number of bits) of its inputs.



Thank you all soo much.

Love,
Tiffany xxxoooxx