Computer Science 60
Principles of Computer Science
Fall 2001

 

Section 1,Assignment 2                        

Due Friday, Feruary 1, 2002 before midnight

(Please note that Section 1 differs from Section 2 on this assignment.)

Introduction

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, mappend, and reduce.

Readings

This assignment covers material in Chapter 3 of the course text. It emphasizes higher-order functions and not recursion.

Restriction: Even if you've read ahead to Chapter 4, your functions must not use recursion or pattern-matching, except as instructed explicitly.

Submission Process

Place your answers in a file named assign1.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 assign1.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]

 

  1. 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

float(22) / 3 ==> 7.33333

 

3.        superreverse

Construct a function superreverse, that creates from a list of lists as a new list of lists containing the reverses of each 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"]]]

  1. 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. 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).

inner_product([2,5,7], [3,2,8]) ==> 72

 

  1. targets

    Suppose that we represent a directed graph by a list of pairs of nodes. Each pair represents an arc connecting the first element of a pair to the second element, as described in the lecture notes. (Note that this representation does not allow nodes that do not have any arc connecting them. We agree to live with this restriction in this problem.)

    Construct the function targets that collect together as a list the targets of a given node. The arguments to targets are a node and a graph representation as described. If the first argument happens not to be a node, then function targets will simply return the empy list.       

graph = [[1, 1], [1, 2], [1, 3], [3, 4], [4, 2], [4, 3]];

targets(1, graph) ==> [1, 2, 3]

targets(2, graph) ==> []

targets(3, graph) ==> [4]

targets(4, graph) ==> [2, 3]

  1. collective_targets

    Construct function collective_targets that is like targets in the previous section, except that its first argument is a set of nodes and the result is the set of nodes that are targets of any of those nodes. This set should not contain duplicates.

graph = [[1, 1], [1, 2], [1, 3], [3, 4], [4, 2], [4, 3]];

collective_targets([2, 4], graph) ==> [2, 3]

collective_targets([1], graph) ==> [1, 2, 3]

collective_targets([], graph) ==> [ ]

collective_targets([1, 2, 3, 4], graph) ==> [1, 2, 3, 4]

  1. cumulative_targets

    Construct the function cumulative_targets that is like collective_targets, except that the result is the union of the first argument and the result of collective_targets:

cumulative_targets([2, 4], graph) ==> [2, 4, 3]

  1. equal_as_sets

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

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

  1. reachable

    Again using the preceding directed graph representation, construct a function reachable that returns all nodes reachable from nodes in a set of nodes in zero or more arcs:

reachable([3], graph) ==> [3, 4, 2]

reachable([2, 3], graph) ==> [2, 3, 4]

reachable([1, 2], graph) ==> [1, 2, 3, 4]

Note that a node is considered reachable from itself in this case.

For this problem it is suggested that you use the following higher-order function that is not built into rex. We give you the definition and you should include it in your source file by copying it verbatim:

iterate(Function, Test, State) =

Test(State) ? iterate(Function, Test, Function(State)) : State;

Here is a description of iterate, which is the functional equivalent of a while loop:

If Test(State) is false, then the result is just State. If Test(State) is true, then the result is that of applying iterate to Function(State) as the third argument, where arguments Function and Test remain unchanged.