Functional Problem Solving (CSC 151 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: In this laboratory, we explore different issues related to searching.
Make a copy of binary-search-lab.rkt
, the code for this lab.
It is often useful when exploring a recursive algorithm to observe the steps the algorithm performs. In Scheme, we can sometimes observe steps in recursive calls by inserting code to display the parameters of the procedure at each recursive call.
a. Add calls to display
and newline
to the definition of
binary-search
, so that it prints out the values
of lower-bound
and upper-bound
each time the kernel procedure is called.
b. Redo steps b-h of Check 3 from the reading and report on the number of steps each search took.
a. What do you expect binary search to do if there are entries with duplicate keys?
b. Add two more entries with a key of "Otto"
and two
more entries with a key of "Amy"
. These new entries
should be slightly different, so that you can tell them apart. Make
sure you keep your vector in sorted order.
c. Which of the three do you expect binary search to return if you
search for "Otto"
?
d. Check your answer experimentally.
e. Which of the three do you expect binary search to return if you
search for "Amy"
?
f. Check your answer experimentally.
g. What does your experience in this exercise suggest about what binary search will do with multiple keys?
As you may have observed, objects-by-width
contains
the same twenty-six objects as in object-by-name
, but
with the objects organized by their width, rather than by name.
a. Write an expression to find an object with a width of 45.
>
(binary-search objects-by-width ___ ___ 45)
b. Write an expression to find an object whose width is 40.
c. Write an expression to find an object whose width is 35.
It is sometimes useful to learn not just that something is not
in the vector, but where it would fall if it were in the vector.
Write documentation and code for new-binary-search
that mostly behaves like binary-search
, except
that it returns a “half value” if the value being
searched for belongs between two neighboring values. For example,
if the key being searched for is larger than the key at position 5 and
smaller than the key at position 6, you should return 5.5. Similarly,
if the key being searched for is smaller than the key at position 0,
you should return -1/2. If the key being searched for is bigger than
the largest key, return (- (vector-length vec) 0.5)
.
For example,
>
(new-binary-search objects-by-name car string<=? "Andy")
0.5
>
(new-binary-search objects-by-name car string<=? "Greg")
7
>
(new-binary-search objects-by-name car string<=? "Heather")
8
>
(new-binary-search objects-by-name car string<=? "Hanna")
7.5
>
(new-binary-search objects-by-width (r-s list-ref 5) <= 1)
-0.5
>
(new-binary-search objects-by-width (r-s list-ref 5) <= 6)
3.5
>
(new-binary-search objects-by-width (r-s list-ref 5) <= 60)
25.5
You should use the code for binary-search
as your
starting point.
Note: If you find it more natural to represent the indices as exact numbers, rather than inexact numbers, you should feel free to do so.
Here are commands to search objects-by-name
for
"Paula"
and objects-by-width
for something
with width 45.
>
(binary-search objects-by-name car string<=? "Paula")
>
(binary-search objects-by-width (r-s list-ref 5) <= 45)
a. What do you expect to have happen if we swap the vectors in these commands, as in the following?
>
(binary-search objects-by-width car string<=? "Paula")
>
(binary-search objects-by-name (r-s list-ref 5) <= 45)
b. Check your answer experimentally.
c. Try searching objects-by-width
for the names
"Otto"
, "Erin"
, "Fred"
, "Charlotte"
, "Janet"
, and "Xerxes"
.
d. What do the previous steps of this experiment tell you about binary search?
As you may recall from Exercise 4, when searching for objects by width, we got only one of a variety of objects with a particular width. In some cases, it's useful to find not just some object of a particular width, but how many objects have that width, or have a width of that size or less.
a. One technique for finding out how many objects have a certain width
or less is to step through the vector until we find the first object
wider than the desired width. Using this technique, write a procedure,
(
, that, given a vector of objects
sorted by width, finds the number of objects that are no wider than
no-wider-than
objects
width
)width
.
b. A more efficient way to find the position is to use a variant of
binary search. Once again, our goal is to find the first object wider
than the desired width. However, this time we use binary search to find
that object. That is, you look in the middle.
If the middle object is wider than the desired width, recurse on the
left half, but also include the middle element since that may be the
one we're looking for. If the middle object is not wider than the
desired width, recurse on the right half.
Write a new version of no-wider-than
that uses
this technique.
Note: For part b, note that you cannot call the binary-search procedure directly. Rather, you will need to use it as a template for your code. That is, copy the procedure and then make modifications as appropriate.
As you've observed, when a key is repeated, binary search picks
one value with that key, but not necessarily the first value with
that key. We might want to write a variant,
newer-binary-search
, that
uses the ideas of binary search to find the first
element in the vector that contains the given key.
a. One strategy for implementing newer-binary-search
is to find some value with the given key (which binary search already
does) and then to step left in the vector until you find the first
value with that key. Implement newer-binary-search
using that strategy.
b. Of course, we use the binary search technique so that
we don't have to step through elements one-by-one. Rewrite
newer-binary-search
so that it continues to
“divide and conquer” in its attempt to find the first
element with that key.