CMSC 471 - Fall 2008

Homework 2 - Part 2

Explanation of the strange grading scheme for this homework:
This homework is worth 80 percent of Homework 2.
This homework is out of 40 points and each problem is worth 8.
There are 9 problems -- only 8 will be graded for full credit.
If all 9 problems are completed, the extra problem is worth 2 extra credit points.

Note that the names of the functions are very important for grading purposes. Make sure your code works on linux.gl. It should, since LISP is standardized, but double check.

Please write a file header comment that contains your name and your username/email.

Write the following functions in one LISP file that contains your last name in the file name (e.g., hw2-miner.lisp), and turn in your LISP code via blackboard (BEFORE class):

1. Write a function (fib n) that returns the nth Fibonacci number. n=0 is 0, n=1 is 1.

2. Write a function (square-each l) that returns a list that has doubled each element in l. You must use a lambda expression to square each individual element in the list. For example, if l is (0 3 4), (square-each l) is (0 9 16).

3. Write two functions (posint-? l) take a list l and return a list containing only the positive integers in the list. For example, (posint-a '(a 2.3 -1 5 hello 3 1 2)) should return (5 3 1 2). You can use the built-in function integerp in your solutions.

posint-a: Implement the posint function using mapcar.
posint-b: Implement the posint function using recursion.

4. Write a function (string-case s) that returns the symbol 'upper if the characters in the string s are all upper case, 'lower if the characters are all lower case, and 'mixed if there are some lower case and some upper case letters (or if the string contains any non-letter characters). Hint: first write two subroutines, upper? that tests to see if a string is upper case and lower? that tests to see if a string is lower case. Then use cond with these subroutines to test for which case to return. Useful built-in functions for solving this problem include char, upper-case-p, and lower-case-p.

5. Write a function (flatten-tree l) that takes an arbitrarily deeply nested list of atoms, and returns a flattened list of these atoms (in the same order they appear in the original list). For example, (flatten-tree '(((1) 2) ((3 (4)) 5) 6)) should return (1 2 3 4 5 6).

6. Write a function (list-merge-sort l) that sorts the list l. Use merge sort. You may assume l will only have integers.

7. Write a function (lottery n m) that returns n items in a list that were randomly selected from the set 1, 2, ..., m. Do not return duplicate numbers (i.e., you should never see (37 4 9 29 212 24 3 9) because there are two 9s).

8. Write a function (prime n) that returns the prime factors of the number n in a list. The naive method of searching for factors is acceptable. For example, (prime 294) gives (2 3 7 7). The order of the factors in the returned list should be in ascending order (e.g., (2 3 7 7), not (7 7 4 2)).

9. Write a function (remove-dups l) that returns a list that has all of the consecutive duplicates in l removed. For example: (remove-dups '(a a a b b b b b a a b b a c a a b)) returns (a b a b a c a b).