Fundamentals of CS I (CS151 2002F)

**Primary:**
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]

**Groupings:**
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]

**ECA:**
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]

**Miscellaenous:**
[Scheme Reference]
[CS151 2002F Gum]
[CS151 2001S]
[SamR]
[Glimmer Labs]
[schemers.org]

- Exercises
- Exercise 0: Preparation
- Exercise 1: Merging
- Exercise 2: Reflecting on Merging
- Exercise 3: Splitting
- Exercise 4: Splitting, Revisited
- Exercise 5: Sorting
- Exercise 6: Special Cases
- Exercise 7: Sorting Students
- Exercise 8: Verifying Sorts
- Exercise 9: Comparing Sorts
- Exercise 10: Experimentally Comparing Sorts

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 words. (You may choose the words yourself. Each list should have at least three elements. You can represent names as strings.)

d. Assume that we represent names as lists of the form
`(`

.
Write an expression to merge the following two lists
*last-name* *first-name*)

(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

d. A length-4 list of lists (each sublist should have length 2 or more).

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 `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.

Assume that we represent students with a list of the form

(lastname firstname id major)

a. Create a list of ten or more students.

b. Write an expression to sort that list by first name.

c. Write an expression to sort that list by id number.

d. Write an expression to sort that list so that students are arranged alphabetically by major and then alphabetically by last name within each major.

a. Write a procedure, `verify-sort`

, that verifies the postconditions
of `merge-sort`

.
That is, `(verify-sort `

should return true (*unsorted* *sorted*
*may-precede?*)`#t`

) if
*sorted* in sorted order and *sorted* is a permutation of
*unsorted*. It should return false (`#f`

) otherwise.

Note that `(verify-sort '(1 1 2) '(1 2 2) <=)`

should return false (`#f`

).

b. Use `verify-sort`

to verify that `merge-sort`

correctly sorts lists of 1000 random

numbers.

b. Use `verify-sort`

to verify that `new-merge-sort`

correctly sorts lists of 1000 random

numbers.

Which version of the merge sort algorithm do you prefer,
`merge-sort`

or `new-merge-sort`

? Why?

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, 1, 10,
100, 500, 1000, 2000, and 5000.

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]

- Created. All new!
- This version available at
`http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/mergesort.html`

.

Thursday, 26 April 2001 [Samuel A. Rebelsky]

- Updated formatting.
- Added the subproblem in which students merge lists of names.
- Added the subproblem in which students reflect on the difference
between the code as given in the reading and the code as given
in the library file. (In the latter, I add a
`get-key`

method.) - Updated the improved
`split`

to return two lists, rather than a list of lists. - This version available at
`http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/mergesort.html`

.

Tuesday, 26 November 2002 [Samuel A. Rebelsky]

- Updated formatting.
- Other minor updates.
- Rewrote
`split`

to return a list of lists. - Added problems that pertain to
`new-merge-sort`

, including problem in which students compare the two versions of merge sort.

Monday, 2 December 2002 [Samuel A. Rebelsky]

- Fixed two stupid typos. (Thanks Phil and Davis!)

Wednesday, 4 December 2002 [Samuel A. Rebelsky]

- Added more information about
`verify-sort`

. - This version available at
`http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/mergesort.html`

.

**Primary:**
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]

**Groupings:**
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]

**ECA:**
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]

**Miscellaenous:**
[Scheme Reference]
[CS151 2002F Gum]
[CS151 2001S]
[SamR]
[Glimmer Labs]
[schemers.org]

**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 Wed Dec 4 13:16:28 2002.

The source to the document was last modified on Wed Dec 4 13:16:25 2002.

This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/mergesort.html`

.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu