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 lab is also available in PDF.
Summary: In the laboratory, you will explore the running time fo a few algorithm variants.
Contents:
a. In DrScheme, create a new file for this lab, called
analysisexamples.scm
.
b. Make the first line of that file an instruction to load
analyst.scm
.
(load "/home/rebelsky/Web/Courses/CS151/2007S/Examples/analyst.scm")
c. Add the comments and code for reverse1
, reverse2
,
and myappend
from the
corresponding reading to your file.
a. Add the following line to the beginning of myappend
(again, immediately after the lambda
).
(display (list 'myappend front back)) (newline)
b. Determine how many times myappend
is called when
reversing a list of length seven using reverse1
.
c. Add the following line to the kernel of reverse2
(immediately after the lambda
).
(display (list 'kernel remaining reversed)) (newline)
d. Determine how many times kernel
is called when
reversing a list of length seven using reverse2
.
e. Comment out the lines that you just added by prefixing them with a semicolon.
a. Replace the define
for reverse1
with
define$
, as in the following.
(define$ reverse1 (lambda (lst) ...))
b. Find out how many times myappend
is called in reversing
a list of seven elements by entering the following command in the
interactions pane.
> (analyze (reverse1 (list 1 2 3 4 5 6 7)) myappend)
c. Did you get the same answer as in the previous exercise? If not, why do you think you got a different result?
d. One potential issue is that we haven't told the analyst to include
the recursive calls in myappend
. We can do so by replacing
define
with define$
in the definition of
myappend
.
e. Once again, find out how many times myappend
is called
in reversing a list of seven elements by entering the following command
in the interactions pane.
> (analyze (reverse1 (list 1 2 3 4 5 6 7)) myappend)
f. Did you get the same answer as in exercise 1? If not, what difference do you see?
g. Replace the define
in reverse2
with
define$
.
h. Find out how many times kernel
is called in reversing
a list of seven elements by entering the following command in the
interactions pane.
> (analyze (reverse2 (list 1 2 3 4 5 6 7)) kernel)
i. Did you get the same answer as in exercise 1? If not, what difference do you see?
In the previous exercise, you considered only a single procedure in each
case (myappend
for reverse1
,
kernel
for reverse2
). Suppose we incorporate
all of the other procedures. What effect does it have?
a. Find out how many total procedure calls are done in reversing a list
of length seven, using reverse1
, with the following.
> (analyze (reverse1 (list 1 2 3 4 5 6 7)))
b. How does that number of calls seem to relate to the number of
calls to myappend
?
c. Are there any procedures you're surprised to see?
d. Find out how many total procedure calls are done in reversing a list
of length seven, using reverse2
, with the following.
> (analyze (reverse2 (list 1 2 3 4 5 6 7)))
e. How does that number of calls seem to relate to the number of
calls to kernel
?
f. Are there any procedures you're surprised to see?
a. Fill in the following chart to the best of your ability.
List Length  r1: Calls to myappend 
r1: Total calls  r2: Calls to kernel 
r2: Total calls 

2  
4  
8  
16 
b. Predict what the entries will be for a list size of 32.
c. Check your results experimentally.
d. Write a formula for the columns, to the best of your ability.
Here is the more efficient version of largestoflist
from the corresponding reading.
;;; Procedures: ;;; largestoflist2 ;;; Parameters: ;;; lst, a nonempty list of real numbers [verified] ;;; Purpose: ;;; Find the largest number in lst. ;;; Produces: ;;; largest, a real number ;;; Preconditions: ;;; [No additional preconditions] ;;; Postconditions: ;;; largest is an element of lst. ;;; For all valid indices i, largest >= (listref lst i) (define largestoflist2 (lambda (lst) (if (null? (cdr lst)) (car lst) (let ((largestremaining (largestoflist2 (cdr lst)))) (if (> (car lst) largestremaining) (car lst) largestremaining)))))
a. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are arranged from largest to smallest.
b. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are arranged from smallest to largest.
c. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are in no particular order.
d. Predict the number of steps this procedure will take on each kind of list, where the length is 32.
Some people prefer to test for a one element list by checking the length. They might rewrite the preceding procedure as follows:
(define$ largestoflist3 (lambda (lst) (if (= 1 (length lst)) (car lst) (let ((largestremaining (largestoflist3 (cdr lst)))) (if (> (car lst) largestremaining) (car lst) largestremaining)))))
a. Does the change seem to have an effect? If so, what is that effect?
b. One problem with the preceding analysis is that we don't know how many
procedure calls the length
procedure makes. So, let's
write our own.
(define$ mylength (lambda (lst) (if (null? lst) 0 (+ 1 (mylength (cdr lst))))))
a. Add this procedure to your file for this lab.
b. Replace the call to length
in largestoflist3
with a call to mylength
.
c. Repeat your analysis. What do you learn?
largestoflist
Here is yet another version of largestoflist
that uses
a recursive kernel to keep track of the largest element found so far
and the position in the list.
(define$ largestoflist4 (letrec ((kernel (lambda (largest lst pos len) (if (>= pos len) largest (kernel (max largest (mylistref lst pos)) lst (+ pos 1) len))))) (lambda (lst) (kernel (car lst) lst 1 (length lst))))) (define$ mylistref (lambda (lst pos) (if (zero? pos) (car lst) (mylistref (cdr lst) ( pos 1)))))
a. Do you expect this to be more or less efficient than
largestoflist2
? Why or why not?
b. Confirm your answer experimentally.
You may recall the iota
procedure from a previous reading.
Given a positive integer, n, as a parameter, iota
creates a list of all the values between 0 and n1. Here are two
common definitions of iota
, one that uses a helper and one
that does not.
(define$ iota1 (lambda (n) (if (zero? n) null (myappend (iota1 ( n 1)) (list ( n 1)))))) (define$ iota2 (letrec ((kernel (lambda (n) (if (zero? n) null (cons ( n 1) (kernel ( n 1))))))) (lambda (n) (reverse2 (kernel n)))))
a. Which do you expect to be more efficient? Why?
b. Check your results experimentally.
c. See if you can figure out a formula for the number of procedure calls made in each version for a given input size.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/analysis.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:15 2007.
The source to the document was last modified on Fri Feb 23 10:37:22 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007S/Labs/analysis.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.