CSC151.01 2009F Functional Problem Solving : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary: In this lab, we explore a variety of issues related to the insertion sort algorithm.
a. Make a copy of insertion-sort-lab.scm
, the code for this lab.
b. In that file is the definition of a list named drawing
.
Look at that definition and do your best to understand the form of the
list.
a. Test the insert-number
procedure from
the reading by inserting the number 42
(list 42 42 42)
.
b. Discuss with your partner (or someone nearby) why you think we had you
do each of these tests. (That is, why would one want to check that
insert-number
works on each of these lists?)
c. What would you expect to happen if the list is
not in ascending order when
insert-number
is invoked?
d. Check you answer experimentally.
Write a new insert-string
procedure that inserts
a string into a list of strings that are in alphabetical order:
>
(insert-string (list "ape" "bear" "cat" "emu" "frog") "dog")
("ape" "bear" "cat" "dog" "emu" "frog")
In case you've forgotten, string<=?
and
string-ci<=?
are useful predicates for
comparing strings for order.
Your goal in this problem is to follow (and therefore better understand)
the pattern of the insert-number
procedure.
Hence, you may not use the generalized insert
procedure in writing insert-string
.
a. Add calls to the display
and
newline
procedures to the body of the helper in
numbers-insertion-sort
so that it displays the
values of unsorted
and sorted
, appropriately
labeled, at each step of the sorting process.
b. Use the revised numbers-insertion-sort
procedure to sort the values 7, 6, 12, 4, 10, 8, 5, and 1.
When we use a new procedure, we often want to test it on a variety of
cases. We've seen that numbers-insertion-sort
works on a few simple cases. But we should also check some
“special cases”, cases that might stress the algorithm.
Make a list of some lists that a poorly-implemented
insertion sort procedure might have difficulty with.
Review the code for numbers-insertion-sort
to figure out what you think it will do for each of the following
cases. Then check your answer experimentally.
a. An empty list.
b. A list containing only one element.
c. A list containing all equal values.
d. A list in which the elements are originally in descending numerical order.
e. A list in which the elements are already in ascending numerical order.
f. A list containing some duplicate elements.
a. Using define$
(for both insert-number
and
numbers-insertion-sort
) and analyze
,
determine how many calls to insert-number
are involved in
sorting each of the following lists. For example, for the first list, you
would write
>
(analyze (numbers-insertion-sort (iota 5)) insert-number)
i. (iota 5)
ii. (iota 10)
iii. (iota 20)
iv. (iota 40)
v. (reverse (iota 5))
vi. (reverse (iota 10))
vii. (reverse (iota 20))
viii. (reverse (iota 40))
b. Explain, to the best of your ability, what the numbers you got say about the number of steps insertion-sort takes.
Write a call to the generalized
list-insertion-sort
to sort the list
("clementine" "starfruit" "apple" "kumquat" "pineapple"
"pomegranate")
alphabetically.
insert!
a. Add the following definition to your definitions pane.
(define numbers (vector 1 5 6 7 2 8 0 3))
b. Check that vector-insert!
works by using it to
move the 2 into the correct place in the first five spaces in
numbers
.
Note: Solving this step requires that you
understand the parameters to vector-insert!
.
c. Extend vector-insert!
so that it displays the
vector and the position at every step. That is, add calls to
display
and newline
in the
kernel, before the cond
.
d. Re-create the numbers
vector from step a, and observe what happens
when we insert the 2, then the 8, then the 0, then the 3.
e. Observe the insertion steps in a vector of about eight randomly-generated numbers.
>
(define nums (vector (random 10) (random 10) (random 10) (random 10) (random 10) (random 10) (random 10) (random 10)))
>
(vector-insertion-sort! nums _____)
f. Explain, in your own words, how this procedure works.
a. Write a call to the generalized
list-keyed-insertion-sort
to sort the list
("clementine" "starfruit" "apple" "kumquat" "pineapple"
"pomegranate")
alphabetically.
b. Review the structure of drawing
(a
list of named objects). Then write a call to the generalized
list-keyed-insertion-sort
to sort drawing
by object name.
c. Write a call to the generalized list-insertion-sort
to sort drawing
alphabetically by color name.
d. Write a call to the generalized
list-keyed-insertion-sort
to sort drawing by
object width.
Write a procedure, (
that sorts a vector of compound objects by key.
vector-keyed-insertion-sort
vec
get-key
may-precede?
)
While it is possible to write this procedure by converting the vector to
a list, using list-keyed-insertion-sort!
, and then
converting the result back to a vector, you should not use this strategy.
Rather, write this procedure directly. (You may want to use
vector-insertion-sort!
as a template.)
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.