Page History

...

1. We need some data to use for our timing experiments. Write a function up: nat -> (list-of nat) which constructs a list of naturals starting with 0 in ascending order or retrieve it from a previous lab. For example, (up 7) returns (list 0 1 2 3 4 5 6). You can probably write it faster using build-list that you can retrieve it. Similarly, write a function down: nat -> (list-of nat) that constructs a list of naturals ending in 0 in descending order. For example, (nums-down 7) returns (list 6 5 4 3 2 1 0).
   
   Now write a function

   Code Block
   rands

   Wiki Markup
   that constructs a list of random numbers in the range from {{0}} to {{32767}}. To create a single random number in the range from {{0}} to {{_n_}}, compute {{(random _n+1_)}}. For larger numbers in the range {{\[0, 32768)}}, try:

   Code Block
   (define max-rand 32768) (random max-rand) ; random is built-in

   Note: Code Blockrandom is a function in the Scheme library, but it is not a mathematical function, since the output is not determined by the input.

   HTML
   </li>

   HTML</ol>
   
   Now, make sure you know how to use

...

1. time

...

1. .

...

<ol>

<li>

...

1. Time

...

1. isort

...

1. on a list of 200 elements.

...

</li>

<li>

1. Run the exact same expression again a couple times.

...

1. Note that the time varies some.

...

1. We typically deal with such variation by taking the

...

1. average of several runs.

...

1. The variation is caused by a number of low-level hardware

...

1. phenomena that are beyond the scope of this course (see

...

1. ELEC 220 and

...

1. COMP

...

1. 221).
   

</li>

</ol>

...

1. Continue timing, filling in the following chart.

...

1. When you're done, compare results with other pairs in the lab.

<table border=1>

<tr>

<td>

</td>

<th colspan=6>

input size

</th>

</tr>

<tr>

<td>

</td>

<th colspan=2>

200

</th>

<th colspan=2>

1000

</th>

<th colspan=2>

5000

</th>

</tr>

<tr>

<th rowspan=3>

isort

</th>

<td>

up

</td>

<td width=60>

</td>

<td>

up

</td>

<td width=60>

</td>

<td>

up

</td>

<td width=60>

</td>

</tr>

<tr>

<td>

down

</td>

<td width=60>

</td>

<td>

down

</td>

<td width=60>

</td>

<td>

down

</td>

<td width=60>

</td>

</tr>

<tr>

<td>

rand

</td>

<td width=60>

</td>

<td>

rand

</td>

<td width=60>

</td>

<td>

rand

</td>

<td width=60>

</td>

</tr>

<tr>

<th rowspan=3>

qsort

</th>

<td>

up

</td>

<td width=60>

</td>

<td>

up

</td>

<td width=60>

</td>

<td>

up

</td>

<td width=60>

</td>

</tr>

<tr>

<td>

down

</td>

<td width=60>

</td>

<td>

down

</td>

<td width=60>

</td>

<td>

down

</td>

<td width=60>

</td>

</tr>

<tr>

<td>

rand

</td>

<td width=60>

</td>

<td>

rand

</td>

<td width=60>

</td>

<td>

rand

</td>

<td width=60>

</td>

</tr>

</table>

</td>

</tr>

...

...

COMP 280
introduces concepts of how these algorithms behave in general.
The punchline is that we can say that both insertion sort and
quicksort on lists are "_O(n

...