Fundamentals of Computer Science 1 (CS151 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]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Summary: We consider a more efficient way to sort values.
Contents:
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. Start DrScheme
a. Write an expresssion to merge the lists (1 2 3)
and
(1 1.5 2.3)
.
b. Write an expression to merge two lists that contain the same values.
c. Write an expression to merge two lists of strings. (You may choose the strings yourself. Each list should have at least three elements.)
d. Assume that we represent names as lists of the form
(last-name first-name)
.
Write an expression to merge the following two lists
(define cs-faculty (list (list "Bishop" "David") (list "Gum" "Ben") (list "Rebelsky" "Samuel") (list "Stone" "John") (list "Walker" "Henry"))) (define young-cs-kids (list (list "Rebelsky" "Daniel") (list "Rebelsky" "Jonathan") (list "Rebelsky" "William")))
a. What will happen if you call merge
with unsorted
lists as the first two parameters?
b. Verify your answer by experimentation.
c. What will happen if you call merge
with sorted lists
of very different lengths as the first two parameters?
d. Verify your answer by experimentation.
Use split
to split:
a. A list of numbers of length 6
b. A list of numbers of length 5
c. A list of strings of length 6
a. Run merge-sort
on a list you design of fifteen integers.
b. Run new-merge-sort
on a list you design of twenty strings.
c. Uncomment the lines in new-merge-sort
that print out
the current list of lists. Rerun new-merge-sort
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 one-element list.
c. Run both versions of merge sort on a list with duplicate elements.
a. Using DrScheme's built-in 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, merge-sort
and
new-merge-sort
on inputs of size 0, 10,
100, 1000, 10000, 20000, and 5000.0
b. Graph your data.
c. Based on your data, what can you say about the relative speeds of the three sorting methods?
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?
Wednesday, 22 November 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/mergesort.html
.
Thursday, 26 April 2001 [Samuel A. Rebelsky]
get-key
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.
new-merge-sort
, 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]
verify-sort
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/mergesort.html
.
Monday, 28 April 2003 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/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]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[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:28:58 2003.
The source to the document was last modified on Mon Apr 28 23:11:53 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Labs/mergesort.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby