算法代写 | Lab03 – Arrays & Algorithm Analysis

本次作业是lisp数组和算法分析的一个算法代写assignment

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 file

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
https://people.duke.edu/~hpgavin/gnuplot.html. For more information on gnuplot, go to http://www.gnuplot.info/.

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:
(load “unit-test-frwrk.lisp”)

Exercise 1

In a lisp file called filter-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 file called test-cases.lisp, write the unit test below which includes test cases that your solution for this exercise must pass.

To test your function filter-seq

(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> (load “filter-seq.lisp”)
RTL-USER> (load “test-cases.lisp”)
RTL-USER> (main)

Make sure your filter-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 efficiency 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 specifically, functions that find the position of an item inside an array.
To start, execute the following into your lisp enviroment:

(ql:quickload :rutils)

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 efficiency 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 file 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 specifically, function generate-points creates an array with a specific 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 file contains 3 values: the size of the array, the running time for aref, and the running time of find.