Computer Science 60
Principles of Computer Science
Fall 2001


Assignment 2
Due WEDNESDAY, September 19 before midnight

Introduction

This assignment is due on Wednesday, September 12 before midnight. Please see the tutoring schedule for the schedule of tutoring hours. You may also send e-mail to cs60help@cs.hmc.edu for help.

Unless otherwise specified you can use any rex built-in functions, arithmetic operators, or comparison operators mentioned in Chapter 3 (e.g., sort, reverse, and append), including higher-order functions such as map and reduce. Even if you've read ahead to Chapter 4, your functions must not use recursion or pattern-matching.

Readings

This assignment covers material in Chapter 3 of the course text.

Submission Process

Place your answers in a file named assign2.rex. To receive credit for your answer, the functions must have exactly the names specified. You may define other functions to be used by your code, if this seems useful. Your file must be loadable into into the rex system without generating any errors, so make sure you have comments around all the non-rex parts of your answers. As before you should run

cs60submit assign2.rex

The Assignment

  1. add42 and add42list

    Construct a function add42 that returns the number 42 greater than its argument. Then construct a function add42list which takes a list of numbers as input and returns a list in which each element of the original list has been incremented by 42. For example:

    add42list([1, -7, -42, 8]) ==> [43,35,0,50]


  2. sum and average

    Construct a function sum that, given a list of numbers, returns their sum.

    sum([1, -7, -42, 8]) ==> -40

    Then, construct a function average that returns the average (arithmetic mean) of the numbers in its list argument.

    average([1, -7, -42, 8]) ==> -10.0


    To ensure that the division is not truncated to an integer, you will want to use the function float, that transforms an integer argument into an equivalent floating-point value. In rex arithmetic, if either argument to an arithmetic operation is floating-point the result will be floating-point; otherwise the result will be an integer. For example,
    22 / 3 ==> 7
    22 / float(3) ==> 7.33333

  3. superreverse

    Construct a function superreverse, that takes a list of lists as outputs and returns a new list of lists containing the reversals of the input lists, in reverse order. For example:

    superreverse([[1,2,3],[4,5,6],[7,8,9]]) ==> [[9,8,7],[6,5,4],[3,2,1]]

    superreverse([[["e","x"],"r"], ["e","v"], ["o","l",["I"]]])
    ==> [[["I"], "l", "o"], ["v","e"], ["r",["e","x"]]]

  4. inner_product

    We can represent vectors as lists of numbers. Construct a function inner_product that computes the inner product of two vectors; the inner product is the sum of the element-wise products. For example, the inner product of [2,5,7] with [3,2,8] is 2*3 + 5*2 + 7*8 = 72. You may assume that the two list inputs have the same length (i.e., that the vectors represented by the lists have the same dimension).

  5. gather

    Construct a function gather that takes a key and an association list and returns a list of all elements paired with this key in the the association list. For example,

    gather(3, [[1,'a'], [2,'b'], [3,'c'], [1,'d'], [3,'e'],[3,'f'],[2,'g']])

    ==> ['c','e','f']

    (By default rex does not print single or double quotes around characters or strings when printing answers, in which case the value returned would look like [c, e, f].)

  6. compose_alists

    Functions on finite domains can be represented as association lists; that is, as a list of [input,output] pairs. (This is sometimes called the graph of the function.) Construct a function compose_alists that returns the association list corresponding to the composite of two input functions represented as association lists. For example:
    compose_alists([[0,3],[1,2],[2,1],[3,0]] , [[0,1],[1,2],[2,3],[3,2]])
    ==> [[0,2],[1,1],[2,0],[3,1]]

    Remember that the composite of two functions first applies the second function and then applies the first function to the result.

  7. is_palindrome and all_palindromes and all_palindromes

    1. Construct a function that, given a string argument, returns 1 if this string contains the same letters backward and forward, and returns 0 otherwise; spaces. You may assume the input string consists only of lowercase letters and spaces, but spaces in the input should be ignored. You may want to use the functions explode and/or implode, which convert a string to a list of characters and a list of characters to a string, respectively. Recall that characters are written with single quotes in rex, so the space character would be ' '.

      is_palindrome("able was i ere i saw elba") ==> 1
      is_palindrome("a man a plan a canal panama") ==> 1
      is_palindrome("almost a palindromeordnilap a tsomla") ==> 0

    2. Then construct the function all_palindromes, which given a list of strings returns a list containing all the palindromes in the argument list.
    3. Finally, construct a two-argument function of all_palindromes such that given an integer N and a list of strings L, all_palindromes(N,L)
      4. returns the strings in the list L which are palindromes that have exactly N non-space letters.


  8. equal_as_sets

    Construct a function that, given two lists, returns 1 if these lists would be considered equal sets, and 0 otherwise. For example:

    equal_as_sets([],[1]) ==> 0
    equal_as_sets([1],[]) ==> 0
    equal_as_sets([1],[1,1,1]) ==> 1
    equal_as_sets([1,2,3],[3,2,1]) ==> 1
    equal_as_sets([1,2,3],[1,2,2,3]) ==> 1
    equal_as_sets([1,2,3],[1,2,4,3]) ==> 0