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).
Quadratic
cdr- Constant time; we just cross off the first element (or follow the second box).
cddr-Constant time; Two steps to chop off the first two.
list-ref- Linear; we have to advance one step for each position
vector-ref- Constant; Sam told us so when we learned vectors. Our experiments show this.
map- Linear. We’ll have to make a list of as many elements as were in the first list.
range- Linear. For(range n), we have to make a list ofnelements.
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.
Sam did this. Lets us tell whether a value is less than or equal to (or greater than) another value.
b. In
binary-search, how do we know if two values are equal?
If the middle key is less than the sought value and the sought value is less than the middle key, they must be equal.
Runner says “That’s like double containment from linear.”
Sam says “If a <= b and b <= a, then a and b are the same.”
c. Explain the role of
midpoint,middle-element,middle-key, which are bound in thelet*ofbinary-search.
The index
Element in the middle section
Middle key is the key of that element; the thing we use when searching.
d. Describe what
lower-boundandupper-boundrepresent.
The left half and the right half of the section of the vector of interest.
lower-boundis inclusive (that means the value we’re searching could be at indexlower-bound).upper-boundis exclusive (that means the value we’re searching for cannot be at indexupper-boundor that indexupper-boundis outside the range of the vector).
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.)
The upper bound becomes the middle index (
midpoint).
If we decreased by one
(- midpoint 1), we might miss an element because upper bound is exclusive.
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.)
The lower bound becomes
(+ midpoint 1).
We use
(+ midpoint 1)rather thanmidpointbecause we know that it’s strictly after the middle (we’ve already compared to the middle)
g. If we double the length of the vector, what is the worst case effect on the number of recursive calls in
binary-search?
About one extra recursive call. We split the range of interest in half each time. So we quickly go from double the size to the original size.
When you want to use the whole value as a key, use (lambda (x) x)
as your get-key procedure.