Fundamentals of Computer Science I (CS151.02 2007S)
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
This laboratory is also available in PDF.
Summary: In this laboratory, you will explore the
Quicksort algorithm. Quicksort takes advantage of two key
algorithm design techniques: divideandconquer and the power of
randomness (a.k.a. luck
).
Contents:
a. Make a copy of sorts.scm
.
b. Scan through the code and make sure you understand the purpose of each procedure. (You need not understand how the procedure does what it does, but you must understand what it does.)
a. Generate a list, grades
, of 50 random numbers,
all between 0 and 100 (inclusive).
b. How many of those numbers in grades
do you expect to be less than 50?
c. Using partition
, segment grades
into three parts:
The values less than 50, the values equal to 50, and the values greater
than 50.
d. Determine the size of each of those three lists using
(map length (partition codes 50 <))
e. Determine the size of each segment in a few random lists of length 1000, using
(map length (partition (randomlist 100 1000) 50 <))
f. What do you expect partition to do if you use <=
rather than <
for the precedes?
parameter?
g. Check your answer experimentally.
a. Generate a list, codes
, of 1000 random numbers, all
between 0 and 100,000 (inclusive).
b. Suppose we segment codes
into three parts, using a random
pivot. How many numbers appeared in each part? You can answer this question
with
(map length (partition codes (randomelement codes) <))
d. Repeat the first two steps nine more times, recording the size of each part each time.
e. Given the results from the previous step, how well does it seem that a randomly chosen number partitions the list?
a. Generate a list, codes
, of 50 random numbers, all
between 0 and 1000 (inclusive).
b. What do you expect to happen if you sort those 50 numbers using
Quicksort
, with <
as the
precedes?
parameter? For example,
> (Quicksort codes <)
c. Check your result experimentally.
d. What do you expect to happen if you sort those 50 numbers using
Quicksort
, with >
as the
precedes?
parameter? For example,
> (Quicksort codes >)
e. Check your result experimentally.
f. What do you expect to happen if you sort those 50 numbers using
Quicksort
, with <=
as the
precedes?
parameter? For example,
> (Quicksort codes <=)
g. Check your result experimentally.
a. Uncomment the lines in Quicksort
that report on what
it is doing. (Hint: They are calls to display
and
newline
.)
b. Generate a list, codes
, of 50 random numbers, all
between 0 and 1000 (inclusive).
c. Observe what happens when you sort the list using Quicksort with
<
as the precedes?
parameter.
d. Observe what happens when you sort the list using Quicksort with
<=
as the precedes?
parameter.
e. Commentout or delete the lines you uncommented in step a.
In studying algorithms, we often count the number of times we call
particular procedures. For example, we might consider how many times
we call cons
or precedes?
. The
analyst.scm
library (already included in
sorts.scm
) supports some sipmle analyses. There are a
few simple steps to analysis:
define
with define$
.
(analyze expression proc)
(analyze expression)
a. Replace the define
for partition
with define$
. This change will slow down
partition
, but will also allow us to analyze it.
a. Build a list, nums
, of 50 random numbers,
all between 0 and 1000 (inclusive).
b. How many times do you expect that partition
will call
cons
in partitioning that list, using a pivot of 500?
c. Check your answer, using
(analyze (partition nums 500 <) cons)
d. How many times do you expect that partition
will call
precedes?
in partitioning that list, using a pivot of 500?
e. Check your answer, using
(analyze (partition nums 500 <) precedes?)
e. What other procedures do you expect to be called, and how many times do you expect each to be called?
f. Check your answer, using
(analyze (partition nums 500 <))
g. In doing analysis, we often care more about the steps than the result (once we've determined that the procedure works correctly). Hence, instead of printing the result, we might want to store it in a variable. For example, we see just the calls for the previous part of the exercise with
(define parts (analyze (partition nums 500 <)))
Verify that this works (and that parts is defined appropriately).
a. Update insertionsort
and insert
to use
define$
instead of define
.
b. Use the following two lines to determine how many calls to
precedes?
the
insertionsort
procedure makes when sorting a list of fifty
random numbers. (Note that the following define
commands let
us capture the results without looking at the results.)
(define sample (randomlist 1000 50)) (define result (analyze (insertionsort sample <) mayprecede?))
c. Try the previous step (that is, generating a random list, insertion
sorting it, and counting the number of calls to mayprecede?
)
three more times. Did you get the same number every time? If not,
why do you think you got different numbers?
d. Rerun the analysis using lists of size 100, 200, and 400 (four lists of each size; simply change the 50 in the lines above and rerun the code). Compute the average number of steps for each size of list.
e. When the list length doubles, what happens to the average number of
calls to mayprecede?
a. Update mergesort
, split
, and
merge
to use
define$
instead of define
.
b. Repeat the remaining steps from exercise 6, using mergesort
instead of insertionsort
.
a. Update Quicksort
and partition
to use
define$
instead of define
.
b. Repeat the remaining steps from exercise 6, using Quicksort
instead of insertionsort
(and precedes?
instead
of mayprecede?
).
a. What other procedures might you use to compare the sorting routines
(other than mayprecede?
)?
b. Perform tests to compare the routines based on the other procedures.
c. Which sorting algorithm seems the most efficient?
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/Quicksort.html
.
[Skip to Body]
Primary:
[Front Door]
[Syllabus]
[Glance]
[Search]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Projects]
[Readings]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151 2006F (Rebelsky)]
[CSC151.01 2007S (Davis)]
[CSCS151 2005S (Stone)]
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 Thu Sep 13 20:54:27 2007.
The source to the document was last modified on Tue Apr 24 21:55:33 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007S/Labs/Quicksort.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.