Tutorial 10: Lots of Math (November 14-16, 2007)
This week's tutorial covers the second half of lecture module 10 (on lambda) and the beginning of module 11. Make sure you look at the updated course notes for module 10. And here's a link to the starter code for this tutorial.
The reason we use the word lambda for anonymous functions comes from the formal model of computation invented by Church and Kleene the better part of a century ago. In this model, basically everything is a lambda application, so there aren't actually any
It can be rather tricky to write complicated functions under these restrictions. But you now have the tools to evaluate lambda expressions using semantic substitution rules. So evaluate the following Scheme expression. For an added challenge, try to figure out what the top-level lambda function is actually doing. Don't cheat and use DrScheme!
((lambda (x) ((lambda (x y) (x x y)) (lambda (x y) (cond ((= 1 y) 1) (else (* y (x x (sub1 y)))))) x)) 3)
Today, let's represent polynomials in a more traditional way, as a list of all coefficients from low to high order. So for example the polynomial
2x5 - 3x3 + x2 +8xwould be represented as
It may be useful to note that, a polynomial of the form f(x) = a + x g(x), where g(x) is also a polynomial, would be represented as
Note that multiplying a polynomial by a scalar (i.e. a number) just means multiplying each coefficient by that scalar.
Without using any recursive calls, write a function
Every polynomial is in fact a function in just one variable, which we have been calling x. But we are representing polynomials as lists, not as functions. Give a function
Sometimes we might want to add to the same polynomial repeatedly. Write a function
Write a function
Hint: Write (and use) a helper function to find the least factor of a given number.
An operation of central importance in cryptography and computational number theory is called the Chinese Remainder Algorithm (CRA). Given a set of images of the form (vi,mi), where all the mi's are relatively prime, the CRA computes the smallest positive integer congruent to each vi modulo each mi. In fact, the final result will always be less than the product of the mi's, so this really produces a single new image which combines all the input images, in some sense.
In Scheme, we will represent each image with the structure
The starter code provides you with a function
produces the value
Your task is to write a function