Warning! You are being recorded (and transcribed).
Approximate overview
csc151 library for the next mini-project.Academic/Scholarly
Cultural
Peer
Wellness
Misc
NO! You do not get tokens for Wonderland Harris.
Your last individual mini-project! (Next up is a multi-week group mini-project.)
Build word clouds.
Will using bold or italic or colors or anything other than the default font count for anything?
Nope. But you might want to use it for your own aesthetics.
filterMost of you got this, or got something close. There are comments on Gradescope.
I will not go over the answer in class. Your first task on the lab is to go over it with your partner. If you can’t figure it out together, check with Maddy or me.
Some of you seem overly enamored of the pos parameter from vectors and
have forgotten the techniques of list recursion. Please avoid recursive
procedures that repeatedly use list-ref. It’s expensive. (So if you
wrote filter using a position, rewrite without it.)
Let’s consider the list-recursive version first. At each recursive step,
we throw away one element using cdr. So for a list of 20 elements, we’ve
called cdr approximately 20 times. For a list of 40 elements, we’ve called
cdr approximately 40 times.
In contrast, consider the version with (list-ref lst pos), where pos
grows from 0 to the index of the last element in the list.
A call to (list-ref lst n) requires n calls to cdr.
(define list-ref
(lambda (lst n)
(if (zero? n)
(car lst)
(list-ref (cdr lst) (- n 1)))))
Hence, if our procedure uses (list-ref lst 0) then (list-ref lst
1), then (list-ref lst 2), then (list-ref lst 3), … we’ll end
up with 0 + 1 + 2 + 3 + … + 19 = 190 calls to cdr for a list of 20
elements. That’s almost ten times as many as in the basic list recursion
version.
What if we have 40 elements? 0 + 1 + 2 + … + 39 = 780 calls. Almost 20 tiimes as many as the basic version! Ouch!
Note: Unlike (list-ref lst n), which requires that we call cdr n
times, (vector-ref vec n) can find the element in “constant time”
(independent of n).
Can we just drop an element as we go?
Yes. But then you don’t need the position. You’re always looking at the first element.
If we have to use list-ref, will it be expensive if we call list-ref
in every recursive call and don’t change the list?
Yes. Try to avoid using
list-ref(or(drop lst pos)) (orlength) (or anything similar).
How do we avoid length?
To make sure it has exactly one element.
(define one-element
(lambda (lst)
(and (pair? lst)
(null? (cdr lst)))))
(define two-elements
(lambda (lst)
(and (pair? lst)
(pair? (cdr lst))
(null? (cddr lst)))))
(define two-elements
(lambda (lst)
(and (pair? lst)
(one-elment (cdr lst)))))
(define three-elements
(lambda (lst)
(and (pair? lst)
(pair? (cdr lst))
(pair? (cddr lst))
(null? (cdddr lst)))))
(define three-elements
(lambda (lst)
(and (pair? lst)
(two-elements (cdr lst)))))
(define four-elements
(lambda (lst)
(and (pair? lst)
(three-elements (cdr lst)))))
Will we get grade reports soon?
Sam intends to send them to most of you tonight.
Are we permitted to use a page of notes on quizzes?
Of course.
Can we bring one page of notes for each quiz?
I suppose so.
Looking ahead to mini-project 9: How will the groups be chosen?
You’ll see next Wednesday. You have agency.
Should the neighboring pixels be a vector or a list or …?
A list.
reduce-rightYour base case should be the singleton list, in which case you return the one value in the list.
(reduce-right + '(1 2 3 4 5))
--> (+ 1 (+ 2 (+ 3 (+ 4 5))))
--> (+ 1 (+ 2 (+ 3 9)))
--> (+ 1 (+ 2 12))
--> (+ 1 14)
--> 15
(reduce-right - '(1 2 3 4 5))
--> (- 1 (- 2 (- 3 (- 4 5))))
--> (- 1 (- 2 (- 3 -1)))
--> (- 1 (- 2 4))
--> (- 1 -2)
--> -3
(reduce-right / '(1 2 3 4 5 6))
--> (/ 1 (/ 2 (/ 3 (/ 4 (/ 5 6)))))
--> (/ 1 (/ 2 (/ 3 (/ 4 5/6))))
--> (/ 1 (/ 2 (/ 3 24/5)))
--> (/ 1 (/ 2 15/24))
--> (/ 1 (/ 2 5/8))
--> (/ 1 16/5)
--> 5/16
index-of-matching!When you are writing index-of-matching, you will almost certainly need a
helper in which you keep track of the position with respect to the original
list.
However, you should not use list-ref. Rather, cdr through the
list as you go. The position represents how many times you’ve called cdr.