ASSIGNMENT 3 (SCHEME)

CPTS355 ­ ASSIGNMENT 3 (SCHEME)
Cpts 355 ­
Scheme Functions

Weight: Assignment 3 will count for 5% of your course grade.
This assignment is to be your own work. Refer to the course academic integrity statement in the syllabus.
This homework provides some practice in Scheme programming. The Racket environment, which can be downloaded from http://racket­lang.org is friendly scheme implementation. It
can be installed on most operating systems (e.g., Mac, Linux, Unix, Windows). On Windows, get the installer from the racket­lang website. For linux systems you can probably find
a racket package in your distribution's package manager. After installing use the drracket command to start up the IDE. Be sure to select R5RS as the language on the
language menu. You should only have to do this once after installing.
You can edit your code in the upper panel of the Racket IDE and save it from there. Or edit in any text editor and load it into Racket.
Turning in your assignment
Turn in a plain text file named HW3.scm containing legal scheme code ­­ you should be able to take the contents of your file and run it through racket without errors. Create your
own test cases for each function: you may include the test cases in what you turn in. To submit your assignment, turn in your file by uploading on the Assignment3 (Scheme)
DROPBOX on Blackboard (under AssignmentSubmisions menu). Be sure to include your name as a comment at the top of the file. You may turn in your assignment up to 5 times.
Only the last one submitted will be graded. Please let the instructor know if you need to resubmit it a 6th time.
The work you turn in is to be your own personal work. You may not copy another student's code or work together on writing code. You may not copy code from the web, or
anything else that lets you avoid solving the problems for yourself.
Grading
The assignment will be marked for correctness and effective programming. You will lose points if you don't (1) provide test functions, (2) explain your code with appropriate
comments, and (3) follow a good programming style.
General rules
Unless directed otherwise, you should implement your functions using recursive definitions that you build up from the basic built­in functions such as cons, car, cdr, list,
etc.
Don't use set! and don't define anything except functions.
Problems
1. (deepCount L) (15%)
The function deepCount takes a single argument, L, a list, and returns how many elements (atoms) are contained in L and the sublists in L.
Example:
(deepCount '(1 (2 3 4) (5) 6 7 (8 9) "10" 11)) = 11
(Note: The lenght function covered in class calculated a shallow count of elements (i.e., only number of elements in L without looking into sublists). deepCount should also look
into sublists and count the elements in each sublist.)
(HINT: The predicate function (pair? L) return true if L is a pair value (such as a list))
2. (nthElement n L) (10%)
The function nthElement takes an index value n and a list L and returns the nth element of the list L (0­based indexing). Assume that the index, n, is at least 0 and smaller than
the length of the list. ( i.e., you do not have to worry about error cases such as when n is negative or too large.)
Example:
(nthElement 3 '(1 2 3 4 (5) "6")) = 4
(nthElement 4 '(1 2 3 4 (5) "6")) = (5)
(HINT: The trick with problems like this is to reduce both the size of the list and the size of the integer argument in recursive calls. The 3rd element of a list is the 2nd element of
the cdr of the list.)
3. (repL n v L) (10%)
12/11/2016 CptS 355 - Assignment 3 - Scheme
http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/Scheme_Assignment.html 2/3
The function repL takes an index value n, a value v, and a list L and returns a (new) list which is the same as L, except that the nth element is v. Again assume 0­based indexing.
Assume that the index, n, is at least 0 and smaller than the length of the list.
Example:
(repL 3 40 '(1 2 3 4 (5) "6")) = (1 2 3 40 (5) "6")
(repL 4 5 '(1 2 3 4 (5) "6")) = (1 2 3 4 5 "6")
4. (range min step max) (15%)
The function range takes a starting index min, a step value step, and a max index max and returns a list of integers (min min+step min+step+step ... max+k*step)
where k is the largest integer such that min+k*step<max and min+(k+1)*stepmax. If min ≥ max and step ≥ 0 OR min<max and step<0 , return the empty list.
Example:
(range 0 5 30) = (0 5 10 15 20 25)
(range 5 ­1 0) = (5 4 3 2 1)
5. (merge2 L1 L2) (10%)
The function merge2 takes two lists of integers, L1 and L2, each already in ascending order, and returns a merged list that is also in ascending order. The length of the new list is
the sum of the lengths of the original lists.
Examples:
(merge2 '(4 6 7) '(3 5 7)) = (3 4 5 6 7 7)
(merge2 '(1 7) '(2 5 7)) = (1 2 5 7 7)
(merge2 '() '(3 5 7)) = (3 5 7)
(fold L)
Just use the definition given in class. You'll need it for the function below.
6. (mergeN Ln) (15%)
Using merge2 function defined above and the fold function, define mergeN which takes a list of lists, each already in ascending order, and returns a new list containing all of the
elements in ascending order.
(Provide an answer using fold; without using recursion).
Example:
(mergeN '()) = ()
(mergeN '((2 4 6) (1 4 5 6))) = (1 2 4 4 5 6 6)
(mergeN '((2 4 6 10) (1 3 6) (8 9))) = (1 2 3 4 6 6 8 9 10)
Note that this requires making sure that your understanding of fold encompasses seeing that it can return a list, not just a simple value; but the solution is, in fact, a very simple
use of fold once you choose the right value for the base case corresponding to the empty list as input.
In a comment, discuss the question of how many cons operations your function uses to produce its result, in terms of the sizes of the input lists. Explain your answer. For this
problem, I suggest looking first at how many cons operations are used by merge2 for lists of length len1 and len2. If mergeN is used for a single list, what is the answer? For 2
lists? For n lists?
7. (matrixMap f M) (10%)
A matrix M can be represnted in Scheme as a list of lists, for example M='((1 2) (3 4))
Without using recursion, write a function matrixMap, which takes a function f and a matrix M as arguments and returns a matrix consisting of f applied to the elements of M.
Example:
(matrixMap (lambda (x) (* x x)) '((1 2) (3 4)) ) = ((1 4) (9 16))
(matrixMap (lambda (x) (+ 1 x)) '((0 1 2) (3 4 5)) ) = ((1 2 3) (4 5 6))
8. (avgOdd L) (15%)
Without using recursion, write a function avgOdd which takes a list L and returns the average of the odd values in L.
Example:
(avgOdd '(1 2 3 4 5)) = 3
Use (odd? n) and (even? n) predicate functions to check if a given number n is odd or even.
12/11/2016 CptS 355 - Assignment 3 - Scheme
http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/Scheme_Assignment.html 3/3