# 算法代写 | Lab03 – Arrays & Algorithm Analysis

## Learning objectives of this lab

Students who successfully complete this lab should be able to

describe and write Lisp programs that combine the following programming elements:

• Looping
• arrays
• data output to a ﬁle

test the theoretical run time of lisp functions

## Before you start working on the lab exercises

Read this document carefully to prepare for the lab properly and become aware of the requirements to turn in your lab solution.

1. Read pages 7 – 9, and 41 to 50 of the textbook
2. Get familiarity with a graphing utility (in Exercise 1 below you are asked to graph data produced by a lisp program). I encourage you to use gnuplot. There are many online tutorials. I like this one

### Preparatory steps

1. Create the following Lab03/ folder:

Lab03/
├── Exercise-1/
└── Exercise-2/

2. Copy unit-test-frwrk.lisp provided into your Lab03/ folder and load it in your lisp environment by executing the command below:

## Exercise 1

In a lisp ﬁle called ﬁlter-seq.lisp, write a function called filter-seq that takes a sequence s (a string) and an alphabet a (a string), and generates a result sequence (a string) by including only the characters of s that occur in the alphabet a. In another lisp ﬁle called test-cases.lisp, write the unit test below which includes test cases that your solution for this exercise must pass.

(deftest test-filter-seq ()
(check
(equal (filter-seq “sdafgacs” “abcf”) “afac”)
(equal (filter-seq “” “abcf”) “”)
(equal (filter-seq “sdafgacs” “”) “”)
(equal (filter-seq “sdafgacs” “abcfs”) “safacs”)))
(defun main ()
(test-filter-seq))

RTL-USER> (main)

Make sure your ﬁlter-seq.lisp in the folder Exercise-1/ contails only your filter-seq function and other helper functions you yourself may have decided to write. Notice: it should not containg any calls to function load, i.e., it should not contain (load “filter-seq.lisp”) and it should not contain (load “test-cases.lisp”)

## Exercise 2

### Preamble

A function’s efﬁciency is obviously dependant on how fast it can perform its intended objective (like parsing a string or accessing an array). In this exercise, we will explore this by experimenting with functions that utilize arrays. More speciﬁcally, functions that ﬁnd the position of an item inside an array.
To start, execute the following into your lisp enviroment:

and

(cl:in-package :rtl-user)

And copy unit-test-frwrk.lisp that is provided in the course lab page into Lab03/ folder and load it.
The RUTILS library will be used throughout the exercise.
Next, download timing-graph-frwrk.lisp. This framework contains functions that can test the efﬁciency of other functions, notably, generate-points. The code for this function is as follows:

(defun generate-points ()
(with-open-file (s “output.dat” :direction :output :if-exists :supersede)
(do* ((init 10000)
(incr 20000)
(lim 1000000)
(reps 1000)
(i init (+ i incr)))
((> i lim))
(let ((x (do ((k 0 (1+ k))
(a (make-array i)))
((= k i) a)
(:= (? a k) k)))
(acc1 0)
(acc2 0))
(dotimes (j reps)
(let ((elem (random i)))
(:+ acc1 (timef (aref x elem)))
(:+ acc2 (timef (find (- elem) x)))))
(format s “~a ~,8F ~,8F~%” i (/ acc1 reps) (/ acc2 reps))))))

You can see that this function creates a data ﬁle containing information about the size of the array and the time the functions (in this case find and aref) took to run when called with the respective input parameters. More speciﬁcally, function generate-points creates an array with a speciﬁc size, calls aref and find passing a number and the array to them, increases the size of the array, calls the function again, and so on until the size of the array hits a certain limit.

Notice that the format function inside generates-points outputs the data points to a stream. Each line of data in the generated data ﬁle contains 3 values: the size of the array, the running time for aref, and the running time of find. E-mail: itcsdx@outlook.com  微信:itcsdx 