Warning! You are being recorded and transcribed, provided the technology is working correctly.
Approximate optimistic overview
Scholarly
Artistic
Multicultural
Peer
Musical, theatric, sporting, and academic events involving this section’s students are welcome.
Wellness
Misc
These do not earn tokens, but are worth your consideration.
Friday PSA
The Dean’s office has asked us to remind you about College academic honesty policies and about our course policies on the use of generative AI.
If you discover evidence that a student may have violated either the college academic honesty policy or the relevant academic honesty policy for your course/assignment, you must report that violation to the Committee on Academic Standing (CAS) for review.
Just in case it’s not clear already:
Can I reflect on S&B articles from past weeks?
Nope. Only the current week.
Is there a limit to the number of tokens I can earn in a week?
Yes. Five.
Can we go over the self check?
Certainly. We’ll do it as a quick TPS exercise.
Constant: Independent of the “size” of the input.
Linear: As the size of the input goes up, the number of steps goes up correspondingly (e.g., if we double the input size, we approximately double the number of steps).
cdr- Constant. Throwing away the first element should not depend on the number of elements in the list.
cddr- Constant. Two constant operations are still constant.
(list-ref lst n)- Linear innbecause we have to keep taking thecdrof the listntimes.
(vector-ref vec n)- Constant. Sam said that we can access the value directly and the size doesn’t matter. (Experiments confirm this.)
(map fun lst)- Linear in length of list. We have to apply the procedure to each element; if we add elements, we have more steps to do.
(range n)- Linear inn. The havenelements in the list, so asnincreases, the number of times we callconsto build the list increases directly.
Have we encountered any examples of quadratic time algorithms yet?
Yes. Many of the list recursive algorithms that use
lengthto determine if we have only one element end up being quadratic.
What exactly does less-equal? check?
It depends on what kinds of values we’re storing and what order they’ve been stored. It hould correspond to the order they’ve been stored.
For numbers, it usually checks if one number is less than or equal to another number. For strings, it normally checks if one string comes before another alphabetically (as determined by
string-ci<=?).
Can we go over the self check?
Certainly. TPS! (I’ve also added a question.)
a. Explain the role of the
less-equal?inbinary-search.
We compare the sought key to the key of the middle element, which lets us determine whether we’re found that key or need to search in the left half or the right half.
As Sam just said, we know that the elements are ordered by
less-equal?.
b. In
binary-search, how do we know if two values (aandb) are equal?
If a is less than or equal to b and b is less than or equal to a, then a equals b. (For our particular code, we say that if key is less than or equal to middle-key and middle-key is less than or equal to key, than key = middle-key.)
We shouldn’t use
equal?. It’s not in the one on the reading, and we’re trying to use that one. Or … some versions ofless-equal?give a different notion of equality. For examplestring-ci<=.(equal? "Lilli" "lilLI")returns false. However(and (string-ci<=? "Lilli" "lilLI") (string-ci<=? "lilLI" "Lilli"))returns true.
c. Explain the role of
midpoint,middle-element,middle-key, which are bound in thelet*ofbinary-search.
midpoint- the index of the middle of the section of interest.
middle-element- the value at that index
middle-key- the key of that element (e.g., the first name if we’ve sorted by name and are searching by name)
d. Describe what
lower-boundandupper-boundrepresent.
They represent the area of the vector that we’re searching. Initially, they represent the whole vector. As we look in the middle, we can usually throw away about half of the elements in the area we’re searching.
lower-boundis inclusive. That means that we (usually) need to consider the value at indexlower-bound.
upper-boundis exclusive. This means that we should not consider the value at indexupper-bound(but should consider things with smaller indices)
e. Describe why and how the
upper-boundof helpersearch-portionchanges when the key we’re looking for is less than the middle key. (If it doesn’t change, explain why not.)
We use
midpoint.
We do not use
(- midpoint 1)because the upper-bound is exclusive. It won’t look atmidpointbased on our policy. If we setupper-boundto(- midpoint 1), that says “we’ll never look at the value at position(- midpoint 1), and we know nothing about the value at the position.
f. Describe why and how the
lower-boundof helpersearch-portionchanges when the key we’re looking for is greater than the middle key. (If it doesn’t change, explain why not.)
We use
(+ midpoint 1)rather thanmidpointbecause the lower-bound is inclusive, and we know that the value atmidpointis not what we’re looking for.
g. If we double the length of the vector, what is the worst case effect on the number of recursive calls in
binary-search?
It’s just one more. In that one more, we cut it in half so it’s back to the original size.