Create a function "average-list" which takes in one parameter,
 a list, and returns the average of all the numbers in the list
 (not including numbers in sublists). If there are no numbers in
 the list, "average-list" should return 0.

 Examples:

   (average-list '(1 5 3 4 3 2 3))    ==>  3

   (average-list '(a b c 1 6 8))      ==>  5

   (average-list '(a i b))            ==>  0

   (average-list '(a b 4 3 (8 7) 8))  ==>  5
   
 Create a function named "make-list" which takes in one
 parameter, a non-negative integer, n. "make-list" returns 
 a list containing n null lists.

 Examples:

   (make-list 2) ==> (() ())

   (make-list 0) ==> ()



The crossproduct of two lists of numbers, X and Y, where each list has the same length, is defined as a list of the products XiYi, where:

Xi    is the ith element of list X, and
Yi    is the ith element of list Y.

Construct a Common LISP function which uses mapcar to compute the
crossproduct of X and Y.  Call the function (what else?) crossproduct.
Here's an example of how it would work:

(crossproduct '(1 2 3) '(1 2 3)) => (1 4 9)



Now write the above function using tail recursion.

Let's make a new function.  The function delete-every-nth does 
exactly what its name suggests:  that is, it deletes every nth 
element from a given list.  Here are some examples of 
delete-every-nth in action:
 
> (delete-every-nth 3 '(a b c d e f g h i))
(a b d e g h)
> (delete-every-nth 2 '(a b c d e f g h i))
(a c e g i)
> (delete-every-nth 1 '(a b c d e f g h i))
()
> (delete-every-nth 0 '(a b c d e f g h i))
(a b c d e f g h i)
> (delete-every-nth 4 '(a b c d))
(a b c)
> (delete-every-nth 4 '(a b c))
(a b c)
> (delete-every-nth 4 ())
()
 
Your job now is to use Scheme to construct the delete-every-nth 
function (and any other functions which might be necessary).  The 
delete-every-nth function takes two arguments, as shown in the examples.  
The first will always be a non-negative integer, and the second will 
be a list of arbitrary length.  You can assume that these constraints 
will always be met; don't do any error checking on the parameters being 
passed.  Oh, I almost forgot...you are to implement delete-every-nth with 
augmenting recursion.  (If you were hoping to do it with tail recursion, 
see the next problem.  And while we're on the topic, the augmenting 
recursion version of this function is not just the tail recursive version 
with some meaningless computation tacked on.)


Now write a tail recursive version of the above function.


Write a function that will be passed a list and will return a new list of 
all even-positioned values.  Use augmentive recursion.

(even-list '(2 1 3 4 6 7 8))          ==> (1 4 7)
(even-list '(two one three four six)) ==> (one four)
(even-list '(4))                      ==> ()

Now write the above function with tail recursion.


Big-O questions for augmentive even-list

 Assume that even-list is passed a 100-element list.  How many 
'cons'es will it perform?

Assume that even-list is passed a 215-element list.  How many 'cons'es 
will it perform?

Assume that even-list is passed an N-element list.  How many 'cons'es 
will it perform?

What is the Big-O of even-list with the above input?


Big-O questions for tail recursive even-list

Assume that my-append is implemented in the following manner:

(define my-append
  (lambda (list1 list2)
    (cond ((null? list1) list2)
          (else (cons (car list1)
                      (my-append (cdr list1) list2))))))


Assume that even-list-tr is passed in a 10-element list.  How many
'cons'es does it peform?

Assume that even-list-tr is passed in a 13-element list.  How many
'cons'es does it perform?

Assume that even-list-tr is passed in an N-element list.  How many
'cons'es does it peform?

What is the Big-O of even-list-tr with the above input?

Write a function that will be passed a list and will return a new list of
all odd-positioned values.  Use augmentive recursion.

(odd-list '(2 1 3 4 6 7 8))          ==> (2 3 6 8)
(odd-list '(two one three four six)) ==> (two three six)
(odd-list '(4))                      ==> (4)

Now write the above function using tail recursion.


Big-O questions for augmentive odd-list

Assume that odd-list is passed a 100-element list.  How many
'cons'es will it perform?

Assume that odd-list is passed a 215-element list.  How many 'cons'es
will it perform?

Assume that odd-list is passed an N-element list.  How many 'cons'es
will it perform?

What is the Big-O of odd-list with the above input?


Big-O questions for tail recursive odd-list

Assume that my-append is implemented in the following manner:

(define my-append
  (lambda (list1 list2)
    (cond ((null? list1) list2)
          (else (cons (car list1)
                      (my-append (cdr list1) list2))))))

 Assume that odd-list-tr is passed in a 10-element list.  How many 
'cons'es does it peform?

 Assume that odd-list-tr is passed in a 13-element list.  How many 
'cons'es does it perform?

 Assume that odd-list-tr is passed in an N-element list.  How many 
'cons'es does it peform?

 What is the Big-O of odd-list-tr with the above input?


Write a function that will be passed a list and will return a new list of
all multiples of n-positioned values.  You may assume n > 0.  Use 
augmentive recursion.

(n-list 3 '(1 2 3 6 5 4 7 8 9))  ==> (3 4 9)
(n-list 1 '(1 2 3 4))            ==> (1 2 3 4)
(n-list 6 '(1 2 3 4 5))          ==> ()
(n-list 2 '(three one five six)) ==> (one six)


Now write the above function using tail recursion.


Big-O questions for augmentive n-list

Assume that n-list is passed a 100-element list and n=5.  How many 
'cons'es does it perform?

 Assume that n-list is passed a 100-element list and n=8.  How many 
'cons'es does it perform?

Assume that n-list is passed a M-element list and n=P.  How many 
'cons'es does it perform?

What is the Big-O of n-list with the above inputs?


Big-O questions for tail recursive n-list


Assume that my-append is implemented in the following manner:

(define my-append
  (lambda (list1 list2)
    (cond ((null? list1) list2)
          (else (cons (car list1)
                      (my-append (cdr list1) list2))))))

 Assume that n-list-tr is passed in a 10-element list and n=3.  How many
'cons'es does it peform?

 Assume that n-list-tr is passed in a 20-element list and n=4.  How many
'cons'es does it perform?

 Assume that n-list-tr is passed in an M-element list and n=P.  How many
'cons'es does it peform?

 What is the Big-O of odd-list-tr with the above input?




Construct a LISP function called "insert-left-all" which takes a
one item (the first argument) and inserts it to the immediate left
of each occurrence of another item (the second argument) in a list
(the third argument).  For example:

    (insert-left-all 'z 'a '(((a)))) => (((z a)))
    (insert-left-all 'z 'a '(a ((b a) ((a (c)))))) =>
      (z a ((b z a) ((z a (c)))))
    (insert-left-all 'z 'a '()) => ()

Construct a LISP function called "insert-right-all" which takes a
one item (the first argument) and inserts it to the immediate right
of each occurrence of another item (the second argument) in a list
(the third argument).  For example:

    (insert-right-all 'z 'a '(((a)))) => (((a z)))
    (insert-right-all 'z 'a '(a ((b a) ((a (c)))))) =>
      (a z((b a z) ((a z (c)))))
    (insert-right-all 'z 'a '()) => ()

Construct a Scheme function called "butlast" that takes in a list
and returns everything in the list except for the last element.  It
must work on nested lists.

(butlast '(a b c d)) ==> (a b c)
(butlast '(a))       ==> ()
(butlast ())         ==> ()
(butlast '((a b c) d e (f g))) ==> ((a b) d e)
(butlast '(a b (c d) (e f (g) h) j)) ==> (a b (c) (e f ()))