Transcript tutorial3x

CS116 – Tutorial 3
Accumulative Recursion/Runtime
Reminders:

Assignment 3 is due Wednesday at Noon.
Review
Accumulative Recursion
 Run Time

How much runtime do you want
me to cover for this tutorial?
A)
B)
C)
D)
E)
None
A little bit
Half the time
It doesn’t matter to me
What’s runtime?
Accumulative Recursion
(define (fn lst)
(local
Usually use in
place of lst when
recursing
Accumulators: can have
as many as you need
[(define (acc-fn whats-left acc1 acc2 … accn)
(cond
Use accs to help
[(base-case whats-left)…acck…] produce the
correct result
…
Put more
cases in if
you need
[else (acc-fn update-parameters)]))]
them
(acc-fn initial-whats-left initial-acck … ))

Accumulators “keep track” of something
so that you can quickly produce the
expected result
Question 1

Write an accumulatively recursive
function sum-list which consumes a
list of numbers and produces their sum.

Trace(sum-list (list 1 2 3))

Compare this accumulative version with
the structural recursive version from
earlier.
Trace of list-to-num
(list-to-num ‘(8 0 2))
⇒ (list-to-num-acc ‘(8 0 2) 0)
⇒ (list-to-num-acc ‘(0 2) (+ (* 10 0) 8))
⇒ (list-to-num-acc ‘(0 2) 8)
⇒ (list-to-num-acc ‘(2) (+ (* 10 8) 0))
⇒ (list-to-num-acc ‘(2) 80)
⇒ (list-to-num-acc empty (+ (* 10 80) 2))
⇒ (list-to-num-acc empty 802)
⇒ 802
Question 3
Write an accumulatively recursive function find
that consumes a list of symbols alos and a
symbol sym, and returns the list of indices of
positions in alos with symbol sym. Recall that
the first position in a list has index 0.You may use
reverse.
 For example, (find (list ‘a ‘v ‘d ‘v) 'v)
should return (list 1 3), while
(find (list ‘a ‘v ‘d ‘v) 'q) should return
empty.

Question 4
Write an accumulatively recursive function
count-max that consumes a nonempty
list of numbers alon and returns the
number of times the largest number in
alon appears.
 For example,

◦ (count-max (list 1 3 5 4 2 3 3 3 5))
=> 2
◦ since the largest element of the list, 5, appears
twice.Your function should pass through the
list only once.
Runtime Review
Look at the “worst case” scenario (i.e.
longest time)
 Only for code that gets executed when
you run it
 Assume function works (i.e. will not
produce an error when you run it)

Runtime Review

O(1) – Constant
◦ does not depend on the size of the input
(first x), (rest x), (symbol? x), (map sqr (list 1 2 3))
Ex: simple functions, or does not do something n
times

O(n) – Linear
◦ depends on the size of the input
(map sqr (list1 2 … n))
Ex: abstract list functions, function call once (on a
single cond case)
Runtime Review

O(n2) – Quadratic
◦ time proportional to square of input
(map sqr (build-list n add1))
Ex: nested abstract list function, O(n) done
multiple times

O(2n) – Exponential
◦ As size of input increases, run time doubles
Module 3, Slide 22: fib
Ex: Multiple function calls
(>1 calls in one cond case)
Question 5

For each of the following determine what
the worst-case runtime is.
Determine the worst-case run-time in terms of n,
assuming n elements in lon
(define (sum-list1 lon)
(cond
[(empty? lon) 0]
[else (+ (first lon)
(sum-list1 (rest lon)))]))
Determine worst-case run-time in terms of n,
assuming n elements in loi
(define (evens loi)
(filter even? loi))
Determine the worst-case run-time in terms of n
(define (create-number-lists n)
(cond
[(= n 0) empty]
[else
(cons (build-list n identity)
(create-number-lists
(sub1 n)))]))
Determine the worst-case run-time in terms of n
(define (create-a-list n)
(cond
[(even? n) empty]
[else
(build-list 3
(lambda (y) (+ n y)))]))