Computer Science Fundamentals (CS153 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
a. Make a copy of mergesort.ss, my implementation of merge sort. Scan through the code and make sure that you understand all the procedures.
b. Make a copy of quicksort.ss, my implementation of Quicksort. Scan through the code and make sure that you understand the procedures.
c. Start DrScheme
a. Write an expression to merge two lists of strings. (You may choose the words yourself. Each list should have at least three elements.)
b. What will happen if you call merge
with unsorted
lists as the first two parameters?
Use split
to split:
a. A list of numbers of length 6
b. A list of strings of length 5
c. A length4 list of lists, where each element list is of the
form (lastname firstname major)
One of my colleagues prefers to define split
something
like the following
(define split (lambda (ls) (let kernel ((rest ls) (left null) (right null)) (if (null? rest) (list left right) (kernel (cdr rest) (cons (car rest) right) left)))))
a. How does this procedure split the list?
b. Why might you prefer one version of split over the other?
a. Run mergesort
on a list you design of fifteen integers.
b. Run newmergesort
on a list you design of twenty strings.
c. Uncomment the lines in newmergesort
that print out
the current list of lists. Rerun newmergesort
on a list
you design of twenty strings. Is the output what you expect?
a. Run both versions of merge sort on the empty list.
b. Run both versions of merge sort on a oneelement list.
c. Run both versions of merge sort on a list with duplicate elements.
d. Consider a list of lists, with each element list of the form
(lastname firstname major)
.
What's the difference between using each of the following as a
comparison algorithm in newmergesort
?
(lambda (val1 val2) (string<=? (car val1) (car val2)))
(lambda (val1 val2) (string<? (car val1) (car val2)))
e. Verify your answer experimentally.
Which version of the merge sort algorithm do you prefer,
mergesort
or newmergesort
? Why?
a. Quicksort a list of ten integers in increasing order.
b. In sorting a list of ten integers, does it make a difference
whether you use <
or <=
as the
comesbefore?
parameter? Why or why not?
c. Verify your results experimentally.
a. Use randomlist
to create a list, values
of fifty values.
b. Uncomment the lines that display the segmentation in
quicksort
.
c. Run quicksort
four times on values
. Do
you see the same steps every time? Why or why not?
Rewrite quicksort
so that it no longer needs same?
as a parameter.
a. Write a procedure, verifysort
, that verifies the
reasonably verifiable postconditions of mergesort
.
That is, (verifysort unsorted sorted
mayprecede?)
should return true (#t
) if
sorted in sorted order and sorted is a permutation of
unsorted. It should return false (#f
) otherwise.
Note that (verifysort '(1 1 2) '(1 2 2) <=)
should return false (#f
).
b. Use verifysort
to verify that mergesort
correctly sorts lists of 1000 random
numbers.
c. Use verifysort
to verify that newmergesort
correctly sorts lists of 1000 random
numbers.
d. Use verifysort
to verify that quicksort
correctly sorts lists of 1000 random
numbers.
a. Using DrScheme's builtin timing mechanism (you may have to look through the
online help to find information about that mechanism), make a table of the
running time of insertion sort, mergesort
,
newmergesort
, and quicksort
on inputs of size 0, 1, 100, 500, 1000, 5000, 10000, 50000, and 100000.
b. Graph your data.
c. Based on your data, what can you say about the relative speeds of the three sorting methods?
Wednesday, 22 November 2000 [Samuel A. Rebelsky]
{cs151}$2000F/Labs/mergesort.html
.
Thursday, 26 April 2001 [Samuel A. Rebelsky]
getkey
method.)
split
to return two lists, rather
than a list of lists.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/mergesort.html
.
Tuesday, 26 November 2002 [Samuel A. Rebelsky]
split
to return a list of lists.
newmergesort
, including
problem in which students compare the two versions of
merge sort.
Monday, 2 December 2002 [Samuel A. Rebelsky]
Wednesday, 4 December 2002 [Samuel A. Rebelsky]
verifysort
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/mergesort.html
.
Thursday, 14 February 2003 [Samuel A. Rebelsky]
fast sorting algorithmslab (was just a merge sort lab).
http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/mergesort.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 6 09:19:47 2003.
The source to the document was last modified on Thu Feb 27 22:10:07 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/fastsorting.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu