CS 381K Assignment 1: Timing

Due: September 7, 2007.

Examine the three list-of-nums functions shown in the paper Lisp Style and Efficiency. The goal of this assignment is to gather experimental data on the performance of these functions. Use (load "/projects/cs381k/bermuda.lsp") or type in the functions. Gather data on the time required to execute the functions for argument n, say for n up to 50000. You can use the time function:

(time (car (list-of-nums3 40000)))

Make a graph showing how the time required for each function varies with the size of the parameter n. Make a second graph using 3-cycle log-log graph paper (this will be furnished, or you can print loglog.ps).

For each function, find a formula that approximately gives the time required as a function of n, based upon your experimental data. It is probably best to use the time that does not include garbage collection; this is called "run-gbc time" in the newer version of GCL. We are primarily interested in the O() timing.

This is a minor assignment to get you started. Hand-drawn graphs and rough approximations of the formulas are quite acceptable; a fancy report is not expected.