Assignment 3, CSC458, Spring 2010

1 Assignment

2 Newton-Raphson

Here’s a data definition for single-variable polynomials,and the signature for a findZeros method.

type term = (double * double) // coefficient and exponent

type poly = term list

//val findZeros : poly * double -> double

The findZeros function should find double values for which the polynomial returns values that are very close to zero. How close? Your function should give up after 1000 iterations, or when the polynomial returns a value that is indistinguishable from zero.

Also, it’s fine for your function to signal an error when the derivative at a tested point is zero (e.g. y = 4) or undefined (e.g. y = 1/x with x = 0).

3 Expectation

Using our existing data definitions for events and random variables, develop the expectedVal function that accepts an arbitrary random variable and a probability of flipping a head on each toss and produces the random variable’s expected value.

type event1 = bool

type event = int -> event1

type rv = event -> double // a random variable

//val expectedVal : rv -> double -> double

For this problem, random variables must be actual functions: that is, they must be deterministic. Also, if the function representing a random variable fails to converge (a.k.a. loops forever) on a particular event, then it’s fine for your expectedVal function to do the same thing.

Also, unsurprisingly, the probability of flipping a head must be in the range [0,1].

4 Grading Rubric

After some reflection, I’ve decided to update my grading rubric to put more weight on organization, readability, and design, and less on correctness. Specifically, correctness and design scores will now have equal weight in the assignment score.

Here are some of the design criteria:

• Your data definitions must match the problem elements. Don’t use numbers to represent boolean values, or strings to represent sequences of numbers. Your choice of data representation is the single most important design choice that you make.

• Every function must have a one-line comment that concisely states its purpose.

• The program’s body should read as a clear description of its meaning. Introduce abstractions that make code more readable. To take a classic example, the body of a merge sort function might read like this:

  let mergesort l =

  recombine (sort-each (split l))

• Every function must have test cases that include inputs and expected outputs, or a comment indicating why it is that testing is implausible.

Broadly speaking, I’d like you to regard your submission as a short essay in the form of a program that clearly demonstrates that you understand how to solve a problem.

5 Parters

I would encourage you to tackle this assignment with a partner.

6 Handin

Write your code in one or more F# files; the result of running your makefile should be an ass3.dll library defining the module Ass3. Submit your code by creating an Assignment2 directory in the repository. Either partner may submit. Include with your submission a "TEAM" file that includes one line for each partner, where each line is of the form "<calpoly-id>, <first & last name>". No, don’t include the quotation marks.

7 Disclaimer

There may well be bugs in this assignment. Let me know right away if you find some!